數(shù)據結構課程設計報告(集合的交并差運算)

1、.淮 陰 工 學 院數(shù)據結構課程設計報告作班學專題者 :級 :院 :業(yè) :目 :學 號：指導教師：2016年 1月.目錄1 課題描述 . 12 系統(tǒng)設計 . 12.1 功能模塊設計. 12.1.1 基于單鏈表設計 . 12.1.2 基于順序表設計 . 22.2 數(shù)據結構設計. 32.2.1 基于單鏈表設計 . 32.1.2 基于順序表設計 . 32.3 算法設計 . 42. 3.1 基于單鏈表，順序表設計 . 43. 1 菜單設計（基于單鏈表）. 53.2 源代碼設計（基于單鏈表） . 63.3 菜單設計（基于順序表）. 123. 4 源代碼設計（基于順序表） . 124. 1 最終結果（基于

2、單鏈表）. 254.2 最終結果（基于順序表）. 25結 論 . 26致 . 27參 考 文 獻 . 29.1 課題描述編制一個能演示執(zhí)行集合的交、并和差運算的程序。集合元素用小寫英文字母，執(zhí)行各種操作應以對話方式執(zhí)行。利用單鏈表表示集合；理解好三種運算的含義 2 系統(tǒng)設計2.1 功能模塊設計2.1.1 基于單鏈表設計（1）節(jié)點結構單元模塊定義有序表的節(jié)點結構；typedef struct lnode/ 定義結構體類型指針 char data;struct lnode*next;*pointer;（2）有序表單元模塊實現(xiàn)有序表的抽象數(shù)據類型；readdata(pointer head)初始條件

3、：head 是以 head 為頭節(jié)點的空鏈表。操作結果：生成以 head 為頭節(jié)點的非空鏈表。pop(pointer head)初始條件：head 是以 head 為頭節(jié)點的非空鏈表。操作結果：將以 head 為頭節(jié)點的鏈表中數(shù)據逐個輸出。（3）集合單元模塊實現(xiàn)集合獲得抽象數(shù)據類型；and(pointer head1,pointer head2,pointer head3)初始條件：鏈表 head1、head2、head3 已存在操作結果：生成一個由 head1 和 head2 的并集構成的集合 head3 。.or(pointer head1,pointer head2,pointer he

4、ad3)初始條件：鏈表 head1、head2、head3 已存在操作結果：生成一個由 head1 和 head2 的交集構成的集合 head3 。 （4）主程序模塊void main（）初始化；do接受命令；處理命令；while（“命令”!=“退出”）；2.1.2 基于順序表設計（1）順序表結構單元模塊定義順序表的結構體；typedef struct / 定義 seqlist 的結構體datatype listmaxsize;int size ; seqlist;（2）函數(shù)單元模塊定義各種所需函數(shù)；int listdel( seqlist *l , int i , datatype *x)/

