1、-作者xxxx-日期xxxx課程設計-圖的遍歷【精品文檔】目錄一、課題的主要功能2設計內容2對課程設計功能的需求分析2二、課題的功能模塊的劃分2模塊劃分2系統的概要設計3三、主要功能的實現4算法思想41.圖的鄰接矩陣的建立42.圖的遍歷的實現4數據結構4主函數流程圖5深度優先遍歷流程圖6深度優先遍歷遞歸7深度優先遍歷流程圖9廣度優先遍歷遞歸流程圖10四、程序調試11程序的調試分析11程序的測試結果11五、總結16六、附件16源程序16一、課題的主要功能設計內容演示圖的深度優先, 廣度優先遍歷過程，并輸出原圖結構及遍歷結果。要求圖的結點數不能少于6個。可以由系統隨機生成圖，也可以由用戶手動輸入圖

2、。報告中要寫出畫圖的思路；畫出圖的結構，有興趣的同學可以進一步改進圖的效果。圖的遍歷并不需要是一個過于復雜的工作環境，一般來說：最合適的才是最好的。軟件設計必須符合我們使用實際情況的需要。根據要求，圖的遍歷主要功能如下：1.用戶可以隨時建立一個有向圖或無向圖；2.用戶可以根據自己的需要，對圖進行深度遍歷或廣度遍歷；3.用戶可以根據自己的需要對圖進行修改；4.在整個程序中,用戶可以不斷的按照不同的方式對圖進行遍歷,若不繼續,用戶也可以隨時跳出程序,同時,如果用戶輸入的序號錯誤,程序會提示用戶重新輸入序號；二、課題的功能模塊的劃分2.1模塊劃分1.隊列的初始化、進隊、出隊、隊列空、隊列滿的函數vo

3、id InitQueue(CirQueue *Q) /初始化隊列int QueueEmpty(CirQueue *Q)/隊列是否為空int QueueFull(CirQueue *Q)/隊列滿Void EnQueue(CirQueue *Q,int x)/將隊員進隊int DeQueue(CirQueue *Q)/將隊員出隊2.創建圖的函數void CreateMGraph(MGraph *G)/根據用戶需要創建一個圖3.圖的深度優先遍歷遞歸void DFSM(MGraph *G,int i)/*含有輸出已訪問的頂點的語句*/4.圖的廣度優先遍歷遞歸 void BFSM(MGraph *G,i

4、nt k) /*含有輸出已訪問的頂點的語句*/5.深度優先遍歷 void DFSTraverseM(MGraph *G)/*調用DFSM函數*/6.廣度優先遍歷 void BFSTraverseM(MGraph *G) /*調用BFSM函數*/7.主函數 main() /*包含一些調用和控制語句*/2.2系統的概要設計開 始信息錄入菜單選擇深度優先修改信息廣度優先退出程序三、主要功能的實現3.1算法思想本課題所采用的是鄰接矩陣的方式存儲圖，實現圖的深度、廣度兩種遍歷，并將每種遍歷結果輸出來。對任意給定的圖（頂點數和邊數自定），根據鄰接矩陣的存儲結構建立圖的鄰接距陣。圖的遍歷包括圖的廣度優先遍歷

5、與深度優先遍歷。對于廣度優先遍歷應利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）來實現。首先建立一空隊列，從初始點出發進行訪問，當被訪問時入隊，訪問完出隊。并以隊列是否為空作為循環控制條件。對于深度優先遍歷則采用遞歸或非遞歸算法來實現，這里我所采用的是遞歸算法。3.2數據結構#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct char vexsMax; int edgesMaxMax; int n,e;MGraph;int visi

6、tedMax;typedef struct int front; int rear; int count; int dataQueueSize;CirQueue;3.3主函數流程圖輸入ch2登陸開始CreateMGraph(G);Ch1=yCh1=y 真 假 Ch2 B r e a kCh1=n 0CreateMGraph(G) 1DFSTraverseM(G) BFSTraverseM(G)BFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G) DFSTraverseM(G)DFSTrav

7、erseM(G) 2 BFSTraverseM(G) 3結束程序DFSTraverseM(MGraph *G)i=0i<G->nvisitedi=FALSEi+i=0 i<G->n 真!visitedi i+ 非零 零DFSM(G,i)結束程序DFSM(MGraph *G,int i) 輸出G->vexsivisitedi=TRUE j=0 j<G->n 真 G->edgesij=1&&!visitedjDFSM(G,i)J+結束程序BFSTraverseM(MGraph *G)i=0i<G->nvisitedi=FA

