數(shù)據(jù)結構課程設計報告集合運算

1、數(shù)據(jù)結構 課程設計報告 設計題目： 集合運算 專 業(yè) 班 級 學 生 學 號 指導教師 2011 年 5 月 1 目目 錄錄 一一.設計題目設計題目 .2 （一）.題目：集合運算.2 （二）.問題描述和分析.2 二二.設計內容設計內容 .3 (一). 數(shù)據(jù)結構設計.3 (二). 算法設計.3 三三.概要設計概要設計 .4 (一一).程序結構圖程序結構圖.4 （二）.具體程序設計.4 四四.算法分析算法分析 .5 源代碼.5 五五.結果分析結果分析 .16 六六.心得體會心得體會 .21 七七.參考文獻參考文獻 .22 2 一一.設計題目設計題目 （一）.題目：集合運算 功能：使用鏈表來表示集合

2、，完成集合的合并，求交集等操作。 主要包含以下內容： 1初步完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)； 2完成最低要求； 3進一步要求： 要求：1）界面友好，函數(shù)功能要劃分好 2）總體設計應畫一流程圖 3）程序要加必要的注釋 4）要提供程序測試方案 5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運 行的程序是沒有價值的。 （二）.問題描述和分析 本課程設計中，鏈表長度不能超過 100，集合輸入的形式為一個以“回車符”為 結束標志的字符串，串中字符順序不限，且允許出現(xiàn)重復字符或非法字符，程 序應能自動濾。輸出的運算結果字符串中將不含重復字符或非法字符。 問題描述：

3、 有兩個集合 a、b，要求它的交集、并集。用兩個鏈表 l1、l2 存儲集合 a、b。描 述該問題的存儲結構，算法，并通過編寫程序來實現(xiàn)。 問題分析： 1. 定義一個鏈表來存儲集合元素； 2. 鏈表 l 包括數(shù)據(jù)域和指針域，數(shù)據(jù)域中存儲集合元素，指針域中存儲下一個 集合元素的位置； 3. 創(chuàng)建若干個基本函數(shù)，通過函數(shù)調用對鏈表進行作，實現(xiàn)集合的交、并運算。 3 二二.設計內容設計內容 (一). 數(shù)據(jù)結構設計 1. 數(shù)據(jù)結構設計考慮 創(chuàng)建三個帶頭結點的單鏈表，用來存儲兩個集合中的元素和最終的結果，為實 現(xiàn)集合的交，并運算功能，應以有序鏈表表示集合。為此，需要兩個抽象數(shù)據(jù) 類型：有序表和集合。 2.

4、 邏輯結構存儲結構 邏輯結構： 創(chuàng)造一個帶結點的單鏈表包括（頭結點 l，結點若干，尾結點） 單鏈表中每個結點包括（*next 表示指針 data 表示域） (二). 算法設計 程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后， 由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；相應的輸入數(shù)據(jù)（濾輸入中 的非法字符）和運算結果顯示在其后。 程序執(zhí)行的命令包括： a) 構造集合 a； b) 構造集合 b； c) 求交集； d) 求并集； e) 結束。 “構造集合 a”和“構造集合 b”時，需以字符串的形式鍵入集合元素。 4 三三.概要設計概要設計 (一).程序結構圖 main 函

5、數(shù) intersect 交函數(shù) union 并函數(shù) sort 鏈表排 序函數(shù) createlist 尾插法建 表 displist 輸出函 數(shù) （二）.具體程序設計 1.定義鏈表 typedef int elemtype； typedef struct lnode 2.返回鏈表長度 3.返回指定節(jié)點的值 4.定位制定值的節(jié)點的值 5.顯示鏈表 void display(struct lnode *l) 6.創(chuàng)建鏈表，并設置鏈表為空 void creat(struct lnode *l) 7.向鏈表中插入元素 void insert(struct lnode *l,int n,elemtype

6、x) 8.插在第 n 個節(jié)點的前面 9.刪除指定位置的節(jié)點 10.初始化鏈表 void init(struct lnode *l,int len) 11.復制鏈表 l1 到 l2 void copy(struct lnode *l1,struct lnode *l2 ) 12.求交集 void intersection(struct lnode *l1,struct lnode *l2,struct lnode *l3) 13.求并集 unionset(struct lnode *l1,struct lnode *l2,struct lnode *l3) 14.把 l1 復制到 l3，然后比較

