數(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)概述四 程序流程圖流程圖五 程序的實(shí)現(xiàn)5.1 主函數(shù)5.2 鏈表的生成5.3 集合的輸出5.4 并運(yùn)算函數(shù)5.5交運(yùn)算函數(shù)5.6 差函數(shù)六 運(yùn)行結(jié)果分析6.1 程序主界面6.2整數(shù)集合并運(yùn)算6.3 整數(shù)集合交運(yùn)算6.4 整數(shù)集合差

2、運(yùn)算6.5 字母集合并運(yùn)算6.6 字母集合交運(yùn)算6.7 字母集合差運(yùn)算6.8 字母和數(shù)據(jù)集合并運(yùn)算6.9 字母和數(shù)據(jù)集合交運(yùn)算6.10 字母和數(shù)據(jù)集合差運(yùn)算6.11 退出程序七 源代碼八 總結(jié)九 參考文獻(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ì)

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

4、據(jù)域和指針域，數(shù)據(jù)域中存儲(chǔ)集合元素，指針域中存儲(chǔ)下一個(gè)集合元素的位置； 3. 創(chuàng)建若干個(gè)基本函數(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)算與求并集的步驟類似，只需按提示輸入即可

5、。3.2 程序的實(shí)現(xiàn)概述（1）輸入的形式和輸入值的范圍： 輸入是從鍵盤輸入的，輸入的內(nèi)容為整數(shù)。（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ù)

6、的比較，輸出兩鏈表中相同的元素。C）差函數(shù) 該函數(shù)用于實(shí)現(xiàn)集合的差運(yùn)算，利用鏈表中的數(shù)據(jù)域進(jìn)行判斷。輸出不同于被減集合中不存在的元素。四 程序流程圖流程圖：開始 定義鏈表創(chuàng)建鏈表輸入數(shù)據(jù)求兩集合的并集輸入數(shù)據(jù) 求兩集合的交集輸入數(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ù)void bangzhu() printf("nttt*"); printf("nttt* 求集合的交并差 *"); printf("

7、;nttt*n"); void main() /* 主函數(shù) */ struct set *p,*q,*r; int m,n,node; bangzhu(); for(;) do printf("請(qǐng)輸入您要選擇操作的代碼:n"); printf("1：求兩集合的并ABn"); printf("2：求兩集合的交ABn"); printf("3：求兩集合的差A(yù)-Bn"); printf("0：退出該程序n"); scanf("%d",&node); while(n

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

9、list_p(p); /* 調(diào)用集合輸出函數(shù)輸出集合A */ printf("集合B中元素為:"); printlist_p(q); /* 調(diào)用集合輸出函數(shù)輸出集合A */while(node<0|node>3); switch(node) case 1: Addset( p,q,r);printf("AB:n");printlist_p(r);break; case 2: Subset( p,q,r);printf("AB:n");printlist_p(r);break; case 3: Intset(p,q,r);

10、printf("A-B:n");printlist_p(r);break; printf("n"); 5.2 鏈表的生成void createlist_p(struct set *&p,int n) int i; struct set *L; p=(struct set *)malloc(sizeof(set); /* 申請(qǐng)結(jié)點(diǎn)p */ p->next=NULL; /* 定義p的next指針為空 */ for(i=n;i>0;i-) L=(struct set *)malloc(sizeof(set); /* 申請(qǐng)結(jié)點(diǎn)L*/ prin

11、tf("請(qǐng)輸入該集合中第%d個(gè)整數(shù)元素:",n-i+1); scanf("%s",&L->coef); L->next=p->next; p->next=L; /生成新鏈表用于存放兩集合中的元素 5.3 集合的輸出void printlist_p(struct set *&p) struct set *L; int i; L=p->next; if(!L) printf("該表為空!n"); while(L!=NULL) printf("%c ",L->coef)

12、; L=L->next; i+; printf("n"); /打印輸入的兩集合中的元素 5.4 并運(yùn)算函數(shù)void Addset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct set *)malloc(sizeof(set); /* 申請(qǐng)結(jié)點(diǎn)r */ r->next=NULL; /* 定義r的next指針為空 */ k=p->next; /* k指向p的下一個(gè)結(jié)點(diǎn) */ for(;k;) m=(struct set *)mal

13、loc(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=(struct set *)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)&

14、amp;&n->next;) n=n->next; /* 與新集合中的元素比較，如果不同則鏈入鏈表中 */if(k->coef!=n->coef)&&!(n->next) m=(struct set *)malloc(sizeof(set); m->next=r->next; r->next=m; m->coef=k->coef; k=k->next; /* 對(duì)第二個(gè)集合中的元素進(jìn)行分析 */ /* 求AB */該函數(shù)采取了用新集合存儲(chǔ)兩集合并后的新集合，利用一個(gè)for循環(huán)來消除新集合中相同的元素，是其在

15、屏幕上只顯示一次。5.5交運(yùn)算函數(shù)void Subset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct set *)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)&&m->next;) m=m->

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

