數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---圖的遍歷

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　目 錄</b></p><p><b>　　摘 要3</b></p><p>　　Abstract3</p><p><b>　　一、引 言4</b><

2、;/p><p>　　二、設(shè)計(jì)目的與任務(wù)4</p><p>　　三、設(shè)計(jì)方案與實(shí)施5</p><p><b>　　1、總體設(shè)計(jì)5</b></p><p><b>　　2、詳細(xì)設(shè)計(jì)5</b></p><p><b>　　3、 程序清單9</b><

3、/p><p>　　4、 程序調(diào)試與體會(huì)14</p><p>　　5、 運(yùn)行結(jié)果（截圖）14</p><p><b>　　四、結(jié) 論20</b></p><p><b>　　五、致 謝20</b></p><p><b>　　六、參考文獻(xiàn)20</b&g

4、t;</p><p><b>　　摘 要</b></p><p>　　隨著計(jì)算機(jī)科技發(fā)展的異常迅速，計(jì)算機(jī)技術(shù)也越來(lái)越為人們所利用，計(jì)算機(jī)已深入到人類社會(huì)的各個(gè)領(lǐng)域，在21世紀(jì)計(jì)算機(jī)技術(shù)勢(shì)必將得到更大的發(fā)展。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，是一門實(shí)踐性非常強(qiáng)的課程，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已經(jīng)成為其他理工專業(yè)的熱門選修課。如果說(shuō)高級(jí)語(yǔ)言程序設(shè)

5、計(jì)課程對(duì)學(xué)生進(jìn)行了結(jié)構(gòu)化程序設(shè)計(jì)的初步訓(xùn)練，那么數(shù)據(jù)結(jié)構(gòu)課程就是要培養(yǎng)其數(shù)據(jù)抽象能力。掌握好數(shù)據(jù)結(jié)構(gòu)很有利于對(duì)計(jì)算機(jī)程序的設(shè)計(jì)。圖是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，本設(shè)計(jì)是對(duì)圖進(jìn)行深度和廣度的遍歷。</p><p>　　關(guān)鍵詞：圖 遍歷 遞歸 鄰接矩陣</p><p><b>　　Abstract </b></p><p>　　Along

6、with the development of computer technology, computer technology and unusually quick for people place more and more use, computer is deeply into every field of human society, computer technology in the 21st century which

7、 will be more big development. Data structure is the important theory computer programming technology base, is a kind of very strong practicality course of computer science, it is not only the core curriculum, and has be

8、come the hottest other tech professional elective cour</p><p>　　Figure is a kind of more linear list and trees more complex data structure, the design is the graph depth and breadth of the traverse.</p>

9、;<p>　　Key words: Figure Traversal Recursion The adjacency matrix</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)</p><p><b>　　圖的遍歷設(shè)計(jì)</b></p><p><b>　　一、引 言 </b></p><

10、;p>　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。</p><p>　　圖是種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系可以是任意的，任意兩個(gè)元素之間都可能有相關(guān)的關(guān)系，這就優(yōu)于了線性表。</p><p>　　圖

11、的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對(duì)于廣度優(yōu)先遍歷應(yīng)利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）來(lái)實(shí)現(xiàn)，而深度優(yōu)先搜索則是一種遞歸的過(guò)程。</p><p><b>　　二、設(shè)計(jì)目的與任務(wù)</b></p><p><b>　　1、設(shè)計(jì)目的是：</b></p><p>　　該設(shè)計(jì)要求學(xué)生本學(xué)期對(duì)數(shù)

12、據(jù)結(jié)構(gòu)的學(xué)習(xí)為背景，設(shè)計(jì)出一個(gè)簡(jiǎn)單的能夠?qū)崿F(xiàn)圖的遍歷的系統(tǒng)。通過(guò)該題目的設(shè)計(jì)過(guò)程，主要達(dá)到如下目的：</p><p>　　加深理解圖、圖的遍歷、圖的廣度優(yōu)先遍歷、圖的深度優(yōu)先遍歷、圖的創(chuàng)建等一系列算法的創(chuàng)建，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)。</p><p>　　熟悉圖的結(jié)構(gòu)和其基本操作，掌握數(shù)組的建立和使用方法，學(xué)會(huì)利用遞歸和非遞歸的方法對(duì)其進(jìn)行遍歷。</p>

