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

1、編號(hào)： 730 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說明書集合的交并差運(yùn)算 學(xué)院： 海洋信息工程學(xué)院 專 業(yè)： 網(wǎng)絡(luò)工程 學(xué)生姓名： xx 學(xué) 號(hào)： xx 指導(dǎo)教師： xx 2017年 12 月 21 日目錄目錄2概述3程序說明31 實(shí)驗(yàn)內(nèi)容41.1實(shí)驗(yàn)?zāi)康?1.2實(shí)驗(yàn)任務(wù)41.3要求42數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及流程圖52.1抽象數(shù)據(jù)結(jié)構(gòu)類型定義52.2本程序包含四個(gè)模塊73測(cè)試數(shù)據(jù)83.1源程序83.2測(cè)試數(shù)據(jù)及程序運(yùn)行情況144總結(jié)15參考文獻(xiàn)15概述本演示程序的編寫，主要運(yùn)用的我們學(xué)的第二章線性表中的知識(shí)。線性結(jié)構(gòu)的特點(diǎn)是：在數(shù)據(jù)元素的非空有限集中，（1）存在唯一的一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素；（2）存在唯一

2、的一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素；（3）除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；（4）除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。本程序需要兩個(gè)抽象數(shù)據(jù)類型：有序表和集合。而且采用了單鏈表來實(shí)現(xiàn)。一、程序說明本程序主要利用單鏈表及函數(shù)，實(shí)現(xiàn)集合的交集、并集和差集運(yùn)算。運(yùn)行程序說明：菜單執(zhí)行的命令包括<0-7>：<1>“請(qǐng)輸入A集合的個(gè)數(shù)與A集合元素”<2>“請(qǐng)輸入B集合個(gè)數(shù)與B集合的元素”<3>“A集合的有序集合”<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<

3、;7>“AB集合的差集”<0>“退出”注：展示程序中，集合元素限定為小寫字母數(shù)據(jù)，以“回車鍵”束標(biāo)志。1、 實(shí)驗(yàn)內(nèi)容1.1實(shí)驗(yàn)?zāi)康模涸O(shè)計(jì)一個(gè)演示集合的交、并、差的運(yùn)算程序1.2實(shí)驗(yàn)任務(wù)1） 使用單鏈表來表示集合，完成集合的交集、并集、差等操作。2） 采用鏈表等數(shù)據(jù)結(jié)構(gòu)。3） 集合的元素限定為數(shù)字和小寫的英文字母1.3實(shí)驗(yàn)要求：1. 初步完成總體設(shè)計(jì)，建立頭文件，確定函數(shù)個(gè)數(shù)。2. 完成以下條件:1) 界面清楚，函數(shù)功能劃分好2) 總體設(shè)計(jì)應(yīng)畫流程圖3) 程序要加必要的注釋4) 提供測(cè)試方案注：程序多次測(cè)試，彌補(bǔ)漏洞。要求：1） 展示程序中，集合元素限定為小寫字母數(shù)據(jù)。集合輸入

4、的形式為一以“回車鍵”束標(biāo)志。2）展示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在程序輸出顯示“提示信息”之后，然后再輸入命令；相應(yīng)的輸入數(shù)據(jù)和運(yùn)算結(jié)果顯示在其后。3）程序執(zhí)行的命令包括<0-7>：<1>“請(qǐng)輸入A集合的個(gè)數(shù)與A集合元素”<2>“請(qǐng)輸入B集合個(gè)數(shù)與B集合的元素”<3>“A集合的有序集合”<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<7>“AB集合的差集”<0>“退出”程序功能：計(jì)算兩個(gè)的集合的交、并、差以及重新輸入集合功能。一、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及流程圖

5、實(shí)現(xiàn)功能： 集合的交 集合的并為了實(shí)現(xiàn)上述程序的功能，應(yīng)以有序單鏈表表示集合。為此，需要抽象數(shù)據(jù)類型：有序表和集合2.1數(shù)據(jù)類型定義1、/線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedef struct LNode ElemType data; struct LNode *next; LinkList;1、 實(shí)現(xiàn)輸出功能的函數(shù)void DispList()/輸出函數(shù)2、 輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表Lvoid CreateList_L1(LinkList *&L,int n)4、實(shí)現(xiàn)集合元素由小到大排序功能void sort(LinkList *&L)5、實(shí)現(xiàn)了將A、B集合的

6、并集，并放到新的單鏈表C中void Union(LinkList *ha,LinkList*hb,LinkList*&hc)6、實(shí)現(xiàn)了將A、B集合的交集，并放到新的單鏈表C中void InterSect(LinkList *ha,LinkList*hb,LinkList*&hc)7、實(shí)現(xiàn)了將A、B集合的差集，并放到新的單鏈表C中void Subs(LinkList *ha,LinkList*hb,LinkList*&hc)8、銷毀表Lvoid DestroyList(LinkList *&L)3、 主程序模塊（）初始化；定義變量；While（）選擇菜單Switc

7、h（）case1：case2:case3：Return 0； 2.2本程序包含四個(gè)模塊1）主菜單模塊2）輸入集合單元模塊：運(yùn)用單鏈表輸入；3）集合運(yùn)算單元模塊：實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型；4）有序表單元模塊：實(shí)現(xiàn)有序表的抽象數(shù)據(jù)類型；模塊關(guān)系： 3.1測(cè)試數(shù)據(jù)：集合A=dop，B=dli，運(yùn)算其交集、并集、差集。3.2源程序：源程序代碼如下：#include <iostream>#include<stdio.h>#include<malloc.h>#include<cstdio>using namespace std;typedef char Ele

