数据结构合并两个线性表

假设有两个线性表A和B，它们的长度分别为m和n。下面介绍两种合并A和B的方法：

1. 直接合并法

将B表中的所有元素直接添加到A表的尾部即可。这种方法的时间复杂度为O(n)，因为需要遍历B表中的所有元素。代码如下：

void merge(List *A, List *B) {
    int i;
    for(i=0;i<B->length;i++) {
        A->data[A->length+i] = B->data[i];
    }
    A->length += B->length;
}

2. 插入合并法

将B表中的每个元素插入到A表中的合适位置，使得合并后的表仍然有序。这种方法的时间复杂度为O(m*n)，因为每次插入都需要遍历A表中的元素，最坏情况下需要遍历m次。代码如下：

void merge(List *A, List *B) {
    int i, j;
    for(i=0;i<B->length;i++) {
        for(j=0;j<A->length;j++) {
            if(B->data[i] < A->data[j]) {
                insert(A, j, B->data[i]);
                break;
            }
        }
        if(j == A->length) {
            insert(A, j, B->data[i]);
        }
    }
}

其中，insert函数可以根据需要自行实现，用于在表A的指定位置插入一个元素。这种方法比直接合并法慢很多，但是能够保证合并后的表仍然有序。