數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--集合的并、交和差運(yùn)算.doc

合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20122013學(xué)年第二學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱集合的并、交和差運(yùn)算學(xué)生姓名張文浩 學(xué)號(hào)1104032028專業(yè)班級(jí)11網(wǎng)工2班指導(dǎo)教師何立新 華珊珊2013年 6月題目： 集合的并、交和差運(yùn)算【問題描述】編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序?！净疽蟆?1) 集合的元素限定為小寫字母字符 a.z 。(2) 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行?！緶y試數(shù)據(jù)】(1)Set1=magazine，Set2=paper，Set1Set2=aegimnprz，Setl Set2=ae，Set1-Set2=gimnz。(2)Set1= 012oper4a6tion89，Set2=error data，Set1Set2=adeinoprt，Setl Set2=aeort，Set1-Set2=inp?！緦?shí)現(xiàn)提示】以有序鏈表表示集合?！具x作內(nèi)容】(1) 集合的元素判定和子集判定運(yùn)算。(2) 求集合的補(bǔ)集。(3) 集合的混合運(yùn)算表達(dá)式求值。(4) 集合的元素類型推廣到其他類型 ， 甚至任意類型。一、 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)題目：編制一個(gè)演示集合的并、交和差運(yùn)算的程序。需求分析：1、 本演示程序中，集合的元素限定為小寫字母字符“a”z”。集合輸入的形式為一個(gè)以“回車符“為結(jié)束標(biāo)志的字符串，串中字符順序不限。2、 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息“之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令；相應(yīng)的輸入數(shù)據(jù)和運(yùn)算結(jié)果顯示在其后。3、 程序執(zhí)行的命令包括：1） 構(gòu)造集合1；2）構(gòu)造在集合2；3）求并集；4）求交集；5)求差集；6）返回；7）結(jié)束?！皹?gòu)造集合1”和“構(gòu)造集合2”時(shí)，需以字符的形式鍵入集合元素。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)為了實(shí)現(xiàn)上述程序的功能，應(yīng)以有序鏈表表示集合。為此，需要兩個(gè)抽象數(shù)據(jù)類型：有序表和集合。1、有序表的抽象數(shù)據(jù)類型定義為：readdata(pointer head)初始條件：head是以head為頭節(jié)點(diǎn)的空鏈表。操作結(jié)果：生成以head為頭節(jié)點(diǎn)的非空鏈表。pop(pointer head)初始條件：head是以head為頭節(jié)點(diǎn)的非空鏈表。操作結(jié)果：將以head為頭節(jié)點(diǎn)的鏈表中數(shù)據(jù)逐個(gè)輸出。2、集合的抽象數(shù)據(jù)類型定義為：and(pointer head1,pointer head2,pointer head3)初始條件：鏈表head1、head2、head3已存在操作結(jié)果：生成一個(gè)由head1和head2的并集構(gòu)成的集合head3。or(pointer head1,pointer head2,pointer head3)初始條件：鏈表head1、head2、head3已存在操作結(jié)果：生成一個(gè)由head1和head2的交集構(gòu)成的集合head3。differ(pointer head1,pointer head2,pointer head3)初始條件：鏈表head1、head2、head3已存在操作結(jié)果：生成一個(gè)由head1和head2的差集構(gòu)成的集合head3。3、本程序抱含四個(gè)模塊：1） 節(jié)點(diǎn)結(jié)構(gòu)單元模塊定義有序表的節(jié)點(diǎn)結(jié)構(gòu)；2） 有序表單元模塊實(shí)現(xiàn)有序表的抽象數(shù)據(jù)類型；3） 集合單元模塊實(shí)現(xiàn)集合獲得抽象數(shù)據(jù)類型；4）主程序模塊：Void main（）初始化；do接受命令；處理命令；while（“命令”!=“退出”）；三、算法設(shè)計(jì)#include#includetypedef struct LNode/定義結(jié)構(gòu)體類型指針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-data=tmp;p-next=head-next;head-next=p;scanf(%c,&tmp);void pop(pointer head)/定義輸出集合函數(shù)pointer p;p=head-next;while(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) p3=(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)p1=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;while(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;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ù)據(jù),按回車鍵結(jié)束,第一個(gè)集合大于第二個(gè)集合)n);pointer head1,head2,head3;head1=(pointer)malloc(sizeof(struct LNode);head1-next=NULL;head2=(pointer)malloc(sizeof(struct LNode);head2-next=NULL;head3=(pointer)malloc(sizeof(struct LNode);head3-next=NULL;printf(請輸入集合1：n);readdata(head1);/調(diào)用輸入集合函數(shù)printf(請輸入集合2：n);readdata(head2);/調(diào)用輸入集合函數(shù)A:printf(1.并集 2.交集 3.差集 4.結(jié)束 x.重新運(yùn)算n); doprintf(請選擇序號(hào)n);scanf(%d,&x);switch(x)case 1:printf(兩集合的并是n);and(head1,head2,head3);/調(diào)用并集函數(shù)pop(head3);head3-next=NULL;break;case 2:printf(兩集合的交是n);or(head1,head2,head3);/調(diào)用交集函數(shù)pop(head3);head3-next=NULL;break;case 3: printf(兩集合的差是n);differ(head1,head2,head3);/調(diào)用差集函數(shù)pop(head3);head3-next=NULL;break; case 4:break;default:goto A;while(x!=4);四、測試數(shù)據(jù)及程序運(yùn)行情況 運(yùn)行時(shí)提示輸入：輸入集合1：asd輸入集合2：asf根據(jù)提示輸入運(yùn)算類型：1.并集 2.交集 3.差集 4.結(jié)束 x.重新運(yùn)算 輸入1，輸出”fasd”輸入2，輸出”as”輸入3，輸出”d”輸入4，輸出”press any key to continue”(結(jié)束)輸入其他數(shù)，輸出” 1.并集 2.交集 3.差集 4.結(jié)束 x.重新運(yùn)算”(重新選擇運(yùn)算類型)下面是運(yùn)行時(shí)的界面(附圖):五、參考資料1 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國鐵道出版社，2006年5月。2 陳朔