交通咨詢系統(tǒng)設計說明書

1、.wd.wdPAGE7 / NUMPAGES7.wd目錄一前言.111設計要求.112設計思想.113設計要求.1二程序流程圖.1三程序源代碼.2四編譯與運行.6五課程總結.9前言:1.設計內(nèi)容：在交通網(wǎng)絡非常興旺，交通工具和交通方式不斷更新的今天，人們在出差、旅游或做其它出行時，不僅關心節(jié)省費用，而且對里程和所需時間等問題也感興趣。對于這樣一個人們關心的問題，可用一個圖構造來表示交通網(wǎng)絡系統(tǒng)，利用計算機建設一個交通咨詢系統(tǒng)。圖中頂點表示城市之間的交通關系。這個交通系統(tǒng)可以答復旅客提出的各種問題。比方任意一個城市到其他城市的最短路徑，任意兩個城市之間的最短路徑問題。本次設計的交通咨詢系統(tǒng)主要是

2、運用C語言來完成交通圖的存儲、圖中頂點的單源最短路徑和任意一對頂點間的最短路徑問題。設計一個交通咨詢系統(tǒng)，能讓旅客咨詢?nèi)我粋€城市到另一個城市之間的最短里程或最低花費或最少時間等問題。對于不同咨詢要求，可輸入城市間的路程或所需費用或所需時間。該交通咨詢系統(tǒng)設計共三局部，一是建設交通網(wǎng)絡圖的存儲構造；二是解決單源路徑問題；最后再實現(xiàn)兩個城市之間的最短路徑問題。2.設計思想：用鄰接矩陣來存儲交通網(wǎng)絡圖的信息，運用迪杰斯特拉算法實現(xiàn)圖上單源最短路徑問題，然后運用費洛伊德算法實現(xiàn)圖中任意一對頂點間最短路徑問題，這樣就會實現(xiàn)旅客所要咨詢的問題。3.設計要求：該交通咨詢系統(tǒng)要完成城市網(wǎng)絡圖的存儲，并要實現(xiàn)求

3、任意一個城市頂點到其他城市頂點的最短路徑問題，還要實現(xiàn)任意兩個城市頂點間的最短路徑問題。故設計要分成三局部，一是建設交通網(wǎng)絡圖的存儲構造；二是解決單源路徑問題；最后再實現(xiàn)兩個城市之間的最短路徑問題。二程序流程圖：程序源代碼:#include#include#define MVNum 100 /最大頂點數(shù)#define Maxint 35000enum booleanFALSE,TRUE;typedef char Vertextype;typedef int Adjmatrix; typedef struct Vertextype vexsMVNum; /頂點數(shù)組， 類型假定為char型Adjm

4、atrix arcsMVNum MVNum; / 鄰接矩陣， 假定為int型 MGraph; int D1MVNum, p1MVNum; int DMVNumMVNum,pMVNumMVNum;/文件名save.c 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

5、(k=1;karcsij=w; printf (有向圖的存儲構造建設完畢！ n); /文件名:dijkstra.c(迪杰斯特拉算法void Dijkstra(MGraph *G, int v1,int n) /用Dijkstra算法求有向圖G的v1頂點到其他頂點v的最短路徑pv及其權Dv /設G是有向圖的鄰接矩陣，假設邊不存在，那么Gij=Maxint /Sv為真當且僅當v屬于S，及以求的從v1到v的最短路徑 int D2MVNum, p2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;varcsv1v; /置初始的最短路徑值 if(D2v

6、 Maxint) p2v=v1; /v1是的前趨雙親 else p2v=0; /v 無前趨 / End_for D2v1=0;Sv1=TRUE; /S集初始時只有源點， 源點到源點的距離為0/開場循環(huán)，每次求的V1到某個V頂點的最短路徑，并加V到S集中 for(i=2;in;i+) /其余n-1個頂點 min=Maxint; / 當前所知離v1頂點的最近距離，設初值為 for(w=1;w=n;w+) /對所有頂點檢查 if(!Sw & D2wmin) /找離v1最近的頂點w，并將其賦給v，距離賦給min v=w; /在S集之外的離v1最近的頂點序號min=D2w; /最近的距離 /W頂點距離V

7、1頂點更近 Sv=TRUE; /將v并入S集 for(w=1;warcsvwarcsvw; /更新D2w p2w=v; /End_if /End_for 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); /文件名 floyd.c(費洛伊德算法void Floyd(MGraph *G, int n)int i, j, k;for(i=1;i=n;i+) /設置路徑長度D和路徑path初值for(j=1;j

8、arcsij!=Maxint)pij=j; /j是i的后繼elsepij=0;Dij=G-arcsij;for(k=1;k=n;k+) /做K次迭代，每次均試圖將頂點K擴大到當前求得的從i到j的最短路徑pij上for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+Dkj%d,k); /輸出后繼頂點k=pkw; /繼續(xù)找下一個后繼頂點printf(-%d,w); / 輸出終點wprintf( 路徑長度:%dn,Dvw); if(xz=1) printf(求單源路徑，輸入起點v :); scanf(%d, &v); Dijkstra(G,v,n); /調用迪杰斯特拉算法 printf(完畢求最短路徑，再見！n);編譯及運行:編譯: 在第一次編譯時出現(xiàn)了很多錯誤，是因為我對C語言的不熟練，比方調用費洛伊德算法時出現(xiàn)了調用的錯誤，找了好久，才改正過來，還有就是for語句的運用，由于本次程序要用很多for循環(huán)，我把一次for循環(huán)放到了上面for循環(huán)中，導致程序不能正確輸出結果。最后把調到外面才OK。運行結果：下面是城市交通圖五.課程總結通過此次課程設計大大加深了我對數(shù)據(jù)構造這門課程的理解，而且尤其對圖這章的理解，可以說有一個大的進步。學習能力也大大