數(shù)據(jù)結(jié)構(gòu)實驗報告五最短路徑

1、實驗課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計專科班學(xué)生名稱學(xué)號指導(dǎo)教師2012-2013學(xué)年第一學(xué)期1-9周目錄一、概述：21.1問題說明21.2系統(tǒng)實現(xiàn)的目標(biāo)21.3系統(tǒng)實施方案2二、系統(tǒng)分析：32.1設(shè)計理念32.2設(shè)計要求32.3需求分析32.4算法說明4三、大綱設(shè)計：63.1程序流程圖7四、詳細設(shè)計：84.1圖中的存儲結(jié)構(gòu)設(shè)置84.2單一來源最短路徑84.3頂點對之間的最短路徑94.4構(gòu)造有向圖的存儲結(jié)構(gòu)104.5第納爾算法104.6弗洛伊德算法114.7運行主節(jié)目12五、操作和測試：13六：總結(jié)和經(jīng)驗15附錄：節(jié)目代碼15一、概述：1.1問題說明交通網(wǎng)絡(luò)牙齒很發(fā)達，交通工具和交通方式牙齒不斷更新的今

2、天，人們出差、旅行或其他旅行時，不僅節(jié)約交通費用，還對里程和必要的時間等感興趣的牙齒。對于這些人關(guān)心的問題，可以使用圖片結(jié)構(gòu)表示交通網(wǎng)絡(luò)系統(tǒng)，使用計算機構(gòu)建交通咨詢系統(tǒng)。圖中的頂點表示城市，邊表示城市之間的交通關(guān)系。牙齒交通系統(tǒng)可以回答旅客提出的各種路徑選擇問題。例如，問題之一是：“從a點到b點的旅客想選擇途中中轉(zhuǎn)次數(shù)最少的路線?！奔僭O(shè)圖中的每個站都要換車，牙齒問題是找到從頂點a到頂點b包含的邊數(shù)最小的路徑。我們只需從頂點a開始，廣度優(yōu)先搜索作畫。一旦遇到頂點b就終止。(阿爾伯特愛因斯坦，northern exposure(美國電視電視劇)，作品)結(jié)果，從樹、根頂點a老師到頂點b的路徑是最少的

3、傳輸路徑。路徑中a和b之間的頂點是路徑的中繼點，但只是最簡單圖形的最短路徑問題。系統(tǒng)還可以回答這樣的路徑選擇問題。1.2系統(tǒng)實現(xiàn)的目標(biāo)通過課程設(shè)計，了解和初步了解實現(xiàn)設(shè)計、大型系統(tǒng)的整個過程，包括系統(tǒng)分析、編碼設(shè)計、系統(tǒng)集成、調(diào)試分析、數(shù)據(jù)結(jié)構(gòu)選擇、設(shè)計、實施和操作方法的掌握，為進一步的應(yīng)用程序開發(fā)奠定了基礎(chǔ)。應(yīng)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識，獨立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識編寫解決指定問題的程序。1.3系統(tǒng)實施方案首先，決定系統(tǒng)要達到什么目的，為了達到這種目的，首先要實現(xiàn)的程序。這是關(guān)鍵部分。劃分模塊、源代碼、牙齒程序大致分為6個模塊，由主函數(shù)組和5個自定義函數(shù)組組成。然后進行機器調(diào)試，協(xié)調(diào)幾個

4、大模塊，組成完全實現(xiàn)其功能的程序，最后提交設(shè)計報告。二、系統(tǒng)分析：2.1設(shè)計理念利用鄰接矩陣存儲與交通網(wǎng)絡(luò)地圖的信息，利用迪塞斯特拉算法實現(xiàn)地圖單一來源最短路問題，然后利用斐洛算法實現(xiàn)圖片中任何一對頂點之間的最短路問題，從而實現(xiàn)旅客需要咨詢的問題。2.2設(shè)計要求牙齒交通咨詢系統(tǒng)必須完成城市網(wǎng)絡(luò)地圖的存儲，實現(xiàn)從任意城市頂點到其他城市頂點的最短路徑問題，還必須實現(xiàn)兩個城市頂點之間的最短路徑問題。因此，設(shè)計必須分為三個部分。一是構(gòu)建交通網(wǎng)絡(luò)地圖的存儲結(jié)構(gòu)。二是解決單一源路徑問題。最后實現(xiàn)兩個城市之間的最短路徑問題。設(shè)計要求：1.構(gòu)建交通網(wǎng)絡(luò)網(wǎng)絡(luò)的存儲結(jié)構(gòu)。整體設(shè)計需要繪制流程圖。3.供應(yīng)商程序測試