13、<p>　　學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，培養(yǎng)學(xué)生的動(dòng)手能力。</p><p>　　能在設(shè)計(jì)的過(guò)程中學(xué)會(huì)文檔的寫作和設(shè)計(jì)，以及提高團(tuán)隊(duì)合作能力。</p><p><b>　　2、設(shè)計(jì)任務(wù)是：</b></p><p>　　從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示），輸出這個(gè)圖的遍歷序列：</p><p&g

14、t;　　A)首先輸入圖的結(jié)點(diǎn)數(shù)->num。</p><p>　　B)依次輸入圖的各條邊（數(shù)據(jù)之間用空格隔開(kāi)）。</p><p>　　C)輸出的形式：按用戶選擇的遍歷方法給出遍歷順序。 </p><p>　　D)程序所能達(dá)到的功能：能夠按要求輸出所要的結(jié)果。</p><p><b>　　三、設(shè)計(jì)方案與實(shí)施</b>&l

15、t;/p><p><b>　　1、總體設(shè)計(jì)</b></p><p>　　（1）使用鍵盤的操作實(shí)行各種信息的輸入（包括圖的結(jié)點(diǎn)、結(jié)點(diǎn)之間的連線），并將相應(yīng)結(jié)果輸出等功能；</p><p>　?。?）建立圖，規(guī)定圖的結(jié)點(diǎn)的個(gè)數(shù)少于二十個(gè)，實(shí)現(xiàn)圖的遍歷；</p><p>　　（3）算法對(duì)于一些精心選擇的典型、苛刻而帶有刁難性的幾組

16、輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果，對(duì)算法實(shí)現(xiàn)過(guò)程中的異常情況能給出出錯(cuò)信息；</p><p>　?。?）圖的遍歷的方法有廣度優(yōu)先遍歷和深度優(yōu)先遍歷，按照輸入的要求實(shí)現(xiàn)圖的兩種遍歷，并且輸出結(jié)果。</p><p><b>　　程序流圖如下：</b></p><p><b>　　2、詳細(xì)設(shè)計(jì)</b></p>

17、<p>　　部分重點(diǎn)的函數(shù)詳細(xì)設(shè)計(jì)如下：</p><p><b>　　1.圖的創(chuàng)建：</b></p><p>　　該課題主要是以鄰接矩陣的方式存儲(chǔ)圖，并以圖形的方式輸出圖，所以在圖的創(chuàng)建的過(guò)程中主要是輸入圖中各結(jié)點(diǎn)的關(guān)系，比方說(shuō)1號(hào)結(jié)點(diǎn)和2號(hào)結(jié)點(diǎn)之間有聯(lián)系，那么就得輸入1，2，但是總得設(shè)置一個(gè)結(jié)束的條件，在這里我就以0，0結(jié)束，這樣比較好控制。而且初始化時(shí)

18、得把所有鄰接矩陣都初始化為0，那么當(dāng)兩個(gè)結(jié)點(diǎn)有關(guān)系時(shí)就可以設(shè)置為1.</p><p>　　void CreateGraph(Graph *g,int n) /*創(chuàng)建圖*/ </p><p><b>　　{ </b></p><p>　　int i,j,r1,r2; </p><p>　　g->vexnum=n; /

19、*頂點(diǎn)數(shù)*/</p><p>　　for(i=1;i<=n;i++) /*頂點(diǎn)用i表示*/ </p><p><b>　　{ </b></p><p>　　g->V[i]=i; </p><p><b>　　} </b></p><p>　　for(i=1;i&l

20、t;=n;i++) /*初始化R*/ </p><p>　　for(j=1;j<=n;j++) </p><p><b>　　{ </b></p><p>　　g->R[i][j]=0; </p><p><b>　　} </b></p><p>　　printf

21、("頂點(diǎn)1、頂點(diǎn)2:\n"); /*輸入R*/ </p><p>　　scanf("%d,%d",&r1,&r2); </p><p>　　while(r1!=0&&r2!=0) /*輸入的邊都賦值為1*/</p><p><b>　　{ </b></p>&

22、lt;p>　　g->R[r1][r2]=1; </p><p>　　g->R[r2][r1]=1; </p><p>　　scanf("%d,%d",&r1,&r2); </p><p><b>　　} </b></p><p><b>　　} </b

