1、榆林學院數據結構課程設計報告題目城市交通咨詢系統作者楊朝專業信息管理與信息系統學號1514210121扌旨導老師張慧答辯時間目錄1.系統需求分析 11.1用戶需求分析 11.2功能需求分析 21.3數據需求分析 21.4小結 32. 系統設計 32.1系統設計功能 32.2每個模塊的具體功能。 4采用C語言定義相關數據類型 4建立鄰接矩陣交通網絡： 4查詢指定城市到其他城市自己建的最短路程： 6查詢任意兩個城市之間的一條最短路徑： 72.3主函數的調用關系圖 83. 系統測試 93.1操作說明 93.2測試數據 10用戶進入界面： 10、具體功能的實現 11、結束程序 124. 總結 135.

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

3、或者做其他的出行之時，都會想 到道路問題，切不僅僅關心的是交通費用，而且對于里程和所需要的時間等的問 題也是同樣的關心，在此系統中，完全面向用戶，可以用一個圖結構來表示交通 網絡系統，利用計算機建立一個交通咨詢系統。且在圖中，頂點表示城市，邊表 示城市之間的交通關系。設計一個交通咨詢系統，能夠讓旅客咨詢從任一城市頂 點到達另外一個城市之間頂點的最短路徑問題（最短里程問題）。當要查詢某兩個城市之間的最短交通路線或者其中一個城市到達其余城市 的最短路線時，是一個很繁瑣的過程。根據用戶自己的需求，可以自定義地圖，此程序就是主要以滿足用戶自己的 環境與實際情況，在難以計算路程時，可將地圖輸入進行計算，

4、系統將會為用戶 提供所用路徑最短的出現路線，更好的滿足用戶需求。以下是針對咨詢用戶說明 其最基本的模塊功能。（1）進入程序后，用戶可自己設置城市的個數，以及所有城市之間總共的 路徑，且分別用頂點和邊表示城市與路徑（2）用戶根據自己設置的城市個數和路徑數， 具體輸入每個路徑的起始點 以及每條路徑的長度。（3）進入菜單選擇界面（4）選擇2,系統為用戶進行提供任意城市的交通查詢，即查詢任意兩個城 市之間的一條最短路徑。（5）選擇1,系統為用戶提供指定城市的交通查詢，即查詢指定城市到其 他城市之間的最短路徑。如若輸入頂點超出范圍顯示錯誤，系統回到菜單重新選 擇（6）選擇0,系統推出程序。1.2功能需求

5、分析城市交通咨詢系統總體的設計目標：用數據結構中的鄰接矩陣作數據結構，并結合數據結構有向圖的最短路徑計算方法，結合相應的數據算法以及c語言的相關知識，編寫一個良好的，具有可操作性的，以及能方便用戶的使用， 包括自定義地圖，路徑與城市個數可結合實際情況而言，相對操作，簡便易懂并無難度。系統在菜單可根據命令進行相應的操作，已滿足用戶的需求。城市交通系統基本功能根據以上分析，此系統具備以下功能：（1）用戶進入后的地圖創建界面（明確地圖中城市的個數以及路徑的個數）（2）地圖完善界面（用戶自己輸入地圖中相關路徑的起始點以及路徑長度）（3）菜單界面包含兩條命令（4）命令1求一個城市到所有城市的最短距離（5

6、）命令2求任意的兩個城市之間的最短距離（6）回復命令0可推出程序。1.3數據需求分析用鄰接矩陣建立交通網絡模塊VertexType vexsMVNum; 頂點數組，類型假定為 charAdjmatrix arcsMVNumMVNum; 鄰接矩陣，類型假定為 int 型 建立鄰接矩陣，用函數 void CreateMGraph（MGraph* G,int n,int e） / 采用鄰接矩陣表示法構造有向圖 G n、e表示圖的當前頂點數和邊數 用迪杰斯特拉算法計算某頂點到其余頂點的最短路徑用函數 void Dijkstra （MGraph * G,int n,int e）來定義此函數采用鄰接矩陣表

