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

1、屆課程設(shè)計圖的建立與遍歷圖的建立與遍歷課程設(shè)計論文課程設(shè)計論文學(xué)生姓名 學(xué) 號 所屬學(xué)院 信息工程學(xué)院 專 業(yè) 計算機科學(xué)與技術(shù) 班 級 計算機 指導(dǎo)教師 教師職稱 講師 塔里木大學(xué)教務(wù)處制塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 1 頁 共 10 頁目錄目錄前言前言.1正文正文.11.1 課程設(shè)計的教學(xué)目的和任務(wù).11.2 課程設(shè)計的主要內(nèi)容.11.3 課程設(shè)計報告的要求 .22.1.問題描述及基本要求.22.2.算法思想.22.3 模塊劃分.32.3.1 深度優(yōu)先搜索.32.3.2 廣度優(yōu)先搜索法.42.3.3 分析與探討.42.3.4 圖的存儲.52.4 測試數(shù)據(jù).82.5 測試情況 .8總總

2、結(jié)結(jié) .1010參考文獻(xiàn)：參考文獻(xiàn)： .1010附附 錄錄 .1111課程總結(jié)課程總結(jié) .1414塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 0 頁 共 10 頁前言前言圖遍歷又稱圖的遍歷，屬于數(shù)據(jù)結(jié)構(gòu)中的內(nèi)容。指的是從圖中的任一頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎(chǔ)之上。 由于圖結(jié)構(gòu)本身的復(fù)雜性，所以圖的遍歷操作也較復(fù)雜，主要表現(xiàn)在以下四個方面: 在圖結(jié)構(gòu)中，沒有一個自然的首結(jié)點，圖中任意一個頂點都可作為第一個被訪問的結(jié)點。 在非連通圖中，從一個頂點出發(fā)，只能夠訪問它所在的連通分量上的所有

3、頂點，因此，還需考慮如何選取下一個出發(fā)點以訪問圖中其余的連通分量。 在圖結(jié)構(gòu)中，如果有回路存在，那么一個頂點被訪問之后，有可能沿回路又回到該頂點。 在圖結(jié)構(gòu)中，一個頂點可以和其它多個頂點相連，當(dāng)這樣的頂點訪問過后，存在如何選取下一個要訪問的頂點的問題。正文正文1.1 課程設(shè)計的教學(xué)目的和任務(wù)(1) 使學(xué)生進(jìn)一步理解和掌握所學(xué)的各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實現(xiàn)算法，以及它們在程序中的使用方法。(2) 使學(xué)生初步掌握軟件開發(fā)過程的問題分析、設(shè)計、編碼、測試等基本方法和基本技能。(3) 使學(xué)生掌握使用各種計算機資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計的基本能力。(4) 使學(xué)生能用系

4、統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。1.2 課程設(shè)計的主要內(nèi)容(1) 問題分析和任務(wù)定義。根據(jù)題目的要求，充分地分析和理解問題，明確問題要求做什么？限制條件是什么？(2) 邏輯設(shè)計。對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明） ，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。(3) 物理設(shè)計。定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽代碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰

5、、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。(4)程序編碼。把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。(5) 程序調(diào)試與測試。采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。(6) 結(jié)果分析。程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯

6、誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析。塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 1 頁 共 10 頁(7) 撰寫課程設(shè)計報告。1.3 3 課程設(shè)計報告的要求課程設(shè)計報告要求規(guī)范書寫。應(yīng)當(dāng)包括如下內(nèi)容： 問題描述：描述要求編程解決的問題。 基本要求：給出程序要達(dá)到的具體的要求。 測試數(shù)據(jù)：設(shè)計測試數(shù)據(jù)，或具體給出測試數(shù)據(jù)。要求測試數(shù)據(jù)能全面地測試所設(shè)計程序的功能。 算法思想：描述解決相應(yīng)問題算法的設(shè)計思想。 模塊劃分：描述所設(shè)計程序的各個模塊（即函數(shù)）功能。 數(shù)據(jù)結(jié)構(gòu)：給出所使用的基本抽象數(shù)據(jù)類型，所定義的具體問題的數(shù)據(jù)類型，以及新定義的抽象數(shù)據(jù)類型。 源程序：給出所有源程序清單，要求程序有

