課程設(shè)計(jì)-圖的遍歷

1、1目目錄錄一、課題的主要功能 .21.1 設(shè)計(jì)內(nèi)容.21.2 對(duì)課程設(shè)計(jì)功能的需求分析.2二、課題的功能模塊的劃分 .22.1 模塊劃分.22.2 系統(tǒng)的概要設(shè)計(jì).3三、主要功能的實(shí)現(xiàn) .43.1 算法思想.41.圖的鄰接矩陣的建立.42.圖的遍歷的實(shí)現(xiàn).43.2 數(shù)據(jù)結(jié)構(gòu).43.3 主函數(shù)流程圖.53.4 深度優(yōu)先遍歷流程圖.63.5 深度優(yōu)先遍歷遞歸.73.6 深度優(yōu)先遍歷流程圖.93.7 廣度優(yōu)先遍歷遞歸流程圖.10四、程序調(diào)試 .114.1 程序的調(diào)試分析.114.2 程序的測(cè)試結(jié)果.11五、總結(jié) .16六、附件 .166.1 源程序.162一、課題的主要功能1.1 設(shè)計(jì)內(nèi)容設(shè)計(jì)內(nèi)容演

2、示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過(guò)程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖的結(jié)點(diǎn)數(shù)不能少于 6 個(gè)?？梢杂上到y(tǒng)隨機(jī)生成圖，也可以由用戶手動(dòng)輸入圖。報(bào)告中要寫(xiě)出畫(huà)圖的思路；畫(huà)出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。1.2 對(duì)課程設(shè)計(jì)功能的需求分析對(duì)課程設(shè)計(jì)功能的需求分析圖的遍歷并不需要是一個(gè)過(guò)于復(fù)雜的工作環(huán)境，一般來(lái)說(shuō)：最合適的才是最好的。軟件設(shè)計(jì)必須符合我們使用實(shí)際情況的需要。根據(jù)要求，圖的遍歷主要功能如下：1.用戶可以隨時(shí)建立一個(gè)有向圖或無(wú)向圖；2.用戶可以根據(jù)自己的需要，對(duì)圖進(jìn)行深度遍歷或廣度遍歷；3.用戶可以根據(jù)自己的需要對(duì)圖進(jìn)行修改；4.4.在整個(gè)程序中,用戶可以不斷的按照不同的方式

3、對(duì)圖進(jìn)行遍歷,若不繼續(xù),用戶也可以隨時(shí)跳出程序,同時(shí),如果用戶輸入的序號(hào)錯(cuò)誤,程序會(huì)提示用戶重新輸入序號(hào)；二、課題的功能模塊的劃分2.12.1 模塊劃分模塊劃分1.1.隊(duì)列的初始化、進(jìn)隊(duì)、出隊(duì)、隊(duì)列空、隊(duì)列滿的函數(shù)隊(duì)列的初始化、進(jìn)隊(duì)、出隊(duì)、隊(duì)列空、隊(duì)列滿的函數(shù)void InitQueue(CirQueue *Q) /初始化隊(duì)列int QueueEmpty(CirQueue *Q)/隊(duì)列是否為空int QueueFull(CirQueue *Q)/隊(duì)列滿Void EnQueue(CirQueue *Q,int x)/將隊(duì)員進(jìn)隊(duì)int DeQueue(CirQueue *Q)/將隊(duì)員出隊(duì)2.2.創(chuàng)

4、建圖的函數(shù)創(chuàng)建圖的函數(shù)void CreateMGraph(MGraph *G)/根據(jù)用戶需要?jiǎng)?chuàng)建一個(gè)圖3.3.圖的深度優(yōu)先遍歷遞歸圖的深度優(yōu)先遍歷遞歸void DFSM(MGraph *G,int i)/*含有輸出已訪問(wèn)的頂點(diǎn)的語(yǔ)句*/34.4.圖的廣度優(yōu)先遍歷遞歸圖的廣度優(yōu)先遍歷遞歸 void BFSM(MGraph *G,int k) /*含有輸出已訪問(wèn)的頂點(diǎn)的語(yǔ)句*/5.5.深度優(yōu)先遍歷深度優(yōu)先遍歷 void DFSTraverseM(MGraph *G)/*調(diào)用 DFSM 函數(shù)*/6.6.廣度優(yōu)先遍歷廣度優(yōu)先遍歷 void BFSTraverseM(MGraph *G) /*調(diào)用 BF

5、SM 函數(shù)*/7.7.主函數(shù)主函數(shù) main() /*包含一些調(diào)用和控制語(yǔ)句*/2.2 系統(tǒng)的概要設(shè)計(jì)系統(tǒng)的概要設(shè)計(jì)開(kāi)開(kāi) 始始信息錄入信息錄入菜單選擇菜單選擇深深度度優(yōu)優(yōu)先先修修改改信信息息廣廣度度優(yōu)優(yōu)先先退出程序退出程序4三、主要功能的實(shí)現(xiàn)3.1 算法思想算法思想本課題所采用的是鄰接矩陣的方式存儲(chǔ)圖，實(shí)現(xiàn)圖的深度、廣度兩種遍歷，并將每種遍歷結(jié)果輸出來(lái)。1.圖的鄰接矩陣的建立圖的鄰接矩陣的建立對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定） ，根據(jù)鄰接矩陣的存儲(chǔ)結(jié)構(gòu)建立圖的鄰接距陣。2.圖的遍歷的實(shí)現(xiàn)圖的遍歷的實(shí)現(xiàn)圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對(duì)于廣度優(yōu)先遍歷應(yīng)利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列

