數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告(公交換乘)

1、課程設(shè)計報告題目:武昌地區(qū)公交查詢與換乘推薦課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 專業(yè)班級: 學 號: 姓 名: 指導教師: 報告日期:計算機科學與技術(shù)學院任務書設(shè)計內(nèi)容掌握圖、查找、排序等數(shù)據(jù)結(jié)構(gòu)的物理存儲結(jié)構(gòu)與基本算法，通過解決較復 雜的基于圖模型的實際問題，提高學生對數(shù)據(jù)結(jié)構(gòu)知識綜合運用的技能與實踐能 力。設(shè)計要求（1）從互聯(lián)網(wǎng)或相關(guān)資料獲取可靠的武漢公交線路及其地理數(shù)據(jù)，通過線性結(jié) 構(gòu)與圖模型對其進行表示，且以文件保存。（2）圖形方式顯示上述圖模型與求解結(jié)果。（3）界面友好，實現(xiàn)的功能包括：錄入與修改公交線路信息；查詢所有線路信 息（線路名號、起點、終點、首末車時間、票價規(guī)則），按線路名或起點站

2、名排 序；查詢指定線路的詳情（沿途站點、首末車時間、票價規(guī)則、站間距離等）； 查詢某一位置途經(jīng)的所有公交線路、指定起點與終點，推薦乘車方案（如要求換 乘次數(shù)最少、路線最短或無要求條件等）。參考文獻1 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語言版）.北京：清華大學出版社,19972 嚴蔚敏，吳偉民，米寧.數(shù)據(jù)結(jié)構(gòu)題集（c語言版）.北京：清華大學出 版社，19993 博客園，華山大師兄的博客，最短路徑di jkstra算法和floyd算法http:/www. cnblogs. com/biyeymyhjob/archive/2012/07/31/2615833. html#33 39167目錄1引言31.1

3、課題背景與意義31公交出行31.2國內(nèi)外研究現(xiàn)狀41.3課程設(shè)計的主要研究工作42系統(tǒng)需求分析與總體設(shè)計62系統(tǒng)需求分析62.2系統(tǒng)總體設(shè)計63系統(tǒng)詳細設(shè)計73有關(guān)數(shù)據(jù)結(jié)構(gòu)的定義73.2主要算法設(shè)計84系統(tǒng)實現(xiàn)與測試134系統(tǒng)實現(xiàn)134.2系統(tǒng)測試145總結(jié)與展望205全文總結(jié)205工作展望216.附錄211引言1.1課題背景與意義1丄1公交出行公交出行是現(xiàn)在城市生活中必不可少的一種出行方式。但往往由于線路四通 八達，車次繁多，乘客眾多，乘公交成了一件麻煩事。公交查詢與換乘推薦系統(tǒng) 正是為了解決乘公交的諸多不便而產(chǎn)生的。1.1.2圖模型圖類型是一種重要的數(shù)據(jù)結(jié)構(gòu)，而公交換查詢與換乘推薦系統(tǒng)是圖

4、模型的典 型應用。在此系統(tǒng)屮，將會模擬圖屮遍歷，查找，最短路徑搜索等重要操作，鞏 固圖模型的各種操作。1.2國內(nèi)外研究現(xiàn)狀如今，公交出行方式已經(jīng)較為成熟。隨著互聯(lián)網(wǎng)吋代的到來，各種查詢系 統(tǒng)也是一應俱全。例如武漢市公交查詢網(wǎng)站：、上均有非常方便的查詢服務提供。國內(nèi)外情況均是如此。1.3課程設(shè)計的主要研究工作主要內(nèi)容：首先要搜集武漢數(shù)武昌區(qū)公交線路站點信息。住由于十分復雜， 使用完整的線路站點信息會導致數(shù)據(jù)料過于龐大且沒有必耍，故采用在武漢市地 鐵交通圖上選取一些具有代表性的線路的站點信息代替。)其然后是進行系統(tǒng)總 體設(shè)計如下：1. 線路信息查詢：線路信息查詢屮要將所有線路的票價、首班時間、末班

