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

1、1 需求分析1.1 設(shè)計任務(wù)集合的元素限定含有兩個數(shù)據(jù)域的結(jié)構(gòu)體，一個數(shù)據(jù)域為整數(shù)，另一個數(shù)據(jù)域為小寫字母字符a.z；演示程序以用戶和計算機(jī)的對話方式執(zhí)行；其中運用了編程軟件microsoft visual c+ 6.0創(chuàng)建鏈表來表示集合，用鏈表的查找、刪除、插入等知識點來實現(xiàn)集合的并、交、差和布爾和四種運算。1.2 功能要求集合輸入的形式為一個以回車符為結(jié)束標(biāo)志的字符串，元素中字符順序為先整數(shù)后字母，否則程序提示重新輸入,若出現(xiàn)重復(fù)元素或非法字符，不符合集合的定義,程序提示重新輸入。本段程序旨在對輸入的元素進(jìn)行并集,交集,差集和布爾和運算。 2 概要設(shè)計2.1鏈表表的抽象數(shù)據(jù)類型定義1為實現(xiàn)

2、上述程序功能，并要求以有序鏈表表示集合。所以，抽象數(shù)據(jù)類型就是單鏈表adt orderedlinklist數(shù)據(jù)對象：d=( ai, bi)|aiinteger，bicharset, i=1,2,.,n, n 0數(shù)據(jù)關(guān)系：rl=| ( ai-1, bi-1), ( ai, bi)d, ( ai-1, bi-1)e)return 1;elseif(enode2.c)return 1;elseif(ode2.c)return -1;elsereturn 0;3.3元素個數(shù)輸入的合法性檢查這個函數(shù)完全是為了程序的健壯性準(zhǔn)備的，當(dāng)用戶錯誤輸入時，程序提

3、示用戶輸入正確的整數(shù)，直到輸入正確后才可以進(jìn)行下一步操作。如果用戶輸入的有多余的字符，存在輸入輸入緩沖卻，將會被函數(shù)中調(diào)用的fflush(stdin) 6函數(shù)處理掉，消除了緩沖區(qū)殘留信息對下一步操作的影響。函數(shù)如下：status input1(int n)while(1)if(scanf(%d,&n)=1)fflush(stdin);/清除輸入緩沖區(qū)break;elsecout請正確輸入整數(shù)：endl;fflush(stdin);/退出循環(huán)就輸入正確了return n;/返回正確輸入的整數(shù)3.4 集合元素輸入的合法性檢查即歸為結(jié)點數(shù)據(jù)輸入的正確性檢查。當(dāng)輸入不正確時，程序提示用戶具體的輸入操作

4、，直到用戶輸入正確后，才可以把輸入的值賦值給結(jié)點的兩個數(shù)據(jù)成員，否則提示用戶重新輸入該元素。具體函數(shù)如下：status input(linklist &s)int a,x;char c;/scanf()函數(shù)的返回值5進(jìn)行條件判斷if(scanf(%d,&a)=1 & scanf(%c,&c)=1)/控制字符為小寫字母if(c=97)s-inte=a;s-c=c;fflush(stdin);/清除緩沖區(qū)的一個輸入流x=1;elsecout輸入失敗,第二部分是小寫字母endl;fflush(stdin);x=-1;elsecout集合元素是先一個整數(shù)后一個小寫字母！nex=null。如用重復(fù)，則需

5、要重新輸入。直到元素的個數(shù)等于用戶第一步輸入的元素個數(shù)時函數(shù)調(diào)用結(jié)束。函數(shù)如下：status createlinklist(linklist &l,int n)cout輸入集合元素時，整數(shù)與字母之間沒有任何符號，endl并且多余的字符將被程序處理掉，元素之間用回車鍵next=null;for(int i=0;inext)& datacompare(*p-next,*s)!=0)/調(diào)用元素大小比較函數(shù)p=p-next;if(p-next)/檢查到重復(fù)元素cout元素有重復(fù)next=s;p=p-next;p-next=null;x=ok;elsei-;/為下一次循環(huán)顯示元素的id號x=-1;ret

