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

1、合肥學(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(cè)試數(shù)據(jù)】(1)Set1="magazine"，Set2="paper"，Set1Set2="aegimnprz"，Setl Se

2、t2="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)

3、內(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ì)

4、為了實(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和

5、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)有序表的抽

6、象數(shù)據(jù)類型；3）  集合單元模塊實(shí)現(xiàn)集合獲得抽象數(shù)據(jù)類型；4）主程序模塊：Void main（）初始化；do接受命令；處理命令；while（“命令”!=“退出”）；三、算法設(shè)計(jì)#include<stdio.h>#include<stdlib.h>typedef struct LNode/定義結(jié)構(gòu)體類型指針char data;struct LNode*next;*pointer;void readdata(pointer head)/定義輸入集合函數(shù)pointer p;char tmp;scanf("%c",&tmp);while(t

7、mp!='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 h

8、ead1,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-&g

9、t;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;

10、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)/定義集合的差集函

11、數(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(&

12、quot;(輸入數(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("請(qǐng)輸入集合1：n");readdata(head1);

13、/調(diào)用輸入集合函數(shù)printf("請(qǐng)輸入集合2：n");readdata(head2);/調(diào)用輸入集合函數(shù)A:printf("1.并集 2.交集 3.差集 4.結(jié)束 x.重新運(yùn)算n"); doprintf("請(qǐng)選擇序號(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(&qu

14、ot;兩集合的交是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);四、測(cè)試數(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)與算法. 北京：中國