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

1、<p><b>　　《圖的建立與遍歷》</b></p><p><b>　　課程設(shè)計(jì)論文</b></p><p>　　學(xué)生姓名 </p><p>　　學(xué) 號(hào) </p><p>　　所屬學(xué)院 信息工程學(xué)院 </p&g

2、t;<p>　　專(zhuān) 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級(jí) 計(jì)算機(jī) </p><p>　　指導(dǎo)教師 </p><p>　　教師職稱(chēng) 講師 </p><p><b>　　目錄</b></p>

3、<p><b>　　前言1</b></p><p><b>　　正文1</b></p><p>　　1.1 課程設(shè)計(jì)的教學(xué)目的和任務(wù)1</p><p>　　1.2 課程設(shè)計(jì)的主要內(nèi)容1</p><p>　　1.3課程設(shè)計(jì)報(bào)告的要求2</p><p>　　

4、2.1.問(wèn)題描述及基本要求2</p><p>　　2.2.算法思想2</p><p>　　2.3 模塊劃分3</p><p>　　2.3.1深度優(yōu)先搜索3</p><p>　　2.3.2廣度優(yōu)先搜索法4</p><p>　　2.3.3分析與探討4</p><p>　　2.3.4圖的存

5、儲(chǔ)5</p><p>　　2.4 測(cè)試數(shù)據(jù)8</p><p>　　2.5 測(cè)試情況8</p><p><b>　　總 結(jié)10</b></p><p><b>　　參考文獻(xiàn)：10</b></p><p><b>　　附 錄11</b><

6、;/p><p><b>　　課程總結(jié)14</b></p><p><b>　　前言</b></p><p>　　圖遍歷又稱(chēng)圖的遍歷，屬于數(shù)據(jù)結(jié)構(gòu)中的內(nèi)容。指的是從圖中的任一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪(fǎng)問(wèn)一次且只訪(fǎng)問(wèn)一次。圖的遍歷操作和樹(shù)的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎(chǔ)之

7、上。 </p><p>　　由于圖結(jié)構(gòu)本身的復(fù)雜性，所以圖的遍歷操作也較復(fù)雜，主要表現(xiàn)在以下四個(gè)方面: </p><p>　　① 在圖結(jié)構(gòu)中，沒(méi)有一個(gè)"自然"的首結(jié)點(diǎn)，圖中任意一個(gè)頂點(diǎn)都可作為第一個(gè)被訪(fǎng)問(wèn)的結(jié)點(diǎn)。 </p><p>　　② 在非連通圖中，從一個(gè)頂點(diǎn)出發(fā)，只能夠訪(fǎng)問(wèn)它所在的連通分量上的所有頂點(diǎn)，因此，還需考慮如何選取下一個(gè)出發(fā)點(diǎn)以訪(fǎng)

8、問(wèn)圖中其余的連通分量。 </p><p>　?、?在圖結(jié)構(gòu)中，如果有回路存在，那么一個(gè)頂點(diǎn)被訪(fǎng)問(wèn)之后，有可能沿回路又回到該頂點(diǎn)。 ④ 在圖結(jié)構(gòu)中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)訪(fǎng)問(wèn)過(guò)后，存在如何選取下一個(gè)要訪(fǎng)問(wèn)的頂點(diǎn)的問(wèn)題。</p><p><b>　　正文</b></p><p>　　1.1 課程設(shè)計(jì)的教學(xué)目的和任務(wù)</p

9、><p>　　(1) 使學(xué)生進(jìn)一步理解和掌握所學(xué)的各種基本抽象數(shù)據(jù)類(lèi)型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?lt;/p><p>　　(2) 使學(xué)生初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、設(shè)計(jì)、編碼、測(cè)試等基本方法和基本技能。</p><p>　　(3) 使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。</p>&

10、lt;p>　　(4) 使學(xué)生能用系統(tǒng)的觀(guān)點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　　1.2 課程設(shè)計(jì)的主要內(nèi)容</p><p>　　(1) 問(wèn)題分析和任務(wù)定義。</p><p>　　根據(jù)題目的要求，充分地分析和理解問(wèn)題，明確問(wèn)題要求做什么？限制條件是什么？</p><p><

11、;b>　　(2) 邏輯設(shè)計(jì)。</b></p><p>　　對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類(lèi)型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類(lèi)型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫(xiě)出每個(gè)抽象數(shù)據(jù)類(lèi)型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明），各個(gè)主要模塊的算法，并畫(huà)出模塊之間的調(diào)用關(guān)系圖。</p><p><b>　　(3) 物理設(shè)計(jì)。&l

12、t;/b></p><p>　　定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫(xiě)出各函數(shù)的偽代碼算法。在這個(gè)過(guò)程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫(xiě)出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義，寫(xiě)出函數(shù)形式的算法框架。</p><p><b>　　(4)程序編碼。&

13、lt;/b></p><p>　　把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚。</p><p>　　(5) 程序調(diào)試與測(cè)試。</p><p>　　采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過(guò)修改程序來(lái)證實(shí)它或繞過(guò)它。調(diào)試正確后，認(rèn)真整理源程序及其注釋?zhuān)纬?/p>

14、格式和風(fēng)格良好的源程序清單和結(jié)果。</p><p><b>　　(6) 結(jié)果分析。</b></p><p>　　程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析。</p><p>　　(7) 撰寫(xiě)課程設(shè)計(jì)報(bào)告。</p><p>　　1.3課程設(shè)計(jì)報(bào)告的要求</p>

