Question

【数据结构·C语言】请高手帮忙检查一个关于【链表的归并】算法是否正确

假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。

现本题对上题的条件作以下两点修改，对顺序表重新编写求得表C的算法。
(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；
(2) 利用A表空间存放表C。

另：因为我是自学的数据结构，所以任何方面都有可能出问题，希望能够帮忙指出，不厌其详，谢谢！！！

我的想法是：首先对A重新非配容量，然后将B归并入A中，然后删除A中多余（重复）的元素。不知道会不会有其他做法？
比如每归并一个B的元素到A就查找一遍A中的元素之类的？哪种更简便？

status Union_C(SqList &A, SqList &B, SqList &C)
if(A.listsize<A.length+B.length)
{ newbase=(ElemType*)realloc(A.elem,(A.length+B.length)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);
}
int i=0,k=0,p;
while(k<=B.length-1)
{ if(B.elem[k]<=A.elem[i])
{ for(p=&(A.elem[A.length-1]);p>=&(A.elem[i]);p--) *(p+1)=p;
A.elem[i]=B.elem[k];
k++; A.length++;
}
else i++;
}//while
i=0;
while(i<A.length)
{ if(A.elem[i]==A.elem[i+1])
{ for (p=&(A.elem[i+1]);p<=&(A.elem[A.length-1]);p++) *(p-1)=*p;
--A.length; i++;
}
else i++;
}//while
return OK;
}Union_C

Answer 1

1. for(p=&(A.elem[A.length-1]);p>=&(A.elem[i]);p--)  *(p+1)=p;  最后的p前面少一个星号，应该改为for(p=&(A.elem[A.length-1]);p>=&(A.elem[i]);p--) *(p+1)=*p;

2. A.elem[i]=B.elem[k];之后，由于B的元素插在了A的i位置，所以，这之后i应该自加1

3. for (p=&(A.elem[i+1]);p<=&(A.elem[A.length-1]);p++) *(p-1)=*p;这里是要覆盖i+1位置的元素，而根据你自己写的初始条件，p一开始就已经指向i+1位置，因此需要修改，同时伴随修改结束条件，最终修改为for (p=&(A.elem[i+1]);p<&(A.elem[A.length-1]);p++) *p=*(p+1);

其他的都还好。

PS，如果想程序运行简单一点，建议你每归并一个B的元素到A就查找一遍A中的元素，但是程序就会麻烦一点，还有，对A的重复元素的自检，可以考虑把if写为while，因为考虑到又可以能连着三个以上的元素相等。

希望采纳，期待对你有帮助，欢迎追问^_^

追问

把if写成while吗？可是原程序里的while(i<A.length)这一句是不是已经考虑到连着的3个以上的元素了？还是我哪里想错了？

追答

顺序表元素的移动是复杂度很大的，关于if改while的地方主导思想是，减少元素移动的次数。
例如：
顺序表内容为1222345
你的程序，检测到第二个2的时候就会把后面的元素统统移动一遍，变为122345，移动了4个元素；然后再发现2又有重复，再把后面的元素统统移动一遍，变为12345，移动3个元素。整个过程移动了7个元素。
如果你修改你的程序使得其能检测到一共有3个一样的元素，那么就可以只移动一遍就可以变为12345，整个过程只移动三个元素，这样一来，你的效率就会有所提高。
当然，我说的是个大致的意思，不是简单的用while去替换if，其实你if的条件有待斟酌，里面的i++也有待斟酌。就是检测相同元素的逻辑，再想想怎样比较好。
如果还有困难，欢迎继续追问。

Answer 2

首先，定义两个指向链表元素的指针，一个指向A中的元素，一个指向B中的元素；
其次，取出这两个指针指向的元素的数据，比较大小：
如果A=B，放弃，两个指针都后移一位；
如果A<B，保存当前A为oldA，并将A后移一位，跳出本次循环重新比较；
如果A>B，B插入oldA之后，并将B后移一位。
循环直到A和B的next都为NULL.
算法上来说，复杂度应该是O(n)

你前面的算法复杂度为O(n^2),因为遍历集合并排序为嵌套循环