5、時間、途徑所有站點 等信息顯示出來。故需要根據(jù)已經(jīng)初始化好的線路信息打印在屏幕上，按照鄰接 列表的存儲順序遍歷圖，一次打印途經(jīng)站點的名字。2. 站點信息查詢：站點信息查詢中，為了方便輸入，提高效率，故先對所有站點編號顯示在屏 幕上供使用者查閱，根據(jù)編號輸入需要查詢的站點。對每一個站點需要了解所在 的所有線路，并分別顯示該站點在該線路上的上一站和下一站，以及該線路的起 點和終點。如果該站點為起點或終點，則另作提示。3. 距離最短路線查詢：使用者對照站點名字與編號輸入起點編號與終點編號，則通過程序得岀兩點 間的最短距離以及沿途站點，并給岀線路推薦。當兩站間有多條線路可以選擇吋, 則給出提示。該部分

6、使用辿杰特拉斯最短路線算法，使用鄰接矩陣的存儲結(jié)構(gòu)進行搜索。 dijkstra算法說明如下：1)算法思想:設(shè)g二(v,e)是一個帶權(quán)有向圖，把圖中頂點集合v分成兩組，第一組 為已求出最短路徑的頂點集合（用s表示，初始時s中只有一個源點，以后每求得一條最短路徑，就將加入到 集合s中，直到全部頂點都加入到s中，算法就結(jié)束了）， 第二組為其余未確定最短路徑的頂點集合（用u表示），按最短路徑長度的遞增 次序依次把第二組的頂點加入s中。在加入的過程中，總保持從源點start到s中各頂點的最短路徑長度不大于從源點start到u中任 何頂點的最短路徑長度。此外，每個頂點對應一個距離，s中的頂點的距離就是從s

7、tart到此頂點的最短路徑長度，u中的頂點的距離， 是從start到此頂點只包括s中的頂點為中間頂點的當前最短路徑長度。2）算法步驟：a. 初始時，s只包含源點，即s = start, start的距離為0。u包含除v外的其他 頂點，即:u=其余頂點,若start與u中頂點u有邊，則v u ,start 正常有權(quán)值,若u不是start的出邊鄰接點，貝0 u ,start 權(quán)值為fb. 從u中選取一個距離start最小的頂點k,把k加入s中（該選定的距離就 是start到k的最短路徑長度）。c以k為新考慮的中間點，修改u中各頂點的距離；若從源點start到頂點u的 距離（經(jīng)過頂點k）比原來距離（

8、不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。d重復步驟b和c直到所有頂點都包含在s屮。在執(zhí)行完迪杰特拉斯算法后，通過訪問最短距離數(shù)組中的相應元素打印出最 短距離。然后對前驅(qū)結(jié)點編號數(shù)組進行調(diào)整，再遍歷調(diào)整后的數(shù)組，從而輸岀途 徑的各站點。最后根據(jù)兩兩站點間的抽彖同路（即弧的鄰接矩陣存儲結(jié)構(gòu)）進行 搜索得出在哪條線路上，從而得出換乘推薦。4. 將數(shù)據(jù)寫入磁盤：本次設(shè)計的系統(tǒng)面向使用者，故所有初始數(shù)據(jù)都己經(jīng)一數(shù)組的形式給出，主 要包括：圖的鄰接數(shù)組、弧權(quán)值數(shù)組、站點信息數(shù)組、站點編號與名稱數(shù)組。針 對這四個數(shù)組，只需要設(shè)置四個文件指針，遍歷數(shù)組的同時分別寫入文

9、件即可。函數(shù)調(diào)用關(guān)系如下圖1：創(chuàng)建圖模型函數(shù)2站點定位函數(shù)3. 最短路徑查詢函數(shù)4文件存盤函數(shù)圖1 系統(tǒng)函數(shù)調(diào)用關(guān)系圖2系統(tǒng)需求分析與總體設(shè)計2.1系統(tǒng)需求分析用戶需要知道是所有線路的信息，包括票價、首班時間、末班時間、沿途經(jīng) 過的所有站點；由于線路可能很多，客戶只需要知道摸個具體站點的信息的話， 具體到每一個站點，則有站點所在的所有線路以及在相應線路上的上一站，下一 站，以及相應的線路的起點終點；客戶需要的最重要的是乘車線路推薦，具體表 現(xiàn)為輸入起點和終點的編號要能夠通過程序求出最短距離以及線路推薦。2.2系統(tǒng)總體設(shè)計針對以上需求，系統(tǒng)需要有初始化保存所有信息的功能，在這一部分中，將 所有站