15、<p>　　課程設(shè)計(jì)報(bào)告要求規(guī)范書(shū)寫(xiě)。應(yīng)當(dāng)包括如下內(nèi)容：</p><p>　?、?問(wèn)題描述：描述要求編程解決的問(wèn)題。</p><p>　?、?基本要求：給出程序要達(dá)到的具體的要求。</p><p>　?、?測(cè)試數(shù)據(jù)：設(shè)計(jì)測(cè)試數(shù)據(jù)，或具體給出測(cè)試數(shù)據(jù)。要求測(cè)試數(shù)據(jù)能全面地測(cè)試所設(shè)計(jì)程序的功能。</p><p>　　⑷ 算法思想：描

16、述解決相應(yīng)問(wèn)題算法的設(shè)計(jì)思想。</p><p>　?、?模塊劃分：描述所設(shè)計(jì)程序的各個(gè)模塊（即函數(shù)）功能。</p><p>　?、?數(shù)據(jù)結(jié)構(gòu)：給出所使用的基本抽象數(shù)據(jù)類(lèi)型，所定義的具體問(wèn)題的數(shù)據(jù)類(lèi)型，以及新定義的抽象數(shù)據(jù)類(lèi)型。</p><p>　?、?源程序：給出所有源程序清單，要求程序有充分的注釋語(yǔ)句，至少要注釋每個(gè)函數(shù)參數(shù)的含義和函數(shù)返回值的含義。</p&

17、gt;<p>　　⑻ 測(cè)試情況：給出程序的測(cè)試情況，并分析運(yùn)行結(jié)果。</p><p>　?、?算法的時(shí)空分析(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)設(shè)想；經(jīng)驗(yàn)和體會(huì)等。</p><p>　?、?參考文獻(xiàn)：列出參考的相關(guān)資料和書(shū)籍。</p><p>　　2.1.問(wèn)題描述及基本要求</p><p>　　利用深度

18、優(yōu)先搜索和廣度優(yōu)先搜索完成出具的排序。/要求建立一個(gè)菜單，菜單包含4個(gè)菜單項(xiàng)供選擇：1、建立圖的鄰接矩陣；2、建立圖的鄰接表； 3、對(duì)圖進(jìn)行深度優(yōu)先遍歷；4、對(duì)圖進(jìn)行廣度優(yōu)先遍歷。要求從鍵盤(pán)輸入無(wú)向有權(quán)圖的頂點(diǎn)數(shù)、邊數(shù)、每條邊的起始頂點(diǎn)序號(hào)、終點(diǎn)序號(hào)、權(quán)值，將每條邊的信息存入到鄰接矩陣和鄰接表中。從鍵盤(pán)輸入深度優(yōu)先遍歷和廣度優(yōu)先遍歷圖時(shí)初始出發(fā)的頂點(diǎn)的序號(hào)，要求在遍歷過(guò)程中輸出訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)序號(hào)。</p><p>

19、<b>　　2.2. 算法思想</b></p><p>　　遍歷圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，因此廣度優(yōu)先搜索遍歷圖和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪(fǎng)問(wèn)的順序不同。深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對(duì)于最新發(fā)現(xiàn)的結(jié)點(diǎn)，如果它還有以此為起點(diǎn)而未搜過(guò)的邊，就沿著邊繼續(xù)搜索下去。當(dāng)結(jié)點(diǎn)v的所有邊都已被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v有

20、那條邊的始結(jié)點(diǎn)。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的結(jié)點(diǎn)，則選擇其中一個(gè)作為源結(jié)點(diǎn)并重復(fù)以上過(guò)程，整個(gè)過(guò)程反復(fù)進(jìn)行直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。</p><p>　　深度優(yōu)先搜索基本算法如下{遞歸算法}：</p><p>　　PROCEDURE dfs_try(i);</p><p>　　FOR i:=1 to maxr DO<

21、/p><p><b>　　BEGIN</b></p><p>　　IF 子結(jié)點(diǎn) mr 符合條件 THEN</p><p><b>　　BEGIN</b></p><p>　　產(chǎn)生的子結(jié)點(diǎn)mr入棧；</p><p>　　IF 子結(jié)點(diǎn)mr是目標(biāo)結(jié)點(diǎn) </p><p

22、><b>　　THEN 輸出</b></p><p>　　ELSE dfs_try(i+1);</p><p><b>　　棧頂元素出棧;</b></p><p><b>　　END;</b></p><p><b>　　END; </b></

23、p><p>　　寬度優(yōu)先搜索算法（又稱(chēng)廣度優(yōu)先搜索算法）是最簡(jiǎn)單的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijksta單源最短路徑算法和Prim最小生成樹(shù)算法都采用了與寬度優(yōu)先搜索類(lèi)似的思想。</p><p>　　寬度優(yōu)先搜索的核心思想是：從初始結(jié)點(diǎn)開(kāi)始，應(yīng)用算符生成第一層結(jié)點(diǎn)，檢查目標(biāo)結(jié)點(diǎn)是否在這些后繼結(jié)點(diǎn)中，若沒(méi)有，再用產(chǎn)生式規(guī)則將所有第一層的結(jié)點(diǎn)逐一擴(kuò)展，得到第二層結(jié)點(diǎn)

24、，并逐一檢查第二層結(jié)點(diǎn)中是否包含目標(biāo)結(jié)點(diǎn)。若沒(méi)有，再用算符逐一擴(kuò)展第二層所有結(jié)點(diǎn)……，如此依次擴(kuò)展，直到發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)為止。</p><p>　　寬度優(yōu)先搜索基本算法如下：</p><p>　　list[1]:=source; {加入初始結(jié)點(diǎn)，list為待擴(kuò)展結(jié)點(diǎn)的表}</p><p>　　head:=0; {隊(duì)首指針}</p><p>　　f

