链表-交集,并集,差集

链表-交集,并集,差集

ID:14399268

大小:50.00 KB

页数:4页

时间:2018-07-28

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

3、(LNode));scanf("%d",&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=(L

4、inkList)malloc(sizeof(LNode));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

5、;//删掉PcPd->next=Pc;//尾查法构建差集L3Pd=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;}returnL3;}intmain(){LinkListhead1=(LinkList)malloc(sizeof(LNode));LinkL

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。