7、充分的注釋語句，至少要注釋每個函數(shù)參數(shù)的含義和函數(shù)返回值的含義。 測試情況：給出程序的測試情況，并分析運行結(jié)果。 算法的時空分析(包括基本操作和其他算法的時間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)設(shè)想；經(jīng)驗和體會等。 參考文獻(xiàn)：列出參考的相關(guān)資料和書籍。2.1.2.1.問題描述及基本要求利用深度優(yōu)先搜索和廣度優(yōu)先搜索完成出具的排序。/要求建立一個菜單，菜單包含 4個菜單項供選擇：1、建立圖的鄰接矩陣；2、建立圖的鄰接表； 3、對圖進(jìn)行深度優(yōu)先遍歷；4、對圖進(jìn)行廣度優(yōu)先遍歷。要求從鍵盤輸入無向有權(quán)圖的頂點數(shù)、邊數(shù)、每條邊的起始頂點序號、終點序號、權(quán)值，將每條邊的信息存入到鄰接矩陣和鄰接表中。從鍵盤輸入

8、深度優(yōu)先遍歷和廣度優(yōu)先遍歷圖時初始出發(fā)的頂點的序號，要求在遍歷過程中輸出訪問過的結(jié)點序號。2.2. 算法思想遍歷圖的過程實質(zhì)上是通過邊或弧找鄰接點的過程，因此廣度優(yōu)先搜索遍歷圖和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對頂點訪問的順序不同。深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的結(jié)點，如果它還有以此為起點而未搜過的邊，就沿著邊繼續(xù)搜索下去。當(dāng)結(jié)點 v 的所有邊都已被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點 v 有那條邊的始結(jié)點。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點可達(dá)的所有結(jié)點為止。如果還存在未被發(fā)現(xiàn)的結(jié)點，則選擇其中一個作為源結(jié)點并重復(fù)以上過程，整個過程反復(fù)進(jìn)行

9、直到所有結(jié)點都被發(fā)現(xiàn)為止。深度優(yōu)先搜索基本算法如下遞歸算法：PROCEDURE dfs_try(i);FOR i:=1 to maxr DOBEGINIF 子結(jié)點 mr 符合條件 THENBEGIN產(chǎn)生的子結(jié)點 mr 入棧；IF 子結(jié)點 mr 是目標(biāo)結(jié)點 THEN 輸出ELSE dfs_try(i+1);棧頂元素出棧;塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 2 頁 共 10 頁END;END; 寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索算法）是最簡單的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijksta 單源最短路徑算法和 Prim 最小生成樹算法都采用了與寬度優(yōu)先搜索類似的思想。寬度優(yōu)先

10、搜索的核心思想是：從初始結(jié)點開始，應(yīng)用算符生成第一層結(jié)點，檢查目標(biāo)結(jié)點是否在這些后繼結(jié)點中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的結(jié)點逐一擴展，得到第二層結(jié)點，并逐一檢查第二層結(jié)點中是否包含目標(biāo)結(jié)點。若沒有，再用算符逐一擴展第二層所有結(jié)點，如此依次擴展，直到發(fā)現(xiàn)目標(biāo)結(jié)點為止。寬度優(yōu)先搜索基本算法如下：list1:=source; 加入初始結(jié)點，list 為待擴展結(jié)點的表head:=0; 隊首指針foot:=1; 隊尾指針REPEAThead:=head+1;FOR x:=1 to 規(guī)則數(shù) DOBEGIN根據(jù)規(guī)則產(chǎn)生新結(jié)點 nw;IF not_appear(nw,list) THEN 若新結(jié)點隊列

