集合的交并差設(shè)計文檔

1、蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 專 業(yè)：xxxxxxxxx 姓 名：xxxxxxxxx 學(xué) 號：xxxxxxxxxx 指導(dǎo)老師：xxxxxxxxx 時 間：2011-7-9目 錄一實習(xí)目的.3二需求分析.31問題描述 2基本功能 3輸入和輸出三概要設(shè)計.31數(shù)據(jù)結(jié)構(gòu)設(shè)計2存儲結(jié)構(gòu)設(shè)計3系統(tǒng)中子程序及功能4各程序模塊之間的調(diào)用關(guān)系四詳細(xì)設(shè)計.5五調(diào)試與測試分析.71調(diào)試2測試六使用說明.9七總結(jié)和心得.9八參考文獻.9九附錄.9集合的交、并和差運算的實現(xiàn)一實習(xí)目的 1.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；2. 初步掌握程序設(shè)計過程中的結(jié)構(gòu)化程序設(shè)計的

2、一般方法，及數(shù)據(jù)類型在設(shè)計中的應(yīng)用。 3.能夠利用所學(xué)的基本知識和技能，解決簡單的程序設(shè)計問題；4. 培養(yǎng)了我們的團隊合作精神，培養(yǎng)了我們對面向?qū)ο蟾呒壵Z言的編寫能力，從而提高我們的編程綜合能力。5. 學(xué)會用有序表和集合對集合的并、交和差運算。二需求分析 1問題描述：用有序單鏈表表示集合，實現(xiàn)集合的交、并、差運算,且空間復(fù)雜度為O(1) 2基本功能：可快速的分別求出兩個字符集合的交、并、差。 3輸入和輸出：（1）輸入：在C+環(huán)境下編寫的程序，其輸入是簡單、方便的，即 按提示分別輸入兩集合的元素。l 輸入字符的范圍：小寫字母a,b,.,y,z,大寫字母A,B,.Y，Z，和數(shù)字0,1，.8,9;l

3、 輸入形式：字符集合，按順序大小排序輸入，允許出現(xiàn)重復(fù)字符，程序能自動濾去；（2）輸出：程序采用單鏈表的存儲結(jié)構(gòu)，使得運算快捷簡便，顯示的結(jié)果也明了。 輸出結(jié)果不含重復(fù)或非法字符；三概要設(shè)計 1數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)對象：屬于同一個結(jié)構(gòu)體的集合。數(shù)據(jù)關(guān)系：具有線性關(guān)系?；静僮鳎海?） InitLinkList(LinkList Head)：初始化集合（2） Check(char ch,LinkList Head)：檢查p1或p2所指向數(shù)據(jù)結(jié)點該不該加入到Head為起始的集合中（3）Merge(LinkList Head1,LinkList Head2)：合并兩個集合 （4）IsExist(char

4、 data,LinkList Head)； IsExist2(char data,LinkList Head)：集合A中的元素，B中是否存在（5）Deprive(LinkList Head1,LinkList Head2)：兩個集合的差集 （6）Insection(LinkList Head1,LinkList Head2)：兩個集合交集（7）PrintLinkList(LinkList Head)：打印集合元素 2存儲結(jié)構(gòu)設(shè)計typedef struct Node char data; Node *next; Node,*LinkList; 該存儲結(jié)構(gòu)不要求邏輯上相鄰的結(jié)點在其物理位置上也相

