數(shù)據(jù)結構課程設計-圖的遍歷和構建

1、<p><b>　　摘 要</b></p><p>　　圖（Graph）是一種復雜的非線性結構。圖可以分為無向圖、有向圖。若將圖的每條邊都賦上一個權，則稱這種帶權圖網(wǎng)絡。在人工智能、工程、數(shù)學、物理、化學、計算機科學等領域中，圖結構有著廣泛的應用。在圖結構中，對結點（圖中常稱為頂點）的前趨和后繼個數(shù)都是不加以限制的，即結點之間的關系是任意的。圖中任意兩個結點之間都可能相關。圖有兩

2、種常用的存儲表示方法：鄰接矩陣表示法和鄰接表表示法。在一個圖中，鄰接矩陣表示是唯一的，但鄰接表表示不唯一。在表示的過程中還可以實現(xiàn)圖的遍歷（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）及求圖中頂點的度。當然對于圖的廣度優(yōu)先遍歷還利用了隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）來實現(xiàn)。這不僅讓我們鞏固了之前學的隊列的基本操作，還懂得了將算法相互融合和運用。</p><p><b>　　目 錄<

3、;/b></p><p>　　第一章 課程設計目的3</p><p>　　第二章 課程設計內容和要求3</p><p>　　2.1課程設計內容3</p><p>　　2.1.1圖的鄰接矩陣的建立與輸出3</p><p>　　2.1.2圖的鄰接表的建立與輸出3</p><p>　　

4、2.1.3圖的遍歷的實現(xiàn)4</p><p>　　2.1.4 圖的頂點的度4</p><p>　　2.2 運行環(huán)境4</p><p>　　第三章 課程設計分析4</p><p><b>　　3.1圖的存儲4</b></p><p>　　3.1.1 圖的鄰接矩陣存儲表示4</p&g

5、t;<p>　　3.1.2 圖的鄰接表存儲表示5</p><p>　　3.2 圖的遍歷5</p><p>　　3.2.1 圖的深度優(yōu)先遍歷5</p><p>　　3.2.2 圖的廣度優(yōu)先遍歷6</p><p>　　3.3圖的頂點的度7</p><p>　　第四章 算法（數(shù)據(jù)結構）描述7<

6、/p><p>　　4.1 圖的存儲結構的建立。7</p><p>　　4.1.1 定義鄰接矩陣的定義類型7</p><p>　　4.1.2定義鄰接表的邊結點類型以及鄰接表類型7</p><p>　　4.1.3初始化圖的鄰接矩陣8</p><p>　　4.1.4 初始化圖的鄰接表8</p><p

7、>　　4.2 圖的遍歷8</p><p>　　4.2.1 深度優(yōu)先遍歷圖8</p><p>　　4.2.2 廣度優(yōu)先遍歷圖9</p><p>　　4.3 main函數(shù)9</p><p>　　4.4 圖的大致流程表10</p><p>　　第五章 源代碼10</p><p>　　

8、第六章 測試結果20</p><p>　　第七章 思想總結21</p><p>　　第八章 參考文獻22</p><p>　　第一章 課程設計目的</p><p>　　本學期我們對《數(shù)據(jù)結構》這門課程進行了學習。這門課程是一門實踐性非常強的課程，為了讓大家更好地理解與運用所學知識，提高動手能力，我們進行了此次課程設計。數(shù)據(jù)結構是計算機軟

9、件和計算機應用專業(yè)的核心課程之一，在眾多的計算機系統(tǒng)軟件和應用軟件中都要用到各種數(shù)據(jù)結構。這次課程設計不但要求學習者掌握《數(shù)據(jù)結構》中的各方面知識，還要求學習者具備一定的C語言基礎和編程能力。具體說來，這次課程設計主要有兩大方面目的：</p><p>　　一是讓學習者通過學習掌握《數(shù)據(jù)結構》中的知識。對于《圖的存儲與遍歷》這一課題來說，所要求掌握的數(shù)據(jù)結構知識主要有：圖的鄰接矩陣存儲、圖的鄰接表存儲、隊列的基本運

10、算實現(xiàn)、鄰接矩陣的算法實現(xiàn)、鄰接表的算法實現(xiàn)、圖的廣度優(yōu)先遍歷算法實現(xiàn)、圖的深度優(yōu)先遍歷算法實現(xiàn)。</p><p>　　二是通過學習鞏固并提高學習者的C語言知識，并初步了解Visual C++的知識，提高其編程能力與專業(yè)水平。</p><p>　　第二章 課程設計內容和要求</p><p><b>　　2.1課程設計內容</b></p&g

