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

1、電子與信息工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：集合的運(yùn)算實(shí)驗(yàn)類型：設(shè)計(jì)（驗(yàn)證、設(shè)計(jì)、創(chuàng)新）班級(jí)：2013級(jí)電信三班學(xué)號(hào)：201307014327姓名:陸杰實(shí)驗(yàn)時(shí)間：2015年6月16日指導(dǎo)教師：余先倫成績:目錄一課程設(shè)計(jì)目的和要求二問題描述及分析三算法思想和程序的實(shí)現(xiàn)概述3.1 算法思想3.2 程序的實(shí)現(xiàn)概述四程序流程圖流程圖5 程序的實(shí)現(xiàn)5.1 主函數(shù)5.2 鏈表的生成5.3 集合的輸出5.4 并運(yùn)算函數(shù)5.5 交運(yùn)算函數(shù)5.6 差函數(shù)6 運(yùn)行結(jié)果分析6.1 程序主界面6.2 整數(shù)集合并運(yùn)算6.3 整數(shù)集合交運(yùn)算6.4 整數(shù)集合差運(yùn)算6.5 字母集合并運(yùn)算6.6 字母集合交運(yùn)算6.7 字母集合

2、差運(yùn)算6.8 字母和數(shù)據(jù)集合并運(yùn)算6.9 字母和數(shù)據(jù)集合交運(yùn)算6.10 字母和數(shù)據(jù)集合差運(yùn)算6.11 退出程序7 源代碼8 總結(jié)9 參考文獻(xiàn)課程設(shè)計(jì)目的和要求目的：深入理解數(shù)據(jù)結(jié)構(gòu)的基本理論，掌握數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)方法，掌握基于數(shù)據(jù)結(jié)構(gòu)的各種操作的實(shí)現(xiàn)方法，訓(xùn)練對(duì)基礎(chǔ)知識(shí)和基本方法的綜合運(yùn)用能力，增強(qiáng)對(duì)算法的理解能力，提高軟件設(shè)計(jì)能力。在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。要求：熟練運(yùn)用C+語言、基本數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)知識(shí)，獨(dú)立編制一個(gè)具有中等難度的、解決實(shí)際應(yīng)用問題的應(yīng)用程序。通過題意分析、選擇數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)、編制程序、調(diào)試程序、軟件測(cè)試、結(jié)果分析、撰寫課程設(shè)計(jì)報(bào)告等環(huán)節(jié)完成

3、軟件設(shè)計(jì)的全過程，不斷地完善程序以提高程序的性能。問題描述及分析問題描述：本課程設(shè)計(jì)中，集合的元素可以是字母a,b,W，也可以是整數(shù)0,1,9,集合的大小集合輸入的形式為一個(gè)以“回車符”為結(jié)束標(biāo)志的字符，允許出現(xiàn)重復(fù)字符或非法字符，程序應(yīng)能自動(dòng)濾去。輸出的運(yùn)算結(jié)果字符串中將不含重復(fù)字符或非法字符。問題描述：有兩個(gè)集合AB,要求它的交集、并集和差集C。用兩個(gè)鏈表p、q存儲(chǔ)集合A、B,用鏈表r存儲(chǔ)集合C描述該問題的存儲(chǔ)結(jié)構(gòu)，算法，并通過編寫程序來實(shí)現(xiàn)。問題分析：1. 定義一個(gè)鏈表來存儲(chǔ)集合元素；2. 鏈表L包括數(shù)據(jù)域和指針域，數(shù)據(jù)域中存儲(chǔ)集合元素，指針域中存儲(chǔ)下一個(gè)集合元素的位置；3. 創(chuàng)建若干個(gè)

4、基本函數(shù)，通過函數(shù)調(diào)用對(duì)鏈表進(jìn)行操作，實(shí)現(xiàn)集合的交、并、差運(yùn)算。算法思想和程序的實(shí)現(xiàn)概述3.1 算法思想定義一個(gè)鏈表，鏈表有整型數(shù)據(jù)和一個(gè)指向鏈表的指針，程序包含定義一個(gè)新鏈表的函數(shù)，集合并函數(shù)，集合交函數(shù)，集合差函數(shù)。求兩集合交集并集差集從兩集合的頭結(jié)點(diǎn)開始，比較兩集合元素大小，進(jìn)行對(duì)應(yīng)的操作，直到讀取到兩集合的末尾元素。主程序先定義三個(gè)集合，創(chuàng)建集合A讀入A數(shù)據(jù)，創(chuàng)建集合B讀入B數(shù)據(jù)，然后輸出集合A,B的元素，求出兩集合并集并輸出。求兩集合的交集和差集的運(yùn)算與求并集的步驟類似，只需按提示輸入即可。3.2 程序的實(shí)現(xiàn)概述（1）輸入的形式和輸入值的范圍：輸入是從鍵盤輸入的，輸入的內(nèi)容為整數(shù)。（