11、中不存在，則加到隊尾BEGINfoot:=foot+1;listfoot:=nw;listfoot.father:=head;IF listfoot=目標(biāo)結(jié)點 THEN 輸出；END；END；UNTIL headfoot; 隊列為空表明再無結(jié)點可擴展2.32.3 模塊劃分2.3.1 深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索法是樹的先根遍歷的推廣，它的基本思想是:從圖 G 的某個頂點 v0 出發(fā)，訪問 v0，然后選擇一個與 v0 相鄰且沒被訪問過的頂點 vi 訪問，再從 vi 出發(fā)選擇一個與vi 相鄰且未被訪問的頂點 vj 進(jìn)行訪問，依次繼續(xù)。如果當(dāng)前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到

12、已被訪問的頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點 w，從 w 出發(fā)按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸算法如下: Boolean visitedMAX_VERTEX_NUM; /訪問標(biāo)志數(shù)組 Status (*VisitFunc)(int v); /VisitFunc 是訪問函數(shù)，對圖的每個頂點調(diào)用該函數(shù) void DFSTraverse (Graph G, Status(*Visit)(int v) VisitFunc = Visit; for(v=0; vG.vexnum; +v) visitedv = FALSE; /訪問標(biāo)志數(shù)組初始化 for(v=0; v=0

13、; w=NextAdjVex(G,v,w) /FirstAdjVex 返回 v 的第一個鄰接頂點，若頂點在 G 中沒有鄰接頂點，則返回空(0)。 /若 w 是 v 的鄰接頂點，NextAdjVex 返回 v 的(相對于 w 的)下一個鄰接頂點。 /若 w 是 v 的最后一個鄰接點，則返回空(0)。 if(!visitedw) DFS(G, w); /對 v 的尚未訪問的鄰接頂點 w 調(diào)用 DFS 2.3.2 廣度優(yōu)先搜索法圖的廣度優(yōu)先搜索是樹的按層次遍歷的推廣，它的基本思想是:首先訪問初始點 vi，并將其標(biāo)記為已訪問過，接著訪問 vi 的所有未被訪問過的鄰接點 vi1,vi2, vi t，并均

14、標(biāo)記已訪問過，然后再按照 vi1,vi2, vi t 的次序，訪問每一個頂點的所有未被訪問過的鄰接點，并均標(biāo)記為已訪問過，依次類推，直到圖中所有和初始點 vi 有路徑相通的頂點都被訪問過為止。其非遞歸算法如下: Boolean visitedMAX_VERTEX_NUM; /訪問標(biāo)志數(shù)組 Status (*VisitFunc)(int v); /VisitFunc 是訪問函數(shù)，對圖的每個頂點調(diào)用該函數(shù) void BFSTraverse (Graph G, Status(*Visit)(int v) VisitFunc = Visit; for(v=0; vG.vexnum, +v) visit

15、edv = FALSE; initQueue(Q); /置空輔助隊列 Q for(v=0; v=0; w=NextAdjVex(G,u,w) if(!Visitedw) /w 為 u 的尚未訪問的鄰接頂點 Visitedw=TRUE; VisitFunc(w); EnQueue(Q, w); 2.3.3 分析與探討目錄結(jié)構(gòu)是一種典型的樹形結(jié)構(gòu)，為了方便對目錄的查找，遍歷等操作，可以選擇孩子兄弟雙親鏈表來存儲數(shù)的結(jié)構(gòu)。程序中要求對目錄的大小進(jìn)行重新計算，根據(jù)用戶的輸入來建立相應(yīng)的孩子兄弟雙親鏈表，最后輸入樹形結(jié)構(gòu)?？梢砸胍粋€ Tree 類，將樹的構(gòu)造，銷毀，目錄大小的重新計算（reSize）

16、，建立樹形鏈表結(jié)構(gòu)（parse） ，樹形結(jié)構(gòu)輸出（outPut）等一系列操作都封裝起來，同時對于每一個樹的借點，它的私有變量除了名稱（Name） ，大?。⊿ize）和層數(shù)（Depth）之外，根據(jù)孩子兄弟雙親鏈表表示的需要，還要設(shè)置三個指針，即父指針（Tree*parent）,下一個兄弟指針（Tree*NextSibling）和第一個孩子指針（Tree*Firstchild） 。下面是幾個主要函數(shù)的實現(xiàn)。1.建立樹形鏈表結(jié)構(gòu)的函數(shù) parse()根據(jù)輸入來確定樹形關(guān)系是，首先讀取根借點目錄/文件名和大小值，并根據(jù)這些信息建立塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 4 頁 共 10 頁一個新的節(jié)點；然后

17、讀入后面的各行信息，對于同一括號中的內(nèi)容，即具有相同父節(jié)點的那些節(jié)點建立兄弟關(guān)聯(lián)。這個函數(shù)實際上是采用層數(shù)遍歷建立樹形鏈表結(jié)構(gòu)。定義一個Tree*類型的數(shù)組 treeArray ，用來存放目錄的節(jié)點信息，并定義兩個整型變量 head 和rear，head 值用來標(biāo)記當(dāng)前節(jié)點的父節(jié)點位置，每處理完一對括號，head 需要增加 1,即下一對待處理括號的父節(jié)點在 treeArray 中要往后移一個位置。如果當(dāng)前處理的節(jié)點是目錄類型，則將它放在 treeArray 數(shù)組中，rear 是 treeArray 的下標(biāo)變量，加入一個樹的節(jié)點，并和 head 所指的父節(jié)點建立關(guān)聯(lián)，但是不用放入 treeArr

18、ay 中。2.目錄大小重新計算函數(shù)reSize()輸入數(shù)據(jù)中對目錄大小的初始化值一般為 1，而目錄的真正大小應(yīng)該是自身的大小和它包含的所有文件及子目錄的大小之和。因此，在計算目錄大小的時候，需要遍歷它下面所有的文件和子目錄，可以采用遞歸嵌套的后序遍歷方式。另外要注意，采用孩子兄弟雙親鏈表表示時，父目錄下的所有子目錄和子文件都在該父目錄的左子樹上（右字?jǐn)?shù)第一個節(jié)點是該目錄的兄弟節(jié)點） ，所以遍歷的時候只需要遍歷目錄的左字?jǐn)?shù)即可。3.輸出樹形結(jié)構(gòu)的函數(shù) outPut()輸出是一個線序遍歷的過程。為完成對樹形的輸出，兄弟目錄之前需要相同的縮進(jìn)，用|上下相連，而斧子目錄或父目錄和子文件之間需要設(shè)定正確