10、點的名稱、編號；站點間的鄰接關(guān)系、距離；車次信息（包括票價、首班 時間、末班時間等）等信息初始化并保存，以備后續(xù)使用。第二個是現(xiàn)實所有線 路信息，在這一部分中，要先建立抽象線路圖，使用鄰接列表的存儲方式建立線 路圖，遍歷圖打印信息。第三個是站點位置信息的獲取，在這一部分總，主要是 對圖進行遍歷，并查找得岀所有位置信息。第四部分是最優(yōu)化路線推薦，在這一部分中主要使用迪杰斯特拉算法得出。最后將所有的初始化信息寫入磁盤即可。3系統(tǒng)詳細設(shè)計3.1有關(guān)數(shù)據(jù)結(jié)構(gòu)的定義1. 站點名稱與編號結(jié)構(gòu)：保存站點名稱與編號，名稱使用字符吊結(jié)構(gòu)長度為 20 個字符：char station_name20;編號使用整型：

11、int station_num;typedef structchar staton_name20|;int station_num;)station_num;2. 圖結(jié)點結(jié)構(gòu)：有鄰接點域，存放與改點相鄰的頂點的編號，使用整型: int verj_num;抽象站點的名稱，使用字符串：char station_name20；自引用 指針域，指向相鄰的下一個節(jié)點：struct tablenode *next；typedef structint verj_num;char station_namef20;struct tablenode *next;tablenode;3. 頭結(jié)點結(jié)構(gòu)：抽象站點的名稱

12、，使用字符串：charstation_name20；抽象 站點編號，整型：int station_num;頭指針：struct tablenode *next；typedef structint station_num;char station_name20;struct tablenode *head;headnode;4. 圖結(jié)構(gòu)：包含一個頭結(jié)點結(jié)構(gòu)數(shù)組：struct headnodemax_line_num;typedef structstruct headnodemax_line_num;jmgraph;5. 線路信息結(jié)構(gòu)：線路編號，整型：int line_num；票價，浮點型：flo

13、at price; 首班時間的小時部分，整型：int start_time_houi'；首班時間的分鐘部分：整型: int start_time_minute；末班時間的小時部分，整型：int end_time_hour:末班 時間的分鐘部分，整型：int end_time_minute；typedef structint line_num;int start_time_hour;int start_time_minute;int end_time_hour;int end_time_minute;line_info;3.2主要算法設(shè)計1創(chuàng)建圖模型：在建立圖模型時，按照線路的結(jié)構(gòu)建立。

14、每一個起點作為一個頭結(jié)點，每一 條單鏈表代表一條線路。故圖的頭結(jié)點數(shù)組長度為max_llne_numo此時耍使用 的輔助存儲結(jié)構(gòu)是線路的鄰接數(shù)組。遍歷鄰接數(shù)組，根據(jù)數(shù)組數(shù)據(jù)判斷是否有下-結(jié)點并讀取結(jié)點所代表的站點編號。流程圖如圖2：j+ ii+圖2：建立線路鄰圖接列表2. 打印線路信息遍歷線路信息數(shù)組，依次輸出每一條線路的票價、首班時間、末班時間等信 息；遍歷圖，每一條鏈表是一條線路，依次輸岀站點名稱，名稱之間用箭頭相連, 顯示岀一天線路的感覺。流程圖如圖3：圖3：打印新路信息3 .站點定位有用戶輸入需要的站點編號，然后程序遍歷圖模型，當站點編號匹配吋，記 錄下該站點所在的線路編號、線路起點終

15、點、該站點在相應線路上的上一站、下 一站。流程圖如下圖4：輸入站點編號計數(shù)變量i,指針變量p記錄前驅(qū)為上一站，記錄后繼為下一站>p=p > next圖4：站點定位4 最優(yōu)化線路推薦使用者對照站點名字與編號輸入起點編號與終點編號，則通過程序得出兩點 間的最短距離以及沿途站點，并給岀線路推薦。當兩站間有多條線路可以選擇時, 則給出提示。該部分使用迪杰特拉斯最短路線算法，使用鄰接矩陣的存儲結(jié)構(gòu)進行搜索。 dijkstra算法說明如下：1）算法思想:設(shè)g=（v,e）是一個帶權(quán)有向圖，把圖中頂點集合v分成兩組，第一組 為已求岀最短路徑的頂點集合（用s表示，初始時s中只有一個源點，以后每求得一