11、t;<p>　　該課題要求以鄰接矩陣和鄰接表的方式存儲圖，輸出鄰接矩陣和鄰接表，并要求實現(xiàn)圖的深度、廣度兩種遍歷及頂點的度。</p><p>　　2.1.1圖的鄰接矩陣的建立與輸出</p><p>　　對任意輸入頂點數(shù)和邊數(shù)的圖，若對無向圖進行討論，根據(jù)鄰接矩陣的存儲結構建立圖的鄰接矩陣并輸出。要求輸出的格式是矩陣形式，這樣便于直觀的了解。</p><p&

12、gt;　　2.1.2圖的鄰接表的建立與輸出</p><p>　　對任意給定的圖（頂點數(shù)和邊數(shù)可以宏定義），若對無向圖進行討論，根據(jù)鄰接表的存儲結構建立圖的鄰接表并輸出。</p><p>　　2.1.3圖的遍歷的實現(xiàn)</p><p>　　圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對于廣度優(yōu)先遍歷應利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）來實

13、現(xiàn)。首先建立一空隊列，從初始點出發(fā)進行訪問，當被訪問時入隊，訪問完出隊。并以隊列是否為空作為循環(huán)控制條件。對于深度優(yōu)先遍歷則采用遞歸算法來實現(xiàn)。當然，若存儲圖的表示不一樣，進行兩種遍歷的方式也不一樣。</p><p>　　2.1.4 圖的頂點的度</p><p>　　在圖中，可以求頂點的度。在無向圖用鄰接矩陣表示，Vi頂點的度即是該矩陣第i行或第j列中非0元素的個數(shù)之和。若無向圖用鄰接表表

14、示，頂點Vi的度則是第i個邊表中的結點個數(shù)。</p><p><b>　　2.2 運行環(huán)境</b></p><p>　　該程序的運行環(huán)境為Windows xp系統(tǒng)，Microsoft Visual C++6.0版本。</p><p>　　第三章 課程設計分析</p><p><b>　　3.1圖的存儲</

15、b></p><p>　　圖的存儲表示方法很多，但常用的是：圖的矩陣表示和鄰接表表示。至于在遇到問題具體選擇哪一種表示法，主要取決于具體的應用和欲施加的操作。</p><p>　　3.1.1 圖的鄰接矩陣存儲表示</p><p>　　本課題有鄰接矩陣存儲表示，鄰接矩陣是表示頂點之間相鄰關系的矩陣。設G=（V，E）</p><p>　　

16、是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質的n階方陣：A[i,j]=1：若（Vi，Vj）是E（G）中的邊；A[i,j]=0：若（Vi，Vj）不是E(G)中的邊。用鄰接矩陣表示法表示圖，除了存儲用于表示頂點間相鄰關系的鄰接矩陣外，通常還需要用一個順序表存儲頂點信息。因此，我們就要進行定義數(shù)據(jù)類型。由于無向圖的鄰接矩陣是對稱的，故采用壓縮存儲方式，僅存儲上三角陣（不包括對角線上的元素）中的元素即可。顯然，鄰接矩陣表示法的空間雜度S（n

17、）=O（n^2）。</p><p>　　開始進行類型定義，用輸入的方式來控制圖的頂點數(shù)和邊數(shù)，并對鄰接矩陣進行初始化，將G->arcs[i][j]=0，再從鍵盤上獲得頂點信息，建立頂點表，在此同時G->arcs[i][j]=1，G->arcs[j][i]=1，最后輸出鄰接矩陣，用兩層for循環(huán)語句來控制。</p><p>　　3.1.2 圖的鄰接表存儲表示</p&g

18、t;<p>　　另外還有鄰接表的存儲表示。鄰接表是一種鏈式的存儲結構，在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點Vi的邊。每個結點由2個域組成，其中鄰接點域（adjvex）指示與頂點Vi鄰接的點在圖中的位置，鏈域（next）指示下一條邊的結點。</p><p>　　所以一開始必須先定義鄰接表的邊結點類型以及鄰接表類型，并對鄰接表進行初始化，然后根據(jù)所輸入的相關信息，