25、oot:=1; {隊(duì)尾指針}</p><p><b>　　REPEAT</b></p><p>　　head:=head+1;</p><p>　　FOR x:=1 to 規(guī)則數(shù) DO</p><p><b>　　BEGIN</b></p><p>　　根據(jù)規(guī)則產(chǎn)生新結(jié)點(diǎn)nw

26、;</p><p>　　IF not_appear(nw,list) THEN {若新結(jié)點(diǎn)隊(duì)列中不存在，則加到隊(duì)尾}</p><p><b>　　BEGIN</b></p><p>　　foot:=foot+1;</p><p>　　list[foot]:=nw;</p><p>　　list[f

27、oot].father:=head;</p><p>　　IF list[foot]=目標(biāo)結(jié)點(diǎn) THEN 輸出；</p><p><b>　　END；</b></p><p><b>　　END；</b></p><p>　　UNTIL head>foot; {隊(duì)列為空表明再無(wú)結(jié)點(diǎn)可擴(kuò)展}&l

28、t;/p><p><b>　　2.3 模塊劃分</b></p><p>　　2.3.1深度優(yōu)先搜索</p><p>　　深度優(yōu)先搜索法是樹(shù)的先根遍歷的推廣，它的基本思想是:從圖G的某個(gè)頂點(diǎn)v0出發(fā)，訪(fǎng)問(wèn)v0，然后選擇一個(gè)與v0相鄰且沒(méi)被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)vi訪(fǎng)問(wèn)，再?gòu)膙i出發(fā)選擇一個(gè)與vi相鄰且未被訪(fǎng)問(wèn)的頂點(diǎn)vj進(jìn)行訪(fǎng)問(wèn)，依次繼續(xù)。如果當(dāng)前被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)

29、的所有鄰接頂點(diǎn)都已被訪(fǎng)問(wèn)，則退回到已被訪(fǎng)問(wèn)的頂點(diǎn)序列中最后一個(gè)擁有未被訪(fǎng)問(wèn)的相鄰頂點(diǎn)的頂點(diǎn)w，從w出發(fā)按同樣的方法向前遍歷，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)。其遞歸算法如下: </p><p>　　Boolean visited[MAX_VERTEX_NUM]; //訪(fǎng)問(wèn)標(biāo)志數(shù)組 </p><p>　　Status (*VisitFunc)(int v); //VisitFunc是訪(fǎng)問(wèn)函數(shù)，對(duì)圖的