16、條最短路徑，就將加入到 集合s中，直到全部頂點都加入到s中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用u表示），按最短路徑長度的遞增 次序依次把第二組的頂點加入s中。在加入的過程中，總保持從源點start到s中各頂點的最短路徑長度不大于從源點start到u中任 何頂點的最短路徑長度。此外，每個頂點對應一個距離，s中的頂點的距離就是從start到此頂點的最短路徑長度，u中的頂點的距離， 是從start到此頂點只包括s中的頂點為中間頂點的當前最短路徑長度。2）算法步驟：a初始時,s只包含源點,即s = start, start的距離為0。u包含除v外的其他 頂點，即:u二其余頂點,若

17、start與u中頂點u有邊,則vu,start 正常有權(quán)值，若u不是start的出邊鄰接點，貝j u ,start 權(quán)值為8。b. 從u中選取一個距離start最小的頂點k,把k加入s中（該選定的距離就 是start到k的最短路徑長度）。c. 以k為新考慮的中間點，修改u中各頂點的距離；若從源點start到頂點u的 距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。d重復步驟b和c直到所有頂點都包含在s中。在執(zhí)行完迪杰特拉斯算法后，通過訪問最短距離數(shù)組屮的相應元素打印出最 短距離。然后對前驅(qū)結(jié)點編號數(shù)組進行調(diào)整，再遍歷調(diào)整后的數(shù)組，

18、從而輸出途 徑的各站點。最后根據(jù)兩兩站點間的抽象同路（即弧的鄰接矩陣存儲結(jié)構(gòu)）進行 搜索得出在哪條線路上，從而得出換乘推薦。流程圖如下圖5：輸入起點編號建立前驅(qū)頂點編號數(shù)組，各點最短距離編號圖5：迪杰特拉斯算法4系統(tǒng)實現(xiàn)與測試4.1系統(tǒng)實現(xiàn)使用c語言編寫系統(tǒng)，完成上述功能。硬件環(huán)境：聯(lián)想thinkpad e431 o具 體數(shù)據(jù)結(jié)構(gòu)定義如下：1. 站點名稱與編號結(jié)構(gòu)：typedef structchar staton_name20;int station_num;station_num;2. 圖結(jié)點結(jié)構(gòu)：typedefstructint verj_num;char station_name20;

19、struct tablenode *next;tablenode3. 頭結(jié)點結(jié)構(gòu)：typedef structint station_num;char station_name20|;struct tablenode *head;jheadnode;4. 圖結(jié)構(gòu)： typedef structstruct headnodemax_line_num;jmgraph;5. 線路信息結(jié)構(gòu)：typedef structint line_num;int start_time_hour;int start_time_minute;int end_t ime_hour;int end_time_minute

20、;line_info;從main函數(shù)進入系統(tǒng)之后，首先直接調(diào)用創(chuàng)建圖函數(shù)將各種初始化的數(shù)據(jù) 建立成圖結(jié)構(gòu)；再進入選擇菜單，根據(jù)不同的選擇(1, 2, 3, 4)進入調(diào)用打印 線路信息函數(shù)、頂點定位函數(shù)、最優(yōu)化路線推薦函數(shù)、保存文件函數(shù)。詳細代碼見附錄。4.2系統(tǒng)測試使用微軟開發(fā)的visual studio 2012作為運行系統(tǒng)和調(diào)試系統(tǒng)的環(huán)境。運行 情況如下：首先進入系統(tǒng)界面：此時現(xiàn)實的簡易文本菜單欄，有提示語“請輸入您的選擇：”字樣，直接從鍵盤輸入數(shù)字并回車;我們首先選擇1:線路信息如下所示:1號線：票價：2.0元苜班車時間：6： 30末班車時間：22： 30光谷廣場-> 廣埠屯-&g

