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

1、<p><b>　　數(shù)學(xué)與計(jì)算機(jī)學(xué)院</b></p><p><b>　　課程設(shè)計(jì)說(shuō)明書(shū)</b></p><p>　　課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì) </p><p>　　課 程 代 碼: </p><p>　　題 目: 圖

2、的遍歷和生成樹(shù)求解實(shí)現(xiàn) </p><p><b>　　目 錄 </b></p><p><b>　　摘 要3</b></p><p><b>　　引 言4</b></p><p><b>　　1 需求分析5</b></p&

3、gt;<p>　　1.1任務(wù)與分析5</p><p><b>　　1.2測(cè)試數(shù)據(jù)5</b></p><p><b>　　2 概要設(shè)計(jì)5</b></p><p>　　2.1 ADT描述5</p><p>　　2.2程序模塊結(jié)構(gòu)7</p><p><

4、b>　　軟件結(jié)構(gòu)設(shè)計(jì)：7</b></p><p>　　2.3　各功能模塊7</p><p><b>　　3 詳細(xì)設(shè)計(jì)8</b></p><p>　　3.1結(jié)構(gòu)體定義19</p><p>　　3.2 初始化21</p><p>　　3.3 插入操作（四號(hào)黑體）21<

5、;/p><p><b>　　4 調(diào)試分析21</b></p><p>　　5 用戶使用說(shuō)明21</p><p><b>　　6 測(cè)試結(jié)果23</b></p><p><b>　　結(jié) 論26</b></p><p><b>　　摘 要

6、</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》課程主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。進(jìn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要達(dá)到以下目的：</p><p>　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；</p><p>　　初步掌

7、握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；</p><p>　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　　這次課程設(shè)計(jì)我們主要是應(yīng)用以前學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο蟪绦蛟O(shè)計(jì)知識(shí)，結(jié)合起來(lái)才完成

8、了這個(gè)程序。</p><p>　　因?yàn)閳D是一種較線形表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線形表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，并且在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。因此，本程序是采用鄰接矩陣、鄰接表、十字鏈表等多種結(jié)構(gòu)存儲(chǔ)來(lái)實(shí)現(xiàn)對(duì)圖的存儲(chǔ)。采用鄰接矩陣即為數(shù)組表示法，鄰接表和十字鏈表都是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)圖的遍歷分別采用了廣度優(yōu)先遍歷

9、和深度優(yōu)先遍歷。</p><p>　　關(guān)鍵詞：計(jì)算機(jī)；圖；算法。 </p><p><b>　　引 言 </b></p><p>　　很多涉及圖的操作的算法都是以圖的遍歷操作為基礎(chǔ)，通過(guò)遍歷的演示，方便在學(xué)習(xí)中更好的理解突地遍歷的過(guò)程。</p><p>　　通過(guò)對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的演示，分別兩種遍歷的

10、不同與其優(yōu)缺點(diǎn)。</p><p>　　我們?cè)趯?duì)一些問(wèn)題進(jìn)行求解時(shí)，會(huì)發(fā)現(xiàn)有些問(wèn)題很難找到規(guī)律，或者根本無(wú)規(guī)律可尋。對(duì)于這樣的問(wèn)題，可以利用計(jì)算機(jī)運(yùn)算速度快的特點(diǎn)，先搜索查找所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。</p><p>　　在深度優(yōu)先搜索算法中，是深度越大的結(jié)點(diǎn)越先得到擴(kuò)展。如果在搜索中把算法改為按結(jié)點(diǎn)的層次進(jìn)行搜索，本層的結(jié)點(diǎn)沒(méi)有搜索處理完

11、時(shí)，不能對(duì)下層結(jié)點(diǎn)進(jìn)行處理，即深度越小的結(jié)點(diǎn)越先得到擴(kuò)展，也就是說(shuō)先產(chǎn)生的結(jié)點(diǎn)先得以擴(kuò)展處理，這種搜索算法稱為廣度優(yōu)先搜索法。很多問(wèn)題都可以用廣度優(yōu)先搜索進(jìn)行處理、如翻幣問(wèn)題、最短路徑問(wèn)題等。</p><p>　　在計(jì)算機(jī)中，有多種方法存儲(chǔ)圖的信息，由于圖的結(jié)構(gòu)復(fù)雜，使用廣泛，一般應(yīng)根據(jù)實(shí)際的應(yīng)用，選擇適合的表示方法。常用的圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接多重表和鄰接表。 在實(shí)際問(wèn)題當(dāng)中，經(jīng)常遇到這類問(wèn)題，為新建的某

