數(shù)據(jù)結構課程設計—城市道路交通咨詢系統(tǒng)

1、榆林學院數(shù)據(jù)結構課程設計報告題目城市交通咨詢系統(tǒng)作者楊朝專業(yè)信息管理與信息系統(tǒng)學號1514210121指導老師張慧答辯時間2016.12.18目錄1.系統(tǒng)需求分析 11.1用戶需求分析 11.2功能需求分析 21.3數(shù)據(jù)需求分析 31.4 小結 42. 系統(tǒng)設計 42.1系統(tǒng)設計功能 42.2每個模塊的具體功能。 5采用 C 語言定義相關數(shù)據(jù)類型 5建立鄰接矩陣交通網絡： 6查詢指定城市到其他城市自己建的最短路程： 8查詢任意兩個城市之間的一條最短路徑： 102.3主函數(shù)的調用關系圖 113. 系統(tǒng)測試 133.1操作說明 133.2測試數(shù)據(jù) 13用戶進入界面： 13、具體功能的實現(xiàn) 14、結

2、束程序 164. 總結 175. 致謝 18186. 附錄1 .系統(tǒng)需求分析現(xiàn)如今網絡非常發(fā)達， 無論人們出差， 旅游或者做其他的出行之時， 都會想 到道路問題， 切不僅僅關心的是交通費用， 而且對于里程和所需要的時間等的問 題也是同樣的關心， 在此系統(tǒng)中， 完全面向用戶， 可以用一個圖結構來表示交通 網絡系統(tǒng)，利用計算機建立一個交通咨詢系統(tǒng)。且在圖中，頂點表示城市，邊表 示城市之間的交通關系。 設計一個交通咨詢系統(tǒng)， 能夠讓旅客咨詢從任一城市頂 點到達另外一個城市之間頂點的最短路徑問題（最短里程問題） 。對系統(tǒng)分析，主要從以下幾個方面進行分析。1. 用戶需求分析2. 功能需求分析3. 數(shù)據(jù)需

3、求分析1.1用戶需求分析現(xiàn)如今網絡非常發(fā)達， 無論人們出差， 旅游或者做其他的出行之時， 都會想 到道路問題， 切不僅僅關心的是交通費用， 而且對于里程和所需要的時間等的問 題也是同樣的關心， 在此系統(tǒng)中， 完全面向用戶， 可以用一個圖結構來表示交通 網絡系統(tǒng)，利用計算機建立一個交通咨詢系統(tǒng)。且在圖中，頂點表示城市，邊表 示城市之間的交通關系。 設計一個交通咨詢系統(tǒng)， 能夠讓旅客咨詢從任一城市頂 點到達另外一個城市之間頂點的最短路徑問題（最短里程問題） 。當要查詢某兩個城市之間的最短交通路線或者其中一個城市到達其余城市 的最短路線時，是一個很繁瑣的過程。根據(jù)用戶自己的需求， 可以自定義地圖，

4、此程序就是主要以滿足用戶自己的 環(huán)境與實際情況， 在難以計算路程時， 可將地圖輸入進行計算， 系統(tǒng)將會為用戶 提供所用路徑最短的出現(xiàn)路線， 更好的滿足用戶需求。 以下是針對咨詢用戶說明 其最基本的模塊功能。（1）進入程序后，用戶可自己設置城市的個數(shù)，以及所有城市之間總共的 路徑，且分別用頂點和邊表示城市與路徑（2）用戶根據(jù)自己設置的城市個數(shù)和路徑數(shù)， 具體輸入每個路徑的起始點 以及每條路徑的長度。（3）進入菜單選擇界面（4）選擇 2，系統(tǒng)為用戶進行提供任意城市的交通查詢 ,即查詢任意兩個城 市之間的一條最短路徑。（5）選擇 1，系統(tǒng)為用戶提供指定城市的交通查詢，即查詢指定城市到其 他城市之間的

5、最短路徑。 如若輸入頂點超出范圍顯示錯誤， 系統(tǒng)回到菜單重新選 擇（6）選擇 0，系統(tǒng)推出程序。1.2 功能需求分析城市交通咨詢系統(tǒng)總體的設計目標： 用數(shù)據(jù)結構 中的鄰接矩陣作數(shù)據(jù)結 構，并結合數(shù)據(jù)結構有向圖的最短路徑計算方法， 結合相應的數(shù)據(jù)算法以及 c 語 言的相關知識，編寫一個良好的，具有可操作性的，以及能方便用戶的使用，包 括自定義地圖， 路徑與城市個數(shù)可結合實際情況而言， 相對操作， 簡便易懂并無難度。系統(tǒng)在菜單可根據(jù)命令進行相應的操作，已滿足用戶的需求城市交通系統(tǒng)基本功能根據(jù)以上分析，此系統(tǒng)具備以下功能：（ 1） 用戶進入后的地圖創(chuàng)建界面（明確地圖中城市的個數(shù)以及路徑的個數(shù)）（ 2