21、t; 街道口-洪山廣場-中南路->江漢路-> 循禮門-> 漢口火車站常青花園2號線：票價：5元首班車時間：7： 0末班車時間：23： 0武漢火車站-> 仁和路-中南路-> 武昌火車站-鐘家村王冢灣-> 新漢陽站首班車時間:6： 30末班車時間:22： 30新漢陽站-王家灣-> 宗關(guān)-王家墩4號線：票價：2.0元春班車時間：7： 0末班車時間：23： 0k關(guān)-崇仁路- >循禮門- >大智路-漢口北大道5號線：票價：15元苜班車時間：6： 30末班車時間：22： 30王家灣-鐘家村江漢路-大智路->漢口北大道這是三，四，五號線。我們可以從

22、屏幕獲取到每一趟車次的票價、首班時 間、末班時間以及從起點到終點沿途經(jīng)過的站點名稱。然后我們選擇2：各站點對應編號如下:站潔 場車晦 屯廣費卩 埠山漢口 廣洪江漢壽站道車大 漢天盲和口 暫蛋示武仁漢0 2 4 6 8 0 2468111112站 m各>礒村薩 翳曇琴漢智 光街中頤吊一王王；大13 5 7 91357911111請輸入你要查詢位置的站點編號:n=ll我們首先可以看到所有站點的編號以及名稱，我們?nèi)我膺x擇一個站點，比如11：“王家灣”在"2號線”上，上一站是“鐘詔寸”： 一一“2號線”的起點皇“武漢火車站”,終點臭“新漢陽站”?！娟枤?亠下一站是“宗關(guān)”。 當墩” o

23、“王家灣” > “肯線”的起點,、下一站是“鐘家村”。 “5號線”甬寒點整“漢北大道”。是否繼續(xù)使用系統(tǒng)？選擇v或者十我們可以看到11號站點“王家灣”在圖中的所有位置信息：三條線路上的 所有信息均分別顯示。由于公交車是往返行駛，故方向只取一個，故起點、終點、 上一站、下一站均是相對的。我們繼續(xù)使用，選擇3：各站點對應編號如下:詁 站道 盤站 車大 斧議很天盲和口 nmwwint 漢0 2 4 6 8 0 2468111112站 口各訂5毒村r 光街中殖吊王王鐘武大13 5 7 91357911111請輸入起點編號:start_nun=13請輸入終點編號;end_nun=l?我們可以看到所

24、有站點的名稱編號，然后我們?nèi)我膺x擇兩個站點比如13和最短距離為:1訐米最短距離的近線路為：13王家墩->12宗關(guān)->14崇仁路->?循禮門->6江漢路-5中南路->18仁和路->1?武漢火車站具體換乘建議如下：ma 家線 王號關(guān)線 宗號 > 2-恿 -穿 劃敘 幺號南 3 hr 艷-tr < -茸敝蠢羈豎魏點禮門壘號線2江漢路乘是否繼續(xù)使用系統(tǒng)？選擇v或者於我們首先看到了兩個站點間的最短距離，然后是最短線路，最后是每兩個 站點間的線路選擇，即換乘推薦。當兩個站點間有多班車往返時，會提示用戶“或” 表示均可選擇。我們繼續(xù)試試其他站點間的情況：比如1

25、至ij 18：各站點對應編號如下:13 5 7 91357911111站 口各門>嗥r 口道 'rr漢智 光街中魯王王大2468101214161820咕 站道 為鋰站車大 飪ijr議很天皆曰和口 皿制蜩如藥果武仁漢請輸入起點編號:start_num=l請輸入終點編號;end_nun=18好,我們輸入了 1到18：我們看到了完全不同的另一套乘車方案。對照之前錄入的地圖信息我們發(fā)現(xiàn)測試正確。最后我們將系統(tǒng)用到的初始化數(shù)據(jù)，包括圖的鄰接矩陣，弧權(quán)值矩陣，名 稱與編號，線路信息等數(shù)據(jù)存入磁盤：我們在f盤中查看是否存盤成功:vrstationlinenodeline j nfoline2