5、 順序表的刪除函數(shù)int listget(seqlist l , int i , datatype *x)/ 獲取順序表的元素函數(shù) void listfind(seqlist l , datatype x)/ 順序表查找元素函數(shù)void selcetsort(seqlist *l ) /順序表選擇排序函數(shù)void unionset(seqlist mylist1 , seqlist mylist2)/ 求并集函數(shù)void mixedset(seqlist mylist1 , seqlist mylist2)/ 求交集元素函數(shù).void diffentset(seqlist mylist1 ,

6、seqlist mylist2) / 求差集元素函數(shù) （3）主函數(shù)單元模塊定義主函數(shù)；void main() seqlist mylist1 , mylist2;/ 定義順序表 mylistint i;datatype temp;listinitiate( &mylist1);listinitiate( &mylist2);/ 初始化兩個順序表2.2 數(shù)據結構設計2.2.1 基于單鏈表設計定義結構體類型指針，集合采用單鏈表存儲。typedef struct lnode/ 定義結構體類型指針head1=(pointer)malloc(sizeof(struct lnode);head1-next

7、=null;head2=(pointer)malloc(sizeof(struct lnode);head2-next=null;head3=(pointer)malloc(sizeof(struct lnode);2.1.2 基于順序表設計typedef struct / 定義 seqlist 的結構體 datatype listmaxsize;int size ;void unionset(seqlist mylist1 , seqlist mylist2) / 求并集.int m, i,j ;datatype x;seqlist test ;listinitiate( &test); /

8、 定義并初始化 2.3 算法設計2.3.1 基于單鏈表，順序表設計數(shù)據輸入界面主菜單界面集合的并集運算集合的交集運算集合的差集運算結束圖 2.1 系統(tǒng)模塊流程圖調用輸入函數(shù)，輸入集合信息顯示主菜單接受用戶選擇是否合法是否.是否為 4.否是調用對應選項函數(shù)圖 2.2 主菜單流程圖主菜單退出系統(tǒng)用戶選擇序號是否合法是否否是否為 1是調用并集函數(shù)和輸出函數(shù)圖 2.3 并集模塊流程圖求交集與差集的流程圖與并集類似。 3 詳細設計3.1 菜單設計（基于單鏈表）圖 3.1 主界面.3.2 源代碼設計（基于單鏈表）#include#includetypedef struct lnode/ 定義結構體類型指針

9、char data;struct lnode*next;*pointer;void readdata(pointer head)/ 定義輸入集合函數(shù)pointer p;char tmp;scanf(%c,&tmp);while(tmp!=n)p=(pointer)malloc(sizeof(struct lnode);/ 為指針 p 申請存空間 p-data=tmp;p-next=head-next;head-next=p;scanf(%c,&tmp);void pop(pointer head)/ 定義輸出集合函數(shù) pop()出棧函數(shù).pointer p;p=head-next;while(

10、p!=null)printf(%c,p-data);p=p-next;printf(n);void and(pointer head1,pointer head2,pointer head3)/ 定義集合的并集函數(shù) pointer p1,p2,p3;p1=head1-next;while(p1!=null)/遍歷鏈表 head1p3=(pointer)malloc(sizeof(struct lnode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;p2=head2-next;.while(p2!=null)/遍歷鏈表

11、 head2p1=head1-next;while(p1!=null)&(p1-data!=p2-data)p1=p1-next;if (p1=null)p3=(pointer)malloc(sizeof(struct lnode);p3-data=p2-data;p3-next=head3-next;head3-next=p3;p2=p2-next;void or(pointer head1,pointer head2,pointer head3)/ 定義集合的交集函數(shù) pointer p1,p2,p3;p1=head1-next;while(p1!=null)p2=head2-next;w

12、hile(p2!=null)&(p2-data!=p1-data)p2=p2-next;.if(p2!=null)&(p2-data=p1-data)p3=(pointer)malloc(sizeof(struct lnode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;void differ(pointer head1,pointer head2,pointer head3)/ 定義集合的差集函數(shù) pointer p1,p2,p3;p1=head1-next;while(p1!=null)p2=head2-next

13、;while(p2!=null)&(p2-data!=p1-data)p2=p2-next;if(p2=null)p3=(pointer)malloc(sizeof(struct lnode);p3-data=p1-data;p3-next=head3-next;.head3-next=p3;p1=p1-next;void main()/主函數(shù)int x;printf(輸入數(shù)據, 按回車鍵結束,第一個集合大于第二個集合)n);pointer head1,head2,head3;head1=(pointer)malloc(sizeof(struct lnode);head1-next=null;

14、head2=(pointer)malloc(sizeof(struct lnode);head2-next=null;head3=(pointer)malloc(sizeof(struct lnode);head3-next=null;printf(請輸入集合 1：n);readdata(head1);/調用輸入集合函數(shù)printf(請輸入集合 2：n);readdata(head2);/調用輸入集合函數(shù)a:printf(1.并集 2.交集 3.差集 4.結束 x.重新運算n);doprintf(請選擇序號 n);scanf(%d,&x);.switch(x)case 1:printf(兩集合

15、的并是 n);and(head1,head2,head3);/ 調用并集函數(shù) pop(head3);head3-next=null;break;case 2:printf(兩集合的交是 n);or(head1,head2,head3);/ 調用交集函數(shù) pop(head3);head3-next=null;break;case 3:printf(兩集合的差是 n);differ(head1,head2,head3);/ 調用差集函數(shù) pop(head3);head3-next=null;break;case 4:break;default:goto a;.while(x!=4);3.3 菜單設

16、計（基于順序表）圖 3.2 主界面3.4 源代碼設計（基于順序表）#include #include #include #define maxsize 100# define equal =typedef char datatype;typedef struct / 定義 seqlist 的結構體 .datatype listmaxsize;int size ; seqlist;void listinitiate( seqlist *l) / 初始化操作l-size = 0;int listlength( seqlist l) / 獲取長度return l.size;int listinser

17、t( seqlist *l , int i , datatype x)/插入函數(shù)的參數(shù)分別是 seqlist 類型的變量，插入位置 i，和插入的元素 x int j;if( l-size = maxsize)printf(順序表已滿，無法插入其他元素！ n);rrrrrr 0;rrrrrr (pause);.else if( il-size )printf(參數(shù) i 不合法！n);rrrrrr 0;rrrrrr (pause);elsefor( j=l-size ; ji ; j-)l-listj = l-listj-1; / 將 i 至 size 中間的元素依次后移一個單 位l-listi

18、= x; /將 x 插入指定的位置 il-size +; /l 的 size，及長度加一return 1;int listdel( seqlist *l , int i , datatype *x) / 順序表的刪除函數(shù)int j;if( l-size = 0)printf(順序表已無數(shù)據可刪！ n);.rrrrrr 0;rrrrrr (pause);else if( il-size-1 )printf(參數(shù) i 不合法！n);rrrrrr 0;rrrrrr (pause);else*x = l-listi; / 保存刪除的元素到 x 中for( j=i+1 ; jsize-1 ; j+)l-

19、listj-1 = l-listj; / 將 i+1 至 size 中間的元素依次前移一個 單位l-size -; /l 的 size，及長度加一return 1;int listget(seqlist l , int i , datatype *x) / 獲取順序表的元素函數(shù)if( il.size-1 ).printf(參數(shù) i 不合法！n);return 0;else*x = l.listi;return 1;void listfind(seqlist l , datatype x) / 順序表查找元素函數(shù) int i;for(i=0 ; il.size; i+)if(l.listi =

20、x)printf(與查找元素相同的位置為： %d n , i+1 ); continue;if( i = l.size-1 ).printf(沒有找到與所查詢相同的元素！ n);void selcetsort(seqlist *l ) / 順序表選擇排序函數(shù) int i,j;datatype temp;int length = listlength( *l);for(i=0; ilisti+1;j=i;while(j -1 & temp listj)l-listj+1 = l-listj;j-;l-listj+1 = temp;void unionset(seqlist mylist1 , s

21、eqlist mylist2) int m, i,j ;datatype x;seqlist test ;./ 求并集.listinitiate( &test); / 定義并初始化for(m=0 ; m listlength(mylist1) ; m+)listget(mylist1 , m , &x);listinsert( &test , m , x ); / 先將順序表一中的元素放入順序表中 for(i=0 ; i listlength(mylist2) ; i+)listget(mylist2 , i , &x);listinsert( &test , m , x ); / 再將順序表

22、二中的元素放入順序表中 m+;for(i=0 ; i listlength(test) ; i+) / 求并集for(j = i+1 ; jlistlength(test); j+) / 將順序表中的相同的元素刪除 if(test.listi = test.listj )listdel( &test , j , &x);selcetsort(&test);printf( the elements of the union set are : );for(i=0 ; i listlength(test) ; i+).listget(test , i , &x); printf(%c , x);p

23、rintf(n);void mixedset(seqlist mylist1 , seqlist mylist2) / 求交集元素函數(shù) int m, i,j ;datatype x;seqlist mylist ;listinitiate( &mylist); /定義并初始化seqlist test;listinitiate( &test);m=0;for(i=0 ; i listlength(mylist1) ; i+) / 求交集for(j = 0 ; jlistlength(mylist2); j+)if(mylist1.listi = mylist2.listj )listinsert

24、( &test , m , mylist1.listi ); / 將相同的元素放在 test順序表中.m+;continue;for(i=0 ; i listlength(test) ; i+) / 求并集for(j = i+1 ; jlistlength(test); j+) / 將順序表中的相同的元素刪除 if(test.listi = test.listj )listdel( &test , j , &x);selcetsort(&test); / 對順序表進行有序化printf( the elements of the mixed set are : );for(i=0 ; i tes

25、t.size ; i+)listget(test , i , &x);printf(%c , x);printf(n);void diffentset(seqlist mylist1 , seqlist mylist2) / 求差集元素函數(shù) .int m=0,n, i,j ;datatype x;seqlist test;listinitiate( &test);for(i=0 ; i listlength(mylist1) ; i+)n=0;for(j = 0 ; jlistlength(mylist2); j+)if(mylist1.listi = mylist2.listj )n+;if

26、(n = 0)listinsert( &test , m , mylist1.listi ); / 將相同的元素放在 test順序表中m+;for(i=0 ; i listlength(test) ; i+) / 求并集for(j = i+1 ; jlistlength(test); j+) / 將順序表中的相同的元素除 if(test.listi = test.listj )listdel( &test , j , &x);.selcetsort(&test);printf( the elements of the diffrent set are : );for(i=0 ; i listl

27、ength(test) ; i+)listget(test , i , &x);printf(%c , x);printf(n);void main()seqlist mylist1 , mylist2; /定義順序表 mylistint i;datatype temp;listinitiate( &mylist1);listinitiate( &mylist2); / 初始化兩個順序表 printf(n%s%sn, equal , equal);printf(n welcome to the program of collection ! printf(n%s%sn, equal , equ

28、al);printf(n 請輸入兩個集合 ! n);printf(n 請輸入集合 1！: );i = 0;.n );.while( (temp=getchar() ) != n)if(96temp & temp123)listinsert( &mylist1 , i , temp); / 順序表一賦值 temp; i+;printf(n 輸入集合 2！: );i = 0;while( (temp=getchar() ) != n)if(96temp & temp123)listinsert( &mylist2 , i , temp); i+;printf(n collection one: )

29、;for(i=0; imylist1.size; i+)printf(%c , mylist1.listi);printf(nn);printf( collection two: );for(i=0; imylist2.size; i+)printf(%c , mylist2.listi);/ 順序表一賦值 temp;.printf(nn);/調用各個函數(shù)printf(n 請選擇功能:!n);printf(n%s%sn, equal , equal);printf( the number 1 is : 并集.n);printf( the number 2 is : 交集.n);printf(

30、the number 3 is : 差集.n);printf(%s%sn, equal , equal);while(1)int choice;printf(n 請輸入您的選擇?。?n (others exit the programe!): ); scanf(%d , &choice);switch(choice)case 1 : unionset( mylist1 , mylist2); break;case 2 : mixedset(mylist1 , mylist2); break;case 3 : diffentset(mylist1 , mylist2); break;default : exit(0);4 測試.4.1 最終結果（基于單鏈表）圖 4.1 結果展示4.2 最終結果（基于順序表）圖 4.2 結