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

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

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

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

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

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

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

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

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

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

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

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

12、已被訪問的頂點(diǎn)序列中最后一個(gè)擁有未被訪問的相鄰頂點(diǎn)的頂點(diǎn) w，從 w 出發(fā)按同樣的方法向前遍歷，直到圖中所有頂點(diǎn)都被訪問。其遞歸算法如下: Boolean visitedMAX_VERTEX_NUM; /訪問標(biāo)志數(shù)組 Status (*VisitFunc)(int v); /VisitFunc 是訪問函數(shù)，對(duì)圖的每個(gè)頂點(diǎn)調(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è)鄰接頂點(diǎn)，若頂點(diǎn)在 G 中沒有鄰接頂點(diǎn)，則返回空(0)。 /若 w 是 v 的鄰接頂點(diǎn)，NextAdjVex 返回 v 的(相對(duì)于 w 的)下一個(gè)鄰接頂點(diǎn)。 /若 w 是 v 的最后一個(gè)鄰接點(diǎn)，則返回空(0)。 if(!visitedw) DFS(G, w); /對(duì) v 的尚未訪問的鄰接頂點(diǎn) w 調(diào)用 DFS 2.3.2 廣度優(yōu)先搜索法圖的廣度優(yōu)先搜索是樹的按層次遍歷的推廣，它的基本思想是:首先訪問初始點(diǎn) vi，并將其標(biāo)記為已訪問過，接著訪問 vi 的所有未被訪問過的鄰接點(diǎn) vi1,vi2, vi t，并均

14、標(biāo)記已訪問過，然后再按照 vi1,vi2, vi t 的次序，訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)，并均標(biāo)記為已訪問過，依次類推，直到圖中所有和初始點(diǎn) vi 有路徑相通的頂點(diǎn)都被訪問過為止。其非遞歸算法如下: Boolean visitedMAX_VERTEX_NUM; /訪問標(biāo)志數(shù)組 Status (*VisitFunc)(int v); /VisitFunc 是訪問函數(shù)，對(duì)圖的每個(gè)頂點(diǎn)調(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); /置空輔助隊(duì)列 Q for(v=0; v=0; w=NextAdjVex(G,u,w) if(!Visitedw) /w 為 u 的尚未訪問的鄰接頂點(diǎn) Visitedw=TRUE; VisitFunc(w); EnQueue(Q, w); 2.3.3 分析與探討目錄結(jié)構(gòu)是一種典型的樹形結(jié)構(gòu)，為了方便對(duì)目錄的查找，遍歷等操作，可以選擇孩子兄弟雙親鏈表來存儲(chǔ)數(shù)的結(jié)構(gòu)。程序中要求對(duì)目錄的大小進(jìn)行重新計(jì)算，根據(jù)用戶的輸入來建立相應(yīng)的孩子兄弟雙親鏈表，最后輸入樹形結(jié)構(gòu)?？梢砸胍粋€(gè) Tree 類，將樹的構(gòu)造，銷毀，目錄大小的重新計(jì)算（reSize）

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

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

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

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

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

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

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

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

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

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

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

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

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

29、搜索 Vk 的每一個(gè)結(jié)點(diǎn)int j=p-adjvex; /Vj 為 Vk 的一個(gè)鄰接點(diǎn)if(!visitedj) /若 Vj 沒有被訪問過則進(jìn)行處理coutjnext;這樣就可以訪問所有結(jié)點(diǎn)，完成圖的廣度優(yōu)先遍歷2.4 測(cè)試數(shù)據(jù)輸入頂點(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 輸入弧 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è)計(jì)第 8 頁 共 10 頁2.5 測(cè)試情況輸入數(shù)據(jù)后出現(xiàn)的效果：圖圖 1 1 編譯初始界面編譯初始界面塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 9 頁 共 10 頁圖圖 2 2 編碼界面編碼界面小小 結(jié)結(jié)通過該題目的設(shè)計(jì)過程,對(duì)數(shù)據(jù)結(jié)構(gòu)以及二叉樹的邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)的理解,對(duì)樹的數(shù)據(jù)結(jié)構(gòu)上基本運(yùn)算的實(shí)現(xiàn)有所掌握,對(duì)課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問題,鍛煉了自己動(dòng)手的能力。完成所有的工作是非常困難和耗時(shí)的。在以后的學(xué)習(xí)中我會(huì)更加注意自己各個(gè)方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計(jì)時(shí)我遇到

31、了很多的問題，在老師的幫助，和對(duì)各種資料的查閱中，將問題解決，培養(yǎng)了我自主動(dòng)手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。參考參考文獻(xiàn)：文獻(xiàn)：1譚浩強(qiáng)編著.C+課程設(shè)計(jì).北京：清華大學(xué)社，20042S.B.Lippman，J.Lajoie 著.潘愛民譯.C+Primer（3rd Edition）中文版.北京：中國(guó)電力出版社，20023H.M.Deitel，Paul James Deitel 著.薛萬鵬譯.C+程序設(shè)計(jì)教程.北京：機(jī)械工業(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è)計(jì)（第三版）.北京：電子工業(yè)出版社 塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 10 頁 共 10 頁附附 錄錄#include /#include #define INFINITY 32767 #define MAX_VEX 20 /最大頂點(diǎn)個(gè)數(shù) #define QUEUE_SIZE (MAX_VEX+1) /隊(duì)列長(zhǎng)度 using namespace

33、std; bool *visited; /訪問標(biāo)志數(shù)組 /圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) typedef struct char *vexs; /頂點(diǎn)向量 int arcsMAX_VEXMAX_VEX; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) Graph; /隊(duì)列類 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(輸入頂點(diǎn)數(shù)和弧數(shù):); sc

35、anf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); /接收回車 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配頂點(diǎn)數(shù)目 printf(輸入%d 個(gè)頂點(diǎn).n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化頂點(diǎn) printf(輸入頂點(diǎn)%d:,i); scanf(%c,&G.vexsi); 塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 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