5、2）輸出的形式從屏幕輸出，顯示用戶輸入集合的元素，并顯示進(jìn)行運(yùn)算后的值。（3）存儲(chǔ)結(jié)構(gòu)在這次設(shè)計(jì)中開始我是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，使得集合的算法定義十分簡潔。（4）算法實(shí)現(xiàn)定義鏈表，創(chuàng)建鏈表，輸出鏈表。利用鏈表的來存儲(chǔ)集合。利用三個(gè)函數(shù)分別實(shí)現(xiàn)課程要求程序?qū)崿F(xiàn)的求并、求交和差三中運(yùn)算?，F(xiàn)分述如下：A）并運(yùn)算函數(shù)該函數(shù)采取了用新集合存儲(chǔ)兩集合并后的新集合，利用一個(gè)for循環(huán)來消除新集合中相同的元素，使其在屏幕上只顯示一次。B）交運(yùn)算函數(shù)該函數(shù)用于實(shí)現(xiàn)集合的并運(yùn)算，利用for嵌套實(shí)現(xiàn)兩鏈表中數(shù)據(jù)的比較，輸出兩鏈表中相同的元素。C）差函數(shù)該函數(shù)用于實(shí)現(xiàn)集合的差運(yùn)算，利用鏈表中的數(shù)據(jù)域進(jìn)行判斷。輸出不同于被

