集合的并、交運(yùn)算(C語言)

1、 題目一：集合的并、交運(yùn)算1 設(shè)計思想首先，建立兩個帶頭結(jié)點的有序單鏈表表示集合A和B。須注意的是：利用尾插入法建立有序單鏈表，輸入數(shù)值是升序排列。 其次，根據(jù)集合的運(yùn)算規(guī)則，利用單鏈表的有序性，設(shè)計交、并和差運(yùn)算。根據(jù)集合的運(yùn)算規(guī)則，集合AB中包含所有既屬于集合A又屬于集合B的元素。因此，須查找單鏈表A和B中的相同元素并建立一個鏈表存于此鏈表中。 根據(jù)集合的運(yùn)算規(guī)則，集合AB中包含所有或?qū)儆诩螦或?qū)儆诩螧的元素。因此， 遍歷兩鏈表的同時若元素相同時只將集合A中的元素存于鏈表中，若集合A中的下一個元素小于B中的元素就將A中的元素存于新建的鏈表中。反之將B中的元素存于鏈表中。2所用數(shù)據(jù)結(jié)構(gòu)線

2、性結(jié)構(gòu)利用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)集合的基本運(yùn)算。3源代碼分析#include<stdio.h>#include<stdlib.h>#define ERROR 0#define OK 1typedef int Status;typedef char Elemtype;typedef struct LNode線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)Elemtype data;struct LNode *next;Lnode,*Linklist;#include"text.h"LNode* Greatlist(int *N,int n) /建立一個帶有頭結(jié)點的單鏈表 Linklis

3、t p,q,L; L=p=(LNode *)malloc(sizeof(LNode);L->next=NULL;if(n!=0)for(int i=0;i<n;i+) q=(LNode *)malloc(sizeof(LNode);/尾部插入結(jié)點建立帶有頭結(jié)點單鏈表q->data=Ni; p->next=q;/指針后移p=q;p->next=NULL;/對于非空表，最后結(jié)點的指針域放空指針return L;LNode* jiaoji(Linklist la,Linklist lb)/求兩集合的交集Linklist pa,pb,pc,Lc;pa=la->nex

4、t;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->data>pb->d

5、ata)/若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-&

6、gt;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->data>pb->data)pc->next=(Linklist)malloc(sizeof(LNode);/若pa所指的元素大于pb所指的元素申請空間將值存入鏈表lc，pb指針后移pc=pc->next;pc->da

7、ta=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&q

8、uot; ,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)含多個結(jié)點的順序表a,b,c,f和c,d,e,fn");printf("建立鏈表L1為n");L1=Greatlist(A,4);Print_Link

9、List(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)含一個結(jié)點的順序表a和空表n");int A11='a'int B11='0'printf("建立鏈表L

10、1為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 B

11、21='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測試數(shù)據(jù)及運(yùn)行結(jié)果(1)含多個結(jié)點的順序表a,b,c,f和c,d,e,f(2)含一個結(jié)點的順序表a和空表 (3)2個空表 5算法分析（1）LNode* Greatlist()/尾插法建立鏈表算法的時間復(fù)雜度為O（n），n為輸入元素個數(shù)。（2）LNode* jiaoji(Linklist l