集合的并、交运算(C语言)

1、共享知识分享快乐盛年不重来，一日难再晨。及时宜自勉，岁月不待人题目一：集合的并、交运算1设计思想首先，建立两个带头结点的有序单链表表示集合A和B。须注意的是：利用尾插入法建立有序单链表，输入数值是升序排列。其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。 根据集合的运算规则，集合AGB中包含所有既属于集合A又属于集合B的元素。 因此，须查找单链表A和B中的相同元素并建立一个链表存于此链表中。根据集合的运算规则，集合 A U B中包含所有或属于集合 A或属于集合B 的元素。因此，遍历两链表的同时若元素相同时只将集合A中的元素存于链表中，若集合A中的下一个元素小于B中的元素就将A

2、中的元素存于新建的链表 中。反之将B中的元素存于链表中。2所用数据结构线性结构利用链式存储结构实现集合的基本运算。3源代码分析#i nclude#in clude#defi ne ERROR 0#defi ne OK 1typedef int Status;typedef char Elemtype;typedef struct LNode线性表的链式存储结构Elemtype data;struct LNode *n ext;L node,*L in klist;#i ncludetext.hLNode* Greatlist(i nt *N,i nt n)建立一个带有头结点的单链表Lin kl

3、ist p,q,L;L=p=(LNode *)malloc(sizeof(LNode);L- next=NULL;if(n !=0)for(i nt i=0;i data=Ni;p-n ext=q;指针后移p=q；p-next=NULL; /对于非空表，最后结点的指针域放空指针return L;LNode* jiaoji(Li nklist la,L i nklist lb)/ 求两集合的交集Lin klist pa,pb,pc,Lc;pa=la-n ext;pb=lb-n ext;Lc=(Li nklist)malloc(sizeof(LNode);申请存储空间Lc- next=NULL;p

4、c=Lc;while(pa&pb)if(pa-data=pb-data)pc-next=(Linklist)malloc(sizeof(LNode); 若相等就申请存储空间链至U Lc上pc=pc- n ext;pc-data=pa-data;pa=pa-next;/la, lb 的指针后移pb=pb-n ext;else if(pa-datapb-data)/若 pa所指的元素大于 pb所指的元素 pb指针后移pb=pb-n ext;elsepa=pa-n ext;pc-next=NULL; 最后给 pc 的 next 赋 NULLreturn Lc;LNode* bingji(Linkli

5、st la,Linklist lb) / 求两集合的并集Lin klist pa,pb,pc,lc;pa=la-n ext;pb=lb-n ext;lc=(L in klist)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- n ext;pc-data=pa-data;pa=pa-n ext;pb=pb-n ext;el

6、se if(pa-datapb-data)pc-next=(Linklist)malloc(sizeof(LNode); 若 pa 所指的元素大于 pb所指的元素申请空间将值存入链表lc, pb指针后移pc=pc- n ext;pc-data=pb-data;pb=pb-n ext;elsepc-next=(Linklist)malloc(sizeof(LNode); 若 pa 所指的元素小于 pb所指的元素申请空间将值存入链表lc，pa指针后移pc=pc- n ext;pc-data=pa-data;pa=pa-n ext;pc-n ext=pa?pa:pb;return lc;void P

7、rin t_Li nkList(Li nklist L)输出元素Lin klist p=L-n ext;while(p)/链表不为空时输出链表中的值printf( %3c ,p-data);p=p-n ext;printf( n);void main()Li nklist L1,L2 丄 a丄b;int A4=a,b,c,f;int B4=c,d,e,f;printf(1)含多个结点的顺序表 a , b和cc, fn e , f printf(建立链表L1为n);L1= Greatlist(A,4);Prin t_Li nkList(L1);printf(建立链表L2为n);L2=Greatl

8、ist(B,4);Prin t_Li nkList(L2);printf(两链表的交集为：n);La=jiaoji(L1,L2);Prin t_Li nkList(La);prin tf(两链表的并集为:n);Lb=b in gji(L1, L2);Prin t_Li nkList(Lb);printf(2)含一个结点的顺序表 a和空表n);int A11=a;int B11=0;printf(建立链表L1为n);L1= Greatlist(A1,1);Prin t_Li nkList(L1);printf(建立链表L2为n);L2=Greatlist(B1,0);Prin t_Li nkLi

9、st(L2);prin tf(两链表的交集为:n);La=jiaoji(L1,L2);Prin t_Li nkList(La);prin tf(两链表的并集为:n);Lb=b in gji(L1, L2);Prin t_Li nkList(Lb);printf(3)2 个空表 n);int A21=0;int B21=0;printf(建立链表L1为n);L仁 Greatlist(A2,0);Prin t_Li nkList(L1);printf(建立链表L2为n);L2=Greatlist(B2,0);Prin t_Li nkList(L2);prin tf(两链表的交集为:n);La=ji

10、aoji(L1,L2);Prin t_Li nkList(La); printf(两链表的并集为：n);Lb=b in gji(L1, L2);Prin t_Li nkList(Lb);free(L1);free(L2);free(La);free(Lb);4测试数据及运行结果(1) 含多个结点的顺序表a , b 和 cc, : f d e , f(2) 含一个结点的顺序表 a和空表(3)2个空表Cffli C ;丫i n d mu ssy5-te m 3 PfmcL exeQ含多个结点的顺序表，JH J J J A】和J L J打 建盖岳夷“a b c f建立链表毗为两链表的交集为:c f两链衷的井集为匕a b c d e f2)含一士结点的顺序表【*】和空表门3L建立链表晞为两链表的交集为1两链表的井集为；a.禹2个空表建立链表X为建立.链表凹为两链衷的交集为：两链表的并集为请按任意键继续5算法分析(1) LNode* Greatlist()尾插法建立链表算法的时间复杂度为o (n), n为输入元素个数。(2) LNode* jiaoji(Linklist la,Linklist lb)算法时间复杂度为O (m