8、mType;typedef struct LNodeElemType data; struct LNode *next; LinkList;void DispList(LinkList*L)/輸出函數(shù)LinkList *p=L->next; while(p!=NULL) printf("%c ",p->data); p=p->next; printf("n");void CreateList_L1(LinkList *&L,int n) /輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L LinkList *p,*q; L=(Li

9、nkList*)malloc(sizeof(LinkList); L->next=NULL; q=L; for(int i=n;i>0;-i) p=(LinkList*)malloc(sizeof(LinkList);/生成新結(jié)點(diǎn) cin>>p->data;/輸入元素值 p->next=NULL; q->next=p;/插入到表尾 q=p; void DestroyList(LinkList *&L)LinkList*p=L->next,*pre=L; while(p!=NULL) free(pre); pre=p; p=pre->

10、next; free(pre);void sort(LinkList *&L) /從小到大排序LinkList *pre,*p,*q; p=L->next->next; L->next->next=NULL; while(p!=NULL) q=p->next; pre=L; while(pre->next!=NULL&&pre->next->data<p->data) pre=pre->next; p->next=pre->next; pre->next=p; p=q; void Uni

11、on(LinkList *ha,LinkList*hb,LinkList*&hc) /求集合的并LinkList *pa=ha->next,*pb=hb->next,*pc,*s; hc=(LinkList*)malloc(sizeof(LinkList); pc=hc; while(pa!=NULL &&pb!=NULL ) if(pa->data<pb->data) s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=

12、pa->next; else if(pa->data>pb->data) s=(LinkList*)malloc(sizeof(LinkList); s->data=pb->data; pc->next=s; pc=s; pb=pb->next; else s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=pa->next; pb=pb->next; if(pb!=NULL) pa=pb; while(pa!=NU

13、LL) s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=pa->next; pc->next=NULL;void InterSect(LinkList *ha,LinkList*hb,LinkList*&hc)/求兩個(gè)有序集合的交用尾插法LinkList *pa=ha->next,*pb,*pc,*s; hc=(LinkList*)malloc(sizeof(LinkList); pc=hc; while(pa!=NULL) pb=hb->

14、next; while(pb!=NULL&&pb->data<pa->data) pb=pb->next;if(pb!=NULL &&pb->data=pa->data)/B節(jié)點(diǎn)在A節(jié)點(diǎn)中復(fù)制A節(jié)點(diǎn) s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=pa->next; pc->next=NULL;void Subs(LinkList *ha,LinkList*hb,LinkList*&h

15、c) /求兩個(gè)有序集合的差 LinkList *pa=ha->next,*pb,*pc,*s; hc=(LinkList*)malloc(sizeof(LinkList); pc=hc; while(pa!=NULL) pb=hb->next; while(pb!=NULL&&pb->data<pa->data) pb=pb->next;if(!(pb!=NULL &&pb->data=pa->data)/B節(jié)點(diǎn)不在A節(jié)點(diǎn)中復(fù)制A節(jié)點(diǎn) s=(LinkList*)malloc(sizeof(LinkList); s-

16、>data=pa->data; pc->next=s; pc=s; pa=pa->next; pc->next=NULL;int main()LinkList *ha,*hb,*hc; int n,k; while(1) cout<<"ntt 集合的簡(jiǎn)單運(yùn)算nn" cout<<"ttt 菜單 n" cout<<"ttt n"cout<<"ttt 1. 請(qǐng)輸入A集合個(gè)數(shù)與A集合的元素 n"cout<<"ttt 2. 請(qǐng)

17、輸入B集合個(gè)數(shù)與B集合的元素 n" cout<<"ttt 3. A集合的有序集合 n" cout<<"ttt 4. B集合的有序集合 n" cout<<"ttt 5. AB集合的并集 n" cout<<"ttt 6. AB集合的交集 n" cout<<"ttt 7. AB集合的差集 n" cout<<"ttt 0. 退出 n" cout<<"ttt n" cout

18、<<"ttt 請(qǐng)選擇(0-7):" cin>>k; switch(k) case 1: cout<<"請(qǐng)輸入A集合的個(gè)數(shù)與A集合元素："cin>>n; CreateList_L1(ha,n);break;case 2:cout<<"請(qǐng)輸入B集合的個(gè)數(shù)與B集合元"cin>>n;CreateList_L1(hb,n); break;case 3:sort(ha);cout<<"n A的有序集合為："DispList(ha);break;

19、case 4:sort(hb);cout<<"n B的有序集合為："DispList(hb);break;case 5:Union(ha,hb,hc);cout<<"n AB集合的并集為："DispList(hc);break;case 6:InterSect(ha,hb,hc);cout<<"n AB集合的交集為：" DispList(hc);break;case 7:Subs(ha,hb,hc);cout<<"n AB集合的差集為："DispList(hc);break;case 0: cout<<"nttt- 謝謝使用！-n"cout<<"nttt按任意鍵退出.n" return 0; / switch /while DestroyList(ha); DestroyList(hb); DestroyList(hc); return 0;3.3測(cè)試數(shù)據(jù)及運(yùn)行情況(1) 選擇功能<0-7>(2) 輸入A集合的個(gè)數(shù)與A集合的元素dop(3) 輸入