《集合的并、交运算(C语言)》由会员分享，可在线阅读，更多相关《集合的并、交运算(C语言)（5页珍藏版）》请在金锄头文库上搜索。
1、 .wd.题目一：集合的并、交运算1设计思想首先，建设两个带头结点的有序单链表表示集合A和B。须注意的是：利用尾插入法建设有序单链表，输入数值是升序排列。其次，根据集合的运算规那么，利用单链表的有序性，设计交、并和差运算。根据集合的运算规那么，集合AB中包含所有既属于集合A又属于集合B的元素。因此，须查找单链表A和B中的一样元素并建设一个链表存于此链表中。根据集合的运算规那么，集合AB中包含所有或属于集合A或属于集合B的元素。因此，遍历两链表的同时假设元素一样时只将集合A中的元素存于链表中，假设集合A中的下一个元素小于B中的元素就将A中的元素存于新建的链表中。反之将B中的元素存于链表中。2所用
2、数据构造线性构造利用链式存储构造实现集合的 基本运算。3源代码分析#include#include#define ERROR 0#define OK 1typedef int Status;typedef char Elemtype;typedef struct LNode线性表的链式存储构造Elemtype data;struct LNode *next;Lnode,*Linklist;#includetext.hLNode* Greatlist(int *N,int n)/建设一个带有头结点的单链表Linklist p,q,L; L=p=(LNode *)malloc(sizeof(LNo
3、de);L-next=NULL;if(n!=0)for(int i=0;idata=Ni;p-next=q;/指针后移p=q;p-next=NULL;/对于非空表，最后结点的指针域放空指针return L;LNode* jiaoji(Linklist la,Linklist lb)/求两集合的交集Linklist pa,pb,pc,Lc;pa=la-next;pb=lb-next;Lc=(Linklist)malloc(sizeof(LNode);/申请存储空间Lc-next=NULL;pc=Lc;while(pa&pb)if(pa-data=pb-data) pc-next=(Linklis
4、t)malloc(sizeof(LNode);/假设相等就申请存储空间链到Lc上pc=pc-next;pc-data=pa-data;pa=pa-next;/la，lb的指针后移pb=pb-next;else if(pa-datapb-data)/假设pa所指的元素大于pb所指的元素pb指针后移pb=pb-next;elsepa=pa-next;pc-next=NULL;/最后给pc的next赋NULLreturn Lc; LNode* bingji(Linklist la,Linklist lb)/求两集合的并集Linklist pa,pb,pc,lc;pa=la-next;pb=lb-ne
5、xt;lc=(Linklist)malloc(sizeof(LNode);lc-next=NULL;pc=lc;while(pa&pb)if(pa-data=pb-data)pc-next=(Linklist)malloc(sizeof(LNode);/假设pa所指的元素等于pb所指的元素申请空间将值存入链表lc，pa，pb指针后移pc=pc-next; pc-data=pa-data;pa=pa-next;pb=pb-next;else if(pa-datapb-data)pc-next=(Linklist)malloc(sizeof(LNode);/假设pa所指的元素大于pb所指的元素申请
6、空间将值存入链表lc，pb指针后移pc=pc-next;pc-data=pb-data;pb=pb-next;elsepc-next=(Linklist)malloc(sizeof(LNode);/假设pa所指的元素小于pb所指的元素申请空间将值存入链表lc，pa指针后移pc=pc-next;pc-data=pa-data;pa=pa-next; pc-next=pa?pa:pb;return lc;void Print_LinkList(Linklist L)/输出元素Linklist p=L-next; while(p)/链表不为空时输出链表中的值printf( %3c ,p-data);
7、p=p-next;printf( n );void main()Linklist L1,L2,La,Lb;int A4=a,b,c,f;int B4=c,d,e,f;printf(1)含多个结点的顺序表a,b,c,f和c,d,e,fn);printf(建设链表L1为n);L1=Greatlist(A,4);Print_LinkList(L1);printf(建设链表L2为n);L2=Greatlist(B,4);Print_LinkList(L2);printf(两链表的交集为：n);La=jiaoji(L1,L2);Print_LinkList(La);printf(两链表的并集为：n);L
8、b=bingji(L1,L2);Print_LinkList(Lb);printf(2)含一个结点的顺序表a和空表n);int A11=a;int B11=0;printf(建设链表L1为n);L1=Greatlist(A1,1);Print_LinkList(L1);printf(建设链表L2为n);L2=Greatlist(B1,0);Print_LinkList(L2);printf(两链表的交集为：n);La=jiaoji(L1,L2);Print_LinkList(La);printf(两链表的并集为：n);Lb=bingji(L1,L2);Print_LinkList(Lb);pr
9、intf(3)2个空表n);int A21=0;int B21=0;printf(建设链表L1为n);L1=Greatlist(A2,0);Print_LinkList(L1);printf(建设链表L2为n);L2=Greatlist(B2,0);Print_LinkList(L2);printf(两链表的交集为：n);La=jiaoji(L1,L2);Print_LinkList(La);printf(两链表的并集为：n);Lb=bingji(L1,L2);Print_LinkList(Lb);free(L1);free(L2);free(La);free(Lb);4测试数据及运行结果(1)含多个结点的顺序表a,b,c,f和c,d,e,f(2)含一个结点的顺序表a和空表(3)2个空表5算法分析1LNode* Greatlist()/尾插法建设链表算法的时间复杂度为On，n为输入元素个数。2LNode* jiaoji(Linklist la,Linklist lb)算法时间复杂度为Om+n，m为集合A元素个数，n为集合B元素个数。3LNode* bingji(Linklist la,Linklist lb)算法时间复杂度为Om+n，m为集合A元素个数，n为集合B元素个数。4void Print_LinkList(Linklist L)算法时间复杂度为Onn为集合元素个数。