6、減集合中不存在的元素。四程序流程圖流程圖:輸入數(shù)據(jù)求兩集合的差集五程序的實(shí)現(xiàn)改程序的實(shí)現(xiàn)步驟是定義鏈表，創(chuàng)建鏈表，輸出鏈表。利用鏈表的來存儲(chǔ)集合。利用三個(gè)函數(shù)分別實(shí)現(xiàn)課程要求程序?qū)崿F(xiàn)的求并、求交和差三中運(yùn)算?，F(xiàn)分述如下：5.1主函數(shù)voidbangzhu()printf("nttt*”);printf("nttt*求集合的交并差*"）；printf("nttt*n");void main() /*主函數(shù)*/structset*p,*q,*r;intm,n,node;bangzhu();for(;)doprintf（"請(qǐng)輸入您要選擇操作

7、的代碼:n"）;printf（"1:求兩集合的并AUB'n"）;printf（"2:求兩集合的交AHB'n"）;printf（"3：求兩集合的差A(yù)-Bn"）;printf（"0：退出該程序n"）;scanf("%d",&node); while(node<0|node>3);if(node=0) exit(1);printf("ttt/*scanf("%d",&m);createlist_p(p,m);/*pri

8、ntf("ttt/*scanf("%d",&n);/*createlist_p(q,n);printf(" 集合A中元素為:"); printlist_p(p); /*printf(" 集合 B 中元素為:");printlist_p(q); /*while(node<0|node>3);switch(node)請(qǐng)輸入集合A中元素的個(gè)數(shù)：*/n"）;調(diào)用鏈表生成函數(shù)生成A鏈表*/B 中元素的個(gè)數(shù)：*/n"）;調(diào)用鏈表生成函數(shù)生成B 鏈表 */調(diào)用集合輸出函數(shù)輸出集合A */調(diào)用集合輸出

9、函數(shù)輸出集合A */case 1: Addset(p,q,r);printf("AUB:n");printlist_p(r);break;case 2: Subset(p,q,r);printf("AAB:n");printlist_p(r);break;case 3: Intset(p,q,r);printf("A-B:n");printlist_p(r);break;printf("n");5.2 鏈表的生成voidcreatelist_p(structset*&p,intn)inti;structse

10、t*L;p=(structset*)malloc(sizeof(set);/*申請(qǐng)結(jié)點(diǎn)p*/p->next=NULL;/*定義p的next指針為空*/for(i=n;i>0;i-)L=(structset*)malloc(sizeof(set);/*申請(qǐng)結(jié)點(diǎn)L*/printf("請(qǐng)輸入該集合中第階整數(shù)元素二n-i+1);scanf("%s",&L->coef);L->next=p->next;p->next=L;/生成新鏈表用于存放兩集合中的元素5.3 集合的輸出voidprintlist_p(structset*&am

11、p;p)structset*L;inti;L=p->next;if(!L)printf("該表為空!n");while(L!=NULL)printf("%c",L->coef);L=L->next;i+;printf("n");/打印輸入的兩集合中的元素5.4 并運(yùn)算函數(shù)voidAddset(structset*&p,structset*&q,structset*&r)structset*k,*m,*n;r */r=(structset*)malloc(sizeof(set);/*r->

12、next=NULL;/*定義 r 的 next 指針為空*/k=p->next;/* k指向 p 的下一個(gè)結(jié)點(diǎn)*/for(;k;)m=(structset*)malloc(sizeof(set);/*申請(qǐng)結(jié)點(diǎn)m*/m->next=r->next;r->next=m;m->coef=k->coef;k=k->next;/*把第一個(gè)集合中的元素放在新集合中*/k=q->next;m=(structset*)malloc(sizeof(set);m->next=r->next;r->next=m;m->coef=k->co

13、ef;k=k->next;for(;k;)for(n=r->next;(k->coef!=n->coef)&&n->next;)n=n->next;/*與新集合中的元素比較，如果不同則鏈入鏈表中*/if(k->coef!=n->coef)&&!(n->next)m=(structset*)malloc(sizeof(set);m->next=r->next;r->next=m;m->coef=k->coef;k=k->next;/*對(duì)第二個(gè)集合中的元素進(jìn)行分析*/*求AUB

14、*/該函數(shù)采取了用新集合存儲(chǔ)兩集合并后的新集合，利用一個(gè)for循環(huán)來消除新集合中相同的元素，是其在屏幕上只顯示一次。5.5 交運(yùn)算函數(shù)voidSubset(structset*&p,structset*&q,structset*&r)structset*k,*m,*n;r=(structset*)malloc(sizeof(set);/*申請(qǐng)結(jié)點(diǎn)r*/r->next=NULL;n=q->next;for(;n;)/*比較p和q鏈表中的元素，相同的元素存入鏈表r中*/m=p->next;for(;(m->coef!=n->coef)&

15、&m->next;)m=m->next;if(m->coef=n->coef)k=(structset*)malloc(sizeof(set);k->next=r->next;r->next=k;k->coef=m->coef;n=n->next;/*求Anb*/該函數(shù)用于實(shí)現(xiàn)集合的并運(yùn)算，利用for嵌套實(shí)現(xiàn)兩鏈表中數(shù)據(jù)的比較，輸出兩鏈表中相同的元素。5.6 差函數(shù)voidIntset(structset*&p,structset*&q,structset*&r)structset*k,*m,*n;r=

16、(structset*)malloc(sizeof(set);r->next=NULL;m=p->next;for(;m;)n=q->next;for(;(m->coef!=n->coef)&&n->next;)n=n->next;if(!n->next&&(m->coef!=n->coef)/*比較鏈表p與q,找出p中不同于q的元素存入鏈表r中*/k=(structset*)malloc(sizeof(set);k->next=r->next;r->next=k;k->coef

17、=m->coef;m=m->next;/*求A-B*/該函數(shù)用于實(shí)現(xiàn)集合的差運(yùn)算，利用鏈表中的數(shù)據(jù)域進(jìn)行判斷。輸出不同于被減集合中不存在的元素。六運(yùn)行結(jié)果分析6.1程序主界面-數(shù)據(jù)結(jié)構(gòu)集合運(yùn)算實(shí)現(xiàn)對(duì)集合元素交并差運(yùn)算*序 嬖苔上懸 SBtH A A flJ3i圖6.1程序主界面6.2整數(shù)集合并運(yùn)算圖6.3整數(shù)集合交運(yùn)算/*請(qǐng)輸入集合B中元素的個(gè)數(shù):推入該強(qiáng)入該輸入該*求集合的玄并差*742臺(tái)呻合R巾Ja：227肺人該集合史第1個(gè)莘教亓凄;3希人讀靠合田盥個(gè)整數(shù)蒜;2c請(qǐng)輸入集合R中元素的個(gè)翻：,亡ilC:ProgramFiletMcro£cftVisualStudio&q

18、uot;MProjiectslll,Debugll.exe1合合合BR代的KNiOiiClffiCWM：作匚器駕封的新的序饕合合程輸兩的比瓠退請(qǐng)1:力黯瓦口第1個(gè)整效兀重連口第2個(gè)蹙數(shù)卷K由集3個(gè)整數(shù)元素二？甲圖6.2整數(shù)集合并運(yùn)算6.3整數(shù)集合交運(yùn)算WCPogramFiesliMicrQSDftV&ual5tudbMyProject5lHDebugll1,Exe-八請(qǐng)輸入集合時(shí)元素為個(gè)數(shù)請(qǐng)輸入您n-BAfl交差的的序臺(tái)合al«修兩兩土桑退【個(gè)整數(shù)元素:E/.請(qǐng)輸入集合E中元素為個(gè)數(shù);富人該集合:力入該蕖合中弟2個(gè)整蛾兀素舊H兀元元M-效數(shù)善整112380ans-ps-n.A

19、TrnltTMtr796l-rD-h-3匚廠匚占臺(tái)臺(tái)好該讀該糅人人人:J犯；口nB喋作的代坦:aUb6.4 整數(shù)集合差運(yùn)算圖6.7字母集合差運(yùn)算c<'CfiProgramFtesliMItrosrftValStudloMyPmj«teUlDebugU1»«»8合合合#1該喙飯RN浪 3 171- 3 3 7，J 3JJ 1 J*求集合的交并差*W疆” 2：求前集合的交Mil求兩衣兩集才的差RB:&出或程序所骨輸人集合由中元素的個(gè)數(shù), ”認(rèn)該集合口燔鼐1八2人萬宗。兀幸二b3個(gè)元素二c小情輸人集合B中元素的人數(shù)；”WtiSS1 情輸入

20、聯(lián)集合口第Z 集合口壬兀室為“b 窠臺(tái)B中元素為* bJH 二=a b c個(gè)百:b個(gè)兀素二方圖6.4整數(shù)集合差運(yùn)算6.5 字母集合并運(yùn)算;內(nèi)代弼二二1白'C：Progir-sKFlcsXHiGroQVisuaJ.S-tudxoXKyFx'Qj?GtaXEVD?bTicKEi-ce?6.6字母集合交運(yùn)算匚 *C : PrcaiiLM FilesVBlcedsoft Visual St udiolilyFcq j ect s 5Debiuu£ 5.條不B勺¥ LT& r 力 r £17-pu 國合合合程 磔曦重讀 退 錚2:3:小»

21、Mktf M W X*求集合的交并差代明二1B-RItf H *W3*T *W H，H rf IrC'SJ VI/*詞輸人室含中中元素的個(gè)藪：1 2 第” 手 合合 i 石士.1 .1請(qǐng)愉入耒合B中元素的個(gè)姮.合 m 2請(qǐng)請(qǐng)集集每合臺(tái)一集柒S人入省為 <素 元元 $12111后fif f元元曙腦得鬻酹代的圖6.6字母集合交運(yùn)算6.7 字母集合差運(yùn)算c："C:FrograjiLFilesiftiLCZDSoftfj.sualStudioByProjectsbDebugAb.eze"流圍憑臺(tái)的套門求肅集宣的各-R，嘴輸入集合A中元素的個(gè)數(shù)二mF二請(qǐng)輸入集合B中元素

22、的個(gè)數(shù):3退出該辭序博卸入該集合中，差i個(gè):窿X該富含嚼rx其.是口合,請(qǐng)請(qǐng)量入讀梟臺(tái)中堂入該建吉市常A口工至為二hfdB口元素為“巖1個(gè)兀素:2個(gè)元素：;請(qǐng)輸入您要進(jìn)F理七的代碼工1:錄而集百的奔Uia塞一幽立柏.契合的差由D0：退出該程序6.8 字母和數(shù)據(jù)集合并運(yùn)算清輸入廖選學(xué)深作的代詞:t玳兩卷;的升n0H羽兩集合的安nClH-藍(lán)商集合的差Rf，喈輸入莫臺(tái)在中元素的個(gè)數(shù)；"-1、j 2/次請(qǐng)輸入集合B中元素的個(gè)數(shù)；Bu- d1元元1 2 a tt12 a-二-im erer- l:ii 該該若 人人吊fl BJBa El-mJ7ruJL.-UJL-1-的B B作 Url-H口筆

23、AAH WS J的的的序圖6.9字母和數(shù)據(jù)集合交運(yùn)算圖6.8字母和數(shù)據(jù)集合并運(yùn)算6.9 字母和數(shù)據(jù)集合交運(yùn)算6.10 字母和數(shù)據(jù)集合差運(yùn)算Gh C; PrvgK u FilcsMiucutfUift Visual StudiuXByPitf MXDcbiiKXl« gxc1"圖6.10字母和數(shù)據(jù)集合差運(yùn)算6.11 退由程序a科,CsProgiraKFi.l0sKi.crofO'f±VismalStudxaKyProjec±s4Debug4«exeIL>=»6X請(qǐng)輸入集合B中元素的個(gè)教士W后入讀集合中第不整數(shù)元請(qǐng)輸入該集合

24、史要個(gè)整數(shù)元請(qǐng)輸入該第合由最小整列元集合ft口云素為二946584213集合B口元素為M6721378m-B：78$5fl49如輸人您要選隹喋作的代碼:軍兩集臺(tái)盼浦UH太兩靠合的為C1B立兩集合的差向E退出該程存yess曰口"keytocnimtinne6.11退出程源代碼#include<stdio.h>#include<malloc.h>#include<stdlib.h>structsetcharcoef;structset*next;/線性表的單鏈表存儲(chǔ)結(jié)構(gòu)voidcreatelist_p(structset*&p,intn)int

25、i;structset*L;p=(structset*)malloc(sizeof(set);p->next=NULL;/建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;i-)L=(structset*)malloc(sizeof(set);/生成新節(jié)點(diǎn)printf("請(qǐng)輸入該集合中第%d個(gè)整數(shù)元素:",n-i+1);scanf("%s",&L->coef);L->next=p->next;p->next=L;/插入到表頭voidprintlist_p(structset*&p)structset*L;

26、inti;L=p->next;if(!L)printf("該表為空!n");while(L!=NULL)printf("%c",L->coef);L=L->next;i+;printf("n");voidAddset(structset*&p,structset*&q,structset*&r)structset*k,*m,*n;r=(structset*)malloc(sizeof(set);r->next=NULL;k=p->next;for(;k;)m=(structset*

27、)malloc(sizeof(set);m->next=r->next;r->next=m;m->coef=k->coef;k=k->next;/r中存放pk=q->next;m=(structset*)malloc(sizeof(set);m->next=r->next;r->next=m;m->coef=k->coef;k=k->next;for(;k;)for(n=r->next;(k->coef!=n->coef)&&n->next;)n=n->next;if(k

28、->coef!=n->coef)&&!(n->next)m=(structset*)malloc(sizeof(set);m->next=r->next;r->next=m;m->coef=k->coef;k=k->next;求AUBvoidSubset(structset*&p,structset*&q,structset*&r)structset*k,*m,*n;r=(structset*)malloc(sizeof(set);r->next=NULL;n=q->next;for(;n

29、;)m=p->next;for(;(m->coef!=n->coef)&&m->next;)m=m->next;if(m->coef=n->coef)k=(structset*)malloc(sizeof(set);k->next=r->next;r->next=k;k->coef=m->coef;n=n->next;求AnBvoidIntset(structset*&p,structset*&q,structset*&r)structset*k,*m,*n;r=(struct

30、set*)malloc(sizeof(set);r->next=NULL;m=p->next;for(;m;)n=q->next;for(;(m->coef!=n->coef)&&n->next;)n=n->next;if(!n->next&&(m->coef!=n->coef)k=(structset*)malloc(sizeof(set);k->next=r->next;r->next=k;k->coef=m->coef;m=m->next;/求A-Bvoidbangzhu()printf("nttt*”);printf("nttt*求集合的交并差*");*n");printf("nttt*voidmain()structset*p,*q,*r;intm,n,node;bangzhu();for(;)doprintf("請(qǐng)輸入您要選擇操作的代碼:n");printf("1:求兩集合的并AUBn");printf("2:求兩集