5、鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此存儲結(jié)構(gòu)采用的是鏈接存儲結(jié)構(gòu)。 3系統(tǒng)中子程序及功能（1） void InitLinkList(LinkList Head)； /初始化集合（2） int Check(char ch,LinkList Head)； /檢查p1或p2所指向數(shù)據(jù)結(jié)點該不該加入到Head為起始的集合中（3）LinkList Merge(LinkList Head1,LinkList Head2)； /合并兩個集合 （4）int IsExist(char data,LinkList Head)； int IsExist2(char data,LinkList Head

6、)； /集合A中的元素，B中是否存在（5）LinkList Deprive(LinkList Head1,LinkList Head2)； /兩個集合的差集 （6）LinkList Insection(LinkList Head1,LinkList Head2)； /兩個集合交集（7）void PrintLinkList(LinkList Head)； /打印集合元素 4各程序模塊之間的調(diào)用關(guān)系求兩個集合的并集時，Merge(LinkList Head1,LinkList Head2)函數(shù)首先調(diào)用了InitLinkList(LinkList Head)函數(shù)，多次調(diào)用了Check(char ch

7、,LinkList Head)函數(shù)。求兩個集合的差集時，Deprive(LinkList Head1,LinkList Head2)函數(shù)同Merge(LinkList Head1,LinkList Head2)函數(shù)一樣首先也調(diào)用了InitLinkList(LinkList Head)函數(shù)，后面循環(huán)調(diào)用IsExist2(char data,LinkList Head)函數(shù)。求兩個集合交集時，Insection(LinkList Head1,LinkList Head2)函數(shù)的思路同Deprive(LinkList Head1,LinkList Head2)函數(shù)類似，它同樣也是先進行初始化，首先調(diào)

8、用了InitLinkList(LinkList Head)函數(shù)，后面循環(huán)調(diào)用IsExist(char data,LinkList Head)函數(shù)。主函數(shù)也即main()依次調(diào)用成員函數(shù)。四詳細(xì)設(shè)計/兩個集合交集 LinkList Insection(LinkList Head1,LinkList Head2) Node *p1=Head1->next; /Node *p2=Head2->next; LinkList Head=(Node*)malloc(SIZE); Head->data='0'Head->next=NULL; Node *p=Head;

9、 while(p1!=NULL) if(IsExist(p1->data,Head2)=1) Node *newNode=(Node*)malloc(SIZE); newNode->data=p1->data; p->next=newNode; p=newNode; p->next=NULL; p1=p1->next; return Head; /兩個集合的差集 LinkList Deprive(LinkList Head1,LinkList Head2) LinkList Head=(Node*)malloc(SIZE); Node *p=Head; No

10、de *p1=Head1->next; while(p1!=NULL) if(IsExist2(p1->data,Head2)=1) Node *newNode=(Node*)malloc(SIZE); newNode->data=p1->data; p->next=newNode; p=newNode; p->next=NULL; p1=p1->next; return Head; 四 調(diào)試與測試分析 調(diào)試：調(diào)試過程中，雖然出現(xiàn)了不少問題，比如說，中英文輸入法沒有轉(zhuǎn)換，導(dǎo)致后面程序編譯時費了好長時間才找出原因；還有就是輸入時由于粗心打錯不少字母，給調(diào)

11、試也帶來了不少麻煩；等等。不過，其中最令我頭疼的是指針問題，指針沒有經(jīng)過初始化，導(dǎo)致程序停止正常工作，而且原因不好發(fā)現(xiàn)（如下圖所示）：指針未經(jīng)初始化還有一個致命的問題就是，運用指針不熟練，或者可以稱為沒有理解指針的真正精髓所在，導(dǎo)致所寫程序一次次通不過編譯，不過，好在圖書館里有不少經(jīng)典書籍，經(jīng)過幾天奮戰(zhàn)，終于把指針理解了。 測試結(jié)果： 六使用說明1.按屏幕提示輸入字符串1的元素，輸入完成后輸入“#”，回車后輸入字符串2，并按“#”后，再按回車鍵，即出現(xiàn)運算結(jié)果；2.按屏幕提示輸入選擇是否繼續(xù)，如果繼續(xù)，則重復(fù)第一步，否則結(jié)束；3.演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示

12、信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；相應(yīng)的輸入數(shù)據(jù)和運算結(jié)果顯示在其后。七總結(jié)和心得通過本次上機實驗，使我掌握了C+面向?qū)ο蟪绦虻幕静僮鳎谏蠙C實踐過程中，編程水平得到了進一步提升實踐能力得到了加強與鍛煉。全面掌握C+面向?qū)ο蟪绦蛟O(shè)計的方法和技術(shù)，通過課程設(shè)計我進一步理解和掌握了C+面向?qū)ο蟪绦虻囊饬x和作用，在上機實踐過程中，我也遇到了很多困難，老師和同學(xué)給了我很大的幫助。上機過程中遇到的主要問題是：1. 對一些語句的使用不太熟悉，不能夠良好的應(yīng)用，通過老師、同學(xué)的幫助了解了一部分，但還需更多的努力。2. 對程序運行的基本條件掌握不夠，在調(diào)試過程中遇到很多困難，多虧有同學(xué)