12、個(gè)機(jī)構(gòu)進(jìn)行選址、道路交通路線、如何走完所有路線、旅游線路等一系列問(wèn)題都涉及到圖的知識(shí)。圖是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，一個(gè)圖G（Grah）由兩個(gè)集合V和E構(gòu)成。圖存在兩種遍歷方式：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。廣度優(yōu)先遍歷基本思路是假設(shè)從圖中某頂點(diǎn)U出發(fā)，在訪問(wèn)了頂點(diǎn)U之后依次訪問(wèn)U的各個(gè)未訪問(wèn)的領(lǐng)接點(diǎn)，然后分別從這些領(lǐng)接點(diǎn)出發(fā)依次訪問(wèn)他們的領(lǐng)接點(diǎn)，并使先訪問(wèn)的頂點(diǎn)的領(lǐng)接點(diǎn)先于后訪問(wèn)的頂點(diǎn)被訪問(wèn)。直至所有領(lǐng)接點(diǎn)被訪問(wèn)到。深度優(yōu)先的基本思路是

13、從某個(gè)頂點(diǎn)出發(fā)訪問(wèn)此頂點(diǎn)，然后依次從V的未被訪問(wèn)的領(lǐng)接點(diǎn)出發(fā)深度優(yōu)先檢索圖。直至圖中所有頂點(diǎn)都被訪問(wèn)到。PRIM算法—KRUSKAL算法，可以對(duì)圖形進(jìn)行最小生成樹(shù)的求解。 樹(shù)型結(jié)構(gòu)是一種非線性結(jié)構(gòu)，它用于描述數(shù)據(jù)元素之間層次關(guān)系，如人類社會(huì)的族譜等，樹(shù)型結(jié)構(gòu)的應(yīng)用非常廣泛，磁盤(pán)文件目錄結(jié)構(gòu)就是一個(gè)典型的例子。</p><p><b>　　1 需求分析 </b></p><

14、p><b>　　1.1任務(wù)與分析 </b></p><p><b>　　問(wèn)題描述：</b></p><p>　　圖的遍歷和生成樹(shù)求解實(shí)現(xiàn)</p><p>　　圖是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層

15、次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。</p><p>　　生成樹(shù)求解主要利用普利姆和克雷斯特算法求解最小生成樹(shù)，只有強(qiáng)連通圖才有生成樹(shù)。</p><p><b>　　基本功能</b></p>&l

16、t;p>　　1) 先任意創(chuàng)建一個(gè)圖；</p><p>　　2) 圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)</p><p>　　3) 最小生成樹(shù)（兩個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)</p><p>　　4) 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)</p><p><b>　　輸入輸出</b></p>

17、<p>　　輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符。</p><p><b>　　1.2測(cè)試數(shù)據(jù)</b></p><p>　　根據(jù)提示，輸入所對(duì)應(yīng)的功能，輸入相關(guān)數(shù)據(jù)進(jìn)行測(cè)試。</p><p><b>　　2 概要設(shè)計(jì) </b></p><p><b>　　設(shè)計(jì)思路：&l

18、t;/b></p><p>　　a.圖的鄰接矩陣存儲(chǔ)：根據(jù)所建無(wú)向圖的結(jié)點(diǎn)數(shù)n,建立n*n的矩陣，其中元素全是無(wú)窮大（int_max），再將邊的信息存到數(shù)組中。其中無(wú)權(quán)圖的邊用1表示，無(wú)邊用0表示；有全圖的邊為權(quán)值表示，無(wú)邊用∞表示。</p><p>　　b.圖的鄰接表存儲(chǔ)：將信息通過(guò)鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的每一行都轉(zhuǎn)成鏈表的形式將有邊的結(jié)點(diǎn)進(jìn)行存儲(chǔ)。</p>

19、;<p>　　c.圖的廣度優(yōu)先遍歷：假設(shè)從圖中的某個(gè)頂點(diǎn)v出發(fā)，在訪問(wèn)了v之后依次訪問(wèn)v的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后再訪問(wèn)此鄰接點(diǎn)的未被訪問(wèn)的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中還有未被訪問(wèn)的，則另選未被訪問(wèn)的重復(fù)以上步驟，是一個(gè)非遞歸過(guò)程。</p><p>　　d.圖的深度優(yōu)先遍歷：假設(shè)從圖中某頂點(diǎn)v