5、節(jié)目。4.界面很熟悉。2.3需求分析根據(jù)需要，在系統(tǒng)中創(chuàng)建無向圖。系統(tǒng)必須靈活，用戶可以根據(jù)當(dāng)前交通網(wǎng)絡(luò)圖輸入和更改初始數(shù)據(jù)。系統(tǒng)基于用戶的輸入構(gòu)建了無向圖的結(jié)構(gòu)，通過dickstra算法和弗洛伊德算法實現(xiàn)了需求，并提供了兩種茄子功能供用戶選擇。2.4算法說明輸入城市和公路數(shù)據(jù)查詢從一個城市到另一個城市的最短路徑基于無向圖生成查詢功能結(jié)構(gòu)建設(shè)教父相通網(wǎng)絡(luò)交通祖懷系統(tǒng)字典城市之間的距離查詢兩個城市之間的最短路徑迪克斯特拉算法特定流程圖開始初始化距離和路徑i=1j=1；j；jn弗洛伊德算法特定流程圖開始初始化距離和路徑從到的最短路徑長度，其中只有集中的節(jié)點設(shè)置為中間節(jié)點輸出結(jié)果最短路徑通過點k最短

6、路徑不通過點k三、大綱設(shè)計：程序包含兩種茄子抽象數(shù)據(jù)類型。一個是圖形，另一個是隊列。1、設(shè)置“圖片”抽象數(shù)據(jù)類型定義。adt graph數(shù)據(jù)對象v: v是具有相同屬性(稱為頂點集)的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系r:r=vrvr=v，w | v，w-vp(v，w)，v，w表示從v到w的圓弧。謂詞p(v，w)定義了圓弧v，w的含義或信息。默認操作p:creategraph(g，v，vr)；初始條件：v是圖形的頂點集，vr是圖形中弧的集合。任務(wù)結(jié)果：按照v和vr定義構(gòu)建圖表。locatevex(g，u):初始條件：圖g存在，u和g的頂點具有相同的特征。操作結(jié)果：如果g具有頂點u，則地物返回該頂點的位置。

7、否則，將返回其他信息。first_next_adj(g，v)；初始條件：圖g存在，v是g的頂點。操作結(jié)果：返回v的第一個相鄰頂點。如果g沒有相鄰頂點，則返回null。dfstraverse(g，i):初始條件：圖g存在，i是鄰接矩陣中頂點的位置。作業(yè)結(jié)果：從i開始，先遍歷圖形的深度。bfstraverse(g，i):初始條件：圖g存在，i是鄰接矩陣中頂點的位置。作業(yè)結(jié)果：從i開始，先遍歷圖片的寬度。 adtgraph2、設(shè)置隊列的抽象數(shù)據(jù)類型定義。adt queue數(shù)據(jù)對象：d= a i a i數(shù)據(jù)關(guān)系：r1=a i，a i1 | a i1，a id，i=2，n規(guī)則a1結(jié)尾是隊列標(biāo)頭，a n結(jié)

8、尾是隊列結(jié)尾?；救蝿?wù)：initqueue(q)任務(wù)結(jié)果：配置空隊列q。enqueue(q，e)初始條件：隊列q已存在。任務(wù)結(jié)果：插入元素e為q的新團隊尾部元素dequeue(q)初始條件：隊列q已存在。任務(wù)結(jié)果：刪除q的相對元素并返回值。queueempty(q)初始條件：隊列q已存在。任務(wù)結(jié)果：如果q為空隊列，則返回1，否則返回0。queuelenghth(q)初始條件：隊列q已存在。操作結(jié)果：返回q的元素數(shù)，即隊列長度。gethead(q，e)初始條件：q是非空隊列。工作結(jié)果：使用e返回q的對手元素。 adt queue3、牙齒程序包含三個茄子模塊。1)主節(jié)目模塊void main()選