6、、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）來(lái)實(shí)現(xiàn)。首先建立一空隊(duì)列，從初始點(diǎn)出發(fā)進(jìn)行訪問(wèn)，當(dāng)被訪問(wèn)時(shí)入隊(duì)，訪問(wèn)完出隊(duì)。并以隊(duì)列是否為空作為循環(huán)控制條件。對(duì)于深度優(yōu)先遍歷則采用遞歸或非遞歸算法來(lái)實(shí)現(xiàn)，這里我所采用的是遞歸算法。3.23.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct char vexsMax; int edgesMaxMax; int n,e;5MGraph;int visitedMax;typedef struct in

7、t front; int rear; int count; int dataQueueSize;CirQueue;3.33.3 主函數(shù)流程圖主函數(shù)流程圖登陸開(kāi)始登陸開(kāi)始輸入 ch26CreateMGraph(G);Ch1=yCh1=y 真 假 0 1 2 33.4 深度優(yōu)先遍歷流程圖深度優(yōu)先遍歷流程圖Ch2Ch1=nCreateMGraph(G)DFSTraverseM(G) BFSTraverseM(G)BFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G)

8、DFSTraverseM(G)BFSTraverseM(G)B r e a k結(jié)束程序DFSTraverseM(MGraph *G)7 真 非零 零3.5 深度優(yōu)先遍歷遞歸深度優(yōu)先遍歷遞歸i=0invisitedi=FALSEi+i=0!visitediDFSM(G,i)ini+結(jié)束程序8 真 DFSM(MGraph *G,int i)visitedi=TRUEjnj=0G-edgesij=1&!visitedjDFSM(G,i)J+結(jié)束程序輸出 G-vexsi93.6 深度優(yōu)先遍歷流程圖深度優(yōu)先遍歷流程圖 真 非零 零BFSTraverseM(MGraph *G)i=0invisit

9、edi=FALSEi+i=0!visitediBFS(G,i)ini+結(jié)束程序103.7 廣度優(yōu)先遍歷遞歸流程圖廣度優(yōu)先遍歷遞歸流程圖 真 BFSM(MGraph *G,int k)InitQueue(&Q)輸出 G-vexskvisitedi=TRUEEnQueue(&Q,k)!QueueEmpty(&Q)i=DeQueue(&Q) j=0 !visitediDFSM(G,i)jni+結(jié)束程序11四、程序調(diào)試4.1 程序的調(diào)試分析程序的調(diào)試分析在調(diào)試過(guò)程中，程序中出現(xiàn)了許多的錯(cuò)誤，有錯(cuò)誤的調(diào)用,一些變量沒(méi)有定義等等。不斷的對(duì)程序進(jìn)行調(diào)試以得到最好的結(jié)果，程序中

10、特別要注意的是類(lèi)的對(duì)象作為作為參數(shù)時(shí)要注意如何去調(diào)用它，使程序有一個(gè)令人滿意的結(jié)果，具體的調(diào)試是在上機(jī)過(guò)程中進(jìn)行的，在編寫(xiě)程序的過(guò)程中主要有如下錯(cuò)誤：1.1.在編寫(xiě)程序的過(guò)程出現(xiàn)了一些函數(shù)名、變量的大小寫(xiě)不統(tǒng)一的錯(cuò)誤，導(dǎo)致程序在運(yùn)行的過(guò)程中出現(xiàn)函數(shù)名、變量沒(méi)有被定義等問(wèn)題；2.2.在編寫(xiě)程序的過(guò)程中數(shù)組的大小寫(xiě)沒(méi)有被確定；3.3.在編寫(xiě)程序的過(guò)程中一些變量沒(méi)有被定義，導(dǎo)致程序出錯(cuò)；4.4.數(shù)組 visitedMax應(yīng)定義為全局變量，若不是則會(huì)出錯(cuò)；5.5.函數(shù)的返回類(lèi)型要確定，是 void 還是其他類(lèi)型要十分注意；6.6.在編程的過(guò)程中，函數(shù)里一些控制語(yǔ)句的嵌套使用，括號(hào)要引起注意，4.2 程