8、LSEi+i=0 i<G->n 真!visitedi i+ 非零 零BFS(G,i)結束程序i=DeQueue(&Q) j=0 !QueueEmpty(&Q)EnQueue(&Q,k)visitedi=TRUE輸出G->vexskInitQueue(&Q)BFSM(MGraph *G,int k) j<G->n 真!visitedi DFSM(G,i)i+結束程序四、程序調試4.1程序的調試分析在調試過程中，程序中出現了許多的錯誤，有錯誤的調用,一些變量沒有定義等等。不斷的對程序進行調試以得到最好的結果，程序中特別要注意的是類的對象

9、作為作為參數時要注意如何去調用它，使程序有一個令人滿意的結果，具體的調試是在上機過程中進行的，在編寫程序的過程中主要有如下錯誤：1.在編寫程序的過程出現了一些函數名、變量的大小寫不統一的錯誤，導致程序在運行的過程中出現函數名、變量沒有被定義等問題；2.在編寫程序的過程中數組的大小寫沒有被確定；3.在編寫程序的過程中一些變量沒有被定義，導致程序出錯；4.數組visitedMax應定義為全局變量，若不是則會出錯；5.函數的返回類型要確定，是void還是其他類型要十分注意；6.在編程的過程中，函數里一些控制語句的嵌套使用，括號要引起注意，4.2程序的測試結果初始進入程序時，程序提示按格式輸入圖的頂點

10、個數和邊數。輸入頂點數和邊數后，程序提示輸入頂點的序號，為各頂點依次進行編號。將各頂點進行編號后，程序提示按格式輸入邊的頂點序號。 按格式依次輸入邊的頂點序號后，按enter鍵程序會出現“選擇菜單”，用戶根據需要進行選擇。用戶選擇2進入深度優先搜索，并輸出深度優先遍歷后的序列，再次輸出菜單欄，進行選擇。用戶再次選擇3進入廣度優先搜索，并輸出廣度優先遍歷后的序列，再次輸出菜單欄，進行選擇。用戶選擇1后進入更改數據，重新創建一個圖。 用戶選擇0，則退出程序。五、總結通過這次數據結構課程設計實踐，我學到了很多東西。本次課程設計對我來說正是一個提高自己能力的機會，我好好的抓住機會，努力做好每一步，完善

11、每一步。自己的C語言知識和數據結構知識得到了鞏固，編程能力也有了一定的提高。同時也學會了解決問題的方法?？偨Y起來，自己主要有以下幾點體會：1.必須牢固掌握基礎知識。由于C語言是大一所學知識，有所遺忘，且未掌握好上學期所學的數據結構這門課，所以在實踐之初感到棘手。不知如何下手，但在后來的實習過程中自己通過看書和課外資料，并請教其他同學，慢慢地對C語言和數據結構知識有所熟悉，這時才逐漸有了思路。所以今后一定要牢固掌握好專業基礎知識。2.必須培養嚴謹的態度。自己在編程時經常因為一些小錯誤而導致出現問題，不夠認真細致，這給自己帶來了許多麻煩。編程是一件十分嚴謹的事情，容不得馬虎。所以在今后自己一定要培

12、養嚴謹的態度。我想這不僅是對于程序設計，做任何事都應如此。3.這次課程設計也讓我充分認識到數據結構這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應用。在實踐過程中，我遇到了許多困難，但都一一克服了。最終我圓滿的完成此次課程設計，學到了很多東西。同時，程序還存在著一些缺陷，我會繼續努力思考，完善程序，做到最好。總的來說，本次課程設計，不僅我的知識面有所提高，另外我的綜合素質也有所提高，這次課程設計為我以后更好的學習和使用c語言打下了基礎。六、附件#include<stdio.h>#include<stdlib.h>

13、#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct char vexsMax; int edgesMaxMax; int n,e;MGraph;/*以鄰接矩陣作為圖的存儲結構*/int visitedMax;/*將visitedMax定義為全局變量并分配最大空間*/typedef struct int front; int rear; int count; int dataQueueSize;CirQueue;/*定義隊列的數據結構*/初始化隊列 vo