19、的縮進(jìn)，子目錄或子文件要比父目錄向右縮進(jìn) 8 個空格。設(shè)置一個標(biāo)志數(shù)組 flag11（每個目錄下最大層次數(shù)為 10） ，當(dāng)前 Tree*temp 指針?biāo)傅墓?jié)點如果有兄弟節(jié)點，則置 flag 數(shù)組值為 1，否則置為 0；并由此節(jié)點反復(fù)查詢它的祖先節(jié)點的情況，知道根節(jié)點位置。輸出時，遇到flag =1 時，屏幕輸出“| ” ，表明是兄弟節(jié)點；遇到 flag =0 時則輸出“ ” ，這樣就可以保證兄弟節(jié)點之間有相同的縮進(jìn)，而子節(jié)點總比父節(jié)點享有縮進(jìn) 8 個空格。2.3.4 圖的存儲圖的存儲圖的深度優(yōu)先遍歷假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問，深度優(yōu)先遍歷可以從圖的初始點出發(fā)，訪問初始點，然后依次從

20、 v 未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 v 有路徑相通的頂點都被訪問到；若此時仍有頂點未被訪問到，則從另一個未被訪問的頂點出發(fā)，重復(fù)上述過程，直至所有點都被訪問到為止。這是一個遞歸的過程。所以在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點是否被訪問。具體過程應(yīng)為：先訪問初始點 Vi，并標(biāo)志其已被訪問。此時定義一指向邊結(jié)點的指針 p，并建立一個 while（）循環(huán)，以指針?biāo)笇ο蟛粸榭諡榭刂茥l件，當(dāng) Vi 的鄰接點未被訪問時，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將 p 指針指向下一個邊結(jié)點。這樣就可以完成圖的深度優(yōu)先遍