19、包括圖的頂點數(shù)、邊數(shù)以及各條邊的起點與終點序號，建立圖的鄰接表。對于無向圖，一條邊的兩的個頂點，互為鄰接點，所以在存儲時，應向起點的單鏈表表頭插入一邊結點，即終點。同時將終點的單鏈表表頭插入一邊結點，即起點。對于鄰接表的輸出，采用for語句輸出各結點。</p><p><b>　　3.2 圖的遍歷</b></p><p>　　和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)

20、，沿著某條搜索路徑對圖中所有的頂點各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點出發(fā)順著邊可以訪問到該圖的所有頂點。圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一頂點都可能和其余頂點相鄰接，故在訪問了某個頂點之后，可能順著某條回路又回到了頂點。為了避免重復訪問同一個頂點必須記住每個頂點是否被訪問過。為此，可設置一個布爾向量visited[n]，它的初始值為0，一旦訪問了頂點Vi，便將visited[i-1]置為1。</p>

21、;<p>　　根據(jù)搜索路徑的方向不同，有兩種常用的遍歷圖的方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。</p><p>　　3.2.1 圖的深度優(yōu)先遍歷</p><p>　　假設給定圖G的初態(tài)是所有頂點未曾被訪問，在G中任選一頂點Vi為初始出發(fā)點，則深度優(yōu)先遍歷可定義如下：首先，訪問出發(fā)點Vi，并將其標記為已訪問過，然后，依次從Vi出發(fā)搜索Vi的每一個鄰接點Vj，若Vj未曾訪問過，則以

22、Vj為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷。顯然這是一個遞歸的過程，它的特點是盡可能先對縱深方向進行搜索，故稱之為深度優(yōu)先遍歷。在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調用深度優(yōu)先搜索函數(shù)。</p><p>　　具體過程應為：先訪問初始點Vi，并標志其已被訪問。此時定義一指向邊結點的指針p，并建立一個while（）循環(huán)，以指針所指對象不為空為控制條件，當Vi的鄰接點未被訪問時，遞歸調用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向

23、下一個邊結點。這樣就可以完成圖的深度優(yōu)先遍歷了。 </p><p>　　對圖進行深度優(yōu)先遍歷時，按訪問頂點的先后順序所得到的頂點序列，稱為該圖的深度優(yōu)先遍歷序列，簡稱DFS序列。一個圖的DFS序列不唯一，它與算法、圖的存儲結構以及初始出發(fā)點有關。在DFS算法中，當從Vi出發(fā)搜索時，是在鄰接矩陣的第i行中從左至右選擇下一個未曾訪問的鄰接點作為新的出發(fā)點，若這種鄰接點多于一個，則選中的是序號較小的那一個。因為圖的鄰接

24、矩陣表示是唯一的，故對于指定的初始出發(fā)點，有DFS算法所得的DFS序列是序列是唯一的。</p><p>　　3.2.2 圖的廣度優(yōu)先遍歷</p><p>　　廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。設圖G中某頂點Vi出發(fā)，在訪問了Vi之后訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點的鄰接點”被訪問，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中

25、尙有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以Vi為起始點，由近及遠，依次訪問和Vi有路徑相通且路徑長度為1，2，……的頂點。</p><p>　　所以要實現(xiàn)算法必須先建立一個元素類型為整型的空隊列，并定義隊首與隊尾指針，同時也要定義一個標志數(shù)組以標記結點是否被訪問。同樣，也是從初始點出發(fā)開始訪問，訪問初始點，標志其已

26、被訪問，并將其入隊。當隊列非空時進行循環(huán)處理。當結點被訪問時對其進行標志，并入隊列。通過while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結點，完成圖的廣度優(yōu)先遍歷。</p><p>　　和定義圖的DFS序列類似，我們可將廣度優(yōu)先遍歷圖所得到的頂點序列，定義為圖的廣度優(yōu)先搜索遍歷序列，簡稱BFS序列。一個圖的BFS序列也是不唯一的，它與算法、圖的存儲結構以及初始出發(fā)點有關。</p><p&

27、gt;<b>　　3.3圖的頂點的度</b></p><p>　　若無向圖用鄰接矩陣表示，Vi頂點的度即是該矩陣第i行或第j列中非0元素的個數(shù)之和。若無向圖用鄰接表表示，Vi的度分為出度和入度。出度即是表結點的個數(shù)，入度即是逆鄰接表的出度。</p><p>　　第四章 算法（數(shù)據(jù)結構）描述</p><p>　　4.1 圖的存儲結構的建立。<