6、） 地圖完善界面（用戶自己輸入地圖中相關路徑的起始點以及路徑長度）（ 3） 菜單界面包含兩條命令（4）命令 1 求一個城市到所有城市的最短距離（5）命令 2 求任意的兩個城市之間的最短距離（6）回復命令 0 可推出程序。1.3數(shù)據(jù)需求分析用鄰接矩陣建立交通網絡模塊VertexType vexsMVNum;/ 頂點數(shù)組，類型假定為 charAdjmatrix arcsMVNumMVNum;/ 鄰接矩陣，類型假定為 int 型 建立鄰接矩陣， 用函數(shù) void CreateMGraph（MGraph * G,int n,int e） / 采用 鄰接矩陣表示法構造有向圖 G，n、e 表示圖的當前頂點

7、數(shù)和邊數(shù) 用迪杰斯特拉算法計算某頂點到其余頂點的最短路徑用函數(shù) void Dijkstra （MGraph * G,int n,int e） 來定義此函數(shù) 采用鄰接矩陣表示法構造有向圖 G，n、e 表示圖的當前頂點數(shù)和邊數(shù) 用弗洛伊德算法求任意一對頂點的最短路徑用函數(shù) void Floyd（MGraph *G,int n） 來定義。利用費洛伊德算法，求出 最短路徑。1.4 小結從各種需求方面下手改編代碼， 并不斷調試， 讓界面更加友好。 不斷地嘗試 上，在各種問題上不斷突破，慢慢的完善代碼，等最大限度的滿足用戶需求。這 幾天短時間的課程設計也讓我認識到了自己在這門課程上還面臨著許許多多的 問題

8、，為以后的具體實踐明確了努力方向。同時，城市交通咨詢系統(tǒng)的實現(xiàn)，為 用戶更好的解決了再實際出行時遇到的路徑問題， 最初的設計也為代碼敲定了編 寫方向。 再三考慮后確定了系統(tǒng)的功能， 確定什么功能有實現(xiàn)必要， 什么功能可 有可無。在這樣的基礎之下使得思路更加清晰。2.系統(tǒng)設計本程序首先是用戶編輯界面， 用戶根據(jù)自己的需求編寫地圖， 從而加入頂點 的數(shù)組之中， 創(chuàng)建的地圖用鄰接矩陣存儲， 在從主函數(shù)之中進行調用， 實現(xiàn)對兩 個算法的調用。用戶在輸入頂點以及邊的信息都會存儲， 在存儲成功之后會提示用戶存儲成 功，之后進入到菜單界面，菜單界面提供兩種選擇口令，分別可以調運 Dijkstra 和 Flo

9、yd 算法，調用之后輸入相應的口令以及要查詢的城市編號，算法會根據(jù)鄰 接矩陣存儲的地圖進行計算，求出最短路徑。在以后使用完系統(tǒng)后，可輸入口令 0，系統(tǒng)會結束一切運算，退出程序。2.1系統(tǒng)設計功能菜單界面的主要功能有兩個(1) 、求一個城市到所有城市的最短距離(2) 、求任意的兩個城市之間的最短距離 城市交通咨詢系統(tǒng)主要有三個模塊分別為：(1) 、鄰接矩陣的輸入與存儲構建交通網絡(2) 、任意兩個城市的最短距離查詢(3) 、兩個指定城市的最短距離查詢主界面的模塊概念圖如圖2-1：用戶進入系統(tǒng)交通網絡構建結果，退出系統(tǒng)圖2.12.2每個模塊的具體功能。采用C語言定義相關數(shù)據(jù)類型1 定義一個，用來存

10、儲頂點信息typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;.2.定義一個 Dijkstra函數(shù)void Dijkstra(MGraph *G,int v,int n);3定義一個Floyd函數(shù)void Floyd(MGraph *G,int n);建立鄰接矩陣交通網絡：開始圖 2-2 鄰接矩陣構造圖結構函數(shù) 數(shù)據(jù)類型定義：typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;void CreateMGraph(MGraph *G,int n,int e)