6、urn x;3.6求集合的并集2求集合的并集，根據(jù)課題要求，轉(zhuǎn)化為合并兩個鏈表的的問題。先把鏈表a的元素拷貝到鏈表c中，然后對鏈表b從頭開始檢索，依次和鏈表c中的每一個元素進(jìn)行比較，如果該元素不存在于鏈表c中，就將該元素用尾插法插入鏈表c。直到鏈表b為空，就完成了兩個集合的并集運算。函數(shù)如下：status unionset(linklist &a,linklist &b,linklist &c)linklist pa=a-next,pb=b-next,s,r;/pb指向b的第一個結(jié)點，s為要插入的結(jié)點，r為掃描指針c=(linklist)malloc(sizeof(lnode);r=c;whi

7、le(pa!=null)/復(fù)制鏈表a的結(jié)點到鏈表c中s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;while(pb!=null)/依次檢索鏈表bpa=a-next;while(pa!=null & datacompare(*pa,*pb)/檢查元素是否重復(fù)pa=pa-next;if(pa=null)/說明該元素不存在于a中/尾插法插入該結(jié)點s=(linklist)malloc(sizeof(lnode);s-inte=pb-inte;s-c=pb-c;r-next=s;r=s;p

8、b=pb-next;r-next=null;return ok;3.7 求a、b集合的交集3轉(zhuǎn)化為求兩個鏈表中相同元素的算法。先創(chuàng)建空鏈表c，外層循環(huán)對鏈表a首元結(jié)點開始檢索，內(nèi)層循環(huán)是將外層循環(huán)的結(jié)點的數(shù)據(jù)域與鏈表b中的非表頭結(jié)點的數(shù)據(jù)域依次進(jìn)行比較，當(dāng)外循環(huán)的節(jié)點數(shù)據(jù)與內(nèi)循環(huán)結(jié)點數(shù)據(jù)相等時，就得到交集的一個元素，用尾插法插入鏈表c中，當(dāng)兩層循環(huán)都結(jié)束時，就完成了集合的交集運算。函數(shù)如下：status interset(linklist &a,linklist &b,linklist &d)linklist pa=a-next,pb,s,r;/pb指向b的第一個結(jié)點，s為要插入的結(jié)點，r為掃

9、描指針d=(linklist)malloc(sizeof(lnode);r=d;while(pa!=null)/外層循環(huán)，對a中元素檢索pb=b-next;while(pb!=null& datacompare(*pb,*pa)內(nèi)層循環(huán)，找相等元素pb=pb-next;if(pb!=null)/此元素在a中s=(linklist)malloc(sizeof(lnode);s-c=pa-c;s-inte=pa-inte;r-next=s;r=s;pa=pa-next;r-next=null;return ok;3.8求差集2轉(zhuǎn)化為求兩表中，存在于前一個表中而不存在于后一個表中的元素的組成，即為差

10、集。具體思路是先創(chuàng)建空鏈表c，外層循環(huán)從首元結(jié)點檢索a表中的元素，內(nèi)層循環(huán)就是將a中的該元素從首元結(jié)點開始與表b中的元素依次作比較，如不等，則為差集的一個元素，用尾插法插入鏈表c中。當(dāng)這兩層循環(huán)結(jié)束時，集合a、b的差集運算就結(jié)束了，便得到了差集c。函數(shù)如下：status diffence(linklist &a,linklist &b,linklist &e)linklist pa=a-next,pb,s,r;/pb指向b的第一個結(jié)點，s為要插入的結(jié)點，r為掃描指針e=(linklist)malloc(sizeof(lnode);r=e;while(pa!=null)/外層循環(huán)，從首元結(jié)點開始

11、檢索表apb=b-next;while(pb!=null& datacompare(*pb,*pa)/相應(yīng)元素作比較pb=pb-next;if(pb=null)/此元素在a中/尾插法插入找到的結(jié)點s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;/外層循環(huán)的指針后移r-next=null;return ok;3.9 求布爾和。依據(jù)數(shù)學(xué)上的定義，布爾和即為兩集合的對稱差，其實質(zhì)是（a-b）u（b-a），再次轉(zhuǎn)化為（aub）-（a b ）。所以只需要對并集和交集調(diào)用求差集函數(shù)即可。4 調(diào)

12、試分析4.1 調(diào)試過程中遇到的問題死循環(huán)問題1. 在輸入合法性檢查中，輸入整數(shù)時，如果不合法，帶有其他字符，產(chǎn)生死循環(huán)。這種問題產(chǎn)生于循環(huán)體的條件是永真式，而循環(huán)體內(nèi)沒有用break語句或者其他跳出語句；2. 同樣是在輸入時造成的死循環(huán)，在while(1)中，用了break語句，但是仍然出現(xiàn)的死循環(huán)。比如用scanf(“%d”,n)=1來判斷是否輸入一個整數(shù)時，在輸入的不是合理整數(shù)的情況下，就死循環(huán)。其原因是輸入的字符存為整數(shù)不成功，它將留在輸入緩沖區(qū)，進(jìn)入下一次存儲，也不成功，就形成死循環(huán)。查閱資料可以找到一個清除輸入緩沖區(qū)的庫函數(shù)fflush(stdin)，這個函數(shù)很有效，在每次有可能在輸

13、入緩沖區(qū)殘留信息的地方調(diào)用一次該函數(shù)就可以了（部分程序如下）：while(1)if(scanf(%d,&n)=1)fflush(stdin);break;elsecout請正確輸入整數(shù)：endl;fflush(stdin);但是據(jù)網(wǎng)友細(xì)說，此函數(shù)在linux下不管用，由于本人及周邊人沒有用linux，所以未得試驗。另一種解決方案，就是自己定義一個字符數(shù)組，把多余的字符接收掉，這樣就不會影響下一次輸入。3. 對于鏈表，條件判定后，指針未后移引起的死循環(huán)。這種主要是判斷條件永真，而漏寫指針后移的語句，檢查程序可以解決。參數(shù)傳遞問題1. 如果參數(shù)是一個數(shù)組，那么形參處就寫明數(shù)組類型和數(shù)組名即可，應(yīng)為

14、數(shù)組名本來就是指向該數(shù)組首地址的一個指針。2. 如果傳遞的是二維數(shù)組，如二維字符數(shù)組，其前面的一維就是數(shù)組如 char a5，那么a1指的是一個字符數(shù)組。3. cannot convert parameter 1 from struct lnode * to struct lnode；這種問題是參數(shù)類型不一致引起的，如果類型是明顯的基本類型時一般不會出現(xiàn)這類錯誤，但是如果是自己定義的類型時，很容忽視類型而引起這類錯誤。字符串?dāng)?shù)組長度問題。我曾花了很多時間在網(wǎng)上搜索關(guān)于求字符串長度的問題，試驗過不少網(wǎng)友提供的方法，大部分人提供的是使用庫函數(shù)strlen(數(shù)組名)，但經(jīng)我試驗，這種方法是錯誤的，如

15、：char *a=111,222,3, ,fjdkal;執(zhí)行printf(“%d”,strlen(a);將得到3。這不是字符串?dāng)?shù)組的長度，其得到的是字符串?dāng)?shù)組中第一個字符串的字符個數(shù)，后來繼續(xù)搜索才找到了正確答案：sizeof(數(shù)組名)/sizeof(數(shù)組元素類型)。這個真是正確答案，我試驗過多次，下面是一個樣例:void main() char *a=111,222,3, ,fjdkal; cout sizeof(a)/sizeof(char*) endl; cout a0 endl;運行結(jié)果如下：指針問題1. 如果指針指向的結(jié)點沒有數(shù)據(jù)，而執(zhí)行輸出語句時卻用了該指針指向的結(jié)點，則會輸出一個

16、很小的負(fù)數(shù)，一看就明白不是想要的結(jié)果。2. 指針未初始化，當(dāng)程序執(zhí)行過程遇到指針未初始化語句時，將無法繼續(xù)執(zhí)行而不正常退出，典型錯誤就是把一個空指針賦值給一個空指針。4.2 算法的時間復(fù)雜度和空間復(fù)雜度分析如果不改變指針本身的值時，就不要用指向指針的指針。算法復(fù)雜度（n，m為元素個數(shù)）創(chuàng)建鏈表時，正確輸入的情況下，檢查元素是否重復(fù)為o(n2)；求并集、交集，差集和布爾和時，時間復(fù)雜度為o(m*n);由于是用鏈表來作運算的，空間上都比較合理。4.3經(jīng)驗與體會遇到問題時，可以自己改動程序，然后編譯和運行，這樣可以找到錯誤的原因；網(wǎng)絡(luò)是較好的資源，但是部分東西還需要我們自己驗證。程序出現(xiàn)問題時，可以

17、自己在程序中加入標(biāo)記，觀察程序執(zhí)行過程，找出錯誤。這次課程設(shè)計讓我的這方面的只是得到了擴(kuò)充，程序設(shè)計思路更為清楚，同時也強(qiáng)化了基礎(chǔ)，學(xué)到了不少新的知識。5 用戶使用說明1 編譯后，點擊運行，出現(xiàn)如圖5-1所示的運行界面；圖5-12 在圖5-1的情況下，用戶輸入兩個集合中第一集合的元素的個數(shù)，輸入的數(shù)必須為正整數(shù)或者0。如果用戶輸入的不是整數(shù)，系統(tǒng)會提示用戶正確輸入整數(shù)，直到用戶輸入正確后方能進(jìn)入下一步（如圖5-2）；如圖5-23 用戶輸入正確后得到如圖5-3所示界面，提示用戶輸入第一個集合的元素，元素必須含有兩個部分-整數(shù)和字符，之間沒有任何其他符號，對于用戶輸入的多余的字母，程序?qū)⒆詣犹幚淼?/p>

18、，元素之間用回車鍵，并提示用戶輸入第一個元素；圖5-34 用戶輸入一個元素，如果是按要求先整數(shù)后小寫字母，系統(tǒng)就提示輸入下一個元素（如圖5-4所示），否則提示用戶輸入正確的元素（如圖5-5所示），如過程中有重復(fù)的元素，系統(tǒng)會提示用戶重新輸入（如圖5-6所示），直到正確輸入用戶在前面輸入的元素個數(shù)，系統(tǒng)提示用戶輸入第二個集合的元素（如圖5-7），其要求和規(guī)則同第一個集合完全一樣；圖5-4圖5-5圖5-6圖5-75 當(dāng)用戶正確完成兩個集合的元素的輸入后，系統(tǒng)將直接輸出兩個集合的并集、交集、差集和布爾和，其順序依次為集合、集合、并集、用直接插入法排序后的并集、交集、用直接選擇法排序后的交集、差集、用

19、冒泡法排序后的差集、布爾和、用希爾排序后的布爾和（如圖5-8所示），之后主程序調(diào)用destroylinklist() 銷毀所有鏈表，程序到此結(jié)束。 圖5-86 測試數(shù)據(jù)與測試結(jié)果請輸入集合a的元素個數(shù)：7依次輸入：98f 56d23b78h21z98q2b請輸入集合b的元素個數(shù)：8依次輸入：56d21z78h98f36j8w1l0x得到結(jié)果：（為了盡可能顯示界面，輸入元素提示處沒有換行）參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)(c語言版). 北京：清華大學(xué)出版社，1997.042 數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析b級 第3版 清華大學(xué)出版社 李春葆 喻丹丹 編著3 數(shù)據(jù)結(jié)構(gòu)教程（第2版）清華大學(xué)出版社 李春葆

20、 等 編著4 data structures & program drsign in c,second edition 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計c語言（第二版） 清華大學(xué)出版社5 c語言程序設(shè)計 復(fù)旦大學(xué)出版社 主編 孟愛國6 7 附錄 源程序#include#include#include#define null 0 #define ok 1#define error 0typedef int status;typedef struct lnode/定義結(jié)構(gòu)體，數(shù)據(jù)域兩種類型int inte;char c;struct lnode *next;lnode,*linklist;/比較元素大小stat

21、us datacompare(lnode node1,lnode node2)/元素大小的比較：結(jié)點作參數(shù)，先比整數(shù)域，再比字母域/用點運算取結(jié)構(gòu)體的成員變量if(e)return 1;elseif(enode2.c)return 1;elseif(ode2.c)return -1;elsereturn 0;/輸入的合法性（檢查輸入元素個數(shù)與input的區(qū)分）status input1(int n)while(1)if(scanf(%d,&n)=1)fflush(stdin);break;elsecout請正確輸入整數(shù)：e

22、ndl;fflush(stdin);return n;/輸入合法性檢查status input(linklist &s)int a,x;char c;/scanf()函數(shù)的返回值進(jìn)行條件判斷if(scanf(%d,&a)=1 & scanf(%c,&c)=1)/控制字符為小寫字母if(c=97)s-inte=a;s-c=c;fflush(stdin);/清除緩沖區(qū)的一個輸入流x=1;elsecout輸入失敗,第二部分是小寫字母endl;fflush(stdin);x=-1;elsecout集合元素是先一個整數(shù)后一個小寫字母！endl;fflush(stdin);x=-1;return x;/創(chuàng)

23、建鏈表status createlinklist(linklist &l,int n)cout輸入集合元素時，整數(shù)與字母之間沒有任何符號，endl并且多余的字符將被程序處理掉，元素之間用回車鍵next=null;for(int i=0;inext)& datacompare(*p-next,*s)!=0)p=p-next;if(p-next)cout元素有重復(fù)next=s;p=p-next;p-next=null;x=ok;elsei-;x=-1;return x;/求集合并集status unionset(linklist &a,linklist &b,linklist &c)linklis