28、;/p><p>　　4.1.1 定義鄰接矩陣的定義類型</p><p>　　typedef int datatype;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char vexs[max];</p><p>

29、　　int arcs[max][max];</p><p>　　int vexsnum,arcsnum; /* 頂點個數(shù)及邊的個數(shù) */</p><p><b>　　}graph;</b></p><p>　　4.1.2定義鄰接表的邊結點類型以及鄰接表類型</p><p>　　typedef char

30、 vextype;</p><p>　　typedef struct node</p><p><b>　　{</b></p><p>　　int adjvex; /* 鄰接點域 */</p><p>　　struct node *next; /* 鏈域 */</p><p

31、>　　}enode; /* 邊表結點 */</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　vextype vertex; /* 頂點信息 */</p><p>　　enode *link; /* 邊表頭指針 */<

32、/p><p>　　}vnode; /* 頂點表結點</p><p>　　4.1.3初始化圖的鄰接矩陣</p><p>　　for(i=0;i<G->vexsnum;i++)</p><p>　　G->vexs[i]=getchar(); </p><p&

33、gt;　　for(i=0;i<G->vexsnum;i++)</p><p>　　for(j=0;j<G->vexsnum;j++)</p><p>　　G->arcs[i][j]=0; </p><p>　　4.1.4 初始化圖的鄰接表</p><p>　　需建立一個鄰接表初始化函數(shù)對圖的鄰接表進行初始化。

34、即建立一個所有邊結點都為空的鄰接表。</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　a[i].vertex=getchar();</p><p>　　a[i].link=NULL; /* 邊表頭指針初始化 */</p>&l

35、t;p><b>　　}</b></p><p><b>　　4.2 圖的遍歷</b></p><p>　　4.2.1 深度優(yōu)先遍歷圖</p><p>　　具體過程應為：在深度優(yōu)先遍歷函數(shù)的參數(shù)中定義一個標志數(shù)組visited1[n]（鄰接矩陣表示）和visited3[n]（鄰接表表示），當某結點已被訪問時visite

36、d1[i]=1或visited3[i]=1，未被訪問時visited1[i]=0或visited3[i]=0。先訪問初始點Vi，并標志其已被訪問。若是鄰接矩陣表示時將定義一指向邊結點的指針p，并建立一個while（）循環(huán)，以指針所指對象不為空為控制條件，當Vi的鄰接點未被訪問時，遞歸調用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結點。這樣就可以完成圖的深度優(yōu)先遍歷了。</p><p>　　深度優(yōu)先遍歷的相關

37、代碼在下面的源代碼中給出。</p><p>　　4.2.2 廣度優(yōu)先遍歷圖</p><p>　　要實現(xiàn)算法必須先建立一個元素類型為整形的空隊列，并定義隊首與隊尾指針，同時也要定義一個標志數(shù)組visited2[n]（鄰接矩陣表示）和visited4[n]（鄰接表表示）和以標記結點是否被訪問。同樣，也是從初始點Vi出發(fā)開始訪問，訪問初始點，標志其已被訪問，并將已訪問過的初始點序號i入隊。當隊列

38、非空時進行循環(huán)處理，刪除隊首元素，第一次執(zhí)行時k的值為i，即front=(front+1)%maxsize。然后取Vk鄰接表的表頭指針int k=p[front]; enode* p=a[k]。當邊結點指針p不為空時，通過while（）循環(huán)，并以p是否為空為控制條件，依次搜索Vk的每一個結點。訪問完后，將p指向p->next。這樣就可以訪問所有結點，完成圖的廣度優(yōu)先遍歷。</p><p>　　廣度優(yōu)先遍歷的

39、相關代碼在下面的源代碼中給出。</p><p>　　4.3 main函數(shù)</p><p>　　在main函數(shù)中運用了菜單。用主菜單來控制是選擇鄰接矩陣的存儲表示還是鄰接表的存儲表示，用子菜單來控制選擇深度優(yōu)先遍歷還是廣度優(yōu)先遍歷。</p><p>　　4.4 圖的大致流程表</p><p><b>　　第五章 源代碼</b&g

40、t;</p><p>　　程序 圖的存儲與遍歷</p><p>　　#include<stdio.h></p><p>　　#include<malloc.h> </p><p>　　#define max 6</p><p>　　typedef int datatype;</p>

