1、<p><b>　　目錄</b></p><p>　　一、課題的主要功能2</p><p><b>　　1.1設(shè)計內(nèi)容2</b></p><p>　　1.2對課程設(shè)計功能的需求分析2</p><p>　　二、課題的功能模塊的劃分2</p><p><b

2、>　　2.1模塊劃分2</b></p><p>　　2.2系統(tǒng)的概要設(shè)計3</p><p>　　三、主要功能的實現(xiàn)4</p><p><b>　　3.1算法思想4</b></p><p>　　1.圖的鄰接矩陣的建立4</p><p>　　2.圖的遍歷的實現(xiàn)4</

3、p><p><b>　　3.2數(shù)據(jù)結(jié)構(gòu)4</b></p><p>　　3.3主函數(shù)流程圖5</p><p>　　3.4深度優(yōu)先遍歷流程圖6</p><p>　　3.5深度優(yōu)先遍歷遞歸7</p><p>　　3.6深度優(yōu)先遍歷流程圖9</p><p>　　3.7廣度優(yōu)先

4、遍歷遞歸流程圖10</p><p><b>　　四、程序調(diào)試11</b></p><p>　　4.1程序的調(diào)試分析11</p><p>　　4.2程序的測試結(jié)果11</p><p><b>　　五、總結(jié)16</b></p><p><b>　　六、附件1

5、6</b></p><p><b>　　6.1源程序16</b></p><p><b>　　一、課題的主要功能</b></p><p><b>　　1.1設(shè)計內(nèi)容</b></p><p>　　演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖

6、的結(jié)點數(shù)不能少于6個?？梢杂上到y(tǒng)隨機生成圖，也可以由用戶手動輸入圖。報告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學可以進一步改進圖的效果。</p><p>　　1.2對課程設(shè)計功能的需求分析</p><p>　　圖的遍歷并不需要是一個過于復(fù)雜的工作環(huán)境，一般來說：最合適的才是最好的。軟件設(shè)計必須符合我們使用實際情況的需要。根據(jù)要求，圖的遍歷主要功能如下：</p><

7、p>　　1.用戶可以隨時建立一個有向圖或無向圖；</p><p>　　2.用戶可以根據(jù)自己的需要，對圖進行深度遍歷或廣度遍歷；</p><p>　　3.用戶可以根據(jù)自己的需要對圖進行修改；</p><p>　　4.在整個程序中,用戶可以不斷的按照不同的方式對圖進行遍歷,若不繼續(xù),用戶也可以隨時跳出程序,同時,如果用戶輸入的序號錯誤,程序會提示用戶重新輸入序號；

8、</p><p>　　二、課題的功能模塊的劃分</p><p><b>　　2.1模塊劃分</b></p><p>　　1.隊列的初始化、進隊、出隊、隊列空、隊列滿的函數(shù)</p><p>　　void InitQueue(CirQueue *Q) //初始化隊列</p><p>　　int Qu

9、eueEmpty(CirQueue *Q)//隊列是否為空</p><p>　　int QueueFull(CirQueue *Q)//隊列滿</p><p>　　Void EnQueue(CirQueue *Q,int x)//將隊員進隊</p><p>　　int DeQueue(CirQueue *Q)//將隊員出隊</p><p&g

10、t;<b>　　2.創(chuàng)建圖的函數(shù)</b></p><p>　　void CreateMGraph(MGraph *G)//根據(jù)用戶需要創(chuàng)建一個圖</p><p>　　3.圖的深度優(yōu)先遍歷遞歸</p><p>　　void DFSM(MGraph *G,int i)/*含有輸出已訪問的頂點的語句*/</p><p>　　4

11、.圖的廣度優(yōu)先遍歷遞歸 </p><p>　　void BFSM(MGraph *G,int k) /*含有輸出已訪問的頂點的語句*/</p><p><b>　　5.深度優(yōu)先遍歷 </b></p><p>　　void DFSTraverseM(MGraph *G)/*調(diào)用DFSM函數(shù)*/</p><p><b&

12、gt;　　6.廣度優(yōu)先遍歷 </b></p><p>　　void BFSTraverseM(MGraph *G) /*調(diào)用BFSM函數(shù)*/</p><p><b>　　7.主函數(shù) </b></p><p>　　main() /*包含一些調(diào)用和控制語句*/</p><p>　　2.2系統(tǒng)的概要設(shè)計</