26、016/2/13 16:16文本文欄2016/2/13 16:16文本文欄2016/2/13 16:16文本文欄2016/2/13 16:16文本文桂2016/1/31 15:18文本文欄我們看到了相應的文本文檔。5總結(jié)與展望5.1全文總結(jié)對自己的工作做一個總結(jié)。主要工作如下：(1) 、搜集關(guān)于武昌區(qū)公交線路圖的信息，最終確定使用截取武漢市地鐵 軌道交通圖作為系統(tǒng)的初始化數(shù)據(jù)；(2) 、分析系統(tǒng)需求，設(shè)計系統(tǒng)板塊；(3) 、編寫系統(tǒng)，調(diào)試系統(tǒng)直至通過；(4) 、撰寫課程設(shè)計報告。吋間安排如下：(1) 、2016年02月5日之前：完成所有要用到的結(jié)構(gòu)體的定義。(2) 、2016 年 02 月 5

27、 002 月 6 日：完成建立合適的圖模型以及信息的初始化。(3) 、2016年02月7日前：將初始化的所有的信息與建立的圖模型完全連接起來，寫調(diào)整函數(shù)將每一條路線的車的信息存放到所有的節(jié)點里去。(4) 、2016年2月8日2010年2月10日: 完成按時間最優(yōu)的方法選擇路線。(5) 、2016 年 2 月 10 日2016 年 2 月 12 0：完成文件寫入的程序。(6) 、2016年2月12日之前：調(diào)試完畢，系統(tǒng)可以投入使用。5.1工作展望在今后的研究中，圍繞著如下幾個方面開展工作：(1) 、使得系統(tǒng)更加人性化，給用戶帶來使用的暢快感;(2) 、使用更加高級的算法使得系統(tǒng)工作更高效；(3)

28、 、學習界面優(yōu)化，編寫岀讓用戶傷心悅目的界面。6.附錄程序完整源代碼如下:#include<stdio.h># include<stdlib.h> #include<string.h> #define ok 1#define error 0#define false 0#define true 1#define max_vertex_num 20#define max_distance 99#define max_line_num 5最大頂點個數(shù)定義一個最大距離抽象為表示無窮大定義線路數(shù)#define o max_vertex_num+1typedef ch