30、每個(gè)頂點(diǎn)調(diào)用該函數(shù) </p><p>　　void DFSTraverse (Graph G, Status(*Visit)(int v)){ </p><p>　　VisitFunc = Visit; </p><p>　　for(v=0; v<G.vexnum; ++v) </p><p>　　visited[v] = FALSE;

31、 //訪(fǎng)問(wèn)標(biāo)志數(shù)組初始化 </p><p>　　for(v=0; v<G.vexnum; ++v) </p><p>　　if(!visited[v]) </p><p>　　DFS(G, v); //對(duì)尚未訪(fǎng)問(wèn)的頂點(diǎn)調(diào)用DFS </p><p><b>　　} </b></p><p>　

32、　void DFS(Graph G, int v){ //從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G </p><p>　　visited[v]=TRUE; VisitFunc(v); //訪(fǎng)問(wèn)第v個(gè)頂點(diǎn) </p><p>　　for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)) </p><p>　　//First

33、AdjVex返回v的第一個(gè)鄰接頂點(diǎn)，若頂點(diǎn)在G中沒(méi)有鄰接頂點(diǎn)，則返回空(0)。 </p><p>　　//若w是v的鄰接頂點(diǎn)，NextAdjVex返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)。 </p><p>　　//若w是v的最后一個(gè)鄰接點(diǎn)，則返回空(0)。 </p><p>　　if(!visited[w]) </p><p>　　DFS(G,

34、 w); //對(duì)v的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn)w調(diào)用DFS </p><p><b>　　} </b></p><p>　　2.3.2廣度優(yōu)先搜索法</p><p>　　圖的廣度優(yōu)先搜索是樹(shù)的按層次遍歷的推廣，它的基本思想是:首先訪(fǎng)問(wèn)初始點(diǎn)vi，并將其標(biāo)記為已訪(fǎng)問(wèn)過(guò)，接著訪(fǎng)問(wèn)vi的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)vi1,vi2,…, vi t，并均標(biāo)記已訪(fǎng)問(wèn)過(guò)，

35、然后再按照vi1,vi2,…, vi t的次序，訪(fǎng)問(wèn)每一個(gè)頂點(diǎn)的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，并均標(biāo)記為已訪(fǎng)問(wèn)過(guò)，依次類(lèi)推，直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。其非遞歸算法如下: </p><p>　　Boolean visited[MAX_VERTEX_NUM]; //訪(fǎng)問(wèn)標(biāo)志數(shù)組 </p><p>　　Status (*VisitFunc)(int v); //Visit

36、Func是訪(fǎng)問(wèn)函數(shù)，對(duì)圖的每個(gè)頂點(diǎn)調(diào)用該函數(shù) </p><p>　　void BFSTraverse (Graph G, Status(*Visit)(int v)){ </p><p>　　VisitFunc = Visit; </p><p>　　for(v=0; v<G.vexnum, ++v) </p><p>　　visite

37、d[v] = FALSE; </p><p>　　initQueue(Q); //置空輔助隊(duì)列Q </p><p>　　for(v=0; v<G.vexnum; ++v) </p><p>　　if(!visited[v]){ </p><p>　　visited[v]=TRUE; VisitFunc(v); </p>&

38、lt;p>　　EnQueue(Q, v); //v入隊(duì)列 </p><p>　　while(!QueueEmpty(Q)){ </p><p>　　DeQueue(Q, u); //隊(duì)頭元素出隊(duì)并置為u </p><p>　　for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w)) </p>&l

39、t;p>　　if(!Visited[w]){ //w為u的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn) </p><p>　　Visited[w]=TRUE; VisitFunc(w); </p><p>　　EnQueue(Q, w); </p><p><b>　　} </b></p><p><b>　　} </b&g

40、t;</p><p><b>　　} </b></p><p>　　2.3.3分析與探討</p><p>　　目錄結(jié)構(gòu)是一種典型的樹(shù)形結(jié)構(gòu)，為了方便對(duì)目錄的查找，遍歷等操作，可以選擇孩子兄弟雙親鏈表來(lái)存儲(chǔ)數(shù)的結(jié)構(gòu)。程序中要求對(duì)目錄的大小進(jìn)行重新計(jì)算，根據(jù)用戶(hù)的輸入來(lái)建立相應(yīng)的孩子兄弟雙親鏈表，最后輸入樹(shù)形結(jié)構(gòu)?？梢砸胍粋€(gè)Tree類(lèi)，將樹(shù)的構(gòu)造

41、，銷(xiāo)毀，目錄大小的重新計(jì)算（reSize），建立樹(shù)形鏈表結(jié)構(gòu)（parse），樹(shù)形結(jié)構(gòu)輸出（outPut）等一系列操作都封裝起來(lái)，同時(shí)對(duì)于每一個(gè)樹(shù)的借點(diǎn)，它的私有變量除了名稱(chēng)（Name），大?。⊿ize）和層數(shù)（Depth）之外，根據(jù)孩子兄弟雙親鏈表表示的需要，還要設(shè)置三個(gè)指針，即父指針（Tree*parent）,下一個(gè)兄弟指針（Tree*NextSibling）和第一個(gè)孩子指針（Tree*Firstchild）。下面是幾個(gè)主要函數(shù)的實(shí)現(xiàn)

42、。1.建立樹(shù)形鏈表結(jié)構(gòu)的函數(shù)parse()根據(jù)輸入來(lái)確定樹(shù)形關(guān)系是，首先讀取根借點(diǎn)目錄/文件名和大小值，并根據(jù)這些信息建立一個(gè)新的節(jié)點(diǎn)；然后讀入后面的各行信息，對(duì)于同一括號(hào)中的內(nèi)容，即具有相同父節(jié)點(diǎn)的那些節(jié)點(diǎn)建立兄弟關(guān)聯(lián)。這個(gè)函數(shù)實(shí)際上是采用層數(shù)遍歷建立樹(shù)形鏈表結(jié)構(gòu)。定義一個(gè)Tree*類(lèi)型的數(shù)組treeArray[ ]，用</p><p><b>　　2.3.4圖的存儲(chǔ)</b></p&

43、gt;<p><b>　　圖的深度優(yōu)先遍歷</b></p><p>　　假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪(fǎng)問(wèn)，深度優(yōu)先遍歷可以從圖的初始點(diǎn)出發(fā)，訪(fǎng)問(wèn)初始點(diǎn)，然后依次從v未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；若此時(shí)仍有頂點(diǎn)未被訪(fǎng)問(wèn)到，則從另一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)出發(fā)，重復(fù)上述過(guò)程，直至所有點(diǎn)都被訪(fǎng)問(wèn)到為止。這是一個(gè)遞歸的過(guò)程。所以在實(shí)現(xiàn)深度優(yōu)

44、先遍歷的過(guò)程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪(fǎng)問(wèn)。</p><p>　　具體過(guò)程應(yīng)為：先訪(fǎng)問(wèn)初始點(diǎn)Vi，并標(biāo)志其已被訪(fǎng)問(wèn)。此時(shí)定義一指向邊結(jié)點(diǎn)的指針p，并建立一個(gè)while（）循環(huán)，以指針?biāo)笇?duì)象不為空為控制條件，當(dāng)Vi的鄰接點(diǎn)未被訪(fǎng)問(wèn)時(shí)，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪(fǎng)問(wèn)之。然后將p指針指向下一個(gè)邊結(jié)點(diǎn)。這樣就可以完成圖的深度優(yōu)先遍歷了。</p>

45、<p><b>　　圖的廣度優(yōu)先遍歷：</b></p><p>　　廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的按層次遍歷的過(guò)程。假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪(fǎng)問(wèn)了v之后訪(fǎng)問(wèn)它們的鄰接點(diǎn)，并使“先被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)的鄰接點(diǎn)”被訪(fǎng)問(wèn)，直到圖中所有已被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)到。若此時(shí)圖中尙有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直到圖中所有