24、t pa=a-next,pb=b-next,s,r;/pb指向b的第一個結(jié)點，s為要插入的結(jié)點，r為掃描指針c=(linklist)malloc(sizeof(lnode);r=c;while(pa!=null)s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;while(pb!=null)pa=a-next;while(pa!=null & datacompare(*pa,*pb)pa=pa-next;if(pa=null)s=(linklist)malloc(sizeof(lno

25、de);s-inte=pb-inte;s-c=pb-c;r-next=s;r=s;pb=pb-next;r-next=null;return ok;/求交集status interset(linklist &a,linklist &b,linklist &d)linklist pa=a-next,pb,s,r;/pb指向b的第一個結(jié)點，s為要插入的結(jié)點，r為掃描指針d=(linklist)malloc(sizeof(lnode);r=d;while(pa!=null)pb=b-next;while(pb!=null& datacompare(*pb,*pa)pb=pb-next;if(pb!=

26、null)/此元素在a中s=(linklist)malloc(sizeof(lnode);s-c=pa-c;s-inte=pa-inte;r-next=s;r=s;pa=pa-next;r-next=null;return ok;/求集合差集status diffence(linklist &a,linklist &b,linklist &e)linklist pa=a-next,pb,s,r;/pb指向b的第一個結(jié)點，s為要插入的結(jié)點，r為掃描指針e=(linklist)malloc(sizeof(lnode);r=e;while(pa!=null)pb=b-next;while(pb!=n

27、ull& datacompare(*pb,*pa)pb=pb-next;if(pb=null)/此元素在a中s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;r-next=null;return ok;/直接插入排序status insertsort(linklist l)linklist p,r,s;p=l-next;/p掃描無序表段，r為掃描有序表段，s指向要插入的結(jié)點while(p-next)r=l;while(r-next!=p-next & datacompare(*p-n

28、ext,*r-next)0)r=r-next;if(r-next=p-next)p=p-next;elseif(r=l)/如果是在表頭后插入，則需要移動表頭指針s=p-next; p-next=p-next-next;s-next=r-next;l-next=s;else /不是在表頭插入s=p-next;p-next=p-next-next;s-next=r-next;r-next=s;return ok;/直接選擇排序status selectsort(linklist l)linklist r,s,p;/r為掃描指針，s為選中的最小結(jié)點，p指向有序段的尾指針int tempinte;ch

29、ar tempc;p=l;while(p-next)r=p;s=p-next;while(r-next)if(datacompare(*s,*(r-next)0)s=r-next;r=r-next;elser=r-next;if(s)/交換結(jié)點的數(shù)據(jù)即可tempinte=s-inte;tempc=s-c;s-inte=p-next-inte;s-c=p-next-c;p-next-inte=tempinte;p-next-c=tempc;p=p-next;return ok;/冒泡排序（大的往下沉）status bubblesort(linklist l)int tempinte;char t

30、empc;linklist p,r;/p為掃描指針，r指向有序段得頭指針r=null;for(r=null;r!=l-next;p=l-next)for(p=l-next;p-next!=null&p-next!=r;)if(datacompare(*p,*(p-next)0)tempinte=p-inte;tempc=p-c;p-inte=p-next-inte;p-c=p-next-c;p-next-inte=tempinte;p-next-c=tempc;else;p=p-next;r=p;return ok;/希爾排序status shellsort(linklist l)int i=

31、0,flag=0;linklist p,r,s;int count=0,d;/count為結(jié)點總數(shù)，d為步長p=l;while(p)/計算鏈表結(jié)點個數(shù)count+;p=p-next;for(d=count/2;d0;d=d/2)r=s=l;for(i=0;inext;for(i=0;inext;while(r)p=l;flag=0;while(flag=0)if(datacompare(*(p-next),*r)0)s-next=r-next;r-next=p-next;p-next=r;r=s-next;break;for(i=0;inext;if(p=r)|(p=null)flag=1;/標(biāo)記掃描結(jié)束break;/防止指針越界if(flag=1)&(r!=null)r=r-next;s=s-next;ret