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

1、 集合運(yùn)算電子與信息工程學(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) 新)班 級: 2013級電信三班 學(xué) 號: 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

2、整數(shù)集合差運(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ù)存儲結(jié)構(gòu)的設(shè)計(jì)方法，掌握基于數(shù)據(jù)結(jié)構(gòu)的各種操作的實(shí)現(xiàn)方法，訓(xùn)練對基礎(chǔ)知識和基本方法的綜合運(yùn)用能力，增強(qiáng)對算法的理解能力，提高軟件設(shè)計(jì)能力。在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。要求：熟練運(yùn)用C+語言、基本數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)知識，獨(dú)立編制一個(gè)具有中等難度的、解決實(shí)際應(yīng)用問題的應(yīng)用程序。通過題意分析、選擇數(shù)據(jù)結(jié)構(gòu)

3、、算法設(shè)計(jì)、編制程序、調(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存儲集合A、B，用鏈表r存儲集合C。描述該問題的存儲結(jié)構(gòu)，算法，并通過編寫程序來實(shí)現(xiàn)。 問題分析： 1. 定義一個(gè)鏈表來存儲集合元素； 2. 鏈

4、表L包括數(shù)據(jù)域和指針域，數(shù)據(jù)域中存儲集合元素，指針域中存儲下一個(gè)集合元素的位置； 3. 創(chuàng)建若干個(gè)基本函數(shù)，通過函數(shù)調(diào)用對鏈表進(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)行對應(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）存儲結(jié)構(gòu) 在這次設(shè)計(jì)中開始我是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，使得集合的算法定義十分簡潔。（4） 算法實(shí)現(xiàn)定義鏈表，創(chuàng)建鏈表，輸出鏈表。利用鏈表的來存儲集合。利用三個(gè)函數(shù)分別實(shí)現(xiàn)課程要求程序?qū)崿F(xiàn)的求并、求交和差三中運(yùn)算?，F(xiàn)分述如下：A） 并運(yùn)算函數(shù) 該函數(shù)采取了用新集合存儲兩集合并后的新集合，利用一個(gè)for循環(huán)來消除新集合中相同的元素，使其在屏幕上只顯示一次。B）交運(yùn)算函數(shù)該函數(shù)用于實(shí)現(xiàn)集合的并運(yùn)算，利用for嵌套實(shí)現(xiàn)兩

6、鏈表中數(shù)據(jù)的比較，輸出兩鏈表中相同的元素。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)建鏈表，輸出鏈表。利用鏈表的來存儲集合。利用三個(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("請輸入您要選擇操作的代碼:n"); printf("1：求兩集合的并ABn"); printf("2：求兩集合的交ABn"); printf("3：求兩集合的差A(yù)-Bn"); printf("0：退出該程序n"); scanf("%d",&node); wh

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

9、printlist_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

10、,r); 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); /* 申請結(jié)點(diǎn)p */ p->next=NULL; /* 定義p的next指針為空 */ for(i=n;i>0;i-) L=(struct set *)malloc(sizeof(set); /* 申請結(jié)點(diǎn)L*/

11、 printf("請輸入該集合中第%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->

12、coef); 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); /* 申請結(jié)點(diǎn)r */ r->next=NULL; /* 定義r的next指針為空 */ k=p->next; /* k指向p的下一個(gè)結(jié)點(diǎn) */ for(;k;) m=(struct set

13、*)malloc(sizeof(set); /* 申請結(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->c

14、oef)&&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; /* 對第二個(gè)集合中的元素進(jìn)行分析 */ /* 求AB */該函數(shù)采取了用新集合存儲兩集合并后的新集合，利用一個(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); /* 申請結(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

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

18、t;next=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)算

19、6.9 字母和數(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; ; /線性表的單鏈表存儲結(jié)構(gòu)void createlist_p(struct set *&p,int n) int i; struct set *L; p=(struct set *)malloc(

20、sizeof(set); p->next=NULL; /建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;i-) L=(struct set *)malloc(sizeof(set); /生成新節(jié)點(diǎn) printf("請輸入該集合中第%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->n

21、ext; 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

22、=(struct 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)&&

23、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; /求AB void Subset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct set *)m

24、alloc(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 s

25、et *&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(s

26、izeof(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("請輸入您要選擇操作的代碼: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); pri