链表-交集并集差集

《链表-交集并集差集》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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#includetypedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;//链表的建立voidIntiList(LinkList&L){inti,n;LinkListq,p=L;puts("请输入链表的长度:");scanf("%d",&n);for(i=0;i

3、&q->data);p->next=q;p=q;}p->next=NULL;}voidShow(LinkListL){for(LinkListp=L->next;p;p=p->next)printf("%d",p->data);printf("");}//L1和L2都为有序的,获得集合L1和L2的并集L1和交集L2//把L2和L1的差集L3(L2-L1)从L2中删掉并插入到L1中LinkListFun(LinkList&L1,LinkList&L2){//L3为差集LinkListL3=(LinkList)malloc(sizeof(LNode));

4、LinkListPa=L1,Pb=L2,Pc,Pd=L3;while(Pa->next&&Pb->next){if(Pa->next->data==Pb->next->data)//L1==L2{Pa=Pa->next;Pb=Pb->next;}elseif(Pa->next->datanext->data)//L1next;}else{//只有L2中比L1小的,才是L1中没有的（差集）Pc=Pb->next;Pb->next=Pc->next;//删掉PcPd->next=Pc;//尾查法构建差集L3Pd=Pc;Pc->

5、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;}returnL3;}intmain(){LinkListhead1=(LinkList)malloc(sizeof(LNode));LinkListhead2=(LinkList)malloc(sizeof(LNode));IntiList(

6、head1);IntiList(head2);LinkListhead3=Fun(head1,head2);puts("他们的交集为:");Show(head1);puts("他们的并集为:");Show(head2);puts("他们的差集为(L2-L1):");Show(head3);system("pause");}/*测试用例5124676234568*/