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

1、課程設(shè)計(jì)報(bào)告課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)課題名稱(chēng)集合的并、交和差運(yùn)算專(zhuān) 業(yè)班級(jí)通信1101學(xué) 號(hào)201103020127姓名皮鋒指導(dǎo)教師張鏖烽田娟秀李杰君2013年6月29日湖南工程學(xué)院課程設(shè)計(jì)任務(wù)書(shū)課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu)課 題集合的并、交和差運(yùn)算專(zhuān)業(yè)班級(jí) 通信1101學(xué)生姓名 皮鋒學(xué) 號(hào) 201103020127指導(dǎo)老師 張塵烽田娟秀李杰君審 批任務(wù)書(shū)下達(dá)日期2013年6月23 日任務(wù)完成日期 2013年6月29 日目錄1. 需求分析11.1. 問(wèn)題描述11.2. 基本要求11.3. 測(cè)試數(shù)據(jù)114實(shí)現(xiàn)提示12. 概要設(shè)計(jì)12.1. 有序表的抽象數(shù)據(jù)類(lèi)型定義為 12.2. 集合的定義為12.3. 基本操作2

2、2.4. 調(diào)用關(guān)系 23. 詳細(xì)設(shè)計(jì)43.1. 具體算法流程43.2. 具體的程序功能實(shí)現(xiàn)43.3. 偽碼算法54. 調(diào)試分析94.1. 調(diào)試過(guò)程中遇到的問(wèn)題 94.2. 算法的時(shí)空分析95. 用戶(hù)使用說(shuō)明106. 測(cè)試結(jié)果116.1. 做完一次運(yùn)算后按回車(chē)鍵繼續(xù)下一次運(yùn)算 116.2. 做完運(yùn)算后輸入字母“ e”退出運(yùn)算 127. 總結(jié)128. 附錄138.1. 程序源代碼13集合的并、交和差運(yùn)算1. 需求分析1.1. 問(wèn)題描述編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序。1.2. 基本要求(1) 集合的元素限定為小寫(xiě)字母字符 a. z 。(2) 演示程序以用戶(hù)和計(jì)算機(jī)的對(duì)話(huà)方式執(zhí)行。1.3

3、. 測(cè)試數(shù)據(jù)(1)Set1=magazine， Set2=paper，SetlU Set2=aegimnprz, Setl A Set2=ae, Set1-Set2=gimnz。(2)Set1= 012oper4a6tion89， Set2=error data，SetlU Set2=adeinoprt, Setl A Set2=aeort, Set1-Set2=inp。1.4. 實(shí)現(xiàn)提示以有序鏈表表示集合。2. 概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能,應(yīng)以有序鏈表表示集合。為此,需要兩個(gè)抽象數(shù)據(jù)類(lèi)型：有序表和集合。2.1. 有序表的抽象數(shù)據(jù)類(lèi)型定義為typedef struct LNodechar da

4、ta;struct LNode *next;LinkList;2.2. 集合的定義為char set1maxsize,set2maxsize;2.3. 基本操作void GreatListR(LinkList *&L,char a,int n) / 尾插法建表void InitList(LinkList *&L) /初始化線(xiàn)性表void DestroyList(LinkList *&L) /銷(xiāo)毀線(xiàn)性表void DispList(LinkList *L) /輸出線(xiàn)性表void sort(LinkList *&L) /元素排序void bingji(LinkList *L,LinkList *N,

5、LinkList *&M)/并集運(yùn)算void dels(LinkList *&M)/刪除相同元素 僅留一個(gè)void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集運(yùn)算void chayunsuan(LinkList *L,LinkList *M,LinkList *&K) /集合差運(yùn)算 int main() /為設(shè)計(jì)程序主頁(yè)面的函數(shù)，并且使用了所有的函數(shù)2.4. 調(diào)用關(guān)系InitList(L);InitList(N);GreatListR(L,set1,i);GreatListR(U,set1,i);sort(U); / 元素排序dels(U);