23、></p><p><b>　　2.深度遞歸遍歷：</b></p><p>　　當(dāng)用戶需要深度優(yōu)先遍歷時(shí)，由于公共變量Visited里的值可能會(huì)受到其他的變化 ，所以一開(kāi)始就把所有結(jié)點(diǎn)都定義為未訪問(wèn)，然后當(dāng)其訪問(wèn)到哪個(gè)結(jié)點(diǎn)時(shí)再把相應(yīng)的結(jié)點(diǎn)的Visited設(shè)置為1，即已經(jīng)訪問(wèn)。再用VisitVex函數(shù)顯示該結(jié)點(diǎn)已訪問(wèn)。再查找該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，實(shí)行遞歸。直到所有的

24、結(jié)點(diǎn)都已經(jīng)訪問(wèn)完。這是一個(gè)遞歸的過(guò)程。所以在實(shí)現(xiàn)深度優(yōu)先遍歷的過(guò)程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪問(wèn)。</p><p>　　void DFS(Graph *g,int vex) /*深度遞歸遍歷*/ </p><p><b>　　{ </b></p><p><b>　　int

25、 w; </b></p><p>　　Visited[vex]=1; /*對(duì)已經(jīng)訪問(wèn)好的頂點(diǎn)標(biāo)記為1*/</p><p>　　VisitVex(g,vex); /*訪問(wèn)頂點(diǎn)*/</p><p>　　for(w=FirstAdjVex(g,vex);w>0;w=NextAdjVex(g,vex,w)) </p><p>　　/

26、*獲取下一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)*/</p><p>　　if(!Visited[w]) /*如果頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)*/</p><p>　　{ DFS(g,w); }/*深度遞歸遍歷*/ </p><p><b>　　} </b></p><p>　　void DFSTraverse(Graph *g) </p

27、><p><b>　　{ </b></p><p><b>　　int i; </b></p><p>　　for(i=1;i<=g->vexnum;i++) /*初始化標(biāo)志數(shù)組*/</p><p>　　Visited[i]=0; </p><p>　　for(i=1

28、;i<=g->vexnum;i++) </p><p>　　if(!Visited[i]) /*如果頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)*/</p><p>　　{ DFS(g,i); } /*調(diào)用深度遞歸遍歷*/</p><p><b>　　} </b></p><p><b>　　3.廣度遍歷：</b>

29、</p><p>　　當(dāng)用戶需要廣度優(yōu)先遍歷時(shí)，首先得初始化一個(gè)隊(duì)列，并初始化其為一個(gè)空隊(duì)列。而且由于公共變量visited里的值可能會(huì)受到其他的變化 ，所以一開(kāi)始就把所有結(jié)點(diǎn)都定義為未訪問(wèn)，然后當(dāng)其訪問(wèn)到哪個(gè)結(jié)點(diǎn)時(shí)再把相應(yīng)的結(jié)點(diǎn)的visited設(shè)置為1，即已經(jīng)訪問(wèn)。再用visitvex函數(shù)顯示該結(jié)點(diǎn)已訪問(wèn)。然后再把該結(jié)點(diǎn)入隊(duì)。只要隊(duì)不為空。就把隊(duì)里的結(jié)點(diǎn)出隊(duì)。并查找下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都已經(jīng)訪問(wèn)完。<