11、序的測(cè)試結(jié)果程序的測(cè)試結(jié)果初始進(jìn)入程序時(shí)，程序提示按格式輸入圖的頂點(diǎn)個(gè)數(shù)和邊數(shù)。12輸入頂點(diǎn)數(shù)和邊數(shù)后，程序提示輸入頂點(diǎn)的序號(hào)，為各頂點(diǎn)依次進(jìn)行編號(hào)。將各頂點(diǎn)進(jìn)行編號(hào)后，程序提示按格式輸入邊的頂點(diǎn)序號(hào)。13 按格式依次輸入邊的頂點(diǎn)序號(hào)后，按 enter 鍵程序會(huì)出現(xiàn)“選擇菜單” ，用戶根據(jù)需要進(jìn)行選擇。用戶選擇 2 進(jìn)入深度優(yōu)先搜索，并輸出深度優(yōu)先遍歷后的序列，再次輸出菜單欄，進(jìn)行選擇。14用戶再次選擇 3 進(jìn)入廣度優(yōu)先搜索，并輸出廣度優(yōu)先遍歷后的序列，再次輸出菜單欄，進(jìn)行選擇。用戶選擇 1 后進(jìn)入更改數(shù)據(jù)，重新創(chuàng)建一個(gè)圖。15 用戶選擇 0，則退出程序。五、總結(jié)通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)踐，

12、我學(xué)到了很多東西。本次課程設(shè)計(jì)對(duì)我來(lái)說(shuō)正是一個(gè)提高自己能力的機(jī)會(huì)，我好好的抓住機(jī)會(huì)，努力做好每一步，完善每一步。自己的 C 語(yǔ)言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問(wèn)題的方法?？偨Y(jié)起來(lái)，自己主要有以下幾點(diǎn)體會(huì)：1.必須牢固掌握基礎(chǔ)知識(shí)。由于 C 語(yǔ)言是大一所學(xué)知識(shí)，有所遺忘，且未掌握好上學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)這門(mén)課，所以在實(shí)踐之初感到棘手。不知如何下手，但在后來(lái)的實(shí)習(xí)過(guò)程中自己通過(guò)看書(shū)和課外資料，并請(qǐng)教其他同學(xué)，慢慢地對(duì) C 語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)知識(shí)有所熟悉，這時(shí)才逐漸有了思路。所以今后一定要牢固掌握好專(zhuān)業(yè)基礎(chǔ)知識(shí)。2.必須培養(yǎng)嚴(yán)謹(jǐn)?shù)膽B(tài)度。自己在編程時(shí)經(jīng)常因?yàn)橐恍┬″e(cuò)

13、誤而導(dǎo)致出現(xiàn)問(wèn)題，不夠認(rèn)真細(xì)致，這給自己帶來(lái)了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)膽B(tài)度。我想這不僅是對(duì)于程序設(shè)計(jì)，做任何事都應(yīng)如16此。3.這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)這門(mén)課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路，不至于無(wú)章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。在實(shí)踐過(guò)程中，我遇到了許多困難，但都一一克服了。最終我圓滿的完成此次課程設(shè)計(jì)，學(xué)到了很多東西。同時(shí)，程序還存在著一些缺陷，我會(huì)繼續(xù)努力思考，完善程序，做到最好?？偟膩?lái)說(shuō)，本次課程設(shè)計(jì)，不僅我的知識(shí)面有所提高，另外我的綜合素質(zhì)也有所提高，這次課程設(shè)計(jì)為我以后更好的學(xué)習(xí)和使用

14、 c 語(yǔ)言打下了基礎(chǔ)。六、附件6.1 源程序源程序#include#include#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct char vexsMax; int edgesMaxMax; int n,e;MGraph;/*以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)*/int visitedMax;/*將 visitedMax定義為全局變量并分配最大空間*/typedef struct 17 int front; int rear; int count; int