6、/刪除相同元素 僅留一個(gè)sort(L); / 元素排序dels(L);/刪除相同元素 僅留一個(gè)printf( 請(qǐng)輸入集合 set2=);for(j=0;jmaxsize;j+)scanf(%c,&set2j);if(set2j=n)break;GreatListR(N,set2,j);sort(N); /元素排序dels(N);/刪除相同元素 僅留一個(gè)bingji(L,N,M); /集合合并 dels(M);/刪除相同元素 僅留一個(gè)DispList(M);jiaoji(M,L,N); /交集運(yùn)算DispList(M);chayunsuan(U,M,K); /集合差運(yùn)算DispList(K);c

7、har n;printf(n 是否退出運(yùn)算？ n); scanf(%c,&n);if(n=e)exit(0);DestroyList(L);DestroyList(N);DestroyList(U);DestroyList(M);DestroyList(K);system(PAUSE);3. 詳細(xì)設(shè)計(jì)3.1.具體算法流程圖3-1具體算法流程32具體的程序功能實(shí)現(xiàn)(1) 利用C+引用類(lèi)型，對(duì)線(xiàn)性表LinkList *L,*N進(jìn)行初始化，并用for循環(huán)將將集合set1maxsize,set2maxsize分別存入線(xiàn)性表L和 K。(2) 用 sort()函數(shù)對(duì)兩個(gè)線(xiàn)性表里的元素進(jìn)行排序，得到兩個(gè)有序

8、表。(3) 用 dels()函數(shù)分別刪除兩個(gè)有序表里相同元素，僅留一個(gè)。(4) 用函數(shù)bingji(L,N,M)合并兩個(gè)有序表，得到有序表M，并再次調(diào)用函數(shù)dels(M) 刪除有序表里相同的元素，僅留下一個(gè)，從而得到集合的并集。(5) 調(diào)用函數(shù) jiaoji(M,L,N) ，進(jìn)行交集運(yùn)算，從而得到一個(gè)新的有序表 M ，存著 兩個(gè)集合的交集。(6) 利用交集運(yùn)算得到的結(jié)果 M 進(jìn)行集合差運(yùn)算， 調(diào)用函數(shù) chayunsuan(U,M,K)， 得到兩個(gè)集合差集為有序表 K 。(7) 調(diào)用函數(shù) DispList() 輸出并集，交集和差集的結(jié)果。(8) 用代碼char n;printf(n 是否退出運(yùn)

9、算？ n); scanf(%c,&n);if(n=e) exit(0);判斷是否進(jìn)行下一次運(yùn)輸，如果進(jìn)行下一次運(yùn)算按回車(chē)鍵繼續(xù)，否則輸入字母“ e”退出運(yùn)算。(9) 最后利用函數(shù) DestroyList() 銷(xiāo)毀所有線(xiàn)性表。(10) 加上頭文件 #include 和語(yǔ)句 system(color B5) 對(duì)界面進(jìn)行顏色 設(shè)置，得到自己喜歡的顏色。3.3. 偽碼算法(1) 并集運(yùn)算void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集運(yùn)算LinkList *pa=L-next,*pb=N-next,*r,*s; /時(shí)歸并算法 M=(LinkLis

