交通咨詢系統(tǒng)設(shè)計(jì)說(shuō)明書

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

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

3、任意一個(gè)城市頂點(diǎn)到其他城市頂點(diǎn)的最短路徑問(wèn)題，還要實(shí)現(xiàn)任意兩個(gè)城市頂點(diǎn)間的最短路徑問(wèn)題。故設(shè)計(jì)要分成三局部，一是建設(shè)交通網(wǎng)絡(luò)圖的存儲(chǔ)構(gòu)造；二是解決單源路徑問(wèn)題；最后再實(shí)現(xiàn)兩個(gè)城市之間的最短路徑問(wèn)題。二程序流程圖：程序源代碼:#include#include#define MVNum 100 /最大頂點(diǎn)數(shù)#define Maxint 35000enum booleanFALSE,TRUE;typedef char Vertextype;typedef int Adjmatrix; typedef struct Vertextype vexsMVNum; /頂點(diǎn)數(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òu)造有向圖G,n,e表示圖的當(dāng)前頂點(diǎn)數(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 (有向圖的存儲(chǔ)構(gòu)造建設(shè)完畢！ n); /文件名:dijkstra.c(迪杰斯特拉算法void Dijkstra(MGraph *G, int v1,int n) /用Dijkstra算法求有向圖G的v1頂點(diǎn)到其他頂點(diǎn)v的最短路徑pv及其權(quán)Dv /設(shè)G是有向圖的鄰接矩陣，假設(shè)邊不存在，那么Gij=Maxint /Sv為真當(dāng)且僅當(dāng)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 無(wú)前趨 / End_for D2v1=0;Sv1=TRUE; /S集初始時(shí)只有源點(diǎn)， 源點(diǎn)到源點(diǎn)的距離為0/開場(chǎng)循環(huán)，每次求的V1到某個(gè)V頂點(diǎn)的最短路徑，并加V到S集中 for(i=2;in;i+) /其余n-1個(gè)頂點(diǎn) min=Maxint; / 當(dāng)前所知離v1頂點(diǎn)的最近距離，設(shè)初值為 for(w=1;w=n;w+) /對(duì)所有頂點(diǎn)檢查 if(!Sw & D2wmin) /找離v1最近的頂點(diǎn)w，并將其賦給v，距離賦給min v=w; /在S集之外的離v1最近的頂點(diǎn)序號(hào)min=D2w; /最近的距離 /W頂點(diǎn)距離V

7、1頂點(diǎn)更近 Sv=TRUE; /將v并入S集 for(w=1;warcsvwarcsvw; /更新D2w p2w=v; /End_if /End_for printf (路徑長(zhǎng)度 路徑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(費(fèi)洛伊德算法void Floyd(MGraph *G, int n)int i, j, k;for(i=1;i=n;i+) /設(shè)置路徑長(zhǎng)度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次迭代，每次均試圖將頂點(diǎn)K擴(kuò)大到當(dāng)前求得的從i到j(luò)的最短路徑pij上for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+Dkj%d,k); /輸出后繼頂點(diǎn)k=pkw; /繼續(xù)找下一個(gè)后繼頂點(diǎn)printf(-%d,w); / 輸出終點(diǎn)wprintf( 路徑長(zhǎng)度:%dn,Dvw); if(xz=1) printf(求單源路徑，輸入起點(diǎn)v :); scanf(%d, &v); Dijkstra(G,v,n); /調(diào)用迪杰斯特拉算法 printf(完畢求最短路徑，再見！n);編譯及運(yùn)行:編譯: 在第一次編譯時(shí)出現(xiàn)了很多錯(cuò)誤，是因?yàn)槲覍?duì)C語(yǔ)言的不熟練，比方調(diào)用費(fèi)洛伊德算法時(shí)出現(xiàn)了調(diào)用的錯(cuò)誤，找了好久，才改正過(guò)來(lái)，還有就是for語(yǔ)句的運(yùn)用，由于本次程序要用很多for循環(huán)，我把一次for循環(huán)放到了上面for循環(huán)中，導(dǎo)致程序不能正確輸出結(jié)果。最后把調(diào)到外面才OK。運(yùn)行結(jié)果：下面是城市交通圖五.課程總結(jié)通過(guò)此次課程設(shè)計(jì)大大加深了我對(duì)數(shù)據(jù)構(gòu)造這門課程的理解，而且尤其對(duì)圖這章的理解，可以說(shuō)有一個(gè)大的進(jìn)步。學(xué)習(xí)能力也大大