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

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

2、t;<p>　　專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級 計(jì)算機(jī) </p><p>　　指導(dǎo)教師 </p><p>　　教師職稱 講師 </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.問題描述及基本要求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、儲5</p><p>　　2.4 測試數(shù)據(jù)8</p><p>　　2.5 測試情況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>　　圖遍歷又稱圖的遍歷，屬于數(shù)據(jù)結(jié)構(gòu)中的內(nèi)容。指的是從圖中的任一頂點(diǎn)出發(fā)，對圖中的所有頂點(diǎn)訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎(chǔ)之

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

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

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

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

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

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

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

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

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

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

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

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

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

20、那條邊的始結(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的結(jié)點(diǎn)，則選擇其中一個作為源結(jié)點(diǎn)并重復(fù)以上過程，整個過程反復(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)先搜索算法（又稱廣度優(yōu)先搜索算法）是最簡單的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijksta單源最短路徑算法和Prim最小生成樹算法都采用了與寬度優(yōu)先搜索類似的思想。</p><p>　　寬度優(yōu)先搜索的核心思想是：從初始結(jié)點(diǎn)開始，應(yīng)用算符生成第一層結(jié)點(diǎn)，檢查目標(biāo)結(jié)點(diǎn)是否在這些后繼結(jié)點(diǎn)中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的結(jié)點(diǎn)逐一擴(kuò)展，得到第二層結(jié)點(diǎn)

24、，并逐一檢查第二層結(jié)點(diǎn)中是否包含目標(biāo)結(jié)點(diǎn)。若沒有，再用算符逐一擴(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ì)列為空表明再無結(jié)點(diǎn)可擴(kuò)展}&l

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

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

30、每個頂點(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、 //訪問標(biāo)志數(shù)組初始化 </p><p>　　for(v=0; v<G.vexnum; ++v) </p><p>　　if(!visited[v]) </p><p>　　DFS(G, v); //對尚未訪問的頂點(diǎn)調(diào)用DFS </p><p><b>　　} </b></p><p>　

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

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

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

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

36、Func是訪問函數(shù)，對圖的每個頂點(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的尚未訪問的鄰接頂點(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)是一種典型的樹形結(jié)構(gòu)，為了方便對目錄的查找，遍歷等操作，可以選擇孩子兄弟雙親鏈表來存儲數(shù)的結(jié)構(gòu)。程序中要求對目錄的大小進(jìn)行重新計(jì)算，根據(jù)用戶的輸入來建立相應(yīng)的孩子兄弟雙親鏈表，最后輸入樹形結(jié)構(gòu)?？梢砸胍粋€Tree類，將樹的構(gòu)造

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

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

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

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

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

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

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

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

49、gt;　　需建立一個鄰接表初始化函數(shù)對圖的鄰接表進(jìn)行初始化。即建立一個所有邊結(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、個判斷所輸結(jié)點(diǎn)是否越界的函數(shù)check（）當(dāng)所輸?shù)捻旤c(diǎn)序號超出序號的范圍時則報(bào)錯，并要求重新輸入。還有就圖是否有向，此時可定義一變量，圖的是否有向，可用變量的值來表示。此處定了變量m，當(dāng)圖為無向時，m等于0。圖為有向時m等于1。用if（）語句判斷m的值，就可將圖分有向和無向兩種情況來進(jìn)行分析了。對于無向圖，各條邊的起點(diǎn)和終點(diǎn)互為鄰接點(diǎn)。所以必須把起點(diǎn)添加到終點(diǎn)的鄰接點(diǎn)域中，并把終點(diǎn)添加到起點(diǎn)的鄰接點(diǎn)域中。而對于有向圖，只能是將弧頭添加到

52、弧尾的鄰接點(diǎn)域中。最后是輸出鄰接表，即對于每個頂點(diǎn)，輸出其鄰接點(diǎn)。由于不了解C++中繪圖函數(shù)的用法，所以利用一些符號來達(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)未曾被訪問，深度優(yōu)先遍歷可以從圖的初始點(diǎn)出發(fā)，訪問初始點(diǎn)，然后依次從v未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到；若此時仍有頂點(diǎn)未被訪問到，則從另一個未被訪問的頂點(diǎn)出發(fā)，重復(fù)上述過程，直至所有點(diǎn)都被訪問到為止。這是一個遞歸的過程。所以在實(shí)現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)

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

57、數(shù)訪問之。然后將p指針指向下一個邊結(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的一個鄰接點(diǎn)的序號</p><p>　　if(!visited[j])</p><p>　　dfsAdjoin(GL,visited,j,n);</p><p>　　p=p->next; //使p指向Vi單鏈表的下一個邊結(jié)點(diǎn)</p><p><b>

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

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

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

63、p><p>　　int j=p->adjvex; //Vj為Vk的一個鄰接點(diǎn)</p><p>　　if(!visited[j]){ //若Vj沒有被訪問過則進(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>　　這樣就可以訪問所有結(jié)點(diǎn)，

65、完成圖的廣度優(yōu)先遍歷</p><p><b>　　2.4 測試數(shù)據(jù)</b></p><p>　　輸入頂點(diǎn)數(shù)和弧數(shù):8 9 輸入8個頂點(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 測試情況</b></p><p>　　輸入數(shù)據(jù)后出現(xiàn)的效果：</p><p>　　圖1 編譯初始界面</p><p><b>

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

68、中我會更加注意自己各個方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計(jì)時我遇到了很多的問題，在老師的幫助，和對各種資料的查閱中，將問題解決，培養(yǎ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著.潘愛民譯.C++Primer（3rd Edition）中文版.北京：中國電力出版社，2002</p><p>　　[3]H.M.Deitel，Paul James Deitel著.薛萬鵬譯.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)個數(shù) </p><p>　　#define QUEUE_SIZE (MAX_VEX+1) //隊(duì)列長度 </p><p>　　using namespace std; </p><p>　　bool *visited; //訪問標(biāo)志數(shù)組 </p><p>　　//圖的鄰接矩陣存儲結(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ì)列類 </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ǎ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(); //接收回車 </p><p>

81、　　G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配頂點(diǎn)數(shù)目 </p><p>　　printf("輸入%d個頂點(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(); //接收回車 </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(); //接收回車 </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的第一個鄰接頂點(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個鄰接頂點(diǎn)的下一個鄰接頂點(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時,k為-1 </p><p>　　for(i=0;i<G.vexnum;i++) </p><p>　　if(!v

91、isited[i]) DFS(G,i); //對尚未訪問的頂點(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]); //訪問第k個頂點(diǎn) </p><p>　　for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i)) </p><p>　　if(!visited[i]) DFS(G,i); //對k的尚未訪問的鄰接頂點(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尚未訪問 </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的尚未訪問的鄰接頂點(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語言知識和數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固，編程能力也有了一定的提高。同時也學(xué)會了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點(diǎn)體會：</p><p>　　1

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

103、的小錯誤而導(dǎo)致錯誤，不夠認(rèn)真細(xì)致，這給自己帶來了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。我想這不僅是對于程序設(shè)計(jì)，做任何事都應(yīng)如此。</p><p>　　3.這次課程設(shè)計(jì)也讓我充分認(rèn)識到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實(shí)際應(yīng)用。</p><p>　　總之，在這次實(shí)