29、ar elemtype;圖頂點數(shù)據(jù)類型typedef struct station_infochar station_name20;int station_num;station_info;typedef structtablenode(表結(jié)點結(jié)構(gòu)iint verj_num; 的頂點vj的序號jchar station_name20; struct tablenode *next;鄰接點域，存放與vi相鄰接抽象站點的名字指針域，將鄰接表的所有表結(jié)點鏈在一起jtablenode;圖的數(shù)據(jù)類型定義typedef structheadn ode頭結(jié)點結(jié)構(gòu)char station_name20;int

30、 station_num;/vi的鄰接表的頭指針struct tablenode *head;jheadnode;typedef struct mgraphstruct headnode linemax_line_num;線路數(shù)組 mgraph;typedef struct line_infoint line_num;float line_price;int start_time_hour;int start_time_minute;int end_time_hour;int end_time_minute;line_infb;line_info linemax_line_num=線路信息1,

31、2,6,30,22,30,2,1.5,7,0,23,0,3,2.5,6,30,22,30,4,2,7,0,23,0,5,1.5,6,30,22,30；int vrmax_vertex_nummax_vertex_num=/012345678910111213141516 1718190,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 ,/01, 0,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,99,/i 99

32、,1, 0,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,99,/2 99, 99,1, 0,1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,99,/3 99, 99, 99, i, 0, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 4, 99, 2, 99,99,/4 99, 99, 99, 99, 2, 0, i, 99, 99, 99, 99, 99, 99, 99, 4, 99, 99, 99, 2,99,/

33、5 99, 99, 99, 99, 99,1, 0, 2, 99, 99, 99, 99, 99, 2, 99, 99, 99, 99, 2,99,/6 99, 99, 99, 99, 99, 99, 2, 0, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,/74, 99, 99, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 2, 0, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 ,/8 99, 99, 99, 99, 99, 99, 99, 99, 99

34、, 0, 1,99, 99, 99, 99, 99, 99, 99, 99, 99 ,/9 99, 99, 99, 99, 99, 99, 99, 99, 99, 1, 0,0,1, 2, 99, 99, 99, 99, 99,99,/10 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 4,1, 0, 99, 99, 99, 99, 99, 99,99,/ll 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99,2, 99, 0, 99, 99, 99, 99, 99,99,/12 99, 99, 99, 99, 99, 99

35、, 2, 99, 99, 99, 99,99,/13 99, 99, 99, 99, 99, 4, 99, 99, 99, 99, 2, 99, 99, 99, 0, 3, 99, 99, 99, 99,/l 4 99, 99, 99, 99, 4, 99, 99, 99, 99, 99, 99, 99, 99, 99, 3, 0, 99, 99, 99, 99,/15 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 0,1, 99,99,/16 99, 99, 99, 99, 2, 99, 99, 99, 99,

36、 99, 99, 99, 99, 99, 99, 99,1, 0, 99,99,/17 99, 99, 99, 99, 99, 2, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 0, 4,/18 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 4, 0,/19；弧權(quán)值二維數(shù)組int line_nummax_line_numlmax_vertex_numl=/0/i/2/3/40,1,2,3,4,5,6,7,8,00,0,0,0,0,0,0,0,0,0

37、,16,17,4,15,14,10,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,10,11,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,station|max_vertex_num=11,13,6,18,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 10,14,5,18,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, ； station_info 詁點信息數(shù)組”光谷廣場“,0,”廣埠屯”,1,”街道口 ”,2,”洪山廣場“,3,“中南路”,4,“江漢路”,5,”循禮門”,6,“漢口火車站”,7, “常青花園”

38、,8,”新漢陽站”,9,”王家灣”,10, 宗關(guān)”,11,”王家墩”,12,”崇仁路”,13,”鐘家村”,14,”武昌火車站”,15,”武漢火車站”,16, ”仁和路”,17,”大智路”,18,”漢口北大道”,19；int save_infomation(void);int print_line_info(mgraph *g); mgraph* creatmgraph(mgraph *g); void dijkstra_time(int start,int end);int locatevex(mgraph *g,int n);函數(shù)名稱：save_infomation();函數(shù)功能：根據(jù)點集和

39、點關(guān)系集創(chuàng)建一個圖； 函數(shù)參數(shù)：點集基址，點關(guān)系矩陣基址，定點數(shù)n;函數(shù)返回：圖的基址；/t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /tint save_infomation(void)file *pl,*p2,*p3,*p4; int

40、 i,j； int *p_vr,*p_line_node; station_info *p_station; line_info *p_line_info;if(pl =fopen(,f:vr.txt,；,wbh)=null)exit(-l);if(p2=fopen(',f:line_node.txt,'wb,)=null)exit(-l);if(p3=fopen(,f:station.txt','wb,)=null) exit(-l);if(p4=fopen(,f:line_info.txt,uwb")=null) exit(-l);for(i 二

41、o;ivmax_vertex_num;i+) for(j=0;j<max_vertex_num;j+)p_vr=&vrij； fwrite(p_vr,sizeof(int), 1 ,p 1); for(i=0;i<max_line_num;i+) for(j=0;j<max_vertex_num;j+)p_line_node=&line_numij; fwrite(p_line_node,sizeof(int),l ,p2); for(i=o;i<max_vertex_num;i+)p_station=&stationi; fwrite(p_st

42、ation,sizeof(station_info),l ,p3); for(i=0;ivmax_line_num;i+)p_line_info=&linei; fwrite(p_line_info,sizeof(line_info), 1 ,p4);fclose(pl);fclose(p2);fclose(p3);fclose(p4);return ok;函數(shù)名稱：print_line_info(mgraph *g)； 函數(shù)功能：屏幕打印線路信息； 函數(shù)參數(shù)：點集基址；函數(shù)返回：若成功則返回0k；/%、tint print_line_info(mgraph *g) int i,n;t

43、ablenode *p; n=max_line_num; printf(nnn);for(i=0;i<n;i+)printf(nn=)；printf("%d 號線:",linei.line_num);printf("t 票價:%l.lf 元nn'f,linei.line_price);printfc*首班車時間：%d： %dm,linei.start_time_hour,linei.start_time_minute);printf("t末班車時間:%d： %dnn",linei.end_time_hour,linei.end_t

44、ime_minute);p=g > linei.head->next;while(p)if(p->next)printf("%s->",p->station_name);elseprintf(,%s',p->station_name);p=p > next;primf(”n=*)；printf(unh);return ok;/ *. *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *

45、八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八 *八函數(shù)名稱：creatmgraph(mgraph* g,int *vr,int n)；函數(shù)功能：根據(jù)點集和點關(guān)系集創(chuàng)建一個圖； 函數(shù)參數(shù)：點集基址，點關(guān)系矩陣基址，定點數(shù)m 函數(shù)返回：圖的基址；/%、tmgraph* creatmgraph(mgraph *g)int i,j,n,m;tablenode *p,*rear;n=max_line_num;m=max_vertex_num;建立圖模

46、型時，是按照線路建立，存儲結(jié)構(gòu)為鄰接列表；每一條鏈表表示 一條線路；for(i=0;i<n;i+)real-g->linei.head;for(j=0;j<m;j+)if(line_numi|j<=m)p=(tablenode *)malloc(sizeof(tablenode); 創(chuàng)建一個新的結(jié) 點p->ver_nu m=line_numij; strcpy(p->station_name,stationline_numij.station_name); p->next=null;rear->next=p;插入鏈尾rear=p;return g

47、;b j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” j” *l* x* x* x* x* rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw

48、 rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw rw函數(shù)名稱：dijkstra_time(int startjnt end)；函數(shù)功能：根據(jù)起點編號和終點編號在圖中計算最短距離；函數(shù)參數(shù)：起點編號，終點編號；函數(shù)返回：最短距離值；函數(shù)說明：dijkstra算法說明如下：1）算法思想:設(shè)g=（v,e）是一個帶權(quán)有向圖，把圖屮頂點集合v分成兩組，第一 組為已求出最短路徑的頂點集合（用s表示，初始i寸s中只有一個源點，以后每求得一條最短路徑，就將加入 到集合s中，直到全部頂

49、點都加入到s中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用u表示），按最短路徑長度的遞增 次序依次把第二組的頂點加入s中。在加入的過程中，總保持從源點start到s中各頂點的最短路徑長度不大于從源點start到u中 任何頂點的最短路徑長度。此外，每個頂點對應一個距離，s中的頂點的距離就是從start到此頂點的最短路徑長度，u中的頂點的距離， 是從start到此頂點只包括s屮的頂點為屮間頂點的當前最短路徑長度。2）算法步驟：a. 初始吋，s只包含源點，即s= start, start的距離為0。u包含除v外的其 他頂點，即:u=其余頂點,若start與u中頂點u有邊，則v u ,s

50、tart正常有權(quán)值，若u不是start的出邊鄰接點，則vu,start權(quán)值為8。b. 從u中選取一個距離start最小的頂點k,把k加入s中（該選定的距離就 是start到k的最短路徑長度）。c. 以k為新考慮的中間點，修改u中各頂點的距離；若從源點start到頂點u 的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。d. 重復步驟b和c直到所有頂點都包含在s中。判斷點是否進入s集合的數(shù)距離數(shù)組前驅(qū)點編號數(shù)組void dijkstra_time(int start,int end)int s_flagmax_vertex_num;

51、 組int distancemax_vertex_num;int prior.ver| max_vertex.num ;intout 1| m ax_vertex_num |= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;輸出線路時的數(shù)組int out2|max_vertex_num=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;輸出線路時的數(shù)組int i j,k,f,min_distance=max_distance,m,change;int* flag;動態(tài)分配一個數(shù)組，記錄一條弧是否已經(jīng)掃描for(i=0;i<m

52、ax_vertex_num;i+)s_flagi=o;distancei=vrstart i;的距離if(distancei=max_distance) prior_veri=-l;elseprior_veri=start;distancestart=o;s_flagstart=l;for(i=l ;i<max_vertex_num;i+) k=start;min_distance=max_distance;始化抽象無窮遠為最短距離剛開始都沒有進入s集合距離數(shù)組中儲存的是從起點到改點起點到自身沒有距離起點已經(jīng)入s集合每一次進入循環(huán)均要初for(j=o;j<max_vertex_num;j+)if(!s_flagj)&&(distancej<min_distance)k=j；