21、歷了。圖的廣度優(yōu)先遍歷：廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點 v 出發(fā)，在訪問了 v 之后訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點的鄰接點”被訪問，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尙有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直到圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以 v 為起始點，由近及遠(yuǎn)，依次訪問和 v 有路徑相通且路徑長度為 1，2，的頂點。所以要實現(xiàn)算法必須先建立一個元素類型為整形的空隊列，并定義隊首與隊尾指針，同時也要定義一個標(biāo)志數(shù)組以標(biāo)記結(jié)點是否

22、被訪問。同樣，也是從初始點出發(fā)開始訪問，訪問初始點，標(biāo)志其已被訪問，并將其入隊。當(dāng)隊列非塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 5 頁 共 10 頁空時進(jìn)行循環(huán)處理。當(dāng)結(jié)點被訪問時對其進(jìn)行標(biāo)志，并入隊列。通過 while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結(jié)點，完成圖的廣度優(yōu)先遍歷。定義鄰接表的邊結(jié)點類型以及鄰接表類型：struct edgenodeint adjvex; /該弧所指向的頂點的位置 edgenode * next; /指向下條條弧的指針; /定義鄰接表的邊結(jié)點類型typedef edgenode * * adjlist; /定義鄰接表類型初始化圖的鄰接表：需建立一個鄰接表初始

23、化函數(shù)對圖的鄰接表進(jìn)行初始化。即建立一個所有邊結(jié)點都為空的鄰接表。void InitGAdjoin(adjlist&GL,int n)/初始化圖的鄰接表GL=new edgenode*n;for(int i=1;i=n;i+)GLi=NULL;建立并輸出圖的鄰接表首先必須輸入圖的相關(guān)信息，包括圖的頂點數(shù)、邊數(shù)、各條邊的起點和終點，為保證輸入數(shù)據(jù)的正確性，我在程序中設(shè)計了一個判斷所輸結(jié)點是否越界的函數(shù) check（）當(dāng)所輸?shù)捻旤c序號超出序號的范圍時則報錯，并要求重新輸入。還有就圖是否有向，此時可定義一變量，圖的是否有向，可用變量的值來表示。此處定了變量 m，當(dāng)圖為無向時，m 等于 0。圖

24、為有向時 m 等于 1。用 if（）語句判斷 m 的值，就可將圖分有向和無向兩種情況來進(jìn)行分析了。對于無向圖，各條邊的起點和終點互為鄰接點。所以必須把起點添加到終點的鄰接點域中，并把終點添加到起點的鄰接點域中。而對于有向圖，只能是將弧頭添加到弧尾的鄰接點域中。最后是輸出鄰接表，即對于每個頂點，輸出其鄰接點。由于不了解 C+中繪圖函數(shù)的用法，所以利用一些符號來達(dá)到圖形化的效果。鄰接表輸出的相關(guān)代碼如下：cout圖的鄰接表為:endl;for(i=1;i=n;i+)edgenode*p=GLi;couti-1 |Vnext)cout|adjvex;cout|;塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 6

