两个线性表合并算法的实现。已知顺序表LA和LB中的数据元素按值非递减有序排列,现要将LA和LB归并为一个新的顺序表LC,且LC中的数据元素仍按值非递减有序排序。例如: LA= (3,5,8,11) LB= (2,6,9,15,20)。
时间: 2023-05-13 13:06:22 浏览: 532
数据结构 两个有序线性表的归并算法 西南交通大学
可以使用双指针法来实现两个线性表的合并。具体步骤如下:
1. 定义三个指针,分别指向LA、LB和LC的起始位置。
2. 比较LA和LB当前位置的元素大小,将较小的元素插入到LC中,并将对应指针向后移动一位。
3. 重复步骤2,直到LA或LB中的元素全部插入到LC中。
4. 将剩余的元素依次插入到LC中。
下面是实现代码:
void mergeList(int LA[], int LB[], int LC[], int lenA, int lenB) {
int i = 0, j = 0, k = 0;
while (i < lenA && j < lenB) {
if (LA[i] <= LB[j]) {
LC[k++] = LA[i++];
} else {
LC[k++] = LB[j++];
}
}
while (i < lenA) {
LC[k++] = LA[i++];
}
while (j < lenB) {
LC[k++] = LB[j++];
}
}
其中,LA、LB、LC分别表示顺序表A、B、C,lenA、lenB分别表示A、B的长度。
阅读全文