11、/ 鄰接矩陣構成有向圖 int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=IDF;printf(輸入d 條邊的 i,j 及 w: n,e); for(k=1;karcsij=w;printf（有向圖的存儲結構建立完畢！n）;其中vexsMAX保存頂點信息，arcsMAXMAX用于保存邊與邊之間 的信息。在構建時通過輸入的邊數(shù)i，j作為矩陣的行、列確定頂點的出度和 入度。用鄰接矩陣方法存儲圖。查詢指定城市到其他城市自己建的最短路程：基本思想：設G（V,E）是一個帶權有向圖，把圖中的頂點集合V分成兩組, 第一組為已經

12、求出的最短路徑的頂點集合（用S表示，初始時S中只有一個原點， 以后每求得一條最短路徑就加入的集合 S中，知道全部頂點都加入到集合中）， 第二組，為其余未確定最短路徑的頂點集合（用 U表示），按最短路徑長度的遞增次序依次把第二組的頂點就如 S中。如果兩個頂點之間有權值，并且各個路徑的權值不同,圖2-4如圖所示若x+yk=u。同理若x+yu ,D v1=0;Sv1=1; /原點編號放入s中for(i=2;i n ;i+)mi n=IDF;for(w=1;w =n; w+)if(!Sw&D wmi n)v=w;mi n=D w;Sv=1;/修改頂點u放入s中for(w=1;warcsvwarcsvw

13、;P w=v;224查詢任意兩個城市之間的一條最短路徑:其具體的流程圖如圖2-5所示:此過程需要應用弗洛伊德算法來具體實現(xiàn)用鄰接矩陣保存圖存儲后，另外需要存一個二維數(shù)組A存放當前頂點之間的最短路徑長度。分量Aij表示當前頂點i到j的最短路徑長度。弗洛伊德算法的基本思維是遞推產生一個矩陣序列A0, A1, A2，.Ak，An，其Akij表示從頂點到vi到頂點vj的路徑上所經過的頂點編號不大于 k的最短路徑長度。Aij=costijA(k+1)ij=mi nAkij,Aki+1k+1+Akk+1j弗洛伊德主要算法，若Akij已求出，頂點i到頂點k+1的路徑長度為Akik+1，頂點路徑長度為Akij

14、，頂點k+1到頂點j的路徑長度為Akk+1j， 如果此時Akik+1+Akk+1j Akij,則將原來的頂點i到頂點j的路徑改為頂 點，否則不需要修改頂點i至叮的路徑。廈 k+1+ 1,jAki,k+1Aki,j圖 2-6若 Akik+1+Akk+1 j Akij, 修改路徑過程：for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+Dkj1 長度=0，1=2 長度=8,1=3 長度=8+6=14，1=4 長度=8+5=13 ；和下圖完全一致=1,2注=2, 3P 6=2, 4h a=-=X 2,6=3, L4- 3 T7向因人市儲姑枸淫立完

15、申！*44*44*4*求城市之間的最趣距 A*4*4*1.求一個城市到所有城市的最短年離=z求仕童的廚個城市之間的最竝站碼=請注樣：1或匕 玄性U追出主1二二二二二二二二求單灌腿律，輸入源點Y； 1路栓 =114132-13-2-14-21長度=6+4=10,2=2長度=0,2=3長度=6,2=4長二二=請選擇：或沢 選擇D退出：1求單源路於.輸入源點”：2= 摩徑長度.路怪=101-3-2=0263-2=542=3，且路徑=請選擇：1或2,選擇0退出；2輸入源點和終點:v. w： 1,3=從頂點1到3最短路徑是1-2-3工二工二詛徑*:度：14_二二材當補黑材宙取*:怖水求城市之間的最短距離

16、察*斗巖*!*：林岀水林=L求一個城市到所有城市的最短距離=2,求任意的兩個城市之間的最短距離=請選擇：1或/選擇0退岀;為14,與下圖結果相同圖3-6為保證結果正確換一個頂點進行：如頂點2到4之間的最短路徑以及距離經過計算可得2到4的最短路徑是2=4,且最短路徑為5請詵擇；1或占選擇0退出；2=二輸入汾點和終點：v, w： 2,4 =從瑣點2到4最短路徑是2-4=珞徑長度：5_=*林林林：Mt#*我城市之間的垠短距離*片片甘甘甘=,或一個埔市亍所嘗城市的最晅躋離=求任意的兩個城市之間的最短融離=青選擇t 1或耳 選擇0退出;圖3-7結束程序當用戶輸入命令0時，結束程序=請逸擇：丄或浜 逸艷

17、退出；0半科比狀*牢埠卓半林結束求最屯路彳圣t 再”見車率寧牢埠杠特科補?ss anv key to centimi?圖3-84總結通過這次數(shù)據(jù)結構課程設計,我對數(shù)據(jù)結構這門課程有了更深一步的了 解，使我對數(shù)據(jù)結構這門課程掌握以及運用更加靈活。同時也讓我發(fā)現(xiàn)了自 己在這門課上的不足與缺陷，同時也明確了自己在以后的類似課程中的具體學習 方法。這次在應用中，我發(fā)現(xiàn)了自己的很多不足，在編寫城市交通咨詢系統(tǒng)的過程 中，自己C語言方面的只是掌握太少，很多功能需求只能退而求其次，一次又 一次的更改，一次又一次的失敗，也終于是在最后也完成了自己的要求， 同時我 也知道了平時用功學習的重要性。 尤其是在日常學

18、習之中，對于單一的只是點也 許掌握的還不錯，但是自己動手太少，實踐經驗嚴重不足，且面臨課程設計之時， 要求多方面的只是結和編碼，對于我而言還是有很大的難度的。如此次對于鄰接 矩陣的存儲于讀取，以及最短路徑算法的實現(xiàn)，兩個及其重要的算法，狄克斯特 拉算法和佛洛依德算法，在具體的應用上還是有很多不足。通過此次課程設計，我也明白了對于一個完成的程序而言， 想要完成它最重 要的代碼，最初，也是最為重要的一個部分就是算法思想， 以及具體程序功能規(guī) 劃，只有最重要的地基部分完美實現(xiàn)，才可以進行接下來的具體代碼編程，以及 更多細節(jié)上的完美。通過這次的課程設計我有懂得了好多數(shù)據(jù)結構的知識，以前上課沒有聽的，

19、不知道的，這次都有所了解了，像有向圖的構建，弗洛伊德算法，迪克斯特拉算 法。這些知識從曾經的聽說到現(xiàn)在的了解，進了一大步。不但如此，這次的課設也是我感覺到了數(shù)據(jù)結構的強大與神奇。 漸漸的愛上他了。 不僅讓我了解了數(shù)據(jù) 結構更加深了對它與 C 語言的聯(lián)系的理解。因為自己的不學習， 導致這次的課設變得如此的艱難。 且因為自己生病住院 也更是浪費了很大的時間， 對于我自己做課程設計的時間就少的可憐， 這也無疑 是對我更大的挑戰(zhàn)。 在臨近答辯， 我的代碼才基本完成， 夜以繼日的努力也終于 是讓我完成5.致謝本次課程設計我遇到了極大的問題， 不管是時間方面還是內容方面， 自己都 顯得慌亂過， 我能夠完成

20、本次課程設計也完全感謝舍友的支持與幫助， 在難點上 能夠對我進行幫助。 尤其感謝我的知道老師張老師。 感謝她在百忙之中抽出時間 來為我解答疑惑， 解決問題， 她對我此次的課程設計有極大的幫助。 再次感謝張 老師。課程設計馬上結束， 同時也謝謝所有的負責老師， 謝謝她們這幾天對我們 的付出，老師辛苦了。6.附錄#include#include#define MVNum 100/ 最大頂點數(shù)#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVe

21、rtexType vexsMVNum;/ 頂點數(shù)組，類型假定為 charAdjmatrix arcsMVNumMVNum;/ 鄰接矩陣，類型假定為 int 型MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;/* 建立有向圖的儲存結構 */void CreateMGraph(MGraph * G,int n,int e)/ 采用鄰接矩陣表示法構造有向圖G，n、e 表示圖的當前頂點數(shù)和邊數(shù)int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;/ 初始化鄰接矩陣printf(”= 輸入%d條邊人i (起點)、j (終點)及 w (路徑長度)n,e);for(k=1;karcsij=w;printf(= 有向圖人存儲結構建立完畢！ =n);/* 迪杰斯特拉算法 */void Dijkstra(MGraph *G,int v1,int n)/利用迪杰斯特拉算法，求出有向圖G的v1頂點到其他頂點 v的最短路徑Pv及權Dvint D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;/ 置初始的最短路徑值