41、<p>　　typedef struct</p><p><b>　　{</b></p><p>　　char vexs[max];</p><p>　　int arcs[max][max];</p><p>　　int vexsnum,arcsnum; /* 頂點個數(shù)及邊的個數(shù) */&

42、lt;/p><p><b>　　}graph;</b></p><p>　　void creatgraph(graph *G) /* 建立鄰接矩陣的無向圖 */</p><p><b>　　{</b></p><p>　　int i,j,k,sum;</p>

43、<p>　　printf("請輸入頂點個數(shù)及邊的個數(shù)：\n");</p><p>　　scanf("%d%d",&G->vexsnum,&G->arcsnum);</p><p>　　printf("請讀入頂點信息，建立頂點表：\n");</p><p>　　getch

44、ar();</p><p>　　for(i=0;i<G->vexsnum;i++)</p><p>　　G->vexs[i]=getchar(); </p><p>　　for(i=0;i<G->vexsnum;i++)</p><p>　　for(j=0;j<G-

45、>vexsnum;j++)</p><p>　　G->arcs[i][j]=0; /* 鄰接矩陣初始化 */</p><p>　　printf("請輸入相鄰接的兩邊的頂點信息：\n");</p><p>　　for(k=0;k<G->arcsnum;k++)</p><p><

46、;b>　　{</b></p><p>　　scanf("%d%d",&i,&j);</p><p>　　G->arcs[i][j]=1;</p><p>　　G->arcs[j][i]=1;</p><p>　　} /* 讀入邊（Vi,Vj） */&

47、lt;/p><p>　　printf("輸出的鄰接矩陣為：\n");</p><p>　　for(i=0;i<G->vexsnum;i++)</p><p><b>　　{</b></p><p>　　printf("\n");</p><p>　　

48、for(j=0;j<G->vexsnum;j++)</p><p>　　printf("%3d",G->arcs[i][j]);</p><p>　　} /* 鄰接矩陣的輸出 */</p><p>　　printf("\n輸出鄰接矩陣Vi頂點的度為：\n");</p>&l

49、t;p>　　for(i=0;i<G->vexsnum;i++)</p><p><b>　　{</b></p><p><b>　　sum=0;</b></p><p>　　for(j=0;j<G->vexsnum;j++)</p><p>　　if(G->arc

50、s[i][j]==1)</p><p><b>　　sum++;</b></p><p>　　printf("V%d的度為：%d\n",i,sum);</p><p>　　} /* 各頂點的度 */</p><p><b>　　}</b></p>

51、<p>　　#define n 4</p><p>　　#define m 5</p><p>　　typedef char vextype;</p><p>　　typedef struct node</p><p><b>　　{</b></p><p>　　int adjvex;

52、 /* 鄰接點域 */</p><p>　　struct node *next; /* 鏈域 */</p><p>　　}enode; /* 邊表結點 */</p><p>　　typedef struct</p><p><b>　　{</b></p><p

53、>　　vextype vertex; /* 頂點信息 */</p><p>　　enode *link; /* 邊表頭指針 */</p><p>　　}vnode; /* 頂點表結點 */</p><p>　　vnode a[n];</p><p>　　void creatlist() /* 建立無向圖

54、的鄰接表 */</p><p><b>　　{</b></p><p>　　int i,j,k,sum;</p><p><b>　　enode *s;</b></p><p>　　printf("請讀入頂點信息，建立頂點表：\n");</p><p>　

55、　getchar();</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　a[i].vertex=getchar();</p><p>　　a[i].link=NULL; /* 邊表頭指針初始化 */</p><p>

56、<b>　　}</b></p><p>　　printf("請輸入相鄰接的兩邊的頂點信息：\n");</p><p>　　for(k=0;k<m;k++)</p><p><b>　　{</b></p><p>　　scanf("%d%d",&i

57、,&j); /* 讀入邊（Vi,Vj） */</p><p>　　s=(enode*)malloc(sizeof(enode)); /* 生成鄰接點序號為j的表結點*s */</p><p>　　s->adjvex=j;</p><p>　　s->next=a[i].link;</p><p>　　a[i].li

58、nk=s; /* 將*s插入頂點Vi的邊表頭部 */</p><p>　　s=(enode*)malloc(sizeof(enode)); /* 生成鄰接點序號為i的邊表結點*s */</p><p>　　s->adjvex=i;</p><p>　　s->next=a[j].link;</p><p>　　a[

59、j].link=s; /* 將*s插入頂點Vj的邊表頭部 */</p><p><b>　　}</b></p><p>　　printf("輸出的鄰接表為：\n");</p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b>