7、 l2 和 l3，得到 l2 與 l3 中沒有的元素，并插入 15.插在排序的位置上 insert( 16.插在鏈尾 5 四四.算法分析算法分析 源代碼如下如下： #include #include #include #define null 0 #define m 100 typedef int elemtype;/*定義鏈表*/ typedef struct lnode elemtype data; struct lnode *next; ; int lenth(struct lnode *l) int n=0; struct lnode *t; t=*l; while(t!=null)

8、n+; t=t-next; return n; elemtype get(struct lnode *l,int n) int i=1; struct lnode *t; t=*l; while (inext; i+; if(t!=null) return(t-data); else 6 printf(the %dth lnode havent find !n,n); int locate(struct lnode *l,elemtype x ) int n=1; struct lnode *t; t=*l; while (t!=null n+; if(t=null) return(0); e

9、lse return(n); void display(struct lnode *l)/*顯示鏈表*/ struct lnode *t; t=*l; if(t=null) printf(the link is null!); else do printf(%d,t-data); t=t-next; while(t!=null); printf(n); void creat(struct lnode *l)/*創(chuàng)建鏈表*/ 7 *l=null; void insert(struct lnode *l,int n,elemtype x)/*向鏈表中插入元素*/ struct lnode *t1,

10、*t2; int j=1; t1=(struct lnode *)malloc(sizeof(struct lnode); t1-data=x; t2=*l; if(n=1) t1-next=t2; *l=t1; else while(jnext!=null) t2=t2-next; j+; if(j=n-1) t1-next=t2-next; t2-next=t1; else printf(insert error!); void delete(struct lnode *l,int n) int i=1; struct lnode *t1,*t2; t1=*l; if(n=1) t2=t1

11、; *l=t1-next; else 8 while(inext!=null) t1=t1-next; i+; if(t1-next!=null t1-next=t2-next; else printf(delete error!n); if(t2=null) free(t2); void init(struct lnode *l,int len)/*初始化鏈表*/ int dm,i,j,k,ti; struct lnode *t; input: for(i=1;i=len;i+) scanf(%d, for(j=1;j=len;j+) for(k=j+1;kdk) ti=dj; dj=dk;

12、 dk=ti; for(i=1;ilen;i+) if(di=di+1) printf(dont allow the same data! please reinput!); 9 goto input; creat( for(i=1;i=len;i+) insert( printf(the data of the linktable is: ); display( void copy(struct lnode *l1,struct lnode *l2 )/*復制鏈表 l1 到 l2*/ int i,len; elemtype t; len=lenth( creat( for(i=1;i=len

13、;i+) t=get( insert( void intersection(struct lnode *l1,struct lnode *l2,struct lnode *l3)/*求交集*/ int i,j,k=1; struct lnode *t1,*t2; t1=*l1; t2=*l2; creat( for(i=1;i=lenth(i+) for(j=1;jdata=t2-data) insert( k+; t2=t2-next; 10 t1=t1-next; t2=*l2; unionset(struct lnode *l1,struct lnode *l2,struct lnode

14、 *l3)/* 求并集*/ int i,j,k; struct lnode *tt,*t2,*t3; creat( copy( t2=*l2; t3=*l3; for(i=1;i=lenth(i+) k=1; for(j=1;jdata=t3-data) k=0; break; else if(t2-datadata) break; else if(t2-datat3-data) k+; if(knext; if(k0 else if(klenth( tt-data=t2-data; 11 tt-next=null; t3-next=tt; t2=t2-next; t3=*l3; void d

15、iffrenceset(struct lnode *l1,struct lnode *l2,struct lnode *l3) int i,t,n; creat( copy( for(i=1;i=lenth(i+) t=get( n=locate( if(n) delete( main() int len1,len2; char r; static struct lnode *head1,*head2,*head3,*head4; printf(/*the begin*/n); printf(please input the lenth of the first linktable! ); s

16、canf(%d, printf(the lenth of the first linktable is %d,please input %d datas! ,len1,len1); init( printf(/-/n); printf(please input the lenth of the second linktable! ); scanf(%d, printf(the lenth of the second linktable is %d,please input %d datas! ,len2,len2); init( printf(nn/-/n); intersection( pr

17、intf(the intersection of two linktable: ); display( unionset( 12 printf(the union set of two linktable: ); display( printf(/*the end*/n); 五五.結果分析結果分析 1.在 turboc2.01 環(huán)境中輸入源代碼 2.按 atl+f9 編譯文件 得到以下結果，發(fā)現(xiàn)無錯誤。 13 3.由提示按任意鍵，后按 ctrl+f9 編譯運行，得到以下結果。 給第一個鏈表的長度設為 5 后按 enter 程序開始（程序開始（thethe beginbegin） 4.輸入以下數(shù)

18、字：10 25 78 99 1000 14 5.輸完數(shù)字后按 enter,得到以下結果，第一個鏈表輸入完畢。 6.由提示任意給定第二個鏈表長度為 17。 15 7.屏幕提示鏈表長度已定，并要求輸入 17 個數(shù)字。 8.輸入以下 17 個數(shù)字：1 2 3 4 5 6 7 8 9 28 78 86 99 100 120 150 10000 16 9.按 enter 屏幕顯示如下 10.按 alt+f5 查看輸出結果 得出交集：78 99 并集：1 2 3 4 5 6 7 8 9 10 25 28 78 86 99 100 120 150 1000 10000 17 程序結束程序結束(the(the end)end) 18 六六.心得體會心得體會 通過實踐才發(fā)現(xiàn) c 語言程序設計的掌握直接關系