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

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

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

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

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

5、t;<p>　　3.1.2 圖的鄰接表存儲(chǔ)表示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圖的頂點(diǎn)的度7</p><p>　　第四章 算法（數(shù)據(jù)結(jié)構(gòu)）描述7<

6、/p><p>　　4.1 圖的存儲(chǔ)結(jié)構(gòu)的建立。7</p><p>　　4.1.1 定義鄰接矩陣的定義類型7</p><p>　　4.1.2定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型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、第六章 測(cè)試結(jié)果20</p><p>　　第七章 思想總結(jié)21</p><p>　　第八章 參考文獻(xiàn)22</p><p>　　第一章 課程設(shè)計(jì)目的</p><p>　　本學(xué)期我們對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課程進(jìn)行了學(xué)習(xí)。這門(mén)課程是一門(mén)實(shí)踐性非常強(qiáng)的課程，為了讓大家更好地理解與運(yùn)用所學(xué)知識(shí)，提高動(dòng)手能力，我們進(jìn)行了此次課程設(shè)計(jì)。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)軟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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; /* 頂點(diǎn)個(gè)數(shù)及邊的個(gè)數(shù) */</p><p><b>　　}graph;</b></p><p>　　4.1.2定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型</p><p>　　typedef char

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

31、>　　}enode; /* 邊表結(jié)點(diǎn) */</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　vextype vertex; /* 頂點(diǎn)信息 */</p><p>　　enode *link; /* 邊表頭指針 */<

32、/p><p>　　}vnode; /* 頂點(diǎn)表結(jié)點(diǎn)</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>　　需建立一個(gè)鄰接表初始化函數(shù)對(duì)圖的鄰接表進(jìn)行初始化。

34、即建立一個(gè)所有邊結(jié)點(diǎn)都為空的鄰接表。</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>　　具體過(guò)程應(yīng)為：在深度優(yōu)先遍歷函數(shù)的參數(shù)中定義一個(gè)標(biāo)志數(shù)組visited1[n]（鄰接矩陣表示）和visited3[n]（鄰接表表示），當(dāng)某結(jié)點(diǎn)已被訪問(wèn)時(shí)visite

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

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

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

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

40、t;</p><p>　　程序 圖的存儲(chǔ)與遍歷</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; /* 頂點(diǎn)個(gè)數(shù)及邊的個(gè)數(shù) */&

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

43、<p>　　printf("請(qǐng)輸入頂點(diǎn)個(gè)數(shù)及邊的個(gè)數(shù)：\n");</p><p>　　scanf("%d%d",&G->vexsnum,&G->arcsnum);</p><p>　　printf("請(qǐng)讀入頂點(diǎn)信息，建立頂點(diǎn)表：\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("請(qǐng)輸入相鄰接的兩邊的頂點(diǎn)信息：\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頂點(diǎn)的度為：\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>　　} /* 各頂點(diǎn)的度 */</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、 /* 鄰接點(diǎn)域 */</p><p>　　struct node *next; /* 鏈域 */</p><p>　　}enode; /* 邊表結(jié)點(diǎn) */</p><p>　　typedef struct</p><p><b>　　{</b></p><p

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

54、的鄰接表 */</p><p><b>　　{</b></p><p>　　int i,j,k,sum;</p><p><b>　　enode *s;</b></p><p>　　printf("請(qǐng)讀入頂點(diǎn)信息，建立頂點(diǎn)表：\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("請(qǐng)輸入相鄰接的兩邊的頂點(diǎn)信息：\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)); /* 生成鄰接點(diǎn)序號(hào)為j的表結(jié)點(diǎn)*s */</p><p>　　s->adjvex=j;</p><p>　　s->next=a[i].link;</p><p>　　a[i].li

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

59、j].link=s; /* 將*s插入頂點(diǎn)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頂點(diǎn)的度為：\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>　　} /* 各頂點(diǎn)的度 */</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]); /* 訪問(wèn)出發(fā)點(diǎn)Vi+1 */</p><p>

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