30、;/p><p>　　void BFSTraverse(Graph *g,int v) /*廣度遍歷*/ </p><p><b>　　{ </b></p><p><b>　　int i; </b></p><p>　　Queue *q=(Queue *)malloc(sizeof(Queue)); &

31、lt;/p><p>　　for(i=1;i<=g->vexnum;i++) /*初始化標(biāo)志數(shù)組*/</p><p>　　{ Visited[i]=0; } </p><p>　　InitQueue(q); /*初始化隊(duì)列*/</p><p>　　EnQueue(q,v); /*讓要求遍歷的第一個(gè)頂點(diǎn)入隊(duì)*/</p>

32、<p>　　VisitVex(g,v);/*輸出第一個(gè)頂點(diǎn)的遍歷結(jié)果*/</p><p>　　Visited[v]=1;/*標(biāo)記第一個(gè)頂點(diǎn)*/</p><p>　　while(Quempty(q)) /*隊(duì)列非空*/</p><p><b>　　{ </b></p><p><b>　　int u,

33、w; </b></p><p>　　u=DeQueue(q); /*出隊(duì)*/</p><p>　　for(w=FirstAdjVex(g,u);w>0;w=Next(g,u,w)) </p><p>　　if(!Visited[w]) /*如果頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)*/</p><p><b>　　{ </b>

34、;</p><p>　　Visited[w]=1;/*對(duì)已經(jīng)訪問(wèn)好的頂點(diǎn)標(biāo)記為1*/</p><p>　　VisitVex(g,w); /*訪問(wèn)頂點(diǎn)*/</p><p>　　EnQueue(q,w); /*入隊(duì)*/</p><p><b>　　} </b></p><p><b>　　}

35、 </b></p><p><b>　　} </b></p><p><b>　　4.主函數(shù)：</b></p><p><b>　　主程序設(shè)計(jì)為：</b></p><p>　　int main() </p><p><b>　　{

36、</b></p><p><b>　　創(chuàng)建圖</b></p><p>　　以鄰接矩陣輸出矩陣 </p><p>　　輸入要遍歷的起始點(diǎn) </p><p><b>　　選擇需要的操作</b></p><p><b>　　調(diào)用深度遍歷函數(shù) </b>

37、;</p><p><b>　　創(chuàng)建隊(duì)列</b></p><p><b>　　調(diào)用廣度優(yōu)先遍歷</b></p><p><b>　　輸出矩陣</b></p><p><b>　　}</b></p><p><b>　　3、

38、程序清單</b></p><p>　　#include <stdio.h> </p><p>　　#include <stdlib.h> </p><p>　　#define M 20 </p><p>　　typedef struct /*定義圖*/</p><p><b&g