13、的幫忙，才使得程序最后能通暢運行。3. 對程序的設(shè)計學(xué)習(xí)還沒有很好的理解，導(dǎo)致設(shè)計過程中漏洞較多，通過老師和同學(xué)的修改才得以正常運行。 在上機過程中還學(xué)習(xí)了很多課本上沒有的知識，實踐能力得到了大幅度的提高，程序的調(diào)試技能有所提高，但更多的是在上機過程中發(fā)現(xiàn)了很多不足之處，需要在以后的學(xué)習(xí)與工作中不斷的學(xué)習(xí)和實踐，扎扎實實的學(xué)習(xí)，一步一個腳印，積累程序設(shè)計的經(jīng)驗和方法。8 參考文獻 王紅梅，數(shù)據(jù)結(jié)構(gòu)（C+）版九附錄源程序：#include<iostream> using namespace std; typedef struct Node char data; Node *next;

14、 Node,*LinkList; #define SIZE sizeof(Node) #define FALSE 0 #define TRUE 1 /初始化集合 void InitLinkList(LinkList Head) char ch;Node *p=Head; Head->next=NULL; Head->data='0' cin>>ch; while(ch!='#') Node *newNode=(Node*)malloc(SIZE); newNode->data=ch; p->next=newNode; p=p-

15、>next; cin>>ch; p->next=NULL; /檢查p1或p2所指向數(shù)據(jù)結(jié)點該不該加入到Head為起始的集合中int Check(char ch,LinkList Head) Node *temp=Head->next; int flag=TRUE; while(temp!=NULL) if(temp->data=ch)/不需要將數(shù)據(jù)插入 flag=FALSE; return flag; temp=temp->next; return flag; /合并兩個集合 LinkList Merge(LinkList Head1,LinkList

16、 Head2) LinkList Head=(Node*)malloc(SIZE); Head->data='0'Head->next=NULL; Node *p1=Head1->next; Node *p2=Head2->next; Node *p=Head; while(p1!=NULL&&p2!=NULL) if(p1->data=p2->data) if(Check(p1->data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode->data=p

17、1->data; p->next=newNode; p=newNode; p->next=NULL; else if(Check(p1->data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode->data=p1->data; p->next=newNode; p=newNode; p->next=NULL; if(Check(p2->data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode->data=p2-&

18、gt;data; p->next=newNode; p=newNode; p->next=NULL; p1=p1->next; p2=p2->next; while(p1!=NULL) if(Check(p1->data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode->data=p1->data; p->next=newNode; p=newNode; p->next=NULL; p1=p1->next; while(p2!=NULL) if(Check(p2->d

19、ata,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode->data=p2->data; p->next=newNode; p=newNode; p->next=NULL; p2=p2->next; return Head; /集合A中的元素，B中是否存在 int IsExist(char data,LinkList Head) Node *p=Head->next; int flag=FALSE; while(p!=NULL) if(p->data=data) return flag=TRU

20、E; p=p->next; return flag; int IsExist2(char data,LinkList Head) Node *p=Head->next; int flag=FALSE; while(p!=NULL) if(p->data=data) return flag; p=p->next; return flag=TRUE; /兩個集合的差集 LinkList Deprive(LinkList Head1,LinkList Head2) LinkList Head=(Node*)malloc(SIZE); Node *p=Head; Node *p

21、1=Head1->next; while(p1!=NULL) if(IsExist2(p1->data,Head2)=1) Node *newNode=(Node*)malloc(SIZE); newNode->data=p1->data; p->next=newNode; p=newNode; p->next=NULL; p1=p1->next; return Head; /兩個集合交集 LinkList Insection(LinkList Head1,LinkList Head2) Node *p1=Head1->next; /Node *p2=Head2->next; LinkList Head=(Node*)malloc(SIZE); Head->data='0'Head->next=NULL; Node *p=Head; while(p1!=NULL) if(IsExist(p1->data,Head2)=1) Node *newNode=(Node*)malloc(SIZE); newNode->data=p1->data; p->next=newNode; p=newNode; p->next=NULL;