14、id InitQueue(CirQueue *Q) Q->front=Q->rear=0; Q->count=0;/隊列空int QueueEmpty(CirQueue *Q) return Q->count=QueueSize;/*返回隊列的最大長度*/ /隊列滿int QueueFull(CirQueue *Q) return Q->count=QueueSize;/*返回隊列的最大長度*/ /進隊void EnQueue(CirQueue *Q,int x) if(QueueFull(Q)/*隊列滿則出錯*/ Error("Queue overfl

15、ow"); else Q->count+;/*否則count+，將x進隊*/ Q->dataQ->rear=x; Q->rear=(Q->rear+1)%QueueSize; /出隊int DeQueue(CirQueue *Q) int temp;/*定義整型的變量*/ if(QueueEmpty(Q)/*若為真則出錯*/ Error("Queue underflow"); else/*為假則count-，將隊員出隊*/ temp=Q->dataQ->front;/*用temp返回其值*/ Q->count-; Q

16、->front=(Q->front+1)%QueueSize; return temp;/*返回出隊元素值*/ /建立一個圖void CreateMGraph(MGraph *G) int i,j,k;/*定義整型變量*/ char ch1,ch2;/*定義字符型變量*/ printf("n請輸入頂點數，邊數（格式：3，4）:"); scanf("%d,%d",&(G->n),&(G->e);/*輸入圖的頂點數和邊數*/ for(i=0;i<G->n;i+) getchar(); printf(&quo

17、t;n請輸入第%d個頂點序號",i+1); scanf("%c",&(G->vexsi);/*輸入頂點的序號*/ for(i=0;i<G->n;i+) for(j=0;j<G->n;j+) G->edgesij=0;/*初始化矩陣*/ for(k=0;k<G->e;k+) getchar(); printf("n請輸入第%d條邊的頂點序號（格式：i，j）:",k+1); scanf("%c,%c",&ch1,&ch2);/*輸入邊的頂點序號*/ for(

18、i=0;ch1!=G->vexsi;i+); for(j=0;ch2!=G->vexsj;j+); G->edgesij=1;/*有邊則賦值為1*/ /深度優先遍歷遞歸 void DFSM(MGraph *G,int i) int j; printf("%c ",G->vexsi); visitedi=TRUE;/*標記visitedi*/ /*依次優先搜索訪問visitedi的每個鄰接點*/for(j=0;j<G->n;j+) /*若visitedi的一個有效鄰接點visitedj未被訪問過，則從visitedj出發進行遞歸調用*/ i

19、f(G->edgesij=1&&!visitedj) DFSM(G,j); /廣度優先遍歷遞歸void BFSM(MGraph *G,int k) int i,j; CirQueue Q;/*定義一個隊列Q，初始化隊列為空*/ InitQueue(&Q); printf("%c ",G->vexsk);/*訪問初始點，并將其標記已訪問過*/ visitedk=TRUE; EnQueue(&Q,k);/*將以訪問過的初始點序號k入隊*/ while(!QueueEmpty(&Q)/*隊列非空進行循環處理*/ i=DeQueu

20、e(&Q);/*將隊首元素出隊*/ for(j=0;j<G->n;j+)/*依次搜索vexsk的每一個可能的鄰接點*/ if(G->edgesij=1 &&! visitedj) visitedj=TRUE;/*標記vexsj已訪問過*/ EnQueue(&Q,j);/*頂點序號j入隊*/ /深度優先遍歷void DFSTraverseM(MGraph *G) int i; printf("n 深度優先遍歷序列:");for(i=0;i<G->n;i+) visitedi=FALSE;/*訪問標志數組初始化*/

21、for(i=0;i<G->n;i+) if(!visitedi)/*對尚未訪問的頂點調用DFSM*/ DFSM(G,i); /廣度優先遍歷void BFSTraverseM(MGraph *G) int i; printf("n 廣度優先遍歷序列:");for(i=0;i<G->n;i+) visitedi=FALSE;/*訪問標志數組初始化*/ for(i=0;i<G->n;i+) if(!visitedi)/*對尚未訪問的頂點調用BFSM*/ BFSM(G,i); main() MGraph *G,a; char ch1; int i,j,ch2; G=&a;printf("ntt 深度優先搜索和廣度優先搜索 n"); CreateMGraph(G);/*調用創建圖矩陣的函數*/ getchar(); ch1='y'/*設置控制語句標志*/ while(ch1='y'|ch1='Y') /*菜單欄*/ printf("n"); printf(" 選擇菜單"); printf("ntt*n&qu