數據結構課程設計城市道路交通咨詢系統

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

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

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

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

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

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

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

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

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

10、Graph *G,int n);2.2.2建立鄰接矩陣交通網絡:結果，退出系統圖2.12.定義一個 Dijkstra 函數任意兩個城市的開始k<=e,k+圖2-2鄰接矩陣構造圖結構函數數據類型定義：typedefstructVertexTypevexsMAX;AdjmatrixarcsMAXMAX;MGraph;voidCreateMGraph(MGraph*G,intn,inte)/inti,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("輸入族邊的i,j及w:n",e);for(k=1;k<=e;k+)scanf（"%d,%d,%d",&i,&j,&w）;G->arcsij=w;printf（"有向圖的存儲結構建立完畢！n"）;其中vexsMAX保存頂點信息,arcsMAXMAX用于保存邊與邊之間的信息。在構建時通過輸入的邊數i,j作為矩陣的行、列確定頂點的出度和入度。用鄰接矩陣方法存儲圖。2.2.3查詢指定城市到其他城市自己建的最短路程:圖2-3斯應用狄克斯特拉算法來具體/現2一步的需求。基本

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

13、t;n;i+)(min=IDF;for(w=1;w<=n;w+)if(!Sw&&Dw<min)(v=w;min=Dw;Sv=1;/修改頂點u放入s中for(w=1;w<=n;w+)if(!Sw&&(Dv+G->arcsvw<Dw)Dw=Dv+G->arcsvw;Pw=v；2.2.4查詢任意兩個城市之間的一條最短路徑:其具體的流程圖如圖2-5所示:用鄰接矩陣保存圖存儲后，另外需要存一個二維數組A存放當前頂點之間的最短路徑長度。分量Aij表示當前頂點i到j的最短路徑長度。弗洛伊德算法的基本思維是遞推產生一個矩陣序列A0,A1,A2

14、,-.Ak,An,其中Ak皿表示從頂點到vi到頂點vj的路徑上所經過的頂點編號不大于k的最短路徑長度A皿=cost皿A(k+1)ij=minAkij,Aki+1k+1+Akk+1j弗洛伊德主要算法，若Akij已求出，頂點i到頂點k+1的路徑長度為Akik+1,頂點路徑長度為Ak皿,頂點k+1到頂點j的路徑長度為Akk+1j,如果此時Akik+1+Akk+1j<Ak皿,則將原來的頂點i到頂點j的路徑改為頂點，否則不需要修改頂點i至”的路徑。k+Aki,k+1Akk+1,jAki,j圖2-6若Akik+1+Akk+1j卜Akij,修改路徑過程：for(k=1;k<=n;k+)for(i

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

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

17、-2(2)輸入具體的頂點以及邊的個數:圖3-3地圖輸入完成，有向圖存儲結構建立完成3.2.2、具體功能的實現1、求一個城市到所有城市之間的最短距離。查詢一個頂點到其他頂點的最短路徑。如下圖。經過手工計算:1=>1長度=0,1=>2長度=8,1=>3長度=8+6=14,1=>4長度=8+5=13;和下圖完全一致=1,2,8=22E-2,4卜5-3j6=3tL437''宣向四人存儲結構律立憲甲！一m：t*±*4*求域幣y二：產；u-*xh*h*L求一卜城tr到所有城t的最原距離=Z第任意的桿個城市之的聶達界高=：盾選擇:1或匕注擇。退出:1求工源蹌

18、j三旬源；.二二疇徑隹度，路徑二=0I=82<-1-1+3<-2<-1=134<-2<-1點*本加求城市之間的最加笈前要*本*4*二三百二不建運麗加彳曲3盲品高=3求任意的兩個城市之間的最短距離=請選擇t1或L透邪0退出上圖3-4為保證結果正確換一個頂點進行：如頂點2到其他的距離經過手工計算：2=>1長度=6+4=10,2=>2長度=0,2=>3長度=6,2=>4長二二二二請選擇：1或2,選擇口退出士1求單源路衿,輸人源點v二2=踣役長度.踣役=二二二101<-3<-2二二二0263<-2=54<-2*粗皿制u0Mc

19、求城市之何的最近距離%*=1.求一個城市到所有城市的最短距離二=2.求任意的兩個城市之間的最短更離=度=5;和下圖完全一致圖3-52、求任意的兩個城市之間的最短距離例1到3之間的最短距離，經過計算可得最短距離為1=>2=>3,且路徑=請選擇：1或2,選擇0退出；2輸入源點和終點:v,w：1,3=從頂點1到3最短路徑是1->2->3二二二二路徑長度114_二二*宓*求城市之間的最短距離*=L求一個城市到所有城市的最短距離=二=二二2,求任意的兩個城市之間的最短距離=請選擇：1或，選擇0退出;為14,與下圖結果相同圖3-6為保證結果正確換一個頂點進行：如頂點2到4之間的最短

20、路徑以及距離經過計算可得2到4的最短路徑是2=>4,且最短路徑為5圖3-73.2.3、結束程序當用戶輸入命令0時，結束程序圖3-84.總結通過這次數據結構課程設計，我對數據結構這門課程有了更深一步的了解，使我對數據結構這門課程掌握以及運用更加靈活。同時也讓我發(fā)現了自己在這門課上的不足與缺陷，同時也明確了自己在以后的類似課程中的具體學習方法。這次在應用中，我發(fā)現了自己的很多不足，在編寫城市交通咨詢系統的過程中，自己C語言方面的只是掌握太少，很多功能需求只能退而求其次，一次又一次的更改，一次又一次的失敗，也終于是在最后也完成了自己的要求，同時我也知道了平時用功學習的重要性。尤其是在日常學習之

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

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

23、助。尤其感謝我的知道老師張老師。感謝她在百忙之中抽出時間來為我解答疑惑，解決問題，她對我此次的課程設計有極大的幫助。再次感謝張老師。課程設計馬上結束，同時也謝謝所有的負責老師，謝謝她們這幾天對我們的付出，老師辛苦了。6 .附錄#include<stdio.h>#include<stdlib.h>#defineMVNum100最大頂點數#defineMaxint32767enumbooleanFALSE,TRUE;typedefcharVertexType;typedefintAdjmatrix;typedefstructVertexTypevexsMVNum;/頂點數組

24、，類型假定為charAdjmatrixarcsMVNumMVNum;/鄰接矩陣，類型假定為int型MGraph;intD1MVNum,P1MVNum;intDMVNumMVNum,PMVNumMVNum;/*建立有向圖的儲存結構*/voidCreateMGraph(MGraph*G,intn,inte)/采用鄰接矩陣表示法構造有向圖G,n、e表示圖的當前頂點數和邊數inti,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;/初

25、始化鄰接矩陣printf("=輸入舔邊人i(起點)、j(終點)及w(路徑長度)：n",e);for(k=1;k<=e;k+)/讀入e條邊，建立鄰接矩陣printf("=");scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("=有向圖人存儲結構建立完畢！=n");/*迪杰斯特拉算法*/voidDijkstra(MGraph*G,intv1,intn)/利用迪杰斯特拉算法，求出有向圖G的v1頂點到其他頂點v的最短路徑Pv及權DvintD2M

26、VNum,P2MVNum;intv,i,w,min;enumbooleanSMVNum;for(v=1;v<=n;v+)/初始化S和DSv=FALSE;/置空最短路徑終點集D2v=G->arcsv1v;/置初始的最短路徑值if(D2v<Maxint)P2v=v1;/v1是v的前趨(雙親)elseP2M=0;/v無前趨(雙親)D2v1=0;Sv1=TRUE;/S集初始時只有源點，距離為0for(i=2;i<n;i+)/其余n-1個頂點min=Maxint;for(w=1;w<=n;w+)if(!Sw&&D2w<min)v=w;min=D2w;/

27、w頂點離v1頂點更近Sv=TRUE;for(w=1;w<=n;w+)/更新當前最短路徑及距離if(!Sw&&(D2M+G->arcsvw<D2w)D2w=D2v+G->arcsvw;P2w=v;printf("=路徑長度，路徑=n");for(i=1;i<=n;i+)printf("=%5d",D2i);printf("%5d",i);v=P2i;while(v!=0)printf("<-%d",v);v=P2v;printf("n");/*費

28、洛伊德算法*/voidFloyd(MGraph*G,intn)/利用費洛伊德算法，求出最短路徑intij,k;for(i=1;i<=n;i+)for(j=1;j<=n;j+)(if(G->arcsij!=Maxint)Pi0=j；elsePiU=O；Dij=G->arcsiU;)for(k=1;k<=n;k+)(for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(Dik+DkU<Dij)Dij=Dik+DkU;)voidmain()(printf("*歡迎使用城市交通咨詢系統*n");printf("n");printf("=n")；MGrap