25、頁 共 10 頁coutendl; /輸出鄰接表圖的遍歷圖的遍歷深度優(yōu)先遍歷圖的鄰接表：假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問，深度優(yōu)先遍歷可以從圖的初始點出發(fā)，訪問初始點，然后依次從 v 未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 v 有路徑相通的頂點都被訪問到；若此時仍有頂點未被訪問到，則從另一個未被訪問的頂點出發(fā)，重復(fù)上述過程，直至所有點都被訪問到為止。這是一個遞歸的過程。所以在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點是否被訪問。具體過程應(yīng)為：在深度優(yōu)先遍歷函數(shù)的參數(shù)中定義一個標(biāo)志數(shù)組 bool*& visit

26、ed，當(dāng)某結(jié)點已被訪問時，標(biāo)志數(shù)組的值為關(guān)鍵字 ture，未被訪問時其值為關(guān)鍵字 false。先訪問初始點 Vi，并標(biāo)志其已被訪問。此時定義一指向邊結(jié)點的指針 p，并建立一個 while（）循環(huán)，以指針?biāo)笇ο蟛粸榭諡榭刂茥l件，當(dāng) Vi的鄰接點未被訪問時，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將 p 指針指向下一個邊結(jié)點。這樣就可以完成圖的深度優(yōu)先遍歷了。深度優(yōu)先遍歷的相關(guān)代碼如下：void dfsAdjoin(adjlist GL,bool*& visited,int i,int n)/從初始點出發(fā)深度優(yōu)先搜索鄰接表 GL 表示的圖coutiadjvex; /j 為 Vi 的一個鄰接點

27、的序號if(!visitedj)dfsAdjoin(GL,visited,j,n);p=p-next; /使 p 指向 Vi 單鏈表的下一個邊結(jié)點廣度優(yōu)先遍歷圖的鄰接表廣度優(yōu)先遍歷圖的鄰接表：圖的廣度優(yōu)先遍歷是從初始點出發(fā)，訪問初始點，再訪問初始點的鄰接點。當(dāng)初始點的所有鄰接點都被訪問過時，再依次訪問各鄰接點的鄰接點。如此循環(huán)下去。算法的實現(xiàn)必須依靠輔助隊列，結(jié)點被訪問后，對其進(jìn)行標(biāo)記，并將結(jié)點入隊列。所以要實現(xiàn)算法必須先建立一個元素類型為整形的空隊列，并定義隊首與隊尾指針，同時也要定義一個標(biāo)志數(shù)組 bool*& visited 以標(biāo)記結(jié)點是否被訪問。塔里木大學(xué)信息工程學(xué)院課程設(shè)計第

28、7 頁 共 10 頁同樣，也是從初始點 Vi 出發(fā)開始訪問，訪問初始點，標(biāo)志其已被訪問，并將已訪問過的初始點序號 i 入隊。當(dāng)隊列非空時進(jìn)行循環(huán)處理，刪除隊首元素，第一次執(zhí)行時 k 的值為 i，即 front=(front+1)%MaxLength。然后取 Vk 鄰接表的表頭指針 int k=qfront; edgenode* p=GLk。當(dāng)邊結(jié)點指針 p 不為空時，通過while（）循環(huán)，并以 p 是否為空為控制條件，依次搜索 Vk 的每一個結(jié)點。若Vj 沒有被訪問過則進(jìn)行處理。訪問完后，將 p 指向 p-next。其中的 while 循環(huán)部分的代碼如下：while(p!=NULL) /依次

29、搜索 Vk 的每一個結(jié)點int j=p-adjvex; /Vj 為 Vk 的一個鄰接點if(!visitedj) /若 Vj 沒有被訪問過則進(jìn)行處理coutjnext;這樣就可以訪問所有結(jié)點，完成圖的廣度優(yōu)先遍歷2.4 測試數(shù)據(jù)輸入頂點數(shù)和弧數(shù):8 9 輸入 8 個頂點. 輸入頂點 0:a 輸入頂點 1:b 輸入頂點 2:c 輸入頂點 3:d 輸入頂點 4:e 輸入頂點 5:f 輸入頂點 6:g 輸入頂點 7:h 輸入 9 條弧. 輸入弧 0:a b 1 輸入弧 1:b d 1 輸入弧 2:b e 1 輸入弧 3:d h 1 輸入弧 4:e h 1 輸入弧 5:a c 1 輸入弧 6:c f