39、t;　　{ </b></p><p>　　int V[M]; </p><p>　　int R[M][M]; </p><p>　　int vexnum; </p><p><b>　　}Graph; </b></p><p>　　void CreateGraph(Graph *g,

40、int n) /*創(chuàng)建圖*/ </p><p><b>　　{ </b></p><p>　　int i,j,r1,r2; </p><p>　　g->vexnum=n; </p><p>　　for(i=1;i<=n;i++) /*頂點(diǎn)用i表示*/ </p><p><b>

41、;　　{ </b></p><p>　　g->V[i]=i; </p><p><b>　　} </b></p><p>　　for(i=1;i<=n;i++) /*初始化R*/ </p><p>　　for(j=1;j<=n;j++) </p><p><b&

42、gt;　　{ </b></p><p>　　g->R[i][j]=0; </p><p><b>　　} </b></p><p>　　printf("頂點(diǎn)1、頂點(diǎn)2:\n"); /*輸入R*/ </p><p>　　scanf("%d,%d",&r1,&

43、amp;r2); </p><p>　　while(r1!=0&&r2!=0) </p><p><b>　　{ </b></p><p>　　g->R[r1][r2]=1; </p><p>　　g->R[r2][r1]=1; </p><p>　　scanf(&qu

44、ot;%d,%d",&r1,&r2); </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　void PrintGraph(Graph *g) /*打印圖的鄰接矩陣*/ </p><p><b>　　{ <

45、;/b></p><p><b>　　int i,j; </b></p><p>　　for(i=1;i<=g->vexnum;i++) </p><p>　　{ for(j=1;j<=g->vexnum;j++) </p><p><b>　　{ </b></

46、p><p>　　printf("%2d ",g->R[i][j]); </p><p><b>　　} </b></p><p>　　printf("\n"); </p><p><b>　　} </b></p><p>　　prin

47、tf("\n");</p><p><b>　　} </b></p><p>　　int Visited[M]; /*全局變量：訪問(wèn)標(biāo)志數(shù)組*/</p><p>　　void VisitVex(Graph *g,int vex) /*訪問(wèn)頂點(diǎn)*/ </p><p><b>　　{ </

48、b></p><p>　　printf("%d ",g->V[vex]); </p><p><b>　　} </b></p><p>　　int FirstAdjVex(Graph *g,int vex) /*獲取第一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)*/</p><p><b>　　{ &

49、lt;/b></p><p><b>　　int w,i; </b></p><p>　　for(i=1;i<=g->vexnum;i++) </p><p><b>　　{ </b></p><p>　　if(g->R[vex][i]==1&&Visited

50、[i]==0) </p><p><b>　　{ </b></p><p><b>　　w=i; </b></p><p><b>　　break; </b></p><p><b>　　} </b></p><p><b&g

51、t;　　else </b></p><p><b>　　{ </b></p><p><b>　　w=0; </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　

52、　return w; </p><p><b>　　} </b></p><p>　　int NextAdjVex(Graph *g,int vex,int w) /*獲取下一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)(深度遍歷)*/</p><p><b>　　{ </b></p><p><b>　　int

53、 t; </b></p><p>　　t=FirstAdjVex(g,w); </p><p>　　return t; </p><p><b>　　} </b></p><p>　　int Next(Graph *g,int vex,int w)/*獲取下一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)(廣度遍歷)*/</p&

54、gt;<p><b>　　{</b></p><p><b>　　int t=0;</b></p><p>　　for(int i=w+1;i<=g->vexnum;i++) </p><p>　　if(g->R[vex][i]==1&&Visited[i]==0) <

55、/p><p><b>　　{ </b></p><p><b>　　t=i; </b></p><p><b>　　break;</b></p><p><b>　　} </b></p><p><b>　　return t;

56、</b></p><p><b>　　}</b></p><p>　　void DFS(Graph *g,int vex) /*深度遞歸遍歷*/ </p><p><b>　　{ </b></p><p><b>　　int w; </b></p>&

57、lt;p>　　Visited[vex]=1; </p><p>　　VisitVex(g,vex); </p><p>　　for(w=FirstAdjVex(g,vex);w>0;w=NextAdjVex(g,vex,w)) </p><p>　　if(!Visited[w]) </p><p><b>　　{ <

58、;/b></p><p>　　DFS(g,w); </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　void DFSTraverse(Graph *g,int v) </p><p><b>　　{ &l

59、t;/b></p><p><b>　　int i; </b></p><p>　　for(i=1;i<=g->vexnum;i++) </p><p>　　Visited[i]=0; </p><p>　　for(i=v;i<=g->vexnum;i++) </p><

60、p>　　if(!Visited[i]) </p><p>　　{DFS(g,i);} </p><p><b>　　} </b></p><p>　　typedef struct /*定義隊(duì)列*/ </p><p><b>　　{</b></p><p>　　int V

61、[M]; </p><p>　　int front; </p><p>　　int rear; </p><p><b>　　}Queue; </b></p><p>　　void InitQueue(Queue *q) /*初始化隊(duì)列*/ </p><p><b>　　{</b

62、></p><p>　　q->front=0; </p><p>　　q->rear=0; </p><p><b>　　} </b></p><p>　　int Quempty(Queue *q) /*判斷隊(duì)列是否為空*/</p><p><b>　　{ </b

63、></p><p>　　if(q->front==q->rear) </p><p><b>　　{ </b></p><p>　　return 0; </p><p><b>　　} </b></p><p><b>　　else </b&

64、gt;</p><p><b>　　{ </b></p><p>　　return 1; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　int EnQueue(Queue *q,int e) /

65、*入隊(duì)操作*/ </p><p><b>　　{ </b></p><p>　　if((q->rear+1)%M==q->front) </p><p><b>　　{ </b></p><p>　　printf("隊(duì)已滿！\n"); </p><

66、p>　　return 0; </p><p><b>　　} </b></p><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　q->V[q->rear]=e; </p><p>　

67、　q->rear=(q->rear+1)%M; </p><p>　　return 1; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　int DeQueue(Queue *q) /*出隊(duì)操作*/ </p><

68、;p><b>　　{ </b></p><p><b>　　int t; </b></p><p>　　if(q->front==q->rear) </p><p><b>　　{ </b></p><p>　　printf("隊(duì)為空！\n"

69、;); </p><p>　　return 0; </p><p><b>　　} </b></p><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　t=q->V[q->front]; &

70、lt;/p><p>　　q->front=(q->front+1)%M; </p><p>　　return t; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　void BFSTraverse(Graph

71、*g,int v) /*廣度遍歷*/ </p><p><b>　　{ </b></p><p><b>　　int i; </b></p><p>　　Queue *q=(Queue *)malloc(sizeof(Queue)); </p><p>　　for(i=1;i<=g->v

72、exnum;i++) </p><p><b>　　{ </b></p><p>　　Visited[i]=0; </p><p><b>　　} </b></p><p>　　InitQueue(q); </p><p>　　EnQueue(q,v);</p>

73、<p>　　VisitVex(g,v);</p><p>　　Visited[v]=1;</p><p>　　while(Quempty(q)) </p><p><b>　　{ </b></p><p><b>　　int u,w; </b></p><p>　

74、　u=DeQueue(q);</p><p>　　for(w=FirstAdjVex(g,u);w>0;w=Next(g,u,w)) </p><p>　　if(!Visited[w]) </p><p><b>　　{ </b></p><p>　　Visited[w]=1;</p><p&g

75、t;　　VisitVex(g,w); </p><p>　　EnQueue(q,w); </p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　int main(

76、) /*主程序*/ </p><p>　　{ printf("**************************************************\n\n\n\n\n\n");</p><p>　　printf(" welcome \n\n");<

77、/p><p>　　printf(" 圖的遍歷 \n\n");</p><p>　　printf(" 成員： \n\n\n\n\n\n");</p><p>　　printf("*************

78、*************************************\n");</p><p>　　system("pause");</p><p>　　system("cls");</p><p>　　int num,v; </p><p>　　Graph *g=(Graph *)ma

79、lloc(sizeof(Graph)); </p><p>　　char menu; </p><p>　　printf("請(qǐng)輸入節(jié)點(diǎn)的個(gè)數(shù)num:\n"); </p><p>　　scanf("%d",&num); </p><p>　　CreateGraph(g,num); </p&g

80、t;<p>　　printf("以鄰接矩陣輸出：\n"); </p><p>　　PrintGraph(g); </p><p>　　system("pause");</p><p><b>　　input: </b></p><p>　　printf("選

81、擇遍歷的起始點(diǎn)：\n");</p><p>　　scanf("%d",&v);</p><p>　　printf("請(qǐng)選擇需要的操作：\n廣度優(yōu)先遍歷輸入b，深度優(yōu)先遍歷輸入d，退出輸入q\n"); </p><p>　　while((menu=getchar())=='\n'); </

82、p><p>　　if(menu=='b') </p><p><b>　　{ </b></p><p>　　printf("廣度優(yōu)先遍歷：\n"); </p><p>　　BFSTraverse(g,v); </p><p>　　printf("\n&qu

83、ot;); </p><p>　　system("pause");</p><p>　　system("cls");</p><p>　　goto input; </p><p><b>　　} </b></p><p>　　else if(menu==&#

84、39;d') </p><p><b>　　{ </b></p><p>　　printf("深度優(yōu)先遍歷：\n"); </p><p>　　DFSTraverse(g,v); </p><p>　　printf("\n"); </p><p>　　

85、system("pause");</p><p>　　system("cls");</p><p>　　goto input; </p><p><b>　　} </b></p><p>　　else if(menu=='q') </p><p&

86、gt;<b>　　{ </b></p><p>　　printf("\n"); </p><p><b>　　exit(0); </b></p><p><b>　　} </b></p><p><b>　　else </b></

87、p><p><b>　　{ </b></p><p>　　printf("\n輸入有誤！\n");</p><p>　　system("pause");</p><p>　　system("cls");</p><p>　　goto inpu

88、t; </p><p><b>　　} </b></p><p>　　system("pause");</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>

89、　　程序調(diào)試與體會(huì)</b></p><p>　　先進(jìn)行對(duì)創(chuàng)建矩陣的函數(shù)進(jìn)行調(diào)試，在確保無(wú)誤的情況下再進(jìn)行后面模塊的調(diào)試，在調(diào)試中間經(jīng)常會(huì)出現(xiàn)一些小問(wèn)題，這時(shí)候需要采用“隔離”的方法進(jìn)行逐步的排查。最后對(duì)整個(gè)程序進(jìn)行總體的調(diào)試，不斷完善一些細(xì)節(jié)方面，并對(duì)輸入的參數(shù)進(jìn)行多方面的改變，以確保程序的正確性。</p><p>　　在整個(gè)程序運(yùn)行無(wú)誤的基礎(chǔ)上，在盡力對(duì)一些函數(shù)進(jìn)行優(yōu)化，加強(qiáng)

90、程序的可讀性，方便性。</p><p>　　在調(diào)試中，團(tuán)隊(duì)的協(xié)調(diào)讓調(diào)試過(guò)程充滿了活力和激情，讓我們感受到團(tuán)隊(duì)合作的重要性。在指導(dǎo)老師朱素英老師的指導(dǎo)和建議下，我們對(duì)程序又進(jìn)行了適當(dāng)?shù)男薷?，老師的辛勤努力，讓我們明白有位?yōu)秀指導(dǎo)老師的必要性。</p><p><b>　　運(yùn)行結(jié)果</b></p><p>　　截圖1，點(diǎn)擊編譯，運(yùn)行，初始狀態(tài)的歡迎

91、界面如下圖：</p><p>　　截圖2，按任意鍵繼續(xù)，要求輸入節(jié)點(diǎn)數(shù)num，節(jié)點(diǎn)數(shù)要求為小于二十，本次課程設(shè)計(jì)調(diào)試運(yùn)行實(shí)驗(yàn)中，我們輸入了8，并輸入了相應(yīng)的邊，輸入邊的信息時(shí)，以0,0結(jié)束輸入：</p><p>　　截圖3，按回車鍵，以鄰接矩陣的形式輸出圖：</p><p>　　截圖4，按任意鍵繼續(xù)，要求選擇遍歷的起始點(diǎn)，這里我們以5為起始點(diǎn)：</p>

92、<p>　　截圖5，要求選擇需要的操作，本次課程設(shè)計(jì)運(yùn)行實(shí)驗(yàn)中，我們先選擇廣度優(yōu)先遍歷，輸入b：</p><p>　　截圖6，輸出廣度優(yōu)先遍歷的遍歷順序，按任意鍵繼續(xù)，要求選擇需要執(zhí)行遍歷的起始點(diǎn)，我們輸入6，并選擇深度優(yōu)先遍歷：</p><p>　　截圖7，按任意鍵繼續(xù)，為驗(yàn)證輸入錯(cuò)誤情況，這次刻意輸入錯(cuò)誤操作字母代碼，我們輸入了s：</p><p>

93、　　提示輸入有錯(cuò)誤，并要求輸入任意鍵繼續(xù)。</p><p>　　調(diào)試完全正確，成功調(diào)試后，選擇退出，輸入q，結(jié)束調(diào)試。</p><p><b>　　四、結(jié) 論</b></p><p>　　圖的遍歷的整體思想并不復(fù)雜，利用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)（鄰接矩陣主要又是對(duì)數(shù)組的利用），對(duì)某個(gè)頂點(diǎn)訪問(wèn)之后再判斷是否有鄰接點(diǎn)，有則對(duì)其鄰接點(diǎn)進(jìn)行訪問(wèn)，否則尋找

94、下個(gè)未被訪問(wèn)的頂點(diǎn)，這個(gè)過(guò)程就利用了遞歸的方法。在進(jìn)行具體的實(shí)現(xiàn)的時(shí)候則將獨(dú)立的需要多次調(diào)用的內(nèi)容獨(dú)自開(kāi)辟個(gè)函數(shù)，以便進(jìn)行多次調(diào)用，也能夠加強(qiáng)程序的可讀性。</p><p>　　通過(guò)兩周的課程設(shè)計(jì)，充分認(rèn)識(shí)到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路，不至于無(wú)章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。</p><p>　　總之，在這次課程設(shè)計(jì)中，自己的C語(yǔ)言與數(shù)

95、據(jù)結(jié)構(gòu)知識(shí)得到提高，編程能力也得到了提高。積累了經(jīng)驗(yàn)，鍛煉了自己分析問(wèn)題和解決問(wèn)題的能力，掌握了必要的文檔寫作知識(shí)，懂得了制作規(guī)范和要求，并學(xué)會(huì)了如何將所學(xué)的各課知識(shí)融會(huì)組織，來(lái)配合學(xué)習(xí)，以及感受到團(tuán)隊(duì)合作的力量。兩周中我收益很大，學(xué)到很多。</p><p><b>　　五、致 謝</b></p><p>　　首先，非常非常感謝我們的輔導(dǎo)老師朱素英老師，在她的數(shù)次精

96、心輔導(dǎo)和幫助下，我們的課程設(shè)計(jì)才得以順利的完成，在她的帶領(lǐng)下，我們學(xué)到了更多的東西。</p><p>　　其次，要對(duì)我們的這個(gè)團(tuán)體表示衷心的感謝，因?yàn)橹挥袌F(tuán)體的共同努力才能讓我們順利而又快速的完成本次的課程設(shè)計(jì)，在本次的課程設(shè)計(jì)中，我們真正感受到了團(tuán)隊(duì)合作的重要性。</p><p>　　最后，也要在此謝謝在這個(gè)過(guò)程給予了我們?cè)S多幫助許多照顧的同學(xué)們和機(jī)房的各位老師，在他們的幫助下，我們的設(shè)

97、計(jì)才能做的更好更順利。</p><p><b>　　六、參考文獻(xiàn)</b></p><p>　　[1] C語(yǔ)言程序設(shè)計(jì)教程.楊路明,北京郵電大學(xué)出版社,2005,1</p><p>　　[2] C語(yǔ)言程序設(shè)計(jì).譚浩強(qiáng),清華大學(xué)出版社,2005,1</p><p>　　[3] 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn).徐孝凱,清華大學(xué)出版社,200

98、2,1</p><p>　　[4] 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.嚴(yán)蔚敏,吳偉民,清華大學(xué)出版社,2008,3</p><p>　　課程設(shè)計(jì)任務(wù)書(shū)及成績(jī)?cè)u(píng)定</p><p>　　課題名稱： 圖的遍歷 </p><p>　　完成者：

99、 </p><p>　　1、設(shè)計(jì)的目的與要求： </p><p>　　加深理解圖的一系列算法的創(chuàng)建，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，掌握數(shù)組的建立和使用方法，學(xué)會(huì)利用遞歸和非遞歸的方法對(duì)其進(jìn)行遍歷。學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，培養(yǎng)學(xué)生的動(dòng)手能力能在設(shè)計(jì)的過(guò)程中學(xué)會(huì)文檔的寫作和設(shè)計(jì)，以及提高團(tuán)隊(duì)合作能力。</p><p>　　2、設(shè)