20、出發(fā)，依依次訪問(wèn)v的鄰接頂點(diǎn)，然后再繼續(xù)訪問(wèn)這個(gè)鄰接點(diǎn)的系一個(gè)鄰接點(diǎn)，如此重復(fù)，直至所有的點(diǎn)都被訪問(wèn)，這是個(gè)遞歸的過(guò)程。</p><p>　　e.圖的連通分量：這是對(duì)一個(gè)非強(qiáng)連通圖的遍歷，從多個(gè)結(jié)點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過(guò)程中得到的頂點(diǎn)訪問(wèn)序列恰為其連通分量的頂點(diǎn)集。本程序利用的圖的深度優(yōu)先遍歷算法。</p><p><b>　　2.1 ADT描述&l

21、t;/b></p><p>　　ADT Queue{</p><p>　　數(shù)據(jù)對(duì)象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}</p><p>　　數(shù)據(jù)關(guān)系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,3,……，n}</p><p><b>　　基本操作：</b

22、></p><p>　　InitQueue(&Q)</p><p>　　操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。</p><p>　　QueueEmpty(Q)</p><p>　　初始條件：Q為非空隊(duì)列。</p><p>　　操作結(jié)果：若Q為空隊(duì)列，則返回真，否則為假。</p><p>　　

23、EnQueue(&Q,e)</p><p>　　初始條件：Q為非空隊(duì)列。</p><p>　　操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。</p><p>　　DeQueue(&Q,e)</p><p>　　初始條件：Q為非空隊(duì)列。</p><p>　　操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。</

24、p><p>　　}ADT Queue</p><p>　　ADT Graph{</p><p>　　數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。</p><p><b>　　數(shù)據(jù)關(guān)系R：</b></p><p><b>　　R={VR}</b></p>

25、<p>　　VR={<v,w>|v,w∈V且P（v，w）,<v,w>表示從v到w的弧，</p><p>　　謂詞P（v,w）定義了弧<v,w>的意義或信息}</p><p><b>　　基本操作P：</b></p><p>　　CreatGraph(&G,V,VR);</p>

26、<p>　　初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。</p><p>　　操作結(jié)果：按V和VR的定義構(gòu)造圖G。</p><p>　　BFSTraverse(G,visit());</p><p>　　初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。</p><p>　　操作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)

27、 </p><p>　　調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 </p><p><b>　　敗，則操作失敗。</b></p><p>　　DFSTraverse(G,visit());</p><p>　　初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。</p><p>　　操

28、作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn) </p><p>　　調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 </p><p><b>　　敗，則操作失敗。</b></p><p>　　DFStra_fen(G)</p><p>　　初始條件：圖G存在，存在圖的深度優(yōu)先遍歷算法。</p&g

29、t;<p>　　操作結(jié)果：從多個(gè)頂點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先遍歷，得到連通分量。</p><p>　　}ADT Graph;</p><p>　　2.2程序模塊結(jié)構(gòu) </p><p><b>　　軟件結(jié)構(gòu)設(shè)計(jì)：</b></p><p>　　2.2.1　結(jié)構(gòu)體定義</p><p><b

30、>　　鄰接矩陣定義:</b></p><p>　　typedef struct ArcCell</p><p>　　typedef struct</p><p><b>　　鄰接表的定義:</b></p><p>　　typedef struct ArcNode//弧結(jié)點(diǎn)</p><

31、p>　　typedef struct VNode//鄰接鏈表頂點(diǎn)頭接點(diǎn)</p><p>　　typedef struct//圖的定義</p><p><b>　　隊(duì)列定義:</b></p><p>　　typedef struct QNode</p><p><b>　　2.3　各功能模塊</b&g

32、t;</p><p>　　鄰接矩陣存儲(chǔ)：int creatMGraph_L(MGraph_L &G)</p><p>　　鄰接矩陣的輸出：void ljjzprint(MGraph_L G) </p><p>　　用鄰接表存儲(chǔ)圖：int creatadj(ALGraph &gra,MGraph_L G)</p><p>　　鄰

33、接表輸出：void adjprint(ALGraph gra,MGraph_L G) </p><p>　　初始化隊(duì)列：Status InitQueue(LinkQueue &Q)</p><p>　　入隊(duì)：Status EnQueue(LinkQueue &Q,QElemType e)//入隊(duì),插入元素e為Q的新的隊(duì)尾元素</p><p>　　出隊(duì)