9、擇要創(chuàng)建的圖表的類型。請創(chuàng)建圖表并以鄰接矩陣格式打印。找到地物的深度和廣度優(yōu)先搜索以及頂點的第一個相鄰點。查找從一個源點到其馀頂點的最短路徑。2)圖形模塊實現(xiàn)圖的抽象數(shù)據(jù)類型和基本操作3)隊列模塊實現(xiàn)隊列的抽象數(shù)據(jù)類型和當(dāng)前操作3.1程序流程圖四、詳細設(shè)計：設(shè)置4.1圖形的存儲結(jié)構(gòu)首先定義交通地圖的存儲結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點之間相鄰關(guān)系的矩陣。g=(v，e)是具有n個頂點的圖形，g的鄰接矩陣是n階方陣，定義如下：ai，j=鄰接矩陣列標(biāo)頭，當(dāng)欄標(biāo)頭順序一致時，插圖的鄰接矩陣表現(xiàn)法是唯一的。根據(jù)圖的鄰接矩陣表示，除了將頂點之間的相鄰關(guān)系存儲為二維陣列的鄰接矩陣外，通常還需要使用n個元素一維

10、陣列存儲頂點信息。其中下標(biāo)是i的元素存儲頂點i的信息。因此，圖的鄰接矩陣存儲結(jié)構(gòu)定義如下：#definf mvnum 88 /最大頂點數(shù)typedef structvertex type vexsmv num；/vertex陣列，假設(shè)為char類型adj matrix arcsmv nummv num；/鄰接矩陣，假設(shè)為int類型 mgraph4.2單一來源最短路徑對最短路徑的提法很多。這里首先介紹單個源最短路問題，即乳香度(卷權(quán))。我想查找從源點sv到g其馀頂點的最短路徑。為了便于敘述，我們將路徑的起點稱為源點，路徑的最后一個頂點稱為終點。(約翰肯尼迪，美國電視電視劇)那么，如何得到給定方向

11、性圖的單個源最短路徑呢？dijkstra提出了隨著路徑長度增加點的最短路徑算法，即dijkstra算法。dijestra算法追求最短路徑實現(xiàn)。g=(v，e)是直接圖形，節(jié)點集，cost是表示g的鄰接矩陣，costij表示轉(zhuǎn)向權(quán)。如果沒有方向邊，則costij的權(quán)重為無窮大，此處為32767。s是每個元素代表一個頂點的集合，從源到牙齒頂點的最短距離已經(jīng)被求出。將頂點v1設(shè)置為源點，并且集合s的初始狀態(tài)僅包含一個元素，頂點v1。陣列dist記錄從源點到其他頂點的當(dāng)前最短距離。初始值為dist i=cost v1 i，i=1，2，n。在非s頂點集v-s中，選擇頂點w以最小化distw的值。因此，僅通

12、過源點到w之間s的頂點，向集合s添加w，并調(diào)整dist中記錄的源點到v-s中每個頂點v的距離。在原始distv和distw costwv中，選擇較小的值作為新dist。重復(fù)以上過程，直到v-s為空。結(jié)果s記錄從源點到其頂點的最短路徑的頂點集合，陣列dist記錄從源點到v中其馀頂點的最短路徑，path是最短路徑的路徑陣列。其中pathi表示從源點到頂點i的最短路徑上的前導(dǎo)頂點。因此，dijestra算法可用的自然語言如下：初始化s和d，清空最短路徑端點集，并設(shè)置初始最短路徑值。sv1=true；dv1=0；/s集最初僅包含源點，從源點到源點的距離為零。while (s集中的頂點數(shù)及其是否存在)。

13、如果有，比較和vi，v1，vj的路徑長度，長度短是當(dāng)前求的最短路徑。牙齒路徑是中間頂點序列號不大于1的最短路徑。其次，考慮從vi到vj是否包含頂點v2為中間頂點的路徑。否則，從vi到vj的當(dāng)前最短路徑是在前面的步驟中獲得的。如果存在，可以使用和分割。牙齒兩條路徑是以前找到的中間頂點序列號不大于1的最短路徑，加上兩條路徑長度即可得出路徑長度。將牙齒長度與從vi到vj的中間頂點編號不大于1的最短路徑進行比較，使用較短的當(dāng)前vi到vj的中間頂點編號不大于2的最短路徑。以這種方式添加頂點vn牙齒從當(dāng)前vi到vj的最短路徑，然后選擇從vi到vj的中間頂點編號不大于n的最短路徑。圖g中的頂點編號不大于n，因此從vi到vj的中間頂點編號不大于n的最短路徑，并且考慮到所有頂點都可能是中間頂點，因此是從vi到vj的最短路徑。4.4構(gòu)造有向圖的存儲結(jié)構(gòu)void createmgraph (mgraph * g，int n，int e)int i、j、k、w；for(i=1)；i=n；i)g-vexsi=(char)i；for(i=1)；i=n；i)for(j=1)；j=n；j)g-arcsij=max int；printf(輸