7、示法構造有向圖 G, n、e表示圖的當前頂點數和邊數用弗洛伊德算法求任意一對頂點的最短路徑用函數void Floyd（MGraph *G,i nt n）來定義。利用費洛伊德算法，求出最短路徑。1.4小結從各種需求方面下手改編代碼，并不斷調試，讓界面更加友好。不斷地嘗試 上，在各種問題上不斷突破，慢慢的完善代碼，等最大限度的滿足用戶需求。這 幾天短時間的課程設計也讓我認識到了自己在這門課程上還面臨著許許多多的 問題，為以后的具體實踐明確了努力方向。同時，城市交通咨詢系統的實現，為 用戶更好的解決了再實際出行時遇到的路徑問題，最初的設計也為代碼敲定了編 寫方向。再三考慮后確定了系統的功能， 確定什

8、么功能有實現必要，什么功能可 有可無。在這樣的基礎之下使得思路更加清晰。2. 系統設計本程序首先是用戶編輯界面，用戶根據自己的需求編寫地圖，從而加入頂點 的數組之中，創建的地圖用鄰接矩陣存儲，在從主函數之中進行調用，實現對兩 個算法的調用。用戶在輸入頂點以及邊的信息都會存儲，在存儲成功之后會提示用戶存儲成 功，之后進入到菜單界面，菜單界面提供兩種選擇口令，分別可以調運Dijkstra 和Floyd算法，調用之后輸入相應的口令以及要查詢的城市編號，算法會根據鄰接矩陣存儲的地圖進行計算，求出最短路徑。在以后使用完系統后，可輸入口令 0,系統會結束一切運算，退出程序。2.1系統設計功能菜單界面的主要

