數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告集合運算

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目： 集合運算專 業(yè) 班 級 學 生 學 號 指導教師 2011 年 5 月1目目 錄錄一一.設(shè)計題目設(shè)計題目 .2（一）.題目：集合運算.2（二）.問題描述和分析.2二二.設(shè)計內(nèi)容設(shè)計內(nèi)容 .3(一). 數(shù)據(jù)結(jié)構(gòu)設(shè)計.3(二). 算法設(shè)計.3三三.概要設(shè)計概要設(shè)計 .4(一一).程序結(jié)構(gòu)圖程序結(jié)構(gòu)圖.4（二）.具體程序設(shè)計.4四四.算法分析算法分析 .5源代碼.5五五.結(jié)果分析結(jié)果分析 .16六六.心得體會心得體會 .21七七.參考文獻參考文獻 .222一一.設(shè)計題目設(shè)計題目（一）.題目：集合運算功能：使用鏈表來表示集合，完成集合的合并，求交集等操作。主要包含以下內(nèi)

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

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

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

5、splist輸出函數(shù)（二）.具體程序設(shè)計1.定義鏈表 typedef int elemtype；typedef struct lnode2.返回鏈表長度3.返回指定節(jié)點的值4.定位制定值的節(jié)點的值5.顯示鏈表 void display(struct lnode *l)6.創(chuàng)建鏈表，并設(shè)置鏈表為空 void creat(struct lnode *l)7.向鏈表中插入元素 void insert(struct lnode *l,int n,elemtype x)8.插在第 n 個節(jié)點的前面9.刪除指定位置的節(jié)點10.初始化鏈表 void init(struct lnode *l,int len)

6、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，然后比較 l2 和 l3，得到 l2 與 l3 中沒有的元素，并插入15.插在排序的位置上insert(&*l3,k,t2-data); 16.插在鏈尾5四四.算法

7、分析算法分析源代碼如下如下：#include #include #include #define null 0#define m 100typedef 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) n+; t=t-next; return n;elemtype get(struct lnode *l,int n) int i=1; struct

8、 lnode *t; t=*l; while (inext; i+; if(t!=null) return(t-data); else6 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&t-data!=x) t=t-next; n+; if(t=null) return(0); else return(n); void display(struct lnode *l)/*顯示鏈表*/ st

9、ruct 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,*t2; int j=1; t1=(struct lnode *)malloc(sizeof(struct lnod

10、e); 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; *l=t1-next; else 8 while(inext!=null) t1=t1-next; i+; if

11、(t1-next!=null&i=n-1) t2=t1-next; 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,&di); for(j=1;j=len;j+) for(k=j+1;kdk) ti=dj; dj=dk; dk=ti; for(i=1;ilen;i+) if(di=di+1

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

13、t=get(&*l1,i); insert(&*l2,i,t); 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(&*l3); for(i=1;i=lenth(&*l1);i+) for(j=1;jdata=t2-data) insert(&*l3,k,t1-data); k+; t2=t2-next; 10 t1=t1-next; t2=*l2; unionset(struc

14、t lnode *l1,struct lnode *l2,struct lnode *l3)/*求并集*/ int i,j,k; struct lnode *tt,*t2,*t3; creat(&*l3); copy(&*l1,&*l3); t2=*l2; t3=*l3; for(i=1;i=lenth(&*l2);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&kdata); else if(klenth(&*

15、l3) tt=(struct lnode *)malloc(sizeof(struct lnode); tt-data=t2-data;11 tt-next=null; t3-next=tt; t2=t2-next; t3=*l3; void diffrenceset(struct lnode *l1,struct lnode *l2,struct lnode *l3) int i,t,n; creat(&*l3); copy(&*l1,&*l3); for(i=1;i=lenth(&*l2);i+) t=get(&*l2,i); n=locate(&*l3,t); if(n) delete(

16、&*l3,n); 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! );scanf(%d,&len1);printf(the lenth of the first linktable is %d,please input %d datas! ,len1,len1);init(&head1,len1);printf(/-/n);printf(p

17、lease input the lenth of the second linktable! );scanf(%d,&len2);printf(the lenth of the second linktable is %d,please input %d datas! ,len2,len2);init(&head2,len2);printf(nn/-/n);intersection(&head1,&head2,&head3);printf(the intersection of two linktable: );display(&head3);unionset(&head1,&head2,&h

18、ead4);12printf(the union set of two linktable: );display(&head4);printf(/*the end*/n);五五.結(jié)果分析結(jié)果分析1.在 turboc2.01 環(huán)境中輸入源代碼2.按 atl+f9 編譯文件得到以下結(jié)果，發(fā)現(xiàn)無錯誤。133.由提示按任意鍵，后按 ctrl+f9 編譯運行，得到以下結(jié)果。給第一個鏈表的長度設(shè)為 5 后按 enter程序開始（程序開始（thethe beginbegin）4.輸入以下數(shù)字：10 25 78 99 1000 145.輸完數(shù)字后按 enter,得到以下結(jié)果，第一個鏈表輸入完畢。6.由提示任意給定第二個鏈表長度為 17。157.屏幕提示鏈表長度已定，并要求輸入 17 個數(shù)字。8.輸入以下 17 個數(shù)字：1 2 3 4 5 6 7 8 9 28 78 86 99 100 120 150 10000169.按 enter 屏幕顯示如下10.按 alt+f5 查看輸出結(jié)果得出交集：78 99并集：1 2 3 4 5 6 7 8 9 10 25 28 78 86 99 100 120 150 1000 1000017程序結(jié)束程序結(jié)束(the(the end)