10、t *)malloc(sizeof(LinkList);r=M; while(pa!=NULL&pb!=NULL)/集合合并 if(pa-datadata) s=(LinkList *)malloc(sizeof(LinkList); s-data=pa-data;r-next=s;r=s; pa=pa-next;elses=(LinkList *)malloc(sizeof(LinkList); s-data=pb-data;r-next=s;r=s;pb=pb-next;while(pa!=NULL)s=(LinkList *)malloc(sizeof(LinkList); s-data

11、=pa-data; r-next=s;r=s; pa=pa-next;while(pb!=NULL)s=(LinkList *)malloc(sizeof(LinkList); s-data=pb-data; r-next=s;r=s; pb=pb-next;r-next=NULL;printf(兩個(gè)集合的并集為setlU set2:);void dels(LinkList *&M)/刪除相同元素僅留一個(gè)LinkList *p=M-next,*q; while(p-next!=NULL) if(p-data=p-next-data)q=p-next;p-next=q-next;free(q);

12、elsep=p-next;(2) 交集運(yùn)算void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集運(yùn)算LinkList *pa=L-next,*pb=N-next,*q,*r; / 以單鏈表 M 的頭節(jié)點(diǎn)創(chuàng)建一個(gè)空單鏈 表M-next=NULL;r=M;/r 指向這個(gè)新鏈表的最后一個(gè)節(jié)點(diǎn)while(pa!=NULL)/以 pa 掃描單鏈表 M 的數(shù)據(jù)節(jié)點(diǎn)，判斷是否 在單鏈表 L 和 N 中while(pb!=NULL&pa-datapb-data)pb=pb-next;if(pa!=NULL&pb!=NULL&pa-data=pb-data)r-

13、next=pa;r=pa;pa=pa-next;elseq=pa;pa=pa-next;free(q);r-next=NULL;printf(兩個(gè)集合的交集為setm set2=);(3) 差集運(yùn)算/集合差運(yùn)算void chayunsuan(LinkList *L,LinkList *M,LinkList *&K) LinkList *p1=L-next,*p2=M-next,*s,*r;K=(LinkList *)malloc(sizeof(LinkList);r=K;r-next=NULL;while(p1!=NULL)p2=M-next;while(p2!=NULL&p2-data!=p

14、1-data)p2=p2-next;if(p2=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=p1-data;r-next=s;r=s; p1=p1-next; r-next=NULL;printf( 兩個(gè)集合的差集為 set1 - set2=);4. 調(diào)試分析4.1. 調(diào)試過(guò)程中遇到的問(wèn)題(1) 由于對(duì)集合的三種運(yùn)算的算法推敲不足，在有序鏈表類(lèi)型的早期版本未設(shè)置尾指針操作，導(dǎo)致算法低效。(2) 由于首先沒(méi)設(shè)置數(shù)組最大值，導(dǎo)致數(shù)組不能正確輸入，后來(lái)定義了#defi nemaxsize 100才解決這個(gè)問(wèn)題。(3) 在子函數(shù)中線(xiàn)性表的創(chuàng)建不正

15、確，導(dǎo)致在輸入數(shù)組后不能正確執(zhí)行，出現(xiàn)下 圖結(jié)果，經(jīng)過(guò)多次調(diào)試才得到正確結(jié)果。數(shù)據(jù)結(jié)構(gòu)心已停止工作出現(xiàn)了一H可題導(dǎo)孜程序停止正常工作如果有可用的解塊方寶” Windows將關(guān)遠(yuǎn)程序并通和怒”I關(guān)勰(4) 在進(jìn)行差運(yùn)算的算法設(shè)計(jì)時(shí)出現(xiàn)邏輯上的錯(cuò)誤，導(dǎo)致結(jié)果不正確，集合的首 元素未能正確參與運(yùn)算。進(jìn)過(guò)仔細(xì)的推敲才發(fā)現(xiàn)沒(méi)有創(chuàng)建一個(gè)空的頭結(jié)點(diǎn)就直 接把pa=pa-next,使第一個(gè)數(shù)據(jù)元素未參加運(yùn)算。(5) 程序首先只能進(jìn)行一次運(yùn)算就退出了，不能人性化的進(jìn)行多次運(yùn)算，后來(lái)在主函數(shù)中加入for語(yǔ)句，進(jìn)行循環(huán)，才能進(jìn)行多次運(yùn)算，并在for語(yǔ)句里加入if條件語(yǔ)句，進(jìn)行是否進(jìn)行下一次運(yùn)算的判斷，使程序更加優(yōu)化

16、。(6) 首先把刪除相同元素的算法寫(xiě)在交集，并集和差集的算法運(yùn)算里面，使程序 代碼冗長(zhǎng)，后來(lái)為了使代碼更加簡(jiǎn)潔，就另外單獨(dú)寫(xiě)了一個(gè)刪除相同元素的算 法，只要在各個(gè)運(yùn)算中調(diào)用即可。4.2.算法的時(shí)空分析(1)void GreatListR(LinkList *&L,char a,int n)/尾插法建表本算法的時(shí)間復(fù)雜度為0(n)，其中n為單鏈表中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)/初始化線(xiàn)性表(2)void In itList(L in kList *&L)本算法的時(shí)間復(fù)雜度為0(1)。(3) void DestroyList(L in kList *&L)(4) void DispList(LinkList *

17、L)/輸出線(xiàn)性表本算法的時(shí)間復(fù)雜度為0(n),其中n為單鏈表中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)。(6) void sort(LinkList *&L)/元素排序本算法的時(shí)間復(fù)雜度為0(n),其中n為單鏈表中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)。(7) void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集運(yùn)算本算法的時(shí)間復(fù)雜度為 0(ListLength(L)+ListLength(N) 。(8) void dels(LinkList *&M)/刪除相同元素僅留一個(gè)本算法的時(shí)間復(fù)雜度為0(n),其中n為單鏈表中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)。(9) void jiaoji(LinkList *&M,

18、LinkList *L,LinkList *N)/交集運(yùn)算本算法的時(shí)間復(fù)雜度為 0(m+n+p)。(10) void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差運(yùn)算本算法的時(shí)間復(fù)雜度為0(n*n),其中n為單鏈表中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)。5. 用戶(hù)使用說(shuō)明用戶(hù)在使用時(shí)首先輸入要進(jìn)行運(yùn)算的兩個(gè)集合,然后按回車(chē)鍵則會(huì)出現(xiàn)運(yùn)算結(jié)果。只能進(jìn)行小寫(xiě)字母a到z的運(yùn)算，如果輸入其他以外的數(shù)字、字母或字符，則 不會(huì)在運(yùn)算結(jié)果中顯示！若用戶(hù)需要在進(jìn)行下一次運(yùn)算,則按回車(chē)鍵繼續(xù),否則按 字母“e”退出計(jì)算！6. 測(cè)試結(jié)果6.1. 做完一次運(yùn)算后按回車(chē)鍵繼續(xù)下一

19、次運(yùn)算* C:Ui erspifen aXDesktc 譙設(shè)D tbu g裁看結(jié)構(gòu)心姑i*集合的井、交和差運(yùn)算運(yùn)請(qǐng)請(qǐng)兩兩兩範(fàn) V 退岀碼算，否則按回車(chē)鍵繼續(xù)下次運(yùn)算! 卑 口 ?etl =iriaa?inepset2=paper口的并集:為 wet丄 |Jset2 :aesfiimpis 合卸交塞為冷曲Pset2=ae 合的差集- set2=gimnH否退岀運(yùn)算?6 a4aatr d=01=e為為為 tltaw* ? se沾幵交差算 合厶ng的運(yùn) 口合合- 入入退-否 請(qǐng)住渦專(zhuān)是令Et 1 Uet2 ：ade inoprt setl| | set 2-aeort=sert 2sinp合 wet

20、l =45 0y 9 5 j Ji4004t -, c3 鈿 v食 et2 =439348tjyghjg04gjj 的并集為思Etl Uset2 zcsflijmtuv臺(tái)的交nset2=hjty 合的差集為砂M - setZ-cmu合& etl =546u?6h5&h7& piset2 =45 t56t/gerf 54g，的并集為SE七1 U set2 : ef g|hiuy 的交集為航1 A set2 =-et2chu是否退出運(yùn)算?是否退岀運(yùn)算?疋Kiff 梵K豪蟲(chóng)箕梵11梵KiWaiEJMaf WX梵KWlifiM Milffitlf*HUEIfiM Miwraif回圖6-1運(yùn)算完一次進(jìn)行

21、第二次運(yùn)算*C：U se rsp ifengDes kto pY気殺 Debu g 謚!虜結(jié)構(gòu) exeaam沅入入MW請(qǐng)請(qǐng)兩兩兩請(qǐng)請(qǐng)兩藺兩運(yùn)請(qǐng)請(qǐng)兩兩兩“J退岀運(yùn)算，否則按回車(chē)鍵繼續(xù)下次運(yùn)算1|QSetl=2131453f45vJef349hfw9eh34a Ipset2=4f319f340j40適井 Sj)setlUset2：efahjwJ的交塞JSCtl Aset2=f j亍的差集為呂航1 - setasjhw|1藁菩的差集為歸“圖6-2進(jìn)行多次運(yùn)算62做元運(yùn)算后輸入子母“ e退出運(yùn)算完入人果集人合厶畐的CAUse rp ife ngDe? Icto pi；sDe bu g 謐曙制exe退岀

22、運(yùn)算，否則按回車(chē)鍵繼續(xù)下次運(yùn)算!setl=vfei12=w為為為 t2集 se井交差e2setl U set2 - ei*wset 11 |set2 =bvjset 1 set2=i*是否退岀運(yùn)算？ePfess any key to continue圖6-1運(yùn)算完按字母“ e”退出7. 總結(jié)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核 心課程，而且也已經(jīng)成為其他理工專(zhuān)業(yè)的熱門(mén)選修課。隨著高級(jí)語(yǔ)言的發(fā)展， 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)的研究和應(yīng)用中已展現(xiàn)出強(qiáng)大的生命力，它兼顧了諸多高級(jí) 語(yǔ)言的特點(diǎn)，是一種典型的結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言，它處理能力強(qiáng)，使用靈活方 便，應(yīng)用面廣，具有良好的可移植

23、性。數(shù)據(jù)結(jié)構(gòu)課設(shè)使我們鞏固了以前的知識(shí)并在此基礎(chǔ)上還對(duì)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和算法有了更深的了解，使我們?cè)谶@門(mén)課程 的實(shí)際應(yīng)用上也有了一個(gè)提高。首先這兩周的學(xué)習(xí)，使我們?cè)陟柟塘嗽械睦碚撝R(shí)上，又培養(yǎng)了靈活運(yùn)用和組合集成所學(xué)過(guò)知識(shí)及技能來(lái)分析、解決實(shí)際 問(wèn)題的能力，使我們體會(huì)到自身知識(shí)和能力在實(shí)際中的應(yīng)用和發(fā)揮。其次，它 激發(fā)了我們創(chuàng)新意識(shí)，開(kāi)發(fā)創(chuàng)造的能力和培養(yǎng)溝通能力。另外，讓我們進(jìn)一步 熟悉了數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)應(yīng)用。每一處編碼都是在反復(fù)的熟悉數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)特 性，及其語(yǔ)法、函數(shù)和程序設(shè)計(jì)思想的過(guò)程，對(duì)我們數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和提高很有益處，并且使我們明白了程序設(shè)計(jì)過(guò)程，如解決一些實(shí)際問(wèn)題，從解決實(shí)際 問(wèn)題的