13、p><p><b>　　三、主要功能的實現(xiàn)</b></p><p><b>　　3.1算法思想</b></p><p>　　本課題所采用的是鄰接矩陣的方式存儲圖，實現(xiàn)圖的深度、廣度兩種遍歷，并將每種遍歷結(jié)果輸出來。</p><p>　　1.圖的鄰接矩陣的建立</p><p>　　

14、對任意給定的圖（頂點數(shù)和邊數(shù)自定），根據(jù)鄰接矩陣的存儲結(jié)構(gòu)建立圖的鄰接距陣。</p><p><b>　　2.圖的遍歷的實現(xiàn)</b></p><p>　　圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對于廣度優(yōu)先遍歷應(yīng)利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）來實現(xiàn)。首先建立一空隊列，從初始點出發(fā)進行訪問，當被訪問時入隊，訪問完出隊。并以隊列是否

15、為空作為循環(huán)控制條件。對于深度優(yōu)先遍歷則采用遞歸或非遞歸算法來實現(xiàn)，這里我所采用的是遞歸算法。</p><p><b>　　3.2數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　#define Max 10</p><p>　　#define FALSE 0</p><p>　　#define TRUE 1</p>

16、<p>　　#define Error printf</p><p>　　#define QueueSize 30</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　char vexs[Max];</p><p>　　int

17、edges[Max][Max];</p><p><b>　　int n,e;</b></p><p><b>　　}MGraph;</b></p><p>　　int visited[Max];</p><p>　　typedef struct </p><p><b

18、>　　{</b></p><p>　　int front;</p><p><b>　　int rear;</b></p><p>　　int count;</p><p>　　int data[QueueSize];</p><p>　　}CirQueue;</p>

19、<p><b>　　3.3主函數(shù)流程圖</b></p><p>　　假 </p><p><b>　　0</b></p><p><b>　　1</b></p>

20、<p><b>　　2 </b></p><p><b>　　3</b></p><p>　　3.4深度優(yōu)先遍歷流程圖</p><p><b>　　真</b></p><p>　　非零 零</p><p>　　3.

21、5深度優(yōu)先遍歷遞歸</p><p>　　真 </p><p>　　3.6深度優(yōu)先遍歷流程圖</p><p><b>　　真</b></p><p>　　非零 零</p><p>　　3.7廣度優(yōu)先遍歷遞歸流程圖<

22、/p><p><b>　　真</b></p><p><b>　　四、程序調(diào)試</b></p><p>　　4.1程序的調(diào)試分析</p><p>　　在調(diào)試過程中，程序中出現(xiàn)了許多的錯誤，有錯誤的調(diào)用,一些變量沒有定義等等。不斷的對程序進行調(diào)試以得到最好的結(jié)果，程序中特別要注意的是類的對象作為作為參數(shù)時

23、要注意如何去調(diào)用它，使程序有一個令人滿意的結(jié)果，具體的調(diào)試是在上機過程中進行的，在編寫程序的過程中主要有如下錯誤：</p><p>　　1.在編寫程序的過程出現(xiàn)了一些函數(shù)名、變量的大小寫不統(tǒng)一的錯誤，導(dǎo)致程序在運行的過程中出現(xiàn)函數(shù)名、變量沒有被定義等問題；</p><p>　　2.在編寫程序的過程中數(shù)組的大小寫沒有被確定；</p><p>　　3.在編寫程序的過程中

24、一些變量沒有被定義，導(dǎo)致程序出錯；</p><p>　　4.數(shù)組visited[Max]應(yīng)定義為全局變量，若不是則會出錯；</p><p>　　5.函數(shù)的返回類型要確定，是void還是其他類型要十分注意；</p><p>　　6.在編程的過程中，函數(shù)里一些控制語句的嵌套使用，括號要引起注意，</p><p>　　4.2程序的測試結(jié)果</

25、p><p>　　初始進入程序時，程序提示按格式輸入圖的頂點個數(shù)和邊數(shù)。</p><p>　　輸入頂點數(shù)和邊數(shù)后，程序提示輸入頂點的序號，為各頂點依次進行編號。</p><p>　　將各頂點進行編號后，程序提示按格式輸入邊的頂點序號。</p><p>　　按格式依次輸入邊的頂點序號后，按enter鍵程序會出現(xiàn)“選擇菜單”，用戶根據(jù)需要進行選擇。&l

