双向链表实现集合的并交差.doc

实验二：双向链表的创建，以及用双向链表实现集合见得并交和差#include#includetypedef struct DuLNode int data; struct DuLNode *prior; struct DuLNode *next; DuLNode,*DuLinkList;/建立空链表,链表头指针的data中存放了链表元素的个数。void InitList(DuLNode *p) *p=(DuLNode *)malloc(sizeof(DuLNode); (*p)-next=(*p)-prior=*p; (*p)-data=0;/在空表的基础上，创建有多个元素的链表。void create_list(DuLNode *p)int i,n,m;DuLinkList a,b;a=*p;printf(输入需要输入的元素的个数:);scanf(%d,&n); printf(n输入需要输入的元素:);for(i=0;idata=m;a-next=b;b-next=*p;b-prior=a;(*p)-prior=b;a=b;(*p)-data+;DuLinkList GetElemP(DuLinkList h,int i) int j; DuLinkList p=h; for(j=1;jnext ; return p;void Listinsert(DuLNode *m,int i,int e) DuLinkList p,q; printf(在第%d个元素前插入元素%dn,i,e); if(m-data=0)p=(DuLinkList)malloc(sizeof(DuLNode); p-data=e; m-next=p; p-prior=m; m-prior=p; p-next=m; m-data+;else q=(DuLinkList)malloc(sizeof(DuLNode); p=(DuLinkList)malloc(sizeof(DuLNode); q=GetElemP(m,i); p-data=e; p-prior=q-prior; q-prior-next=p; p-next=q; q-prior=p; m-data+;void ListDelete(DuLinkList L,int i)printf(删除第%d个元素n,i);DuLinkList p; p=GetElemP(L,i); p-prior-next=p-next; p-next-prior=p-prior;L-data -; free(p);void Display( DuLinkList L) DuLinkList p;if(L-data=0)printf(该集合为空n);elseprintf(输出该集合的元素); for(p=L-next ;p!=L;)printf(%dt,p-data); p=p-next ;printf(n该集合的元素个数:%dn,L-data);void Union(DuLinkList &la,DuLinkList lb)/求两个集合la,lb的并将结果保存在la中。int a,b,i,j,m; DuLinkList p,q;a=la-data;b=lb-data ;p=lb-next ;printf(对两个集合并操作:n);for(i=1;inext ;for(j=1;jdata !=q-data )q=q-next ;m=0;elsem=1;break;if(m=0)Listinsert(la,la-data+1 ,p-data );p=p-next ;void intersect(DuLinkList &lc,DuLinkList la,DuLinkList lb)/求两个集合la和lb的交集将结果保存在lc中。 int a,b,i,j; DuLinkList p,q;a=la-data ;b=lb-data ;p=lb-next ;for(i=1;inext ;for(j=1;jdata =q-data )Listinsert(lc,1,p-data );break;elseq=q-next;p=p-next ;void decrease(DuLinkList &ld,DuLinkList la,DuLinkList lb)/求集合la-lb的差并将结果保存在ld中。int a,b,i,j,m; DuLinkList p,q;a=la-data ;b=lb-data ;p=la-next ;for(i=1;inext ;for(j=1;jdata !=q-data)q=q-next ;m=0;elsem=1;break;if(m=0)printf(将两个集合的差插入到差集合中);Listinsert(ld,1,p-data);p=p-next ;if(ld-data=0)printf(两个集合的差为空);void main() DuLinkList la,lb,ld,lc,lj; InitList(&la) ;InitList(&lb) ;InitList(&lc) ;InitList(&ld) ;InitList(&lj) ;printf(集合la:);create_list(&la); printf(集合lb:);create_list(&lb); printf(集合lc:);create_list(&lc);printf(对la进行插入操n); Listinsert(la,1,5) ; Listinsert(la,1,2) ; Listinsert(la,2,4) ; Listinsert(la,2,3) ; Listinsert(la,1,1) ;Listinsert(la,1,6) ;printf(对lb进行插入操n); Listinsert(lb,1,7) ; Listinsert(lb,1,9) ; Listinsert(lb,1,3) ;decrease(ld,la,lb);printf(两个集合的差集合:); Display(ld);printf(求两个集合la和lb的交集:n);intersect(lj,la,lb);/求