數據結構課程設計集合運算(完整)

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

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

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

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

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

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

7、的代碼:n"）;printf（"1:求兩集合的并AUB'n"）;printf（"2:求兩集合的交AHB'n"）;printf（"3：求兩集合的差A-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)請輸入集合A中元素的個數：*/n"）;調用鏈表生成函數生成A鏈表*/B 中元素的個數：*/n"）;調用鏈表生成函數生成B 鏈表 */調用集合輸出函數輸出集合A */調用集合輸出

9、函數輸出集合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);/*申請結點p*/p->next=NULL;/*定義p的next指針為空*/for(i=n;i>0;i-)L=(structset*)malloc(sizeof(set);/*申請結點L*/printf("請輸入該集合中第階整數元素二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 并運算函數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 的下一個結點*/for(;k;)m=(structset*)malloc(sizeof(set);/*申請結點m*/m->next=r->next;r->next=m;m->coef=k->coef;k=k->next;/*把第一個集合中的元素放在新集合中*/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;/*對第二個集合中的元素進行分析*/*求AUB

14、*/該函數采取了用新集合存儲兩集合并后的新集合，利用一個for循環(huán)來消除新集合中相同的元素，是其在屏幕上只顯示一次。5.5 交運算函數voidSubset(structset*&p,structset*&q,structset*&r)structset*k,*m,*n;r=(structset*)malloc(sizeof(set);/*申請結點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*/該函數用于實現集合的并運算，利用for嵌套實現兩鏈表中數據的比較，輸出兩鏈表中相同的元素。5.6 差函數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*/該函數用于實現集合的差運算，利用鏈表中的數據域進行判斷。輸出不同于被減集合中不存在的元素。六運行結果分析6.1程序主界面-數據結構集合運算實現對集合元素交并差運算*序 嬖苔上懸 SBtH A A flJ3i圖6.1程序主界面6.2整數集合并運算圖6.3整數集合交運算/*請輸入集合B中元素的個數:推入該強入該輸入該*求集合的玄并差*742臺呻合R巾Ja：227肺人該集合史第1個莘教亓凄;3希人讀靠合田盥個整數蒜;2c請輸入集合R中元素的個翻：,亡ilC:ProgramFiletMcro£cftVisualStudio&q

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

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

20、聯集合口第Z 集合口壬兀室為“b 窠臺B中元素為* bJH 二=a b c個百:b個兀素二方圖6.4整數集合差運算6.5 字母集合并運算;內代弼二二1白'C：Progir-sKFlcsXHiGroQVisuaJ.S-tudxoXKyFx'Qj?GtaXEVD?bTicKEi-ce?6.6字母集合交運算匚 *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/*詞輸人室含中中元素的個藪：1 2 第” 手 合合 i 石士.1 .1請愉入耒合B中元素的個姮.合 m 2請請集集每合臺一集柒S人入省為 <素 元元 $12111后fif f元元曙腦得鬻酹代的圖6.6字母集合交運算6.7 字母集合差運算c："C:FrograjiLFilesiftiLCZDSoftfj.sualStudioByProjectsbDebugAb.eze"流圍憑臺的套門求肅集宣的各-R，嘴輸入集合A中元素的個數二mF二請輸入集合B中元素

22、的個數:3退出該辭序博卸入該集合中，差i個:窿X該富含嚼rx其.是口合,請請量入讀梟臺中堂入該建吉市常A口工至為二hfdB口元素為“巖1個兀素:2個元素：;請輸入您要進F理七的代碼工1:錄而集百的奔Uia塞一幽立柏.契合的差由D0：退出該程序6.8 字母和數據集合并運算清輸入廖選學深作的代詞:t玳兩卷;的升n0H羽兩集合的安nClH-藍商集合的差Rf，喈輸入莫臺在中元素的個數；"-1、j 2/次請輸入集合B中元素的個數；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字母和數據集合交運算圖6.8字母和數據集合并運算6.9 字母和數據集合交運算6.10 字母和數據集合差運算Gh C; PrvgK u FilcsMiucutfUift Visual StudiuXByPitf MXDcbiiKXl« gxc1"圖6.10字母和數據集合差運算6.11 退由程序a科,CsProgiraKFi.l0sKi.crofO'f±VismalStudxaKyProjec±s4Debug4«exeIL>=»6X請輸入集合B中元素的個教士W后入讀集合中第不整數元請輸入該集合

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

25、i;structset*L;p=(structset*)malloc(sizeof(set);p->next=NULL;/建立一個帶頭結點的單鏈表for(i=n;i>0;i-)L=(structset*)malloc(sizeof(set);/生成新節(jié)點printf("請輸入該集合中第%d個整數元素:",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("請輸入您要選擇操作的代碼:n");printf("1:求兩集合的并AUBn");printf("2:求兩集