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

题目一：集合的并、交运算1 设计思想首先，建立两个带头结点的有序单链表表示集合A和B。须注意的是：利用尾插入法建立有序单链表，输入数值是升序排列。 其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。根据集合的运算规则，集合AB中包含所有既属于集合A又属于集合B的元素。因此，须查找单链表A和B中的相同元素并建立一个链表存于此链表中。 根据集合的运算规则，集合AB中包含所有或属于集合A或属于集合B的元素。因此， 遍历两链表的同时若元素相同时只将集合A中的元素存于链表中，若集合A中的下一个元素小于B中的元素就将A中的元素存于新建的链表中。反之将B中的元素存于链表中。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(LNode);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=(Linklist)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-next;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所指的元素申请空间将值存入链表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);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);Lb=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);printf(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算法分析（1）LNode* Greatlist()/尾插法建立链表算法的时间复杂度为O（n），n为输入元素个数。（2）LNode* jiaoji(Linklist la,Linklist lb) 算法时间复杂度为O（m+n），m为集合A元素个数，n为集合B元素个数。（3）LNode* bingji(Linklist la,Linklist lb)算法时间复杂度为O（m+n），m为集合A元素个数，n为集合B元素个数。（4）void Print_LinkList(Linklist L)算法时间复杂度为O（n）n为集合元素个数。