60、;</p><p>　　printf("\n%c ",a[i].vertex);</p><p>　　s=a[i].link;</p><p><b>　　while(s)</b></p><p><b>　　{</b></p><p>　　printf

61、("%d->",s->adjvex);</p><p>　　s=s->next;</p><p><b>　　}</b></p><p>　　} /* 鄰接表的輸出 */</p><p>　　printf("輸出鄰接表Vi頂點的度為：\n");</

62、p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　s=a[i].link;</p><p><b>　　sum=0;</b></p><p><b>　　while(s)</b></p&

63、gt;<p><b>　　{</b></p><p><b>　　sum++;</b></p><p>　　s=s->next;</p><p><b>　　}</b></p><p>　　printf("V%d的度為：%d\n",i,s

64、um);</p><p>　　} /* 各頂點的度 */</p><p><b>　　}</b></p><p>　　int visited1[max]={0}; /* 定義布爾向量visited1為全程量 */</p><p>　　void dfs1(graph *G,int i) /* 從Vi+1

65、出發(fā)深度優(yōu)先搜索圖G，G用鄰接矩陣表示 */</p><p><b>　　{</b></p><p><b>　　int j;</b></p><p>　　printf("node:%c\n",G->vexs[i]); /* 訪問出發(fā)點Vi+1 */</p><p>

66、;　　visited1[i]=1; /* 標記Vi+1已被訪問 */</p><p>　　for(j=0;j<G->vexsnum;j++) /* 依次搜索Vi+1的鄰接點 */</p><p>　　if((G->arcs[i][j])&&(!visited1[j]))</p><p>　　dfs1(G,j);/* 若Vi+

67、1的鄰接點Vi+1未曾訪問過，則從Vi+1出發(fā)進行深度優(yōu)先搜索 */</p><p><b>　　}</b></p><p>　　#define maxsize 80</p><p>　　typedef int datatype;</p><p>　　typedef struct</p><p>

68、<b>　　{</b></p><p>　　datatype data[maxsize];</p><p>　　int front,rear;</p><p>　　}sequeue; /* 順序隊列的類型 */</p><p>　　sequeue *p; /* p是順序隊列類型的指針 */</p>

69、;<p>　　void setnull() /* 置隊列p為空對 */</p><p><b>　　{</b></p><p>　　p->front=maxsize-1;</p><p>　　p->rear=maxsize-1;</p><p><b>　　}</b>