46、頂點(diǎn)都被訪(fǎng)問(wèn)到為止。換句話(huà)說(shuō)，廣度優(yōu)先搜索遍歷圖的過(guò)程是以v為起始點(diǎn)，由近及遠(yuǎn)，依次訪(fǎng)問(wèn)和v有路徑相通且路徑長(zhǎng)度為1，2，……的頂點(diǎn)。</p><p>　　所以要實(shí)現(xiàn)算法必須先建立一個(gè)元素類(lèi)型為整形的空隊(duì)列，并定義隊(duì)首與隊(duì)尾指針，同時(shí)也要定義一個(gè)標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪(fǎng)問(wèn)。同樣，也是從初始點(diǎn)出發(fā)開(kāi)始訪(fǎng)問(wèn)，訪(fǎng)問(wèn)初始點(diǎn)，標(biāo)志其已被訪(fǎng)問(wèn)，并將其入隊(duì)。當(dāng)隊(duì)列非空時(shí)進(jìn)行循環(huán)處理。當(dāng)結(jié)點(diǎn)被訪(fǎng)問(wèn)時(shí)對(duì)其進(jìn)行標(biāo)志，并入隊(duì)列。通過(guò)

47、while（）循環(huán)，并以是否被訪(fǎng)問(wèn)為控制條件，訪(fǎng)問(wèn)所有結(jié)點(diǎn)，完成圖的廣度優(yōu)先遍歷。</p><p>　　定義鄰接表的邊結(jié)點(diǎn)類(lèi)型以及鄰接表類(lèi)型：</p><p>　　struct edgenode{</p><p>　　int adjvex; //該弧所指向的頂點(diǎn)的位置</p><p>　　edgenode * ne

48、xt; //指向下條條弧的指針</p><p>　　}; //定義鄰接表的邊結(jié)點(diǎn)類(lèi)型</p><p>　　typedef edgenode * * adjlist; //定義鄰接表類(lèi)型</p><p><b>　　初始化圖的鄰接表：</b></p><p&

49、gt;　　需建立一個(gè)鄰接表初始化函數(shù)對(duì)圖的鄰接表進(jìn)行初始化。即建立一個(gè)所有邊結(jié)點(diǎn)都為空的鄰接表。</p><p>　　void InitGAdjoin(adjlist&GL,int n)</p><p>　　//初始化圖的鄰接表</p><p><b>　　{</b></p><p>　　GL=new edgen

50、ode*[n];</p><p>　　for(int i=1;i<=n;i++)GL[i]=NULL;</p><p><b>　　}</b></p><p>　　建立并輸出圖的鄰接表</p><p>　　首先必須輸入圖的相關(guān)信息，包括圖的頂點(diǎn)數(shù)、邊數(shù)、各條邊的起點(diǎn)和終點(diǎn)，為保證輸入數(shù)據(jù)的正確性，我在程序中設(shè)計(jì)了一

51、個(gè)判斷所輸結(jié)點(diǎn)是否越界的函數(shù)check（）當(dāng)所輸?shù)捻旤c(diǎn)序號(hào)超出序號(hào)的范圍時(shí)則報(bào)錯(cuò)，并要求重新輸入。還有就圖是否有向，此時(shí)可定義一變量，圖的是否有向，可用變量的值來(lái)表示。此處定了變量m，當(dāng)圖為無(wú)向時(shí)，m等于0。圖為有向時(shí)m等于1。用if（）語(yǔ)句判斷m的值，就可將圖分有向和無(wú)向兩種情況來(lái)進(jìn)行分析了。對(duì)于無(wú)向圖，各條邊的起點(diǎn)和終點(diǎn)互為鄰接點(diǎn)。所以必須把起點(diǎn)添加到終點(diǎn)的鄰接點(diǎn)域中，并把終點(diǎn)添加到起點(diǎn)的鄰接點(diǎn)域中。而對(duì)于有向圖，只能是將弧頭添加到

52、弧尾的鄰接點(diǎn)域中。最后是輸出鄰接表，即對(duì)于每個(gè)頂點(diǎn)，輸出其鄰接點(diǎn)。由于不了解C++中繪圖函數(shù)的用法，所以利用一些符號(hào)來(lái)達(dá)到圖形化的效果。鄰接表輸出的相關(guān)代碼如下：</p><p>　　cout<<"圖的鄰接表為:"<<endl;</p><p>　　for(i=1;i<=n;i++){</p><p>　　edgen

53、ode*p=GL[i];</p><p>　　cout<<i-1<<" |"<<"V"<<i;</p><p>　　for(p=GL[i];p!=NULL;p=p->next)</p><p>　　cout<<"|-|->|"<&

54、lt;p->adjvex;</p><p>　　cout<<"|^|";</p><p>　　cout<<endl; </p><p>　　} //輸出鄰接表</p><p><b>　　圖的遍歷</b></p><p>　　深度

55、優(yōu)先遍歷圖的鄰接表：</p><p>　　假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪(fǎng)問(wèn)，深度優(yōu)先遍歷可以從圖的初始點(diǎn)出發(fā)，訪(fǎng)問(wèn)初始點(diǎn)，然后依次從v未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；若此時(shí)仍有頂點(diǎn)未被訪(fǎng)問(wèn)到，則從另一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)出發(fā)，重復(fù)上述過(guò)程，直至所有點(diǎn)都被訪(fǎng)問(wèn)到為止。這是一個(gè)遞歸的過(guò)程。所以在實(shí)現(xiàn)深度優(yōu)先遍歷的過(guò)程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)

