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

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

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

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

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

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

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

7、,LinkList Head)函數(shù)。求兩個(gè)集合的差集時(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ù)。求兩個(gè)集合交集時(shí)，Insection(LinkList Head1,LinkList Head2)函數(shù)的思路同Deprive(LinkList Head1,LinkList Head2)函數(shù)類(lèi)似，它同樣也是先進(jìn)行初始化，首先調(diào)

8、用了InitLinkList(LinkList Head)函數(shù)，后面循環(huán)調(diào)用IsExist(char data,LinkList Head)函數(shù)。主函數(shù)也即main()依次調(diào)用成員函數(shù)。四詳細(xì)設(shè)計(jì)/兩個(gè)集合交集 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; /兩個(gè)集合的差集 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)試與測(cè)試分析 調(diào)試：調(diào)試過(guò)程中，雖然出現(xiàn)了不少問(wèn)題，比如說(shuō)，中英文輸入法沒(méi)有轉(zhuǎn)換，導(dǎo)致后面程序編譯時(shí)費(fèi)了好長(zhǎng)時(shí)間才找出原因；還有就是輸入時(shí)由于粗心打錯(cuò)不少字母，給調(diào)

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

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

13、的幫忙，才使得程序最后能通暢運(yùn)行。3. 對(duì)程序的設(shè)計(jì)學(xué)習(xí)還沒(méi)有很好的理解，導(dǎo)致設(shè)計(jì)過(guò)程中漏洞較多，通過(guò)老師和同學(xué)的修改才得以正常運(yùn)行。 在上機(jī)過(guò)程中還學(xué)習(xí)了很多課本上沒(méi)有的知識(shí)，實(shí)踐能力得到了大幅度的提高，程序的調(diào)試技能有所提高，但更多的是在上機(jī)過(guò)程中發(fā)現(xiàn)了很多不足之處，需要在以后的學(xué)習(xí)與工作中不斷的學(xué)習(xí)和實(shí)踐，扎扎實(shí)實(shí)的學(xué)習(xí)，一步一個(gè)腳印，積累程序設(shè)計(jì)的經(jīng)驗(yàn)和方法。8 參考文獻(xiàn) 王紅梅，數(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é)點(diǎn)該不該加入到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; /合并兩個(gè)集合 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; /兩個(gè)集合的差集 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; /兩個(gè)集合交集 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;