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

5、計(jì)課程對學(xué)生進(jìn)行了結(jié)構(gòu)化程序設(shè)計(jì)的初步訓(xùn)練，那么數(shù)據(jù)結(jié)構(gòu)課程就是要培養(yǎng)其數(shù)據(jù)抽象能力。掌握好數(shù)據(jù)結(jié)構(gòu)很有利于對計(jì)算機(jī)程序的設(shè)計(jì)。圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，本設(shè)計(jì)是對圖進(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ī)存儲、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。</p><p>　　圖是種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系可以是任意的，任意兩個元素之間都可能有相關(guān)的關(guān)系，這就優(yōu)于了線性表。</p><p>　　圖

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

12、據(jù)結(jié)構(gòu)的學(xué)習(xí)為背景，設(shè)計(jì)出一個簡單的能夠?qū)崿F(xiàn)圖的遍歷的系統(tǒng)。通過該題目的設(shè)計(jì)過程，主要達(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é)會利用遞歸和非遞歸的方法對其進(jìn)行遍歷。</p>

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

14、t;　　A)首先輸入圖的結(jié)點(diǎn)數(shù)->num。</p><p>　　B)依次輸入圖的各條邊（數(shù)據(jù)之間用空格隔開）。</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>　?。?）使用鍵盤的操作實(shí)行各種信息的輸入（包括圖的結(jié)點(diǎn)、結(jié)點(diǎn)之間的連線），并將相應(yīng)結(jié)果輸出等功能；</p><p>　?。?）建立圖，規(guī)定圖的結(jié)點(diǎn)的個數(shù)少于二十個，實(shí)現(xiàn)圖的遍歷；</p><p>　?。?）算法對于一些精心選擇的典型、苛刻而帶有刁難性的幾組

16、輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果，對算法實(shí)現(xiàn)過程中的異常情況能給出出錯信息；</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>　　該課題主要是以鄰接矩陣的方式存儲圖，并以圖形的方式輸出圖，所以在圖的創(chuàng)建的過程中主要是輸入圖中各結(jié)點(diǎn)的關(guān)系，比方說1號結(jié)點(diǎn)和2號結(jié)點(diǎn)之間有聯(lián)系，那么就得輸入1，2，但是總得設(shè)置一個結(jié)束的條件，在這里我就以0，0結(jié)束，這樣比較好控制。而且初始化時

18、得把所有鄰接矩陣都初始化為0，那么當(dāng)兩個結(jié)點(diǎn)有關(guān)系時就可以設(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)先遍歷時，由于公共變量Visited里的值可能會受到其他的變化 ，所以一開始就把所有結(jié)點(diǎn)都定義為未訪問，然后當(dāng)其訪問到哪個結(jié)點(diǎn)時再把相應(yīng)的結(jié)點(diǎn)的Visited設(shè)置為1，即已經(jīng)訪問。再用VisitVex函數(shù)顯示該結(jié)點(diǎn)已訪問。再查找該結(jié)點(diǎn)的下一個結(jié)點(diǎn)，實(shí)行遞歸。直到所有的

24、結(jié)點(diǎn)都已經(jīng)訪問完。這是一個遞歸的過程。所以在實(shí)現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎ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; /*對已經(jīng)訪問好的頂點(diǎn)標(biāo)記為1*/</p><p>　　VisitVex(g,vex); /*訪問頂點(diǎn)*/</p><p>　　for(w=FirstAdjVex(g,vex);w>0;w=NextAdjVex(g,vex,w)) </p><p>　　/

26、*獲取下一個未被訪問的鄰接節(jié)點(diǎn)*/</p><p>　　if(!Visited[w]) /*如果頂點(diǎn)沒有被訪問過*/</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)沒有被訪問過*/</p><p>　　{ DFS(g,i); } /*調(diào)用深度遞歸遍歷*/</p><p><b>　　} </b></p><p><b>　　3.廣度遍歷：</b>

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

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); /*讓要求遍歷的第一個頂點(diǎn)入隊(duì)*/</p>

32、<p>　　VisitVex(g,v);/*輸出第一個頂點(diǎn)的遍歷結(jié)果*/</p><p>　　Visited[v]=1;/*標(biāo)記第一個頂點(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)沒有被訪問過*/</p><p><b>　　{ </b>

34、;</p><p>　　Visited[w]=1;/*對已經(jīng)訪問好的頂點(diǎn)標(biāo)記為1*/</p><p>　　VisitVex(g,w); /*訪問頂點(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]; /*全局變量：訪問標(biāo)志數(shù)組*/</p><p>　　void VisitVex(Graph *g,int vex) /*訪問頂點(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) /*獲取第一個未被訪問的鄰接節(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) /*獲取下一個未被訪問的鄰接節(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)/*獲取下一個未被訪問的鄰接節(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("請輸入節(jié)點(diǎn)的個數(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("請選擇需要的操作：\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)試與體會</b></p><p>　　先進(jìn)行對創(chuàng)建矩陣的函數(shù)進(jìn)行調(diào)試，在確保無誤的情況下再進(jìn)行后面模塊的調(diào)試，在調(diào)試中間經(jīng)常會出現(xiàn)一些小問題，這時候需要采用“隔離”的方法進(jìn)行逐步的排查。最后對整個程序進(jìn)行總體的調(diào)試，不斷完善一些細(xì)節(jié)方面，并對輸入的參數(shù)進(jìn)行多方面的改變，以確保程序的正確性。</p><p>　　在整個程序運(yùn)行無誤的基礎(chǔ)上，在盡力對一些函數(shù)進(jìn)行優(yōu)化，加強(qiáng)

90、程序的可讀性，方便性。</p><p>　　在調(diào)試中，團(tuán)隊(duì)的協(xié)調(diào)讓調(diào)試過程充滿了活力和激情，讓我們感受到團(tuán)隊(duì)合作的重要性。在指導(dǎo)老師朱素英老師的指導(dǎo)和建議下，我們對程序又進(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)的邊，輸入邊的信息時，以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)證輸入錯誤情況，這次刻意輸入錯誤操作字母代碼，我們輸入了s：</p><p>

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

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

95、據(jù)結(jié)構(gòu)知識得到提高，編程能力也得到了提高。積累了經(jīng)驗(yàn)，鍛煉了自己分析問題和解決問題的能力，掌握了必要的文檔寫作知識，懂得了制作規(guī)范和要求，并學(xué)會了如何將所學(xué)的各課知識融會組織，來配合學(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>　　其次，要對我們的這個團(tuán)體表示衷心的感謝，因?yàn)橹挥袌F(tuán)體的共同努力才能讓我們順利而又快速的完成本次的課程設(shè)計(jì)，在本次的課程設(shè)計(jì)中，我們真正感受到了團(tuán)隊(duì)合作的重要性。</p><p>　　最后，也要在此謝謝在這個過程給予了我們許多幫助許多照顧的同學(xué)們和機(jī)房的各位老師，在他們的幫助下，我們的設(shè)

97、計(jì)才能做的更好更順利。</p><p><b>　　六、參考文獻(xiàn)</b></p><p>　　[1] C語言程序設(shè)計(jì)教程.楊路明,北京郵電大學(xué)出版社,2005,1</p><p>　　[2] C語言程序設(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án)蔚敏,吳偉民,清華大學(xué)出版社,2008,3</p><p>　　課程設(shè)計(jì)任務(wù)書及成績評定</p><p>　　課題名稱： 圖的遍歷 </p><p>　　完成者：

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