24、角度。 課程設(shè)計(jì)讓我們受益匪淺。我們深深認(rèn)識(shí)到，要學(xué)好一門(mén)學(xué)科， 沒(méi)有刻苦鉆研的精神是不行的，只有在不斷的嘗試中，經(jīng)歷失敗，從失敗中總結(jié)經(jīng)驗(yàn)，然后再不斷的嘗試，才能獲得成功。8. 附錄8.1. 程序源代碼#include#include using namespace std;#define maxsize 100typedef struct LNodechar data;struct LNode *next;LinkList;/尾插法建表/創(chuàng)建頭節(jié)點(diǎn)void GreatListR(LinkList *&L,char a,int n)LinkList *s,*r;int i;L=(LinkLi

25、st *)malloc(sizeof(LinkList); r=L;for(i=0;idata=ai;r-next=s;r=s; r-next=NULL;void InitList(LinkList *&L)/初始化線(xiàn)性表L=(LinkList *)malloc(sizeof(LinkList); L-next=NULL;void DestroyList(LinkList *&L)LinkList *pre=L,*p=L-next; while(p!=NULL) free(pre); pre=p; p=pre-next;free(pre);void DispList(LinkList *L)/

26、輸出線(xiàn)性表LinkList *p=L-next; while(p!=NULL) if(p-data=a)&(p-datadata); p=p-next;printf(n);void sort(LinkList *&L) /元素排序LinkList *p,*pre,*q;p=L-next-next; /p 指向 L 的第 2 個(gè)數(shù)據(jù)節(jié)點(diǎn)L-next-next=NULL;/構(gòu)件只含一個(gè)數(shù)據(jù)節(jié)點(diǎn)的有序表while(p!=NULL)q=p-next;while(p!=NULL)q=p-next; /q 保存 *p 節(jié)點(diǎn)沒(méi)后繼節(jié)點(diǎn)的指針 pre=L;從有序表開(kāi)頭進(jìn)行比較，pre指向插入*p的前驅(qū)節(jié)點(diǎn)wh

27、ile(pre-next!=NULL&pre-next-datadata) pre=pre-next;p-next=pre-next;pre-next=p;p=q;void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集運(yùn)算LinkList *pa=L-next,*pb=N-next,*r,*s; /時(shí)歸并算法 M=(LinkList *)malloc(sizeof(LinkList);r=M;while(pa!=NULL&pb!=NULL)/集合合并if(pa-datadata) s=(LinkList *)malloc(sizeof(Link

28、List); s-data=pa-data;r-next=s;r=s;pa=pa-next;elses=(LinkList *)malloc(sizeof(LinkList);s-data=pb-data;r-next=s;r=s;pb=pb-next;while(pa!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=pa-data;r-next=s;r=s;pa=pa-next;while(pb!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=pb-data;r-next=s;r=s;

29、pb=pb-next;r-next=NULL;printf(兩個(gè)集合的并集為 setl U set2:);void dels(LinkList *&M)/刪除相同元素僅留一個(gè)LinkList *p=M-next,*q;while(p-next!=NULL)if(p-data=p-next-data)q=p-next;p-next=q-next;free(q);elsep=p-next;void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集運(yùn)算LinkList *pa=L-next,*pb=N-next,*q,*r; / 以單鏈表 M 的頭節(jié)點(diǎn)創(chuàng)

30、建一個(gè)空 單鏈表M-next=NULL;r=M;/r 指向這個(gè)新鏈表的最后一個(gè)節(jié)點(diǎn)while(pa!=NULL)/以 pa 掃描單鏈表 M 的數(shù)據(jù)節(jié)點(diǎn)，判斷是否在單鏈表 L 和 N 中while(pb!=NULL&pa-datapb-data)pb=pb-next; if(pa!=NULL&pb!=NULL&pa-data=pb-data) r-next=pa;r=pa;pa=pa-next;elseq=pa;pa=pa-next;free(q);r-next=NULL;printf(兩個(gè)集合的交集為 setl n set2=);/集合差運(yùn)算void chayunsuan(LinkList *L,LinkList *M,LinkList *&K) LinkList *p1=L-next,*p2=M-next,*s,*r; K=(LinkList *)malloc(sizeof(LinkList); r=K;r-next=NULL; while(p1!=NULL)p2=M-next;while(p2!=NUL