17、uct 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) /* 比較鏈表p與q ,找出p中不同于q的元素存入鏈表r中 */ k=(struct set *)malloc(sizeof(set); k->next=r->next; r->nex

18、t=k; k->coef=m->coef; m=m->next; /* 求A-B */ 該函數(shù)用于實(shí)現(xiàn)集合的差運(yùn)算，利用鏈表中的數(shù)據(jù)域進(jìn)行判斷。輸出不同于被減集合中不存在的元素。六 運(yùn)行結(jié)果分析6.1 程序主界面圖 6.1 程序主界面6.2整數(shù)集合并運(yùn)算 圖6.2 整數(shù)集合并運(yùn)算6.3 整數(shù)集合交運(yùn)算 圖 6.3 整數(shù)集合交運(yùn)算6.4 整數(shù)集合差運(yùn)算圖6.4 整數(shù)集合差運(yùn)算6.5 字母集合并運(yùn)算圖6.5 字母集合并運(yùn)算6.6 字母集合交運(yùn)算圖6.6 字母集合交運(yùn)算6.7 字母集合差運(yùn)算圖6.7 字母集合差運(yùn)算6.8 字母和數(shù)據(jù)集合并運(yùn)算圖6.8 字母和數(shù)據(jù)集合并運(yùn)算6.9 字

19、母和數(shù)據(jù)集合交運(yùn)算圖6.9 字母和數(shù)據(jù)集合交運(yùn)算6.10 字母和數(shù)據(jù)集合差運(yùn)算圖6.10 字母和數(shù)據(jù)集合差運(yùn)算6.11 退出程序 圖6.11退出程七 源代碼#include<stdio.h> #include<malloc.h> #include<stdlib.h> struct set char coef; struct set *next; ; /線性表的單鏈表存儲(chǔ)結(jié)構(gòu)void createlist_p(struct set *&p,int n) int i; struct set *L; p=(struct set *)malloc(sizeo

20、f(set); p->next=NULL; /建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;i-) L=(struct set *)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; /插入到表頭 void printlist_p(struct set *&p) struct set *L; int i; L=p->next;

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

22、uct set *)malloc(sizeof(set); m->next=r->next; r->next=m; m->coef=k->coef; k=k->next; /r中存放p k=q->next; m=(struct set *)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->

23、;next;) n=n->next; if(k->coef!=n->coef)&&!(n->next) m=(struct set *)malloc(sizeof(set); m->next=r->next; r->next=m; m->coef=k->coef; k=k->next; /求AB void Subset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct set *)malloc

24、(sizeof(set); r->next=NULL; n=q->next; for(;n;) m=p->next; for(;(m->coef!=n->coef)&&m->next;) m=m->next; if(m->coef=n->coef) k=(struct set *)malloc(sizeof(set); k->next=r->next; r->next=k; k->coef=m->coef; n=n->next; /求AB void Intset(struct set *&

25、amp;p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct 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=(struct set *)malloc(sizeof

26、(set); k->next=r->next; r->next=k; k->coef=m->coef; m=m->next; /求A-B void bangzhu() printf("nttt*"); printf("nttt* 求集合的交并差 *"); printf("nttt*n"); void main() struct set *p,*q,*r; int m,n,node; bangzhu(); for(;) do printf("請(qǐng)輸入您要選擇操作的代碼:n"); printf("1：求兩集合的并ABn"); printf("2：求兩集合的交ABn"); printf("3：求兩集合的差A(yù)-Bn"); printf("0：退出該程序n"); scanf("%d",&node); while(node<0|node>3); if(node=0) exit(1); p