15、 dataQueueSize;CirQueue;/*定義隊(duì)列的數(shù)據(jù)結(jié)構(gòu)*/初始化隊(duì)列 void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0;/隊(duì)列空int QueueEmpty(CirQueue *Q) return Q-count=QueueSize;/*返回隊(duì)列的最大長(zhǎng)度*/ /隊(duì)列滿int QueueFull(CirQueue *Q) return Q-count=QueueSize;/*返回隊(duì)列的最大長(zhǎng)度*/ /進(jìn)隊(duì)void EnQueue(CirQueue *Q,int x) if(QueueFull(Q)/*隊(duì)列滿則出錯(cuò)*/

16、 Error(Queue overflow);18 else Q-count+;/*否則 count+，將 x 進(jìn)隊(duì)*/ Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; /出隊(duì)int DeQueue(CirQueue *Q) int temp;/*定義整型的變量*/ if(QueueEmpty(Q)/*若為真則出錯(cuò)*/ Error(Queue underflow); else/*為假則 count-，將隊(duì)員出隊(duì)*/ temp=Q-dataQ-front;/*用 temp 返回其值*/ Q-count-; Q-front=(Q-front+1)%Queu

17、eSize; return temp;/*返回出隊(duì)元素值*/ /建立一個(gè)圖void CreateMGraph(MGraph *G) int i,j,k;/*定義整型變量*/ char ch1,ch2;/*定義字符型變量*/ printf(n 請(qǐng)輸入頂點(diǎn)數(shù)，邊數(shù)（格式：3，4）:);19 scanf(%d,%d,&(G-n),&(G-e);/*輸入圖的頂點(diǎn)數(shù)和邊數(shù)*/ for(i=0;in;i+) getchar(); printf(n 請(qǐng)輸入第%d 個(gè)頂點(diǎn)序號(hào),i+1); scanf(%c,&(G-vexsi);/*輸入頂點(diǎn)的序號(hào)*/ for(i=0;in;i+) fo

18、r(j=0;jn;j+) G-edgesij=0;/*初始化矩陣*/ for(k=0;ke;k+) getchar(); printf(n 請(qǐng)輸入第%d 條邊的頂點(diǎn)序號(hào)（格式：i，j）:,k+1); scanf(%c,%c,&ch1,&ch2);/*輸入邊的頂點(diǎn)序號(hào)*/ for(i=0;ch1!=G-vexsi;i+); for(j=0;ch2!=G-vexsj;j+); G-edgesij=1;/*有邊則賦值為 1*/ /深度優(yōu)先遍歷遞歸 void DFSM(MGraph *G,int i) int j; printf(%c ,G-vexsi); visitedi=TRUE;

19、/*標(biāo)記 visitedi*/ /*依次優(yōu)先搜索訪問(wèn) visitedi的每個(gè)鄰接點(diǎn)*/20for(j=0;jn;j+) /*若 visitedi的一個(gè)有效鄰接點(diǎn) visitedj未被訪問(wèn)過(guò)，則從 visitedj出發(fā)進(jìn)行遞歸調(diào)用*/ if(G-edgesij=1&!visitedj) DFSM(G,j); /廣度優(yōu)先遍歷遞歸void BFSM(MGraph *G,int k) int i,j; CirQueue Q;/*定義一個(gè)隊(duì)列 Q，初始化隊(duì)列為空*/ InitQueue(&Q); printf(%c ,G-vexsk);/*訪問(wèn)初始點(diǎn)，并將其標(biāo)記已訪問(wèn)過(guò)*/ visite

20、dk=TRUE; EnQueue(&Q,k);/*將以訪問(wèn)過(guò)的初始點(diǎn)序號(hào) k 入隊(duì)*/ while(!QueueEmpty(&Q)/*隊(duì)列非空進(jìn)行循環(huán)處理*/ i=DeQueue(&Q);/*將隊(duì)首元素出隊(duì)*/ for(j=0;jn;j+)/*依次搜索 vexsk的每一個(gè)可能的鄰接點(diǎn)*/ if(G-edgesij=1 &! visitedj) visitedj=TRUE;/*標(biāo)記 vexsj已訪問(wèn)過(guò)*/ EnQueue(&Q,j);/*頂點(diǎn)序號(hào) j 入隊(duì)*/ /深度優(yōu)先遍歷void DFSTraverseM(MGraph *G)21 int i; pri

21、ntf(n 深度優(yōu)先遍歷序列:);for(i=0;in;i+) visitedi=FALSE;/*訪問(wèn)標(biāo)志數(shù)組初始化*/ for(i=0;in;i+) if(!visitedi)/*對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用 DFSM*/ DFSM(G,i); /廣度優(yōu)先遍歷void BFSTraverseM(MGraph *G) int i; printf(n 廣度優(yōu)先遍歷序列:);for(i=0;in;i+) visitedi=FALSE;/*訪問(wèn)標(biāo)志數(shù)組初始化*/ for(i=0;in;i+) if(!visitedi)/*對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用 BFSM*/ BFSM(G,i); 22 main() MGraph *G,a; char ch1; int i,j,ch2; G=&a;printf(ntt 深度優(yōu)先搜索和廣度優(yōu)先搜索 n); CreateMGraph(G);/*調(diào)用創(chuàng)建圖矩陣