《链表-交集,并集,差集》由会员分享，可在线阅读，更多相关《链表-交集,并集,差集（4页珍藏版）》请在金锄头文库上搜索。
1、一个函数求两链表的求两链表的交、差、并集简单说下算法的思路：例如有如下 2 个链表(有序)：L1: 1 -2 -4 -6 -7 (设其游标指针为 Pa)L2: 2 -3 -4 -5 -6-8(设其游标指针为 Pb)使用归并的思想求两链表的交、差、并集必须明确如下几点：1.巧妙地移动游标指针，当两链表元素相同时，二者是同时移动的。 2.规定当 L1 的元素小于 L2 时值,只移动 Pa. 3.当 L2 的元素小于 L1，此时的元素真是 L1 中没有的，即 L2-L1 的差集。 4.把 L2-L1 的差集从 L2 中删除，L2 中所剩的即二者的交集。 5.把 L2-L1 的差集有序地接到 L1 中
2、即二者的并集。有了如上的思路，代码就好实现了：#include #include typedef int ElemType;typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;/链表的建立 void IntiList(LinkList LinkList q,p=L; puts(“请输入链表的长度: “); scanf(“%d“, for(i=0;idata); p-next=q; p=q; p-next=NULL; void Show(LinkList L) for(LinkList p=L-next;p
3、;p=p-next) printf(“%d “,p-data); printf(“n“); /L1 和 L2 都为有序的,获得集合 L1 和 L2 的并集 L1 和交集 L2 /把 L2 和 L1 的差集 L3(L2-L1)从 L2 中删掉并插入到 L1 中 LinkList Fun(LinkList LinkList Pa=L1,Pb=L2,Pc,Pd=L3;while(Pa-next Pb=Pb-next; else if(Pa-next-data next-data) /L1next; else /只有 L2 中比 L1 小的,才是 L1 中没有的（差集） Pc=Pb-next; Pb-
4、next=Pc-next; /删掉 Pc Pd-next=Pc; /尾查法构建差集 L3 Pd=Pc;Pc-next=Pa-next; /把删掉的 Pc 有序地插入到 L1 中 Pa-next=Pc; Pa=Pc; Pd-next=Pb-next; /L2 中剩下的也是差集 if(Pb-next!=NULL) /L2 中还剩下比 L1 大的从 L2 中删除并接到 L1 后面 Pa-next=Pb-next; Pb-next=NULL; return L3; int main() LinkList head1=(LinkList)malloc(sizeof(LNode); LinkList head2=(LinkList)malloc(sizeof(LNode); IntiList(head1); IntiList(head2); LinkList head3=Fun(head1,head2); puts(“他们的交集为:“); Show(head1); puts(“他们的并集为:“); Show(head2); puts(“他们的差集为(L2-L1):“); Show(head3); system(“pause“); /*测试用例 5 1 2 4 6 7 6 2 3 4 5 6 8 */