9、功能有兩個：（1）、求一個城市到所有城市的最短距離（2）、求任意的兩個城市之間的最短距離 城市交通咨詢系統主要有三個模塊分別為：（1）、鄰接矩陣的輸入與存儲構建交通網絡（2）、任意兩個城市的最短距離查詢（3）、兩個指定城市的最短距離查詢主界面的模塊概念圖如圖2-1 :用戶進入系統交通網絡構建結果，退出系統圖2.12.2每個模塊的具體功能。采用C語言定義相關數據類型1 定義一個，用來存儲頂點信息typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;.2.定義一個 Dijkstra函數void Dijkstra(MGraph *G

10、,int v,int n);3.定義一個Floyd函數void Floyd(MGraph *G,int n);建立鄰接矩陣交通網絡:開始鄰接矩陣構造圖結構函數 數據類型定義：typedef structVertexType vexsMAX; Adjmatrix arcsMAXMAX;MGraph;void CreateMGraph(MGraph *G,i nt n,i nt 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->

11、arcsij=IDF;printf("輸入%d 條邊的 i,j 及 w: n",e); for(k=1;k<=e;k+)sea nf（"%d,%d,%d",&i,&j,&w）;G->arcsij=w; printf（"有向圖的存儲結構建立完畢!n"）;其中vexsMAX保存頂點信息，arcsMAXMAX用于保存邊與邊之 間的信息。在構建時通過輸入的邊數i, j作為矩陣的行、列確定頂點的出度 和入度。用鄰接矩陣方法存儲圖。查詢指定城市到其他城市自己建的最短路程：應用狄克斯特拉算法來具體實現這一步的需求

12、。基本思想：設G（V,E）是一個帶權有向圖，把圖中的頂點集合V分成兩組， 第一組為已經求出的最短路徑的頂點集合（用S表示，初始時S中只有一個原點， 以后每求得一條最短路徑就加入的集合 S中，知道全部頂點都加入到集合中）， 第二組，為其余未確定最短路徑的頂點集合（用 U表示），按最短路徑長度的遞 增次序依次把第二組的頂點就如 S中。如果兩個頂點之間有權值，并且各個路徑的權值不同，就把最小的作為頂點與頂點的最短距離y圖2-4如圖所示 若x+y<z，則最短的路徑就是v=>k=>u。同理若x+y<z，則最短 的路徑就是v=>u,D v1=0;Sv1=1;/原點編號放入s中

13、for(i=2;i <n ;i+)mi n=IDF;for(w=1;w <=n; w+)if(!Sw&&D w<mi n)v=w;mi n=D w;Sv=1;修改頂點u放入s中for(w=1;w<=n; w+)if(!Sw &&(D v+G->arcsvw<D w)D w=D v+G->arcsvw;P w=v;2.2.4查詢任意兩個城市之間的一條最短路徑：用鄰接矩陣保存圖存儲后，另外需要存一個二維數組A存放當前頂點之間的最短路徑長度。分量Aij表示當前頂點i到j的最短路徑長度。弗洛伊德算法的基本思維是遞推產生一個矩陣序

14、列 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，頂點k+1到頂點j的路徑長度為Akk+1j， 如果此時Akik+1+Akk+1j< Akij, 則將原來的頂點i到頂點j的路徑改為 頂點，否則不需要修改頂點i至叮的路徑。圖2-6若 Akik+1+Akk+1 j< Akij,修改路徑過程：for(k=1;k<=

15、n ;k+)for(i=1;i<=n ;i+) for(j=1;j<=n ;j+) if(Dik+Dkj<Dij)Dij=Dik+Dkj; /修改長度Pij=Pik;2.3主函數的調用關系圖程序是通過進入程序之后，用戶開始根據自己的實際情況來輸入具體的地圖參數，構建自己所需要的地圖大小以及城市個數和路徑長短。當輸入完畢參數之后，用戶進入主菜單查詢界面?？筛鶕煌倪x口令，用戶可以選擇不同的系統 功能。查詢1可以進入狄克斯特函數，來求取得到一個城市到所有城市自己還能的 具體的最短路徑以及走法。當用戶輸入口令2之后，可以進入弗洛伊德函數的調用，更加提示用戶輸入想要查詢的兩個城市，

16、 系統會根據地圖自動計算出所需要 的最短距離以及最短路徑，完美的滿足用戶自己的需求。當輸入口令0之后，用 戶可以選擇退出程序，結束城市查詢。同時由于地圖的鄰接矩陣建立是由 malloc 函數申請的空間，在結束運行之后，系統自動釋放空間，從而減少系統空間的占 有率。3. 系統測試3.1操作說明雙擊“城市交通咨詢系統.exe ”根據屏幕菜單提示信息，選擇任意可選項 進行相關操作。根據提示開始輸入城市個數以及路徑總個數。 之后開始建立地圖, 建立成功后根據菜單界面選擇功能。3.2測試數據輸入測試數據可以對程序進行如下的圖的數據進行數據測試。下面運行程序檢查輸入，輸出結果321用戶進入界面：（1）、輸

17、入城市個數與路徑個數嘗:、飯歸阿汎埠好MD曲-X寧*衿鉗*雙返低用城市交通世館系純岸*率口*檔屮A=輸入城P個數和路徑個數m e：圖3-2（2）輸入具體的頂點以及邊的個數:LI*+*+*歡迎 使用城市交適 咨詢系紛*煒*輸入坤市嚇致和聽徑牛數n” e；=1T = -Z輸入6棗邊人i （起點）、j 變點）踣徑長度八一-有向圖人有磧站構建衛充畢！一-水甘*專*柑；*求曲市龍'可的短莎為*#*L求一個城市到所7有城市的最晅底離=2.求開卷的兩個城市之間的帚甸蹴離=請選擇；】或乙 選薦。退岀;圖3-3地圖輸入完成，有向圖存儲結構建立完成、具體功能的實現1、求一個城市到所有城市之間的最短距離。查

18、詢一個頂點到其他頂點的最短路徑。如下圖。經過手工計算：仁>1長度=0,仁>2長度=8，仁>3長度=8+6=14,仁>4長度=8+5=13;和下圖完全一致865647 占3b4>2,h3. h 右ns N £ L=揺孟驚嚮穀翻I蠶篙=沽注甘：1或氏 玄桂退出主1二二二二二二二二二二二二二求單薄覚隹，輸入源點Y； 1=蹄徑良鹿*路樓 二工8 2<-1=13+<-2-1ic#mf¥*¥*#* 出.城市上:可 Fj最 迪跆曳*mf¥#>：*#¥=2：爰任為慕鑑熬髓雒需二=請迭抒* 1或人遺掃0謹出土圖3-

19、4為保證結果正確換一個頂點進行：如頂點2到其他的距離經過手工計算：2=>1長度=6+4=10, 2=>2長度=0，2=>3長度=6， 2=>4長 度=5;和下圖完全一致二二育選擇：1或浜 選擇D退出：1求單鍊路程.輸入澹點忙2= 曄徑長度.路徑=101<-3<-2工0263<-2=54<-2* *林*甘* * *求城市之間的最炬距離臥*水* *=1.求一個城市到浙有城市的最短距離=2.永任憲的商個城幣2向砂最短距H=圖3-52、求任意的兩個城市之間的最短距離例1到3之間的最短距離，經過計算可得最短距離為仁>2=>3,且路徑為14,與下

20、圖結果相同。=請選擇：1或2,選擇0退出；2輸入源點和終點:v. w： 1,3=從頂點1到3最短路徑是1->2-3工二工二薪徑*:度：14_二=岀帝*冶*店*：1£琳水求城市之可白勺最短距離京*斗容*斗：*；*：*：岀案尙岀=L求一個城市到所有城市的最短距離=2,求任意的兩個城市之間的最短距離=請選擇：1或/選擇0退岀;圖3-6為保證結果正確換一個頂點進行：如頂點2到4之間的最短路徑以及距離經過計算可得2到4的最短路徑是2=>4,且最短路徑為5=請詵擇；1或3迭開Q逞出；2=諭入游點和終點；V, w； 2,4=從頂點2到4最短路徑是2 T4 =路徑長度；5-=罕* *宰*

21、宰*5*林林求城市之間的最短距鬲襯*甘帖字*J|*f：二,求一個城市和所有城市的最矩跨省=?,求任肯的兩個城市之間的最短審離=亍=請選擇t 1或乙選擇0退出;圖3-7、結束程序當用戶輸入命令0時，結束程序=請逸擇：1或宴 逸擇0 辱；0半*案*！和結束求最短路徑， 再見!t*半杠半半杠口Pl*l=*半ess anv kev to continue圖3-84. 總結通過這次數據結構課程設計,我對數據結構這門課程有了更深一步的了 解，使我對數據結構這門課程掌握以及運用更加靈活。同時也讓我發現了自 己在這門課上的不足與缺陷，同時也明確了自己在以后的類似課程中的具體學習 方法。這次在應用中，我發現了自

22、己的很多不足，在編寫城市交通咨詢系統的過程 中，自己C語言方面的只是掌握太少，很多功能需求只能退而求其次，一次又一 次的更改，一次又一次的失敗，也終于是在最后也完成了自己的要求， 同時我也 知道了平時用功學習的重要性。尤其是在日常學習之中，對于單一的只是點也許 掌握的還不錯，但是自己動手太少，實踐經驗嚴重不足，且面臨課程設計之時， 要求多方面的只是結和編碼，對于我而言還是有很大的難度的。如此次對于鄰接 矩陣的存儲于讀取，以及最短路徑算法的實現，兩個及其重要的算法，狄克斯特 拉算法和佛洛依德算法，在具體的應用上還是有很多不足。通過此次課程設計，我也明白了對于一個完成的程序而言， 想要完成它最重

23、要的代碼，最初，也是最為重要的一個部分就是算法思想， 以及具體程序功能規 劃，只有最重要的地基部分完美實現，才可以進行接下來的具體代碼編程，以及 更多細節上的完美。通過這次的課程設計我有懂得了好多數據結構的知識，以前上課沒有聽的， 不知道的，這次都有所了解了，像有向圖的構建，弗洛伊德算法，迪克斯特拉算 法。這些知識從曾經的聽說到現在的了解，進了一大步。不但如此，這次的課設 也是我感覺到了數據結構的強大與神奇。漸漸的愛上他了。不僅讓我了解了數據 結構更加深了對它與C語言的聯系的理解。因為自己的不學習，導致這次的課設變得如此的艱難。 且因為自己生病住院 也更是浪費了很大的時間，對于我自己做課程設計

24、的時間就少的可憐， 這也無疑 是對我更大的挑戰。在臨近答辯，我的代碼才基本完成，夜以繼日的努力也終于 是讓我完成5. 致謝本次課程設計我遇到了極大的問題， 不管是時間方面還是內容方面，自己都 顯得慌亂過，我能夠完成本次課程設計也完全感謝舍友的支持與幫助， 在難點上 能夠對我進行幫助。尤其感謝我的知道老師張老師。感謝她在百忙之中抽出時間 來為我解答疑惑，解決問題，她對我此次的課程設計有極大的幫助。 再次感謝張 老師。課程設計馬上結束，同時也謝謝所有的負責老師，謝謝她們這幾天對我們 的付出，老師辛苦了。6. 附錄#in clude<stdio.h>#in clude<stdlib

25、.h>#define MVNum 100 最大頂點數#define Maxi nt 32767enum boolea nFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum; 頂點數組，類型假定為charAdjmatrix arcsMVNumMVNum;鄰接矩陣，類型假定為int 型MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;/*建立有向圖的儲存結構*/void CreateMGraph(MGr

26、aph * G,i nt n,i nt e)/采用鄰接矩陣表示法構造有向圖G，n、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=Maxint;/ 初始化鄰接矩陣printf("= 輸入%d條邊人i (起點八j (終點)及w (路徑長度)：n”,e);for(k=1;k<=e;k+)讀入e條邊，建立鄰接矩陣 pri ntf("=");sca nf("%d

27、,%d,%d", &i,&j, &w);G->arcsij=w;=n");printf(”=有向圖人存儲結構建立完畢！/*迪杰斯特拉算法*/void Dijkstra(MGraph *G,i nt v1,i nt n)利用迪杰斯特拉算法，求出有向圖G的v1頂點到其他頂點v的最短路徑Pv及權Dvint D2MVNum,P2MVNum;int v,i,w,mi n;enum boolean SMVNum;for(v=1;v<=n;v+) 初始化 S 和 DSv=FALSE;置空最短路徑終點集D2v=G->arcsv1v;置初始的最短路徑

28、值if(D2v<Maxi nt)P2v=v1;/v1是v的前趨(雙親)elseP2v=0;/v無前趨(雙親)D2v1=0;Sv1=TRUE;/S 集初始時只有源點，距離為 0for(i=2;i<n;i+)/ 其余 n-1 個頂點mi n=Max int;for(w=1;w <=n; w+)if(!Sw && D2w<min) v=w;min=D2w; /w頂點離v1頂點更近Sv=TRUE;for(w=1;w<=n;w+)/更新當前最短路徑及距離if(!Sw&&(D2v+G->arcsvw<D2w) D2w=D2v+G-&

29、gt;arcsvw;P2w=v;printf(”= 路徑長度，路徑=n");for(i=1;i<=n ;i+)ouroE po>2 曰 d"m二 ds=Qv_mQ+N=Q)(+ruuvrud04 (+UHV'L.!I)O4 (+xuuvxlrM)04 宀 s三 370=一Q o"=曰 d二=cxlcr=pg% soir旦二 d auxel/ll!.=二soeoM (+ruuvrud04 (+UHV'L.!l)04mu 一 "WMW玨坯m旺氣/) (u -u 一o* Udeol/I)PAO 匚 po> /*WMW玨坯鋼*/宀 宀M=ur£u_d 3>2du>M>=p%-V=)tu_d) o