单链表的交并补1

本文格式为Word版，下载可任意编辑——单链表的交并补1单链表的交并补

1.需求分析

任意给定两个包含10-2000个元素的集合A,B（集合中元素类型为任意整型数），求这两个集合的交集、并集和补集。

单链表合并，时间繁杂度O(m*n))，空间繁杂度O(n)2.概要设计

首先设计程序的设计结构用来表示集合

//线性表的单链表存储结构

typedefstructLNode{chardata;

structLNode*next;}LNode,*LinkList;

创立生成次集合的函数

voidCreateList_L(LinkList//线性表的单链表存储结构typedefstructLNode{chardata;structLNode*next;}LNode,*LinkList;

voidCreateList_L(LinkList

L->next=NULL;//先建立一个带头结点的单链表for(inti=n;i>0;i--){

LNode*p=newLNode;//生成新结点cin>>p->data;//输入元素值

p->next=L->next;//插入到表头L->next=p;}}

voidBing(LinkListLa,LinkListLb,LinkListLc->next=NULL;LNode*pa=La->next;

while(pa)//把集合La中的元素复制到集合Lc中{

LNode*q=newLNode;q->data=pa->data;q->next=Lc->next;Lc->next=q;

pa=pa->next;//指向La的指针pa后移}

LNode*pb=Lb->next;

while(pb)//假使集合b中元素不同于集合a中元素，就添加到集合c中{

boolflag=true;//flag用来标记a,b中是否有一致元素pa=La->next;while(pa){

if(pa->data==pb->data)

{flag=false;break;}elsepa=pa->next;}

if(flag){//元素不同LNode*p=newLNode;p->data=pb->data;p->next=Lc->next;Lc->next=p;}pb=pb->next;}}

voidJiao(LinkListLa,LinkListLb,LinkListLc->next=NULL;LNode*pb=Lb->next;

while(pb)//假使元素即属于集合a又属于集合b,则把该元素放到集合c中{

LNode*pa=La->next;while(pa){

if(pa->data==pb->data)//有一致元素{LNode*p=newLNode;p->data=pb->data;p->next=Lc->next;Lc->next=p;break;

}

elsepa=pa->next;//没有继续后移}pb=pb->next;}}

voidCha(LinkListLa,LinkListLb,LinkListLc->next=NULL;LNode*pa=La->next;

while(pa)//假使元素属于集合a不属于集合b,则把该元素放到集合c中{boolflag=true;LNode*pb=Lb->next;while(pb){

if(pb->data==pa->data)

{flag=false;break;}elsepb=pb->next;}

if(flag){//元素不属于bLNode*p=newLNode;p->data=pa->data;p->next=Lc->next;Lc->next=p;}pa=pa->next;}}

voidoutput(LinkListL)//输出元素{

LNode*p=L->next;while(p){

coutnext;}cout>a;cout>b;