56、中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪(fǎng)問(wèn)。</p><p>　　具體過(guò)程應(yīng)為：在深度優(yōu)先遍歷函數(shù)的參數(shù)中定義一個(gè)標(biāo)志數(shù)組bool*& visited，當(dāng)某結(jié)點(diǎn)已被訪(fǎng)問(wèn)時(shí)，標(biāo)志數(shù)組的值為關(guān)鍵字ture，未被訪(fǎng)問(wèn)時(shí)其值為關(guān)鍵字false。先訪(fǎng)問(wèn)初始點(diǎn)Vi，并標(biāo)志其已被訪(fǎng)問(wèn)。此時(shí)定義一指向邊結(jié)點(diǎn)的指針p，并建立一個(gè)while（）循環(huán)，以指針?biāo)笇?duì)象不為空為控制條件，當(dāng)Vi的鄰接點(diǎn)未被訪(fǎng)問(wèn)時(shí)，遞歸調(diào)用深度優(yōu)先遍歷函

57、數(shù)訪(fǎng)問(wèn)之。然后將p指針指向下一個(gè)邊結(jié)點(diǎn)。這樣就可以完成圖的深度優(yōu)先遍歷了。</p><p>　　深度優(yōu)先遍歷的相關(guān)代碼如下：</p><p>　　void dfsAdjoin(adjlist GL,bool*& visited,int i,int n)</p><p>　　//從初始點(diǎn)出發(fā)深度優(yōu)先搜索鄰接表 GL表示的圖</p><p&g

58、t;<b>　　{</b></p><p>　　cout<<i<<' ';</p><p>　　visited[i]=true;</p><p>　　edgenode* p=GL[i];</p><p>　　while(p!=NULL){</p><p>　

59、　int j=p->adjvex; //j為Vi的一個(gè)鄰接點(diǎn)的序號(hào)</p><p>　　if(!visited[j])</p><p>　　dfsAdjoin(GL,visited,j,n);</p><p>　　p=p->next; //使p指向Vi單鏈表的下一個(gè)邊結(jié)點(diǎn)</p><p><b>

60、;　　}</b></p><p><b>　　}</b></p><p>　　廣度優(yōu)先遍歷圖的鄰接表：</p><p>　　圖的廣度優(yōu)先遍歷是從初始點(diǎn)出發(fā)，訪(fǎng)問(wèn)初始點(diǎn)，再訪(fǎng)問(wèn)初始點(diǎn)的鄰接點(diǎn)。當(dāng)初始點(diǎn)的所有鄰接點(diǎn)都被訪(fǎng)問(wèn)過(guò)時(shí)，再依次訪(fǎng)問(wèn)各鄰接點(diǎn)的鄰接點(diǎn)。如此循環(huán)下去。算法的實(shí)現(xiàn)必須依靠輔助隊(duì)列，結(jié)點(diǎn)被訪(fǎng)問(wèn)后，對(duì)其進(jìn)行標(biāo)記，并將結(jié)點(diǎn)入隊(duì)

61、列。</p><p>　　所以要實(shí)現(xiàn)算法必須先建立一個(gè)元素類(lèi)型為整形的空隊(duì)列，并定義隊(duì)首與隊(duì)尾指針，同時(shí)也要定義一個(gè)標(biāo)志數(shù)組bool*& visited以標(biāo)記結(jié)點(diǎn)是否被訪(fǎng)問(wèn)。同樣，也是從初始點(diǎn)Vi出發(fā)開(kāi)始訪(fǎng)問(wèn)，訪(fǎng)問(wèn)初始點(diǎn)，標(biāo)志其已被訪(fǎng)問(wèn)，并將已訪(fǎng)問(wèn)過(guò)的初始點(diǎn)序號(hào)i入隊(duì)。當(dāng)隊(duì)列非空時(shí)進(jìn)行循環(huán)處理，刪除隊(duì)首元素，第一次執(zhí)行時(shí)k的值為i，即front=(front+1)%MaxLength。然后取Vk鄰接表的表

62、頭指針int k=q[front]; edgenode* p=GL[k]。當(dāng)邊結(jié)點(diǎn)指針p不為空時(shí)，通過(guò)while（）循環(huán)，并以p是否為空為控制條件，依次搜索Vk的每一個(gè)結(jié)點(diǎn)。若Vj沒(méi)有被訪(fǎng)問(wèn)過(guò)則進(jìn)行處理。訪(fǎng)問(wèn)完后，將p指向p->next。其中的while循環(huán)部分的代碼如下：</p><p>　　while(p!=NULL){</p><p>　　//依次搜索Vk的每一個(gè)結(jié)點(diǎn)</

63、p><p>　　int j=p->adjvex; //Vj為Vk的一個(gè)鄰接點(diǎn)</p><p>　　if(!visited[j]){ //若Vj沒(méi)有被訪(fǎng)問(wèn)過(guò)則進(jìn)行處理</p><p>　　cout<<j<<' ';</p><p>　　visited[j]=true;</p><p

64、>　　rear=(rear+1)%MaxLength;</p><p>　　q[rear]=j;</p><p><b>　　}</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　這樣就可以訪(fǎng)問(wèn)所有結(jié)點(diǎn)，

65、完成圖的廣度優(yōu)先遍歷</p><p><b>　　2.4 測(cè)試數(shù)據(jù)</b></p><p>　　輸入頂點(diǎn)數(shù)和弧數(shù):8 9 輸入8個(gè)頂點(diǎn). 輸入頂點(diǎn)0:a 輸入頂點(diǎn)1:b 輸入頂點(diǎn)2:c 輸入頂點(diǎn)3:d 輸入頂點(diǎn)4:e 輸入頂點(diǎn)5:f 輸入頂點(diǎn)6:g 輸入頂點(diǎn)7:h 輸入9條弧. 輸入弧0:a b 1 輸入弧1:b d 1 輸入弧2:b e 1