67、1的鄰接點(diǎn)Vi+1未曾訪問(wèn)過(guò)，則從Vi+1出發(fā)進(jìn)行深度優(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; /* 順序隊(duì)列的類型 */</p><p>　　sequeue *p; /* p是順序隊(duì)列類型的指針 */</p>

69、;<p>　　void setnull() /* 置隊(duì)列p為空對(duì) */</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的隊(duì)頭元素 */</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插入隊(duì)列p的隊(duì)尾 */</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() /* 刪除隊(duì)列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]); /* 訪問(wèn)出發(fā)點(diǎn)Vk+1 */</p><p>　　visited2[k]=1;</p><p>　　enqueue(k);</p><p>　　while(!

81、empty()) /* 隊(duì)非空時(shí)執(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]); /* 訪問(wèn)Vi+1的未曾訪問(wèn)的鄰接點(diǎn)Vj+1 */</p><p>　　visited2[j]=1;</p><p>　　enqueue(j); /* 訪問(wèn)

83、過(guò)的頂點(diǎn)入隊(duì) */</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的鄰接點(diǎn) */</p><p><b>　　{</b></p><p>　　if(!visited3[p->adjvex])&

86、lt;/p><p>　　dfs2(p->adjvex); /* 從Vi+1的未曾訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索 */</p><p>　　p=p->next; /* 找Vi+1下一個(gè)鄰接點(diǎn) */</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的鄰接點(diǎn) */</p>

90、<p><b>　　{</b></p><p>　　if(!visited4[p->adjvex]) /* 訪問(wèn)Vi+1的未曾訪問(wèn)的鄰接點(diǎn) */</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); /* 訪問(wèn)過(guò)的頂點(diǎn)入隊(duì) */</p><p><b>　　}</b></p><p>　　p=p->next; /* 找Vi+1的下一個(gè)鄰接點(diǎn) */&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("=============歡迎進(jìn)

94、入=============\n");</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　printf("請(qǐng)選擇輸入\n1為用鄰接矩陣存儲(chǔ)圖\n2為用鄰接表存儲(chǔ)圖\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("請(qǐng)選擇輸入\n1為鄰接矩陣深度優(yōu)先遍歷\n2為鄰接矩陣廣度優(yōu)先遍歷\n0為返回繼續(xù)選擇圖的存儲(chǔ)：\n");</p><p>　　scanf("%d",&y);</p><p><b>　　switch(y)

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

98、p><p>　　case 2:printf("請(qǐng)輸入廣度優(yōu)先遍歷的頂點(diǎn)：\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;請(qǐng)選擇輸入\n1為鄰接表深度優(yōu)先遍歷\n2為鄰接表廣度優(yōu)先遍歷\n0為返回繼續(xù)選擇圖的存儲(chǔ)：\n：");</p><p>　　scanf("%d",& z);</p><p><b>　　switch(z)</b></p><p><b>　　{</b></p>

101、<p>　　case 1:printf("請(qǐng)輸入深度優(yōu)先遍歷的頂點(diǎn)：\n");</p><p>　　scanf("%d",&s);</p><p>　　dfs2(s);break;</p><p>　　case 2:printf("請(qǐng)輸入廣度優(yōu)先遍歷的頂點(diǎn)：\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>　　第六章 測(cè)試結(jié)果</b></p><

104、p>　　由于學(xué)習(xí)之初對(duì)圖的存儲(chǔ)結(jié)構(gòu)了解不是很清楚，所以在運(yùn)行出了錯(cuò)誤。首先在運(yùn)行當(dāng)中少了一句算法：在建立鄰接表，輸入頂點(diǎn)信息時(shí)，少了getchar()語(yǔ)句。因?yàn)槌绦虮旧頉](méi)報(bào)錯(cuò)，但是在執(zhí)行的過(guò)程中出現(xiàn)了錯(cuò)誤的信息，而且總是在執(zhí)行鄰接表操作時(shí)出錯(cuò)。另外在宏定義時(shí)定義了m,n，但我還在main函數(shù)中定義了int類型的m,n，所以程序報(bào)錯(cuò)了，這讓我懂得了宏定義的作用和意義。在小的細(xì)節(jié)上，偶爾打錯(cuò)單詞，造成錯(cuò)誤。

105、 </p><p>　　V0 V3</p><p>　　例如我們運(yùn)用右圖（無(wú)向圖）來(lái)執(zhí)行操作的話 </p><p>　　便可得到相應(yīng)的結(jié)果： </p><p>　　V1 V2</p>

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

107、t;<b>　　圖b</b></p><p>　　在main函數(shù)中還有相應(yīng)的子菜單，當(dāng)我們?cè)谥鞑藛沃羞x的是1用鄰接矩陣存儲(chǔ)時(shí)，子菜單中就有一系列算法：鄰接矩陣深度優(yōu)先遍歷（圖b）和廣度優(yōu)先遍歷（圖c）。</p><p><b>　　圖c</b></p><p><b>　　第七章 思想總結(jié)</b>&l

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

109、程中自己通過(guò)看書(shū)和課外資料，并請(qǐng)教其他同學(xué)，慢慢地對(duì)C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)知識(shí)有所熟悉。所以，這次學(xué)習(xí)之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎(chǔ)知識(shí)。</p><p>　　2、必須培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。自己在編程時(shí)經(jīng)常因?yàn)橐恍╊愃朴凇吧倭朔痔?hào)”、“單詞打錯(cuò)”的小錯(cuò)誤而導(dǎo)致錯(cuò)誤，不夠認(rèn)真細(xì)致，這給自己帶來(lái)了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。我想這不僅是對(duì)于程序設(shè)計(jì)，

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