26、t;/p><p>　　用戶選擇2進入深度優(yōu)先搜索，并輸出深度優(yōu)先遍歷后的序列，再次輸出菜單欄，進行選擇。</p><p>　　用戶再次選擇3進入廣度優(yōu)先搜索，并輸出廣度優(yōu)先遍歷后的序列，再次輸出菜單欄，進行選擇。</p><p>　　用戶選擇1后進入更改數(shù)據(jù)，重新創(chuàng)建一個圖。</p><p>　　用戶選擇0，則退出程序。</p>&

27、lt;p><b>　　五、總結(jié)</b></p><p>　　通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實踐，我學到了很多東西。本次課程設(shè)計對我來說正是一個提高自己能力的機會，我好好的抓住機會，努力做好每一步，完善每一步。自己的C語言知識和數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固，編程能力也有了一定的提高。同時也學會了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點體會：</p><p>　　1.必須牢

28、固掌握基礎(chǔ)知識。由于C語言是大一所學知識，有所遺忘，且未掌握好上學期所學的《數(shù)據(jù)結(jié)構(gòu)》這門課，所以在實踐之初感到棘手。不知如何下手，但在后來的實習過程中自己通過看書和課外資料，并請教其他同學，慢慢地對C語言和數(shù)據(jù)結(jié)構(gòu)知識有所熟悉，這時才逐漸有了思路。所以今后一定要牢固掌握好專業(yè)基礎(chǔ)知識。</p><p>　　2.必須培養(yǎng)嚴謹?shù)膽B(tài)度。自己在編程時經(jīng)常因為一些小錯誤而導(dǎo)致出現(xiàn)問題，不夠認真細致，這給自己帶來了許多麻煩

29、。編程是一件十分嚴謹?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)膽B(tài)度。我想這不僅是對于程序設(shè)計，做任何事都應(yīng)如此。</p><p>　　3.這次課程設(shè)計也讓我充分認識到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應(yīng)用。</p><p>　　在實踐過程中，我遇到了許多困難，但都一一克服了。最終我圓滿的完成此次課程設(shè)

30、計，學到了很多東西。同時，程序還存在著一些缺陷，我會繼續(xù)努力思考，完善程序，做到最好。</p><p>　　總的來說，本次課程設(shè)計，不僅我的知識面有所提高，另外我的綜合素質(zhì)也有所提高，這次課程設(shè)計為我以后更好的學習和使用c語言打下了基礎(chǔ)。</p><p><b>　　六、附件</b></p><p><b>　　6.1源程序</

31、b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define Max 10</p><p>　　#define FALSE 0</p><p>　　#define TRUE 1</p>

32、<p>　　#define Error printf</p><p>　　#define QueueSize 30</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　char vexs[Max];</p><p>　　in

33、t edges[Max][Max];</p><p><b>　　int n,e;</b></p><p>　　}MGraph;/*以鄰接矩陣作為圖的存儲結(jié)構(gòu)*/</p><p>　　int visited[Max];/*將visited[Max]定義為全局變量并分配最大空間*/</p><p>　　typedef st

34、ruct </p><p><b>　　{</b></p><p>　　int front;</p><p><b>　　int rear;</b></p><p>　　int count;</p><p>　　int data[QueueSize];</p>

35、<p>　　}CirQueue;/*定義隊列的數(shù)據(jù)結(jié)構(gòu)*/</p><p><b>　　//初始化隊列 </b></p><p>　　void InitQueue(CirQueue *Q)</p><p><b>　　{</b></p><p>　　Q->front=Q->re

36、ar=0;</p><p>　　Q->count=0;</p><p><b>　　}</b></p><p><b>　　//隊列空</b></p><p>　　int QueueEmpty(CirQueue *Q)</p><p><b>　　{</

37、b></p><p>　　return Q->count=QueueSize;/*返回隊列的最大長度*/</p><p><b>　　} </b></p><p><b>　　//隊列滿</b></p><p>　　int QueueFull(CirQueue *Q)</p>

38、<p><b>　　{</b></p><p>　　return Q->count==QueueSize;/*返回隊列的最大長度*/</p><p><b>　　} </b></p><p><b>　　//進隊</b></p><p>　　void EnQ