70、</p><p>　　int empty() /* 判別p是否為空 */</p><p><b>　　{</b></p><p>　　if(p->front==p->rear)</p><p><b>　　return 1;</b></p><p>　　els

71、e return 0;</p><p><b>　　}</b></p><p>　　int front() /* 取p的隊頭元素 */</p><p><b>　　{</b></p><p>　　if(empty())</p><p><b>　　{</

72、b></p><p>　　printf("the sequeue is empty");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　else return p->data[(p->fron

73、t+1)%maxsize];</p><p><b>　　}</b></p><p>　　int enqueue(int x) /* 將新元素x插入隊列p的隊尾 */</p><p><b>　　{</b></p><p>　　if((p->rear+1)%maxsize==p->fr

74、ont)</p><p><b>　　{</b></p><p>　　printf("the queue is full.");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p

75、><b>　　else </b></p><p><b>　　{</b></p><p>　　p->rear=(p->rear+1)%maxsize;</p><p>　　p->data[p->rear]=x;</p><p>　　return x;</p>

76、;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　int dequeue() /* 刪除隊列p的頭元素，并返回該元素 */</p><p><b>　　{</b></p><p>　　if(empty())<

77、;/p><p><b>　　{</b></p><p>　　printf("the sequeue is empty");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>&

78、lt;b>　　else{</b></p><p>　　p->front=(p->front+1)%maxsize;</p><p>　　return (p->data[p->front]);</p><p><b>　　}</b></p><p><b>　　}<

79、/b></p><p>　　int visited2[max]={0};</p><p>　　void bfs1(graph *G,int k)/*從Vi+1出發(fā)廣度優(yōu)先搜索圖G，G用鄰接矩陣表示*/</p><p><b>　　{</b></p><p><b>　　int i,j;</b>

80、</p><p>　　setnull();</p><p>　　printf("node:%c\n",G->vexs[k]); /* 訪問出發(fā)點Vk+1 */</p><p>　　visited2[k]=1;</p><p>　　enqueue(k);</p><p>　　while(!

81、empty()) /* 隊非空時執(zhí)行 */</p><p><b>　　{</b></p><p>　　i=dequeue();</p><p>　　for(j=0;j<G->vexsnum;j++)</p><p>　　if((G->arcs[i][j])&&(!visit

82、ed2[j]))</p><p><b>　　{</b></p><p>　　printf("%c\n",G->vexs[j]); /* 訪問Vi+1的未曾訪問的鄰接點Vj+1 */</p><p>　　visited2[j]=1;</p><p>　　enqueue(j); /* 訪問

83、過的頂點入隊 */</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int visited3[n]={0};</p><p>　　void dfs2(int i)

84、 /* 從Vi+1出發(fā)深度優(yōu)先遍歷搜索圖a，a圖用鄰接表表示*/</p><p><b>　　{</b></p><p><b>　　enode *p;</b></p><p>　　printf("node:%c\n",a[i].vertex);</p><p>　　visite

85、d3[i]=1;</p><p>　　p=a[i].link; /* 取Vi+1的邊表頭指針 */</p><p>　　while(p!=NULL) /* 依次搜索Vi+1的鄰接點 */</p><p><b>　　{</b></p><p>　　if(!visited3[p->adjvex])&

86、lt;/p><p>　　dfs2(p->adjvex); /* 從Vi+1的未曾訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索 */</p><p>　　p=p->next; /* 找Vi+1下一個鄰接點 */</p><p><b>　　}</b></p><p><b>　　}</b></

87、p><p>　　int visited4[n]={0};</p><p>　　void bfs2(int k) /* 從Vi+1出發(fā)廣度優(yōu)先搜索圖a,a用鄰接表表示 */</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>

88、<b>　　enode *p;</b></p><p>　　setnull();</p><p>　　printf("node:%c\n",a[k].vertex);</p><p>　　visited4[k]=1;</p><p>　　enqueue(k);</p><p>

89、　　while(!empty())</p><p><b>　　{</b></p><p>　　i=dequeue();</p><p>　　p=a[i].link; /* 取Vi+1的邊表頭指針 */</p><p>　　while(p!=NULL) /* 依次搜索Vi+1的鄰接點 */</p>

90、<p><b>　　{</b></p><p>　　if(!visited4[p->adjvex]) /* 訪問Vi+1的未曾訪問的鄰接點 */</p><p><b>　　{</b></p><p>　　printf("node:%c\n",a[p->adjvex].v

91、ertex);</p><p>　　visited4[p->adjvex]=1;</p><p>　　enqueue(p->adjvex); /* 訪問過的頂點入隊 */</p><p><b>　　}</b></p><p>　　p=p->next; /* 找Vi+1的下一個鄰接點 */&l

92、t;/p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><

93、p>　　int i,j,x,y,z,s,t;</p><p><b>　　graph a;</b></p><p>　　int flag=0;</p><p>　　p=(sequeue*)malloc(sizeof(sequeue));</p><p>　　printf("=============歡迎進

94、入=============\n");</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　printf("請選擇輸入\n1為用鄰接矩陣存儲圖\n2為用鄰接表存儲圖\n0為退出：\n");</p><p>　

95、　scanf("%d",&x);</p><p><b>　　switch(x)</b></p><p><b>　　{</b></p><p>　　case 1:creatgraph(&a);</p><p>　　while(flag==0)</p>

96、<p><b>　　{</b></p><p>　　printf("請選擇輸入\n1為鄰接矩陣深度優(yōu)先遍歷\n2為鄰接矩陣廣度優(yōu)先遍歷\n0為返回繼續(xù)選擇圖的存儲：\n");</p><p>　　scanf("%d",&y);</p><p><b>　　switch(y)

97、</b></p><p><b>　　{</b></p><p>　　case 1:printf("請輸入深度優(yōu)先遍歷的頂點：\n");</p><p>　　scanf("%d",&i);</p><p>　　dfs1(&a,i);break;</

98、p><p>　　case 2:printf("請輸入廣度優(yōu)先遍歷的頂點：\n");</p><p>　　scanf("%d",&j);</p><p>　　bfs1(&a,j);break;</p><p>　　case 0:flag=1;</p><p><b

99、>　　}</b></p><p><b>　　}break;</b></p><p>　　case 2:creatlist();</p><p>　　while(flag==0)</p><p><b>　　{</b></p><p>　　printf(&q

100、uot;請選擇輸入\n1為鄰接表深度優(yōu)先遍歷\n2為鄰接表廣度優(yōu)先遍歷\n0為返回繼續(xù)選擇圖的存儲：\n：");</p><p>　　scanf("%d",& z);</p><p><b>　　switch(z)</b></p><p><b>　　{</b></p>

101、<p>　　case 1:printf("請輸入深度優(yōu)先遍歷的頂點：\n");</p><p>　　scanf("%d",&s);</p><p>　　dfs2(s);break;</p><p>　　case 2:printf("請輸入廣度優(yōu)先遍歷的頂點：\n");</p>

102、<p>　　scanf("%d",&t);</p><p>　　bfs2(t);break;</p><p>　　case 0:flag=1;</p><p><b>　　}</b></p><p><b>　　}break;</b></p>&

103、lt;p>　　case 0:exit(0);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　第六章 測試結果</b></p><

104、p>　　由于學習之初對圖的存儲結構了解不是很清楚，所以在運行出了錯誤。首先在運行當中少了一句算法：在建立鄰接表，輸入頂點信息時，少了getchar()語句。因為程序本身沒報錯，但是在執(zhí)行的過程中出現(xiàn)了錯誤的信息，而且總是在執(zhí)行鄰接表操作時出錯。另外在宏定義時定義了m,n，但我還在main函數(shù)中定義了int類型的m,n，所以程序報錯了，這讓我懂得了宏定義的作用和意義。在小的細節(jié)上，偶爾打錯單詞，造成錯誤。

105、 </p><p>　　V0 V3</p><p>　　例如我們運用右圖（無向圖）來執(zhí)行操作的話 </p><p>　　便可得到相應的結果： </p><p>　　V1 V2</p>

106、<p><b>　　圖a</b></p><p>　　當我們選擇從鍵盤上輸入1時，程序執(zhí)行的是用鄰接矩陣存儲圖，相應的我們要從鍵盤了輸入頂點個數(shù)及邊的個數(shù)，如4，5。再讀入頂點信息，如0123。根據(jù)提示信息再從鍵盤上輸入相鄰接的兩邊的頂點信息，如0，1；0，2；0，3；1，2；1，3。這樣便可以得到所存儲的鄰接矩陣了，同時也輸出了各個頂點的度。</p><p&g

107、t;<b>　　圖b</b></p><p>　　在main函數(shù)中還有相應的子菜單，當我們在主菜單中選的是1用鄰接矩陣存儲時，子菜單中就有一系列算法：鄰接矩陣深度優(yōu)先遍歷（圖b）和廣度優(yōu)先遍歷（圖c）。</p><p><b>　　圖c</b></p><p><b>　　第七章 思想總結</b>&l

108、t;/p><p>　　轉眼，為期兩周的《數(shù)據(jù)結構》課程設計學習即將結束。在這次學習中，自己的C語言知識和數(shù)據(jù)結構知識得到了鞏固，編程能力也有了一定的提高。同時也學會了解決問題的方法?？偨Y起來，自己主要有以下幾點體會：</p><p>　　1、必須牢固掌握基礎知識。由于C語言是大一所學知識，有所遺忘，且未掌握好這學期所學的《數(shù)據(jù)結構》這門課，所以在學習之初感到棘手。不知如何下手，但在后來的學習過

109、程中自己通過看書和課外資料，并請教其他同學，慢慢地對C語言和數(shù)據(jù)結構知識有所熟悉。所以，這次學習之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎知識。</p><p>　　2、必須培養(yǎng)嚴謹?shù)目茖W態(tài)度。自己在編程時經(jīng)常因為一些類似于“少了分號”、“單詞打錯”的小錯誤而導致錯誤，不夠認真細致，這給自己帶來了許多麻煩。編程是一件十分嚴謹?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)目茖W態(tài)度。我想這不僅是對于程序設計，

110、做任何事都應如此。</p><p>　　3、這次課程設計也讓我充分認識到《數(shù)據(jù)結構》這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應用。</p><p>　　總之，在這次學習中，自己的C語言以及數(shù)據(jù)結構知識得到提高，編程能力也得到了提高。</p><p><b>　　第八章 參考文獻</b&g