线性表的两个非递减集合求并集

假设有两个非递减的线性表A和B，它们的元素类型相同，长度分别为m和n。我们可以先定义一个空的线性表C，用于存放A和B的并集，然后使用双指针的方法依次比较A和B中的元素大小，将较小的元素加入到C中，并将指向该元素的指针向后移动一位，直到其中一个线性表中的元素全部加入到C中。此时，将剩余的元素依次加入到C中即可。

下面是具体的实现代码：

void mergeList(List A, List B, List &C) {
    int i = 1, j = 1, k = 0;
    int m = A.length, n = B.length;
    while (i <= m && j <= n) {
        if (A.data[i] <= B.data[j]) {
            C.data[++k] = A.data[i++];
        } else {
            C.data[++k] = B.data[j++];
        }
    }
    while (i <= m) {
        C.data[++k] = A.data[i++];
    }
    while (j <= n) {
        C.data[++k] = B.data[j++];
    }
    C.length = k;
}

其中，List为线性表的结构体，data为存放元素的数组，length为线性表的长度。在函数中，我们使用三个指针i、j和k分别指向A、B和C中的元素，初始值都为1，表示第一个元素。然后，我们使用while循环依次比较A和B中的元素大小，将较小的元素加入到C中，并将指向该元素的指针向后移动一位。当其中一个线性表中的元素全部加入到C中时，我们使用另外两个while循环将剩余的元素依次加入到C中。最后，我们更新C的长度为k，即为A和B的并集的长度。