39、ueue(CirQueue *Q,int x)</p><p><b>　　{</b></p><p>　　if(QueueFull(Q))/*隊列滿則出錯*/</p><p><b>　　{</b></p><p>　　Error("Queue overflow");</

40、p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　Q->count++;/*否則count++，將x進隊*/</p><p>　　Q->data[Q-&g

41、t;rear]=x;</p><p>　　Q->rear=(Q->rear+1)%QueueSize;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//出隊</b></p><p&g

42、t;　　int DeQueue(CirQueue *Q)</p><p><b>　　{</b></p><p>　　int temp;/*定義整型的變量*/</p><p>　　if(QueueEmpty(Q))/*若為真則出錯*/</p><p><b>　　{</b></p>&

43、lt;p>　　Error("Queue underflow");</p><p><b>　　}</b></p><p>　　else/*為假則count--，將隊員出隊*/</p><p><b>　　{</b></p><p>　　temp=Q->data[Q-&

44、gt;front];/*用temp返回其值*/</p><p>　　Q->count--;</p><p>　　Q->front=(Q->front+1)%QueueSize;</p><p>　　return temp;/*返回出隊元素值*/</p><p><b>　　}</b></p>

45、<p><b>　　} </b></p><p><b>　　//建立一個圖</b></p><p>　　void CreateMGraph(MGraph *G)</p><p><b>　　{</b></p><p>　　int i,j,k;/*定義整型變量*/

46、</p><p>　　char ch1,ch2;/*定義字符型變量*/</p><p>　　printf("\n請輸入頂點數(shù)，邊數(shù)（格式：3，4）:");</p><p>　　scanf("%d,%d",&(G->n),&(G->e));/*輸入圖的頂點數(shù)和邊數(shù)*/</p><p

47、>　　for(i=0;i<G->n;i++)</p><p><b>　　{</b></p><p>　　getchar();</p><p>　　printf("\n請輸入第%d個頂點序號",i+1);</p><p>　　scanf("%c",&(G-

48、>vexs[i]));/*輸入頂點的序號*/</p><p><b>　　}</b></p><p>　　for(i=0;i<G->n;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<G->n;j++)</p>&

49、lt;p><b>　　{</b></p><p>　　G->edges[i][j]=0;/*初始化矩陣*/</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(k=0;k<G->e;k++)<

50、/p><p><b>　　{</b></p><p>　　getchar();</p><p>　　printf("\n請輸入第%d條邊的頂點序號（格式：i，j）:",k+1);</p><p>　　scanf("%c,%c",&ch1,&ch2);/*輸入邊的頂點序號

51、*/</p><p>　　for(i=0;ch1!=G->vexs[i];i++);</p><p>　　for(j=0;ch2!=G->vexs[j];j++);</p><p>　　G->edges[i][j]=1;/*有邊則賦值為1*/</p><p><b>　　}</b></p>

52、<p><b>　　} </b></p><p>　　//深度優(yōu)先遍歷遞歸 </p><p>　　void DFSM(MGraph *G,int i)</p><p><b>　　{</b></p><p><b>　　int j;</b></p>&

53、lt;p>　　printf("%c ",G->vexs[i]);</p><p>　　visited[i]=TRUE;/*標記visited[i]*/</p><p>　　/*依次優(yōu)先搜索訪問visited[i]的每個鄰接點*/</p><p>　　for(j=0;j<G->n;j++)</p><p&

54、gt;　　/*若visited[i]的一個有效鄰接點visited[j]未被訪問過，則從visited[j]出發(fā)進行遞歸調(diào)用*/</p><p>　　if(G->edges[i][j]==1&&!visited[j])</p><p>　　DFSM(G,j);</p><p><b>　　} </b></p>

55、<p>　　//廣度優(yōu)先遍歷遞歸</p><p>　　void BFSM(MGraph *G,int k)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　CirQueue Q;/*定義一個隊列Q，初始化隊列為空*/<

56、;/p><p>　　InitQueue(&Q);</p><p>　　printf("%c ",G->vexs[k]);/*訪問初始點，并將其標記已訪問過*/</p><p>　　visited[k]=TRUE;</p><p>　　EnQueue(&Q,k);/*將以訪問過的初始點序號k入隊*/<

57、/p><p>　　while(!QueueEmpty(&Q))/*隊列非空進行循環(huán)處理*/</p><p><b>　　{</b></p><p>　　i=DeQueue(&Q);/*將隊首元素出隊*/</p><p>　　for(j=0;j<G->n;j++)/*依次搜索vexs[k]的每一個可

58、能的鄰接點*/</p><p><b>　　{</b></p><p>　　if(G->edges[i][j]==1 &&! visited[j])</p><p><b>　　{</b></p><p>　　visited[j]=TRUE;/*標記vexs[j]已訪問過*/&

59、lt;/p><p>　　EnQueue(&Q,j);/*頂點序號j入隊*/</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b&

60、gt;</p><p><b>　　//深度優(yōu)先遍歷</b></p><p>　　void DFSTraverseM(MGraph *G)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　pr

61、intf("\n 深度優(yōu)先遍歷序列:");</p><p>　　for(i=0;i<G->n;i++)</p><p><b>　　{</b></p><p>　　visited[i]=FALSE;/*訪問標志數(shù)組初始化*/</p><p><b>

62、;　　}</b></p><p>　　for(i=0;i<G->n;i++)</p><p><b>　　{</b></p><p>　　if(!visited[i])/*對尚未訪問的頂點調(diào)用DFSM*/</p><p><b>　　{</b></p><

63、p>　　DFSM(G,i);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　} </b></p><p><b>　　//廣度優(yōu)先遍歷</b></p><p>　　

64、void BFSTraverseM(MGraph *G)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　printf("\n 廣度優(yōu)先遍歷序列:");</p><p>　　for(i=0

65、;i<G->n;i++)</p><p><b>　　{</b></p><p>　　visited[i]=FALSE;/*訪問標志數(shù)組初始化*/</p><p><b>　　}</b></p><p>　　for(i=0;i<G->n;i++)</p><

66、;p><b>　　{</b></p><p>　　if(!visited[i])/*對尚未訪問的頂點調(diào)用BFSM*/</p><p><b>　　{</b></p><p>　　BFSM(G,i);</p><p><b>　　}</b></p><p

67、><b>　　}</b></p><p><b>　　} </b></p><p><b>　　main()</b></p><p><b>　　{</b></p><p>　　MGraph *G,a;</p><p><

68、;b>　　char ch1;</b></p><p>　　int i,j,ch2;</p><p><b>　　G=&a;</b></p><p>　　printf("\n\t\t 深度優(yōu)先搜索和廣度優(yōu)先搜索 \n");</p><p>　

69、　CreateMGraph(G);/*調(diào)用創(chuàng)建圖矩陣的函數(shù)*/</p><p>　　getchar(); </p><p>　　ch1='y';/*設(shè)置控制語句標志*/</p><p>　　while(ch1=='y'||ch1=='Y')</p><p>　　{ /

70、*菜單欄*/</p><p>　　printf("\n");</p><p>　　printf(" 選擇菜單"); </p><p>　　printf("\n\t\t******************************************

71、\n");</p><p>　　printf("\t\t* 更改數(shù)據(jù)請按:1 *\n");</p><p>　　printf("\t\t* 深度優(yōu)先搜索請按:2 *\n");</p><p>　　printf("\t\t

72、* 廣度優(yōu)先搜索請按:3 *\n");</p><p>　　printf("\t\t* 退出搜索請按:0 *\n");</p><p>　　printf("\t\t******************************************\n"

73、);</p><p>　　printf("\n\t\t請選擇菜單號（0-3）：");</p><p>　　scanf("%d",&ch2);</p><p>　　getchar();</p><p>　　switch(ch2)</p><p><b>　　{&l

74、t;/b></p><p><b>　　case 1:</b></p><p>　　CreateMGraph(G);/*選1創(chuàng)建一個新的圖矩陣*/</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p>

75、<p>　　DFSTraverseM(G);/*選2進入深度優(yōu)先搜索*/</p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　BFSTraverseM(G);/*選3進入廣度優(yōu)先搜索*/</p><p><b>

76、;　　break;</b></p><p>　　case 0:/*選0結(jié)束搜索，退出程序*/</p><p><b>　　ch1='n';</b></p><p><b>　　break;</b></p><p><b>　　default:</b>

77、</p><p>　　system("cls");</p><p>　　printf("\n\t\t輸入有誤！\n");</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　if

78、(ch2==1||ch2==2||ch2==3)</p><p>　　printf("\n\n\t\t ");/*控制格式*/</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　計算機與通信學院課程設(shè)計評分表</p>