66、 輸入弧3:d h 1 輸入弧4:e h 1 輸入弧5:a c 1 輸入弧6:c f 1 輸入弧7:c g 1 輸入弧8:f g 1 </p><p><b>　　2.5 測(cè)試情況</b></p><p>　　輸入數(shù)據(jù)后出現(xiàn)的效果：</p><p>　　圖1 編譯初始界面</p><p><b>

67、　　圖2 編碼界面</b></p><p><b>　　小 結(jié)</b></p><p>　　通過(guò)該題目的設(shè)計(jì)過(guò)程,對(duì)數(shù)據(jù)結(jié)構(gòu)以及二叉樹(shù)的邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)的理解,對(duì)樹(shù)的數(shù)據(jù)結(jié)構(gòu)上基本運(yùn)算的實(shí)現(xiàn)有所掌握,對(duì)課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題,鍛煉了自己動(dòng)手的能力。完成所有的工作是非常困難和耗時(shí)的。在以后的學(xué)習(xí)

68、中我會(huì)更加注意自己各個(gè)方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計(jì)時(shí)我遇到了很多的問(wèn)題，在老師的幫助，和對(duì)各種資料的查閱中，將問(wèn)題解決，培養(yǎng)了我自主動(dòng)手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。</p><p><b>　　參考文獻(xiàn)：</b></p><p>　　[1]譚浩強(qiáng)編著.C++課程設(shè)計(jì).北京：清華大學(xué)社，2004</p><p

69、>　　[2]S.B.Lippman，J.Lajoie著.潘愛(ài)民譯.C++Primer（3rd Edition）中文版.北京：中國(guó)電力出版社，2002</p><p>　　[3]H.M.Deitel，Paul James Deitel著.薛萬(wàn)鵬譯.C++程序設(shè)計(jì)教程.北京：機(jī)械工業(yè)出版社，2000</p><p>　　[4]Stephen R.Savis著.C++ For Dummie

70、s 4th edition，IDG Books Worldwide，Inc.，2002</p><p>　　[5]Harvey M.Deitel .Jack W.Davidson著.邱仲潘譯.C++大學(xué)教程（第二版）.北京：電子工業(yè)出版社，2002</p><p>　　[6]James P.Cohoon.Jack W.Davidson著.劉瑞挺等譯.C++程序設(shè)計(jì)（第三版）.北京：電子工業(yè)

71、出版社</p><p><b>　　附 錄</b></p><p>　　#include <iostream> </p><p>　　//#include <malloc.h> </p><p>　　#define INFINITY 32767 </p><p>　　#de

72、fine MAX_VEX 20 //最大頂點(diǎn)個(gè)數(shù) </p><p>　　#define QUEUE_SIZE (MAX_VEX+1) //隊(duì)列長(zhǎng)度 </p><p>　　using namespace std; </p><p>　　bool *visited; //訪(fǎng)問(wèn)標(biāo)志數(shù)組 </p><p>　　//圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) </p&

73、gt;<p>　　typedef struct{ </p><p>　　char *vexs; //頂點(diǎn)向量 </p><p>　　int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣 </p><p>　　int vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) </p><p><b>　　}

74、Graph; </b></p><p><b>　　//隊(duì)列類(lèi) </b></p><p>　　class Queue{ </p><p><b>　　public: </b></p><p>　　void InitQueue(){ </p><p>　　base=

75、(int *)malloc(QUEUE_SIZE*sizeof(int)); </p><p>　　front=rear=0; </p><p><b>　　} </b></p><p>　　void EnQueue(int e){ </p><p>　　base[rear]=e; </p><p&g

76、t;　　rear=(rear+1)%QUEUE_SIZE; </p><p><b>　　} </b></p><p>　　void DeQueue(int &e){ </p><p>　　e=base[front]; </p><p>　　front=(front+1)%QUEUE_SIZE; </p&g

77、t;<p><b>　　} </b></p><p><b>　　public: </b></p><p>　　int *base; </p><p>　　int front; </p><p>　　int rear; </p><p><b>　　}

78、; </b></p><p>　　//圖G中查找元素c的位置 </p><p>　　int Locate(Graph G,char c){ </p><p>　　for(int i=0;i<G.vexnum;i++) </p><p>　　if(G.vexs[i]==c) return i; </p><

79、p>　　return -1; </p><p><b>　　} </b></p><p><b>　　//創(chuàng)建無(wú)向網(wǎng) </b></p><p>　　void CreateUDN(Graph &G){ </p><p>　　int i,j,w,s1,s2; </p><

80、;p>　　char a,b,temp; </p><p>　　printf("輸入頂點(diǎn)數(shù)和弧數(shù):"); </p><p>　　scanf("%d%d",&G.vexnum,&G.arcnum); </p><p>　　temp=getchar(); //接收回車(chē) </p><p>