30、1 輸入弧 7:c g 1 輸入弧 8:f g 1 塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 8 頁 共 10 頁2.5 測試情況輸入數(shù)據(jù)后出現(xiàn)的效果：圖圖 1 1 編譯初始界面編譯初始界面塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 9 頁 共 10 頁圖圖 2 2 編碼界面編碼界面小小 結(jié)結(jié)通過該題目的設(shè)計過程,對數(shù)據(jù)結(jié)構(gòu)以及二叉樹的邏輯結(jié)構(gòu),存儲結(jié)構(gòu)的理解,對樹的數(shù)據(jù)結(jié)構(gòu)上基本運算的實現(xiàn)有所掌握,對課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會了如何把學(xué)到的知識用于解決實際問題,鍛煉了自己動手的能力。完成所有的工作是非常困難和耗時的。在以后的學(xué)習(xí)中我會更加注意自己各個方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計時我遇到

31、了很多的問題，在老師的幫助，和對各種資料的查閱中，將問題解決，培養(yǎng)了我自主動手，獨立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅實的基礎(chǔ)。參考參考文獻(xiàn)：文獻(xiàn)：1譚浩強編著.C+課程設(shè)計.北京：清華大學(xué)社，20042S.B.Lippman，J.Lajoie 著.潘愛民譯.C+Primer（3rd Edition）中文版.北京：中國電力出版社，20023H.M.Deitel，Paul James Deitel 著.薛萬鵬譯.C+程序設(shè)計教程.北京：機械工業(yè)出版社，20004Stephen R.Savis 著.C+ For Dummies 4th edition，IDG Books World

32、wide，Inc.，20025Harvey M.Deitel .Jack W.Davidson 著.邱仲潘譯.C+大學(xué)教程（第二版）.北京：電子工業(yè)出版社，20026James P.Cohoon.Jack W.Davidson 著.劉瑞挺等譯.C+程序設(shè)計（第三版）.北京：電子工業(yè)出版社 塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 10 頁 共 10 頁附附 錄錄#include /#include #define INFINITY 32767 #define MAX_VEX 20 /最大頂點個數(shù) #define QUEUE_SIZE (MAX_VEX+1) /隊列長度 using namespace

33、std; bool *visited; /訪問標(biāo)志數(shù)組 /圖的鄰接矩陣存儲結(jié)構(gòu) typedef struct char *vexs; /頂點向量 int arcsMAX_VEXMAX_VEX; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點數(shù)和弧數(shù) Graph; /隊列類 class Queue public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; vo

34、id DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear; ; /圖 G 中查找元素 c 的位置 int Locate(Graph G,char c) for(int i=0;iG.vexnum;i+) if(G.vexsi=c) return i; return -1; /創(chuàng)建無向網(wǎng) void CreateUDN(Graph &G) int i,j,w,s1,s2; char a,b,temp; printf(輸入頂點數(shù)和弧數(shù):); sc

35、anf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); /接收回車 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配頂點數(shù)目 printf(輸入%d 個頂點.n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化頂點 printf(輸入頂點%d:,i); scanf(%c,&G.vexsi); 塔里木大學(xué)信息工程學(xué)院課程設(shè)計第 11 頁 共 10 頁temp=getchar(); /接收回車 for(i=0;iG.vexnum;i+) /初始化鄰接矩陣 for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(輸入%d 條弧.n,G.arcnum); for(i=0;i=0 & kG.vexnum) /k 合理 for(int i=0;i=0 & i=0 & jG.vexnum) /i,j 合理 fo