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

,.题目一：集合的并、交运算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)到 lc 上pc-next=(linklist)malloc(sizeof(lnode);/ 若相等就申请存储空间链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 赋 null return 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和, cc, , f dn, ); e, f 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和, cc, , f 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