81、　　G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配頂點(diǎn)數(shù)目 </p><p>　　printf("輸入%d個(gè)頂點(diǎn).\n",G.vexnum); </p><p>　　for(i=0;i<G.vexnum;i++){ //初始化頂點(diǎn) </p><p>　　printf("輸入頂點(diǎn)

82、%d:",i); </p><p>　　scanf("%c",&G.vexs[i]); </p><p>　　temp=getchar(); //接收回車(chē) </p><p><b>　　} </b></p><p>　　for(i=0;i<G.vexnum;i++) //初始化

83、鄰接矩陣 </p><p>　　for(j=0;j<G.vexnum;j++) </p><p>　　G.arcs[i][j]=INFINITY; </p><p>　　printf("輸入%d條弧.\n",G.arcnum); </p><p>　　for(i=0;i<G.arcnum;i++){ //初始化

84、弧 </p><p>　　printf("輸入弧%d:",i); </p><p>　　scanf("%c %c %d",&a,&b,&w); //輸入一條邊依附的頂點(diǎn)和權(quán)值 </p><p>　　temp=getchar(); //接收回車(chē) </p><p>　　s1=Loca

85、te(G,a); </p><p>　　s2=Locate(G,b); </p><p>　　G.arcs[s1][s2]=G.arcs[s2][s1]=w; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　//圖G中

86、頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn) </p><p>　　int FirstVex(Graph G,int k){ </p><p>　　if(k>=0 && k<G.vexnum){ //k合理 </p><p>　　for(int i=0;i<G.vexnum;i++) </p><p>　　if(G.arcs[k]

87、[i]!=INFINITY) return i; </p><p><b>　　} </b></p><p>　　return -1; </p><p><b>　　} </b></p><p>　　//圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) </p><p>　　in

88、t NextVex(Graph G,int i,int j){ </p><p>　　if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理 </p><p>　　for(int k=j+1;k<G.vexnum;k++) </p><p&g

89、t;　　if(G.arcs[i][k]!=INFINITY) return k; </p><p><b>　　} </b></p><p>　　return -1; </p><p><b>　　} </b></p><p><b>　　//深度優(yōu)先遍歷 </b></p

90、><p>　　void DFS(Graph G,int k){ </p><p><b>　　int i; </b></p><p>　　if(k==-1){ //第一次執(zhí)行DFS時(shí),k為-1 </p><p>　　for(i=0;i<G.vexnum;i++) </p><p>　　if(!v

91、isited[i]) DFS(G,i); //對(duì)尚未訪(fǎng)問(wèn)的頂點(diǎn)調(diào)用DFS </p><p><b>　　} </b></p><p><b>　　else{ </b></p><p>　　visited[k]=true; </p><p>　　printf("%c ",G.vex

92、s[k]); //訪(fǎng)問(wèn)第k個(gè)頂點(diǎn) </p><p>　　for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i)) </p><p>　　if(!visited[i]) DFS(G,i); //對(duì)k的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn)i遞歸調(diào)用DFS </p><p><b>　　} </b></p><p&

93、gt;<b>　　} </b></p><p><b>　　//廣度優(yōu)先遍歷 </b></p><p>　　void BFS(Graph G){ </p><p><b>　　int k; </b></p><p>　　Queue Q; //輔助隊(duì)列Q </p>

94、<p>　　Q.InitQueue(); </p><p>　　for(int i=0;i<G.vexnum;i++) </p><p>　　if(!visited[i]){ //i尚未訪(fǎng)問(wèn) </p><p>　　visited[i]=true; </p><p>　　printf("%c ",G.vexs

95、[i]); </p><p>　　Q.EnQueue(i); //i入列 </p><p>　　while(Q.front!=Q.rear){ </p><p>　　Q.DeQueue(k); //隊(duì)頭元素出列并置為k </p><p>　　for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w)) &

96、lt;/p><p>　　if(!visited[w]){ //w為k的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn) </p><p>　　visited[w]=true; </p><p>　　printf("%c ",G.vexs[w]); </p><p>　　Q.EnQueue(w); </p><p><b>

97、　　} </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　//主函數(shù) </b></p><p>　　voi

98、d main(){ </p><p><b>　　int i; </b></p><p><b>　　Graph G; </b></p><p>　　CreateUDN(G); </p><p>　　visited=(bool *)malloc(G.vexnum*sizeof(bool)); <

99、;/p><p>　　printf("\n廣度優(yōu)先遍歷: "); </p><p>　　for(i=0;i<G.vexnum;i++) </p><p>　　visited[i]=false; </p><p>　　DFS(G,-1); </p><p>　　printf("\n深度優(yōu)先遍

100、歷: ");</p><p>　　for(i=0;i<G.vexnum;i++) </p><p>　　visited[i]=false; </p><p><b>　　BFS(G); </b></p><p>　　printf("\n程序結(jié)束.\n"); </p>&l

101、t;p><b>　　}</b></p><p><b>　　課程總結(jié)</b></p><p>　　轉(zhuǎn)眼，為期兩周的《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)實(shí)習(xí)即將結(jié)束了。在這次實(shí)習(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

102、.必須牢固掌握基礎(chǔ)知識(shí)。由于C語(yǔ)言是大一所學(xué)知識(shí)，有所遺忘，且未掌握好這學(xué)期所學(xué)的《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課，所以在實(shí)習(xí)之初感到棘手。不知如何下手，但在后來(lái)的實(shí)習(xí)過(guò)程中自己通過(guò)看書(shū)和課外資料，并請(qǐng)教其他同學(xué)，慢慢地對(duì)C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)知識(shí)有所熟悉。這時(shí)才逐漸有了思路。所以，這次實(shí)習(xí)之后，我告誡自己：今后一定要牢固掌握好專(zhuān)業(yè)基礎(chǔ)知識(shí)。</p><p>　　2.必須培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。自己在編程時(shí)經(jīng)常因?yàn)橐恍╊?lèi)似于“少了分號(hào)”

103、的小錯(cuò)誤而導(dǎo)致錯(cuò)誤，不夠認(rèn)真細(xì)致，這給自己帶來(lái)了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。我想這不僅是對(duì)于程序設(shè)計(jì)，做任何事都應(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>　　總之，在這次實(shí)