34、：Status DeQueue(LinkQueue &Q,QElemType &e)//出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回，并返回真，否則假</p><p>　　判斷隊(duì)為空：Status QueueEmpty(LinkQueue Q</p><p>　　廣度優(yōu)先遍歷：void BFSTraverse(ALGraph gra)</p><p&g

35、t;　　深度優(yōu)先遍歷：int DFS(ALGraph gra,int i)</p><p>　　連通分量：int DFSTraverse_fen(ALGraph gra)</p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p><b>　　主函數(shù)：</b></p><p>　　int ma

36、in()</p><p><b>　　{</b></p><p><b>　　int s;</b></p><p>　　char y='y';</p><p>　　cout<<"||¤¤¤¤¤¤

37、4;¤¤¤¤¤¤¤¤¤¤菜單¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;</p><p>　　cout

38、<<"||-------------------------【0、創(chuàng)建一個(gè)無(wú)向圖------------------------------||"<<endl;</p><p>　　cout<<"||-------------------------【1、顯示該圖的鄰接矩陣--------------------------||"<

39、<endl;</p><p>　　cout<<"||-------------------------【2、顯示該圖的鄰接表----------------------------||"<<endl;</p><p>　　cout<<"||-------------------------【3、廣度優(yōu)先遍歷------

40、--------------------------||"<<endl;</p><p>　　cout<<"||-------------------------【4、深度優(yōu)先遍歷--------------------------------||"<<endl;</p><p>　　cout<<"||

41、-------------------------【5、最小生成樹(shù)MiniSpanTree_PRIM算法-------------||"<<endl;</p><p>　　cout<<"||-------------------------【6、最小生成樹(shù)MiniSpanTree_KRUSCAL算法----------||"<<endl;</

42、p><p>　　cout<<"||-------------------------【7、連通分量------------------------------------||"<<endl;</p><p>　　cout<<"||¤¤¤¤¤¤¤¤&#

43、164;¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;</p><p>　　whil

44、e(y=='y')</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)選擇菜單："<<endl;</p><p><b>　　cin>>s;</b></p><p><b>　　if(s==0

