******************************************/
2 /* 额外的几个复杂操作 */
3 /************************************************************************/
4
5 //1、合并线性表AB，把在线性表B里，但不存在于线性表A的元素插入到A中
6 //只改变A，不修改B
7 void Union(SqList *LA, SqList LB)
8 {
9 int i;
10 int e;
11 int lengthA = LA->length;
12 int lengthB = LB.length;
13
14 //在B里依次取得每个数据元素，顺序在A里比较，若不存在则插入
15 for (i = 1; i <= lengthB; i++)
16 {
17 GetElem(LB, i, &e);
18 if (!LocateElem(*LA, e))//A里没有这个元素
19 {
20 //插入到A尾部
21 /*lengthA++;
22 ListInsert(LA, lengthA, e);*/
23 ListInsert(LA, ++lengthA, e);
24 }
25 }
26 Destory(&LB);
27 }
复制代码
算法复杂度分析：
GetElem函数执行和表长没有关系，插入函数每次都在最后一位插入，执行时间和表长也没有关系，而LocateElem函数执行时间和表长有关系，无序合并算法的时间复杂度主要取决于LocateElem的执行时间，前面分析过，LocateElem时间复杂度：0（lengthA），那么本算法的时间复杂度为：O（lengthA x lengthB）
复制代码
1 //2、合并线性表AB，AB的元素按值非递减有序的排列，要把A和B归并为一个新表C，且C的元素依然是按照值非递减的有序排列
2 void MergeList(SqList LA, SqList LB, SqList *LC)
3 {
4 InitList(LC);//构造新表c
5 int lengthA = LA.length;
6 int lengthB = LB.length;
7 int lengthC = LC->length;//C表初始化为空表,0
8 int i = 1;//i标记LA
9 int j = 1;//j标记LB
10 int iLA;
11 int jLB;
12
13 while ((i <= lengthA) && (j <= lengthB))
14 {
15 //分别取得元素值，比较
16 GetElem(LA, i, &iLA);
17 GetElem(LB, j, &jLB);
18 if (iLA <= jLB)//LA，LB都是非递减排列
19 {
21 ListInsert(LC, lengthC, iLA);
22 i++;
23 }
24 else
25 {
26 ListInsert(LC, ++lengthC, jLB);
27 j++;
28 }
29 }
30 //AB不会同时比完，一定会有一个表完全插入到c之后，另一表剩余
31 while (i <= lengthA)
32 {
33 GetElem(LA, i++, &iLA);
34 ListInsert(LC, ++lengthC, iLA);//本来AB就有序，直接全部插入到C末尾即可
35 }
36 //or
37 while (j <= lengthB)
38 {
39 GetElem(LB, j++, &jLB);
40 ListInsert(LC, ++lengthB, jLB);
41 }
42 }
复制代码
算法时间复杂度分析：
不论表AB，哪个表，肯定有一个表先完全比完，比如是LA，比较了lengthA次。之后，两个while语句，就执行一个，就是LB剩余的元素顺次插入C表剩余次数的过程，加上之前LB和LA的比较次数，那么综合得其时间复杂度为0（lengthA + lengthB）
本算法的另一种思路，不依靠前面已经定义好，能拿来就用的函数，使用指针进行比较，赋值
复制代码
1 //2、合并线性表AB，AB的元素按值非递减有序的排列，要把A和B归并为一个新表C，且C的元素依然是按照值非递减的有序排列
2 void MergeList(SqList LA, SqList LB, SqList *LC)
3 {
4 //还是先构造表C，不用下标，只能使用指针来操作
5 LC->listsize = LA.length + LB.length;
6 LC->length = LA.length + LB.length;
7 int *c = (int *)malloc((LC->listsize) * sizeof(int));
8 int *a = LA.elem;
9 int *b = LB.elem;
10 int *lastA = LA.elem + (LA.length - 1) * sizeof(int);
11 int *lastB = LB.elem + (LB.length - 1) * sizeof(int);
12 LC->elem = c;
13 if (!LC->elem)
14 {
15 puts("c表构建失败！");
16 exit(-1);
17 }
18 while (a <= lastA && b <= lastB)
19 {
20 if (*a <= *b)
21 {
22 *c++ = *a++;//从右到左运算，先计算*c = *a，后a++，c++
23 }
24 else
25 {
26 *c++ = *b++;
27 }
28 }
29 while (a <= lastA)
30 {
31 *c++ = *a++;
32 }
33 while (b <= lastB)
34 {
35 *c++ = *b++;
36 }
37 }
复制代码
1、时间复杂度还是0（lengthA + lengthB）
2、这里发现，当线性表的元素无序的时候，进行插入操作的时间复杂度比有序的时候的时间复杂度要大的多。
因为，有序的线性表AB，比如依次递增（都不相等），则比较AB元素大小时，不用把B的每一个元素都和A比较！因为可以保证前面的元素肯定是小于后面的。这样大大节省了运行时间！
3、还有发现如果是两表归并到新表里，那么新表开始就是空的，只