链表-交集,并集,差集.doc

一个函数求两链表的求两链表的交、差、并集简单说下算法的思路：例如有如下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中即二者的并集。有了如上的思路，代码就好实现了：#include #include typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/链表的建立 void IntiList(LinkList &L)int i,n;LinkList q,p=L;puts(请输入链表的长度: );scanf(%d,&n);for(i=0;idata);p-next=q;p=q; p-next=NULL; void Show(LinkList L)for(LinkList p=L-next;p;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 &L1,LinkList &L2)/L3为差集 LinkList L3=(LinkList)malloc(sizeof(LNode); LinkList Pa=L1,Pb=L2,Pc,Pd=L3;while(Pa-next & Pb-next)if(Pa-next-data = Pb-next-data)/ L1=L2Pa=Pa-next; Pb=Pb-next;else if(Pa-next-data next-data) /L1next;else /只有L2中比L1小的,才是L1中没有的（差集） Pc=Pb-next;Pb-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(