45、)</b></p><p><b>　　{</b></p><p><b>　　++o;</b></p><p><b>　　if(o==2)</b></p><p><b>　　{</b></p><p><b&

46、gt;　　n=0;</b></p><p><b>　　l=0;</b></p><p><b>　　o=0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>&l

47、t;b>　　switch(s)</b></p><p><b>　　{</b></p><p>　　case 0:cout<<"創(chuàng)建一個(gè)無(wú)向圖："<<endl;</p><p>　　MGraph_L G;</p><p>　　creatMGraph_L(G);

48、</p><p>　　ALGraph gra;</p><p>　　creatadj(gra,G);</p><p><b>　　break;</b></p><p>　　case 1:cout<<"鄰接矩陣顯示如下："<<endl;</p><p>　

49、　ljjzprint(G);</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　cout<<"鄰接表顯示如下："<<endl;</p><p>　　adjprint(gra,G);&l

50、t;/p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　cout<<"廣度優(yōu)先遍歷：";</p><p>　　BFSTraverse(gra);</p><p>　　cout<

51、;<endl;</p><p><b>　　break;</b></p><p><b>　　case 4:</b></p><p>　　cout<<"深度優(yōu)先遍歷：";</p><p>　　DFStra(gra);</p><p>　　

52、cout<<endl;</p><p><b>　　break;</b></p><p><b>　　case 5:</b></p><p>　　if(n==0){cout<<"無(wú)權(quán)圖沒(méi)有最小生成樹(shù)";break;}</p><p>　　else if(l

53、>0){cout<<"若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)，最小生成樹(shù)不存在"<<endl;break;}</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　int i,g[max][max];</p>

54、<p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(int j=0;j!=G.vexnum;++j)</p><p>　　g[i+1][j+1]=G.arcs[i][j].adj;</p><p>　　cout<<"普利姆算法:"<<endl;</p>&l

55、t;p>　　MiniSpanTree_PRIM(g,G.vexnum);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　case 6:if(n==0){cout<<"無(wú)權(quán)圖沒(méi)有最小生成樹(shù)";break;}</p>

56、;<p>　　else if(l>0){cout<<"該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)，最小生成樹(shù)不存在"<<endl;break;}</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<

57、;<"克魯斯卡爾算法:"<<endl;</p><p>　　MiniSpanTREE_KRUSCAL(G,gra);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　case 7:cout<&l

58、t;"連通分量:"<<endl;</p><p>　　DFSTraverse_fen(gra);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　cout<<endl<<"

59、是否繼續(xù)？y/n:";</p><p><b>　　cin>>y;</b></p><p>　　if(y=='n')</p><p><b>　　break;</b></p><p><b>　　}</b></p><p

60、><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　鄰接矩陣存儲(chǔ)：</b></p><p>　　int creatMGraph_L(MGraph_L &G)//創(chuàng)建圖用鄰接矩陣表示</p><p><

61、b>　　{</b></p><p>　　char v1,v2;</p><p>　　int i,j,w;</p><p>　　cout<<"請(qǐng)輸入頂點(diǎn)和弧的個(gè)數(shù)"<<endl;</p><p>　　cin>>G.vexnum>>G.arcnum;</p

62、><p>　　cout<<"輸入各個(gè)頂點(diǎn)"<<endl;</p><p>　　for(i=0;i<G.vexnum;++i)</p><p><b>　　{</b></p><p>　　cin>>G.vexs[i];</p><p><

63、;b>　　}</b></p><p>　　for(i=0;i<G.vexnum;++i)</p><p>　　for(j=0;j<G.vexnum;++j)</p><p><b>　　{</b></p><p>　　G.arcs[i][j].adj=int_max;</p>

64、<p>　　G.arcs[i][j].info=NULL;</p><p><b>　　}</b></p><p>　　for(int k=0;k<G.arcnum;++k)</p><p><b>　　{</b></p><p>　　cout<<"輸入一條邊依

65、附的頂點(diǎn)和權(quán)"<<endl;</p><p>　　cin>>v1>>v2>>w;//輸入一條邊依附的兩點(diǎn)及權(quán)值</p><p>　　i=localvex(G,v1);//確定頂點(diǎn)V1和V2在圖中的位置</p><p>　　j=localvex(G,v2);</p><p>　　G.ar

66、cs[i][j].adj=w;</p><p>　　G.arcs[j][i].adj=w;</p><p><b>　　}</b></p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b

67、>　　{</b></p><p>　　if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=1;</p><p><b>　　}</b></p><p>　　if(n>=1)cout<<"這是一個(gè)有權(quán)圖"<<

68、;endl;</p><p>　　else cout<<"這是一個(gè)無(wú)權(quán)圖"<<endl;</p><p>　　cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl;</p><p>　　return G.vexnum;</p><p><b>　　

69、}</b></p><p><b>　　鄰接矩陣的輸出：</b></p><p>　　void ljjzprint(MGraph_L G) //鄰接矩陣的輸出</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p&

70、gt;<p><b>　　if(n==0)</b></p><p><b>　　{</b></p><p>　　for(i=0;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　for(j=0;j!=G.vexnum;+

71、+j)</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j].adj==int_max){cout<<"0"<<" ";}</p><p>　　else {cout<<G.arcs[i][j].adj<<" &

72、quot;;}</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b&g

73、t;</p><p><b>　　{</b></p><p>　　for(i=0;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{</

74、b></p><p>　　if(G.arcs[i][j].adj==int_max){cout<<"∞"<<" ";}</p><p>　　else {cout<<G.arcs[i][j].adj<<" ";}</p><p><b>　　}

75、</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　用鄰接表存儲(chǔ)圖：&

76、lt;/b></p><p>　　int creatadj(ALGraph &gra,MGraph_L G)//用鄰接表存儲(chǔ)圖</p><p><b>　　{</b></p><p>　　int i=0,j=0;</p><p>　　ArcNode *arc;//,*tem,*p;</p>&

77、lt;p>　　for(i=0;i!=G.vexnum;++i)</p><p><b>　　{</b></p><p>　　gra.vertices[i].data=G.vexs[i];</p><p>　　gra.vertices[i].firstarc=NULL;</p><p><b>　　}<

78、;/b></p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j].adj!=int_max)</p><p><

79、;b>　　{</b></p><p>　　arc=(ArcNode *)malloc(sizeof(ArcNode));</p><p>　　arc->adjvex=j;</p><p>　　arc->nextarc=gra.vertices[i].firstarc;</p><p>　　gra.vertices

80、[i].firstarc=arc;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　gra.vexnum=G.vexnum;</p><p>　　gra.arcnum=G.arcnum;</p><p>　　cout<

81、<"圖G鄰接表創(chuàng)建成功！"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　鄰接表輸出：</b></p><p>　　void adjprint(AL

82、Graph gra,MGraph_L G) //鄰接表輸出</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p&g

83、t;<p>　　ArcNode *p;</p><p>　　cout<<"["<<i<<","<<G.vexs[i]<<"]";</p><p>　　p=gra.vertices[i].firstarc;</p><p>　　whil

84、e(p!=NULL)</p><p><b>　　{</b></p><p>　　cout<<"->"<<"["<<p->adjvex<<"]";</p><p>　　p=p->nextarc;</p>&

85、lt;p><b>　　}</b></p><p>　　cout<<"->"<<"End";</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　

86、　}</b></p><p><b>　　初始化隊(duì)列：</b></p><p>　　Status InitQueue(LinkQueue &Q)//初始化隊(duì)列</p><p><b>　　{</b></p><p>　　Q.front=Q.rear=(QueuePtr)mallo

87、c(sizeof(QNode));</p><p>　　if(!Q.front)return 0;//存儲(chǔ)分配失敗</p><p>　　Q.front->next=NULL;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p>

88、<p><b>　　入隊(duì)：</b></p><p>　　Status EnQueue(LinkQueue &Q,QElemType e)//入隊(duì),插入元素e為Q的新的隊(duì)尾元素</p><p><b>　　{</b></p><p>　　QueuePtr p;</p><p>　　p

89、=(QueuePtr)malloc(sizeof(QNode));</p><p>　　if(!p)return 0;//存儲(chǔ)分配失敗</p><p>　　p->data=e;p->next=NULL;</p><p>　　Q.rear->next=p;Q.rear=p;</p><p><b>　　return

90、1;</b></p><p><b>　　}</b></p><p><b>　　出隊(duì)：</b></p><p>　　Status DeQueue(LinkQueue &Q,QElemType &e)//出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回，并返回真，否則假</p>&l

91、t;p><b>　　{</b></p><p>　　QueuePtr p;</p><p>　　if(Q.front==Q.rear)return 0;</p><p>　　p=Q.front->next;</p><p>　　e=p->data;</p><p>　　Q.fro

92、nt->next=p->next;</p><p>　　if(Q.rear==p)Q.rear=Q.front;</p><p><b>　　free(p);</b></p><p><b>　　return 1;</b></p><p><b>　　}</b>&l

93、t;/p><p><b>　　判斷隊(duì)為空：</b></p><p>　　Status QueueEmpty(LinkQueue Q)//判斷隊(duì)為空</p><p><b>　　{</b></p><p>　　if(Q.front==Q.rear) return 1;</p><p&g

94、t;<b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　廣度優(yōu)先遍歷：</b></p><p>　　void BFSTraverse(ALGraph gra)</p><p><b>　　{</b>&

95、lt;/p><p><b>　　int i,e;</b></p><p>　　LinkQueue q;</p><p>　　for(i=0;i!=gra.vexnum;++i)visited[i]=0;</p><p>　　InitQueue(q);</p><p>　　for(i=0;i!=gra.

96、vexnum;++i)</p><p>　　if(!visited[i])</p><p><b>　　{ </b></p><p>　　visited[i]=1;</p><p>　　cout<<gra.vertices[i].data;</p><p>　　EnQueue(q,i)

97、;</p><p>　　while(!QueueEmpty(q))</p><p><b>　　{</b></p><p>　　DeQueue(q,e);</p><p>　　for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.ve

98、rtices[e],we))</p><p><b>　　{</b></p><p>　　if(!visited[we])</p><p><b>　　{</b></p><p>　　visited[we]=1;</p><p>　　cout<<gra.verti

99、ces[we].data;</p><p>　　EnQueue(q,we);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b&g

100、t;</p><p><b>　　}</b></p><p><b>　　深度優(yōu)先遍歷：</b></p><p>　　int DFS(ALGraph gra,int i)</p><p><b>　　{</b></p><p>　　visited[i]=

101、1;</p><p><b>　　int we1;</b></p><p>　　cout<<gra.vertices[i].data;</p><p>　　for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))&l

102、t;/p><p><b>　　{</b></p><p><b>　　we1=we;</b></p><p>　　if(visited[we]==0)</p><p>　　DFS(gra,we);</p><p><b>　　we=we1;</b></

103、p><p><b>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int DFStra(ALGraph gra)</p><p><b>　　{</b>

104、;</p><p><b>　　int i,j;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p><p>　　visited[i]=0;</p><p><b>　　}</b&g

105、t;</p><p>　　for(j=0;j!=gra.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(visited[j]==0)DFS(gra,j);</p><p><b>　　}</b></p><p><b>　　

106、return 0;</b></p><p><b>　　}</b></p><p><b>　　連通分量：</b></p><p>　　int DFSTraverse_fen(ALGraph gra)</p><p><b>　　{</b></p>&

107、lt;p><b>　　int i,j;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p>　　visited[i]=0;</p><p>　　for(j=0;j!=gra.vexnum;++j)</p><p><b>　　{</b></p

108、><p>　　if(visited[j]==0)</p><p><b>　　{</b></p><p>　　DFS(gra,j);</p><p>　　cout<<endl;</p><p><b>　　l++;</b></p><p>&l

109、t;b>　　}</b></p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　主要函數(shù)的程序流程圖，實(shí)現(xiàn)設(shè)計(jì)中主程序和其他子模塊的算法，以流程圖的形式表示。&

110、lt;/p><p><b>　　3.1結(jié)構(gòu)體定義</b></p><p><b>　　鄰接矩陣定義:</b></p><p>　　typedef struct ArcCell</p><p><b>　　{</b></p><p>　　VRType adj;

111、//VRType是頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型</p><p>　　InfoType *info;//該弧相關(guān)信息的指針</p><p>　　}ArcCell,AdjMatrix[max][max];</p><p>　　typedef struct</p><p><b>　　{</b&

112、gt;</p><p>　　VertexType vexs[max];//頂點(diǎn)向量</p><p>　　AdjMatrix arcs;//鄰接矩陣</p><p>　　int vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)</p><p>　　}MGraph_L;</p><p><b>　　鄰接表的定

113、義:</b></p><p>　　typedef struct ArcNode//弧結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　int adjvex;//該弧指向的頂點(diǎn)的位置</p><p>　　struct ArcNode *nextarc;//指向下一條弧的指針</p>

114、<p>　　InfoType *info;//該弧相關(guān)信息的指針</p><p><b>　　}ArcNode;</b></p><p>　　typedef struct VNode//鄰接鏈表頂點(diǎn)頭接點(diǎn)</p><p><b>　　{</b></p><p>　　VertexType

115、data;//頂點(diǎn)信息</p><p>　　ArcNode *firstarc;//指向第一條依附該頂點(diǎn)的弧的指針</p><p>　　}VNode,AdjList;</p><p>　　typedef struct//圖的定義</p><p><b>　　{</b></p><p>　　AdjL

116、ist vertices[max];</p><p>　　int vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)</p><p><b>　　}ALGraph;</b></p><p><b>　　隊(duì)列定義:</b></p><p>　　typedef struct QNode</p&g

117、t;<p><b>　　{</b></p><p>　　QElemType data;</p><p>　　struct QNode *next;</p><p>　　}QNode,*QueuePtr;</p><p>　　typedef struct</p><p><b&g

118、t;　　{</b></p><p>　　QueuePtr front;//隊(duì)頭指針</p><p>　　QueuePtr rear;//隊(duì)尾指針</p><p>　　}LinkQueue;</p><p><b>　　3.2 初始化</b></p><p><b>　　初始化

119、隊(duì)列：</b></p><p>　　Status InitQueue(LinkQueue &Q)//初始化隊(duì)列</p><p><b>　　{</b></p><p>　　Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));</p><p>　　if(!Q.f

120、ront)return 0;//存儲(chǔ)分配失敗</p><p>　　Q.front->next=NULL;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　3.3 插入操作</b></p>

121、;<p>　　Status EnQueue(LinkQueue &Q,QElemType e)//入隊(duì),插入元素e為Q的新的隊(duì)尾元素</p><p><b>　　{</b></p><p>　　QueuePtr p;</p><p>　　p=(QueuePtr)malloc(sizeof(QNode));</p>

122、;<p>　　if(!p)return 0;//存儲(chǔ)分配失敗</p><p>　　p->data=e;p->next=NULL;</p><p>　　Q.rear->next=p;Q.rear=p;</p><p><b>　　return 1;</b></p><p><b>

123、　　}</b></p><p><b>　　4 調(diào)試分析</b></p><p>　　4.1實(shí)際完成的情況說(shuō)明；</p><p>　　a. 先任意創(chuàng)建一個(gè)圖；</p><p>　　b. 圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)</p><p>　　c. 最小生成樹(shù)（兩個(gè)算法）的實(shí)現(xiàn)，

124、求連通分量的實(shí)現(xiàn)</p><p>　　d. 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)</p><p>　　支持的數(shù)據(jù)類型：整型和字符型</p><p>　　4.2程序的性能分析，包括時(shí)空分析；</p><p>　　本程序的圖的遍歷是以鄰接表做圖的存儲(chǔ)結(jié)構(gòu)，其時(shí)間復(fù)雜度為O（n+e）。</p><p>　　4.3上機(jī)過(guò)程

125、中出現(xiàn)的問(wèn)題及其解決方案；</p><p>　　a.程序開(kāi)始對(duì)無(wú)權(quán)圖和有權(quán)圖的鄰接矩陣的輸出時(shí)，無(wú)邊都用的10000（無(wú)窮大int_max）表示的，這種表示和我們習(xí)慣上的0與∞的表示有差異。所以在程序中定義了全局變量n（初值為0）,來(lái)判斷創(chuàng)建的無(wú)向圖是有權(quán)圖還是無(wú)權(quán)圖，n>0為有權(quán)圖，此時(shí)輸出的時(shí)候用∞代替10000；n=0為無(wú)權(quán)圖，此時(shí)輸出的時(shí)候用0代替10000.</p><p>

126、;　　b.程序中有的功能對(duì)某些圖是不適用的，比如無(wú)權(quán)圖沒(méi)有最小生成樹(shù)，非強(qiáng)連通圖沒(méi)有最小生成樹(shù)等。所以在程序中又新增了全局變量l,l>0時(shí)表示為非強(qiáng)連通圖，則在求最小生成樹(shù)時(shí)報(bào)錯(cuò)。</p><p>　　C.當(dāng)程序先創(chuàng)建一個(gè)有權(quán)圖后，n的值會(huì)大于1，第二次創(chuàng)無(wú)權(quán)圖時(shí)也會(huì)被程序認(rèn)為有權(quán)圖，所以在程序中在定義全局變量o（初值為0）,來(lái)判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時(shí)，所有全局變量在開(kāi)始全歸零。<

127、/p><p>　　4.4程序中可以改進(jìn)的地方說(shuō)明；</p><p>　　當(dāng)建立一個(gè)圖時(shí)先得求其連通分量，從而確定全局變量l的值，從而才能判斷該圖是否有最小生成樹(shù)。</p><p><b>　　5 用戶使用說(shuō)明</b></p><p>　　用戶應(yīng)該在windows操作系統(tǒng)下，按照提示進(jìn)行操作。</p><p

128、><b>　　先選0創(chuàng)建一個(gè)圖。</b></p><p><b>　　選擇y繼續(xù)操作。</b></p><p>　　按照菜單編碼選擇操作。</p><p><b>　　6 測(cè)試結(jié)果</b></p><p><b>　　創(chuàng)建一個(gè)無(wú)權(quán)圖：</b><

129、/p><p>　　創(chuàng)建一個(gè)費(fèi)強(qiáng)連通的有權(quán)圖：</p><p>　　創(chuàng)建一個(gè)有權(quán)連通圖：</p><p><b>　　結(jié) 論 </b></p><p>　　在做這個(gè)程序的時(shí)候你首先必須知道圖的一些概念，圖是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；

130、在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。</p><p>　　當(dāng)我們拿到一個(gè)圖時(shí)，我們對(duì)該圖的遍歷就要有一些方法，所以有了深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們要明白這兩種遍歷是怎么實(shí)現(xiàn)的，然后根據(jù)我們?nèi)四X中的方法把它寫(xiě)成電腦算

131、法。</p><p>　　對(duì)一個(gè)圖我們還定義了連通分量，所以將圖存到電腦中時(shí)，我們對(duì)連通分量得有個(gè)算法。</p><p>　　求圖的最小生成樹(shù)有兩種算法，普利姆是從結(jié)點(diǎn)出發(fā)尋找權(quán)最小的邊，知道所有結(jié)點(diǎn)都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小邊的方法。</p><p>　　算法的實(shí)現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，要求做到具體到實(shí)現(xiàn)該方法的

132、每一個(gè)步驟，然后再將每一個(gè)步驟通過(guò)代碼實(shí)現(xiàn)。</p><p>　　這要求我們要明確各個(gè)數(shù)據(jù)元素和個(gè)元素之間的關(guān)系，然后才能明確使用算法去調(diào)用這些數(shù)據(jù)。</p><p>　　通過(guò)本次的課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識(shí)，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對(duì)其操作的方法。但同時(shí)也發(fā)現(xiàn)在自己有很多的不足，在使用語(yǔ)言和如何精煉語(yǔ)言需要進(jìn)行更多的訓(xùn)練。</p><p>&l