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

2、整數集合差運算6.5 字母集合并運算6.6 字母集合交運算6.7 字母集合差運算6.8 字母和數據集合并運算6.9 字母和數據集合交運算6.10 字母和數據集合差運算6.11 退出程序七 源代碼八 總結九 參考文獻一 課程設計目的和要求目的：深入理解數據結構的基本理論，掌握數據存儲結構的設計方法，掌握基于數據結構的各種操作的實現方法，訓練對基礎知識和基本方法的綜合運用能力，增強對算法的理解能力，提高軟件設計能力。在實踐中培養獨立分析問題和解決問題的作風和能力。要求：熟練運用C+語言、基本數據結構和算法的基礎知識，獨立編制一個具有中等難度的、解決實際應用問題的應用程序。通過題意分析、選擇數據結構

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

4、表L包括數據域和指針域，數據域中存儲集合元素，指針域中存儲下一個集合元素的位置； 3. 創建若干個基本函數，通過函數調用對鏈表進行操作，實現集合的交、并、差運算。 三 算法思想和程序的實現概述3.1 算法思想 定義一個鏈表，鏈表有整型數據和一個指向鏈表的指針，程序包含定義一個新鏈表的函數，集合并函數，集合交函數，集合差函數。求兩集合交集并集差集從兩集合的頭結點開始，比較兩集合元素大小，進行對應的操作，直到讀取到兩集合的末尾元素。主程序先定義三個集合，創建集合A讀入A數據，創建集合B讀入B數據，然后輸出集合A,B的元素，求出兩集合并集并輸出。求兩集合的交集和差集的運算與求并集的步驟類似，只需按提

5、示輸入即可。3.2 程序的實現概述（1）輸入的形式和輸入值的范圍： 輸入是從鍵盤輸入的，輸入的內容為整數。（2）輸出的形式 從屏幕輸出，顯示用戶輸入集合的元素，并顯示進行運算后的值。 （3）存儲結構 在這次設計中開始我是采用鏈式存儲結構，使得集合的算法定義十分簡潔。（4） 算法實現定義鏈表，創建鏈表，輸出鏈表。利用鏈表的來存儲集合。利用三個函數分別實現課程要求程序實現的求并、求交和差三中運算。現分述如下：A） 并運算函數 該函數采取了用新集合存儲兩集合并后的新集合，利用一個for循環來消除新集合中相同的元素，使其在屏幕上只顯示一次。B）交運算函數該函數用于實現集合的并運算，利用for嵌套實現兩

6、鏈表中數據的比較，輸出兩鏈表中相同的元素。C）差函數 該函數用于實現集合的差運算，利用鏈表中的數據域進行判斷。輸出不同于被減集合中不存在的元素。四 程序流程圖流程圖：開始 定義鏈表創建鏈表輸入數據求兩集合的并集輸入數據 求兩集合的交集輸入數據求兩集合的差集五 程序的實現改程序的實現步驟是定義鏈表，創建鏈表，輸出鏈表。利用鏈表的來存儲集合。利用三個函數分別實現課程要求程序實現的求并、求交和差三中運算。現分述如下：5.1 主函數void bangzhu() printf("nttt*"); printf("nttt* 求集合的交并差 *"); printf(

7、"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-Bn"); printf("0：退出該程序n"); scanf("%d",&node); wh

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

9、printlist_p(p); /* 調用集合輸出函數輸出集合A */ printf("集合B中元素為:"); printlist_p(q); /* 調用集合輸出函數輸出集合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); /* 申請結點p */ p->next=NULL; /* 定義p的next指針為空 */ for(i=n;i>0;i-) L=(struct set *)malloc(sizeof(set); /* 申請結點L*/

11、 printf("請輸入該集合中第%d個整數元素:",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 并運算函數void Addset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct set *)malloc(sizeof(set); /* 申請結點r */ r->next=NULL; /* 定義r的next指針為空 */ k=p->next; /* k指向p的下一個結點 */ for(;k;) m=(struct set

13、*)malloc(sizeof(set); /* 申請結點m */m->next=r->next; r->next=m; m->coef=k->coef; k=k->next; /* 把第一個集合中的元素放在新集合中 */ 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; /* 對第二個集合中的元素進行分析 */ /* 求AB */該函數采取了用新集合存儲兩集合并后的新集合，利用一個for循環來消除新集合中相同的元

15、素，是其在屏幕上只顯示一次。5.5交運算函數void Subset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct set *)malloc(sizeof(set); /* 申請結點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 */該函數用于實現集合的并運算，利用for嵌套實現兩鏈表中數據的比較，輸出兩鏈表中相同的元素。5.6 差函數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 */ 該函數用于實現集合的差運算，利用鏈表中的數據域進行判斷。輸出不同于被減集合中不存在的元素。六 運行結果分析6.1 程序主界面圖 6.1 程序主界面6.2整數集合并運算 圖6.2 整數集合并運算6.3 整數集合交運算 圖 6.3 整數集合交運算6.4 整數集合差運算圖6.4 整數集合差運算6.5 字母集合并運算圖6.5 字母集合并運算6.6 字母集合交運算圖6.6 字母集合交運算6.7 字母集合差運算圖6.7 字母集合差運算6.8 字母和數據集合并運算圖6.8 字母和數據集合并運算

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

20、sizeof(set); p->next=NULL; /建立一個帶頭結點的單鏈表for(i=n;i>0;i-) L=(struct set *)malloc(sizeof(set); /生成新節點 printf("請輸入該集合中第%d個整數元素:",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-Bn"); printf("0：退出該程序n"); scanf("%d",&node); while(node<0|node>3); if(node=0) exit(1); pri