交通咨詢系統(tǒng)設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書(共21頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 交通資訊系統(tǒng)1. 系統(tǒng)需求分析 1.1問題描述 在交通網(wǎng)絡(luò)非常發(fā)達(dá)的今天，人們出差、旅游或做其他出行時，不僅關(guān)心節(jié)省交通費(fèi)用，而且對里程和所需時間等問題也很感興趣。對于這樣一個人們關(guān)心的問題，可用一個圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計算機(jī)建立一個交通咨詢系統(tǒng)。圖中頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。設(shè)計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一個城市頂點(diǎn)到達(dá)另外一個城市頂點(diǎn)之間的最短路徑（里程）的問題。 1.2功能要求1.交通資訊系統(tǒng)提供用戶三種決策方案：一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)。二是 某個城市到達(dá)其余各城市的最短路徑。三是實(shí)現(xiàn)兩個城市之間最短路徑的問題。主 要目的

2、是給用戶提供路徑咨詢。 2.本系統(tǒng)規(guī)定：(1)在程序中輸入城市名稱時，需輸入0到5的城市代號(2)在選擇功 能是，應(yīng)輸入與所選功能對應(yīng)的一個整形數(shù)據(jù)。(3)程序的輸出信息主要是：城市代號，某城市到達(dá)其余各城市的最短路徑，兩城市之間最短路徑2.概要設(shè)計2.1系統(tǒng)總體設(shè)計 交通資訊系統(tǒng) 一個城市到其他城市 兩個城市之間存儲交通圖獲得最佳路徑獲得最佳路徑查詢最短距離查詢最短距離 圖2.1系統(tǒng)總體設(shè)計2.2各模塊的功能void main() 主函數(shù)void Dijkstr() 采用狄克斯特拉算法求從頂點(diǎn)v到其余個頂點(diǎn)的最短路徑void DisPath() 由path計算最短路徑void Ppath()

3、 輸出各條最短路徑void Floyd() 采用弗洛伊德算法求所有頂點(diǎn)之間的最短路徑void DisPath2() 由path計算最短路徑void Ppath2() 輸出各條最短路徑2.3相關(guān)數(shù)據(jù)結(jié)構(gòu)設(shè)計 1.數(shù)據(jù)結(jié)構(gòu) typedef int InfoType; typedef struct char cityname; int no; InfoType info; VertexType; typedef struct int edgesMAXVMAXV;int n,e;VertexType vxsMAXV; MGraph;2. 數(shù)據(jù)庫結(jié)構(gòu)：下表構(gòu)成該系統(tǒng)的基本數(shù)據(jù)庫城市代號鄰接矩陣邊數(shù)組城市

4、個數(shù)路徑城市名稱intintintintchar3.詳細(xì)設(shè)計 3.1采用c語言定義相關(guān)的數(shù)據(jù)結(jié)構(gòu)本系統(tǒng)定義了整形int,字符型char,還有結(jié)構(gòu)體定義，建立圖的存儲結(jié)構(gòu)首先定義交通圖的存儲結(jié)構(gòu)，鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣.設(shè)G=（V，E）是具有n(n>0)個頂點(diǎn)的圖，則鄰接矩陣具有如下定義的n階方陣Wij 若vivj 且<vi,vj>E(G)Aij= 其他一個圖的鄰接矩陣表示是唯一的,除了許用一個二維數(shù)組存儲頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個具有n個元素的一維數(shù)組來存儲頂點(diǎn)信息 3.2函數(shù)調(diào)用關(guān)系圖3.2.1主函數(shù) main函數(shù)z=1查看系統(tǒng)中的

5、城市代號z=0退出程序z=3;調(diào)用Floyd函數(shù)求所有定點(diǎn)之間的最短路徑z=2;調(diào)用Dijkstra函數(shù)求v到其余各頂點(diǎn)的最短路徑調(diào)用DisPath2函數(shù)計算最短路徑調(diào)用DisPath函數(shù)計算最短路徑調(diào)用ppath函數(shù)輸出各條最短路徑調(diào)用ppath2函數(shù)輸出各條最短路徑 void main()int i,j,z,x;MGraph g;int AMAXV=INF,5,INF,7,INF,INF,INF,INF,4,INF,INF,INF, 8,INF,INF,INF,INF,9,INF,INF,5,INF,INF,6,INF,INF,INF,5,INF,INF,3,INF,INF,INF,1,I

6、NF;g.n=6;g.e=10;for(i=0;i<g.n;i+)for(j=0;j<g.n;j+)g.edgesij=Aij; printf("* 交通咨詢系統(tǒng) *n"); printf("* 1-查看系統(tǒng)中的城市代號 *n"); printf("* 2-一個城市到所有城市的最短路徑 *n"); printf("* 3-任意的兩個城市之間的最短路徑 *n"); printf("* 0-退出 *n"); printf("n"); printf("請選擇：

7、");scanf("%d",&z); while(z!=0) switch(z) case 1: printf("0北京,1天津,2上海,3廣州,4南京,5廈門n"); printf("n"); main(); scanf("%d",&z); break; case 2: printf("請輸入城市代號:"); scanf("%d",&x); switch(x) case 0: printf("以下是最短路徑：n");Di

8、jkstra(g,x);break; case 1: printf("以下是最短路徑：n");Dijkstra(g,x);break; case 2: printf("以下是最短路徑：n");Dijkstra(g,x);break; case 3: printf("以下是最短路徑：n");Dijkstra(g,x);break; case 4: printf("以下是最短路徑：n");Dijkstra(g,x);break; case 5: printf("以下是最短路徑：n");Dijkstr

9、a(g,x);break; default : printf("輸入有誤，請重新輸入n"); printf("n"); main(); printf("n");main(); scanf("%d",&z);break; case 3: Floyd(g);printf("請選擇：");printf("n");main(); scanf("%d",&z);break; case 0: exit(-1);break; default: print

10、f("輸入有誤，請重新輸入n"); printf("n"); main(); 3.2.2狄克斯特拉函數(shù) 初始化距離和路徑，將s置為空。將遠(yuǎn)點(diǎn)編號v放入s中,循環(huán)直到所有頂點(diǎn)的最短路徑都求出，將mindis置最小長度初值，選取不在s中且具有最小距離的頂點(diǎn)u將頂點(diǎn)u加入s中，修改不在s中的頂點(diǎn)的距離，輸出最短路徑void Dijkstra(MGraph g,int v) int distMAXV,pathMAXV;int sMAXV;int mindis,i,j,u;for(i=0;i<g.n;i+) disti=g.edgesvi; si=0; if

11、(g.edgesvi<INF) pathi=v; else pathi=-1;sv=1;pathv=0;for(i=0;i<g.n;i+) mindis=INF; for(j=0;j<g.n;j+) if(sj=0&&distj<mindis) u=j; mindis=distj; su=1;for(j=0;j<g.n;j+)if(sj=0)if(g.edgesuj<INF&&distu+g.edgesuj<distj)distj=distu+g.edgesuj;pathj=u; Dispath(dist,path,s,

12、g.n,v);3.2.3 Ppath函數(shù) 前向遞歸查找路徑上的頂點(diǎn)，找到起點(diǎn)則返回，找頂點(diǎn)k的前一個頂點(diǎn)，輸出頂點(diǎn)k。void Ppath(int path,int i,int v)int k;k=pathi;if(k=v) return;Ppath(path,k,v);printf("%d,",k);3.2.4 Dispath函數(shù) 有path函數(shù)計算最短路徑，搜索最短路徑的所有邊，輸出路徑上的起點(diǎn)，輸出路徑上的中間點(diǎn)，輸出路徑上的終點(diǎn)。void Dispath(int dist,int path,int s,int n,int v)int i;for(i=0;i<n

13、;i+) if(si=1&&disti!=INF) printf("從%d到%d的最短路徑長度為：%dt路徑為：",v,i,disti); printf("%d,",v); Ppath(path,i,v); printf("%dn",i);else printf("從%d到%d不存在路徑n",v,i);3.2.5弗洛伊德函數(shù) 設(shè)置路徑長度A和路徑path初值。做k次迭代，每次均試圖將頂點(diǎn)K擴(kuò)充到點(diǎn)錢球得的從i到j(luò)的最短路徑Pij上，修開路徑長度，輸出最短路徑。void Floyd(MGraph g)

14、 int pathMAXVMAXV,AMAXVMAXV; int i,j,k; for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;k<g.n;k+) for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) if(Aij>Aik+Akj) Aij=Aik+Akj; pathij=k; 3.2.6 Ppath2函數(shù) 向前遞歸查找路徑上的頂點(diǎn)，找到了起點(diǎn)則返回，找頂點(diǎn)i的前一個頂點(diǎn)k，找頂點(diǎn)k的前一個頂點(diǎn)j。在path中遞歸輸出從頂點(diǎn)i到頂點(diǎn)j的最短路徑voi

15、d Ppath2(int pathMAXV,int i,int j) int k;k=pathij; if(k=-1)return;Ppath2(path,i,k);printf("%d,",k);Ppath2(path,k,j);3.2.7 DisPath2函數(shù) 由path計算最短路徑，若頂點(diǎn)i和頂點(diǎn)j之間沒有邊，則輸出i到j(luò)沒有路徑，若有邊則輸出路勁上的起點(diǎn)、中間點(diǎn)和終點(diǎn)。void Dispath2(int AMAXV,int pathMAXV,int n) int i,j; printf("請輸入起點(diǎn)和終點(diǎn)(i,j)："); scanf("

16、;%d,%d",&i,&j); if(Aij=INF) if(i!=j) printf("從%d到%d沒有路徑n",i,j);elseprintf("從%d到%d路徑為：",i,j); printf("%d,",i); Ppath2(path,i,j); printf("%d",j); printf("t路徑長度為：%dn",Aij);4.系統(tǒng)調(diào)試4.1系統(tǒng)調(diào)試中的問題（1） 只考慮函數(shù)而忽視數(shù)據(jù)庫和標(biāo)點(diǎn)：在存儲文件時，沒有<stdlib.h>頭文件；在程序

17、中，有部分；和遺漏。（2） 控制程序功能，只能使用一次，導(dǎo)致整個程序無實(shí)際作用；對圖的存儲結(jié)構(gòu)不太熟悉;沒有初始化路徑，致使出現(xiàn)了亂碼；使用單個字符輸入一個字符串，導(dǎo)致字符串輸入異常；5.運(yùn)行結(jié)果5.1輸入界面輸入界面如圖 5.1所示 圖5.1 輸入界面5.2顯示界面顯示界面如圖5.2所示 圖5.2 顯示界面5.3查詢界面查詢一個城市到其余各城市最短路徑界面如圖5.3所示 圖5.3查詢一個城市到其余各城市最短路徑界面查詢兩城市之間最短路徑界面如圖5.4所示 圖5.4查詢兩城市之間最短路徑界面5.4退出界面退出界面如圖5.5所示 圖5.5退出界面6.心得體會 這次的任務(wù)分配，從難度上來說，我這個

18、交通資訊系統(tǒng)并不復(fù)雜，在書本上基本上能找到一摸一樣的程序，但關(guān)鍵是理解。平時不聽課，現(xiàn)在要把這些整體連接起來就跟困難，雖然書上的程序能看懂，但實(shí)踐設(shè)計不比理解，要是練得少，往往捉襟見肘，要學(xué)會融會貫通，就是難上加難，所以我這次就不斷演練，不斷打擊信心，結(jié)果程序不是自己的，有時候覺得計算機(jī)語言真的好難學(xué)，我想還是練少了，醬油打多了。盡管這學(xué)期課聽了很多，但效果還是不好。 總的來說，這次編程還是學(xué)到了一些東西，盡管微乎其微，算法逼近是死的，但人的大腦是活的，只有不斷地實(shí)踐，才能找到信心，也才能學(xué)到東西，盡管這次編程是借鑒網(wǎng)絡(luò)上的，但還是可以學(xué)到很多東西，怎樣的思考方法，怎樣連接是邏輯語句更加完善。

19、所以在編程中和調(diào)試過程中要認(rèn)真分析和善于發(fā)現(xiàn)問題并及時解決的習(xí)慣，不懂得及時問老師或其他同學(xué)通過本次實(shí)驗(yàn)，掌握了最短路徑的問題，并結(jié)合圖的存儲結(jié)構(gòu)，狄克斯特拉算法、弗洛伊德算法等解決交通資訊系統(tǒng)的設(shè)計問題，源程序打出來后有多處錯誤，大小寫錯誤、符號錯誤、遺漏錯誤。7.附錄7.1源代碼#include<stdio.h>#include<stdlib.h>#include "string.h"#define INF 32767#define MAXV 10typedef int InfoType;typedef structchar cityname;

20、int no; InfoType info;VertexType;typedef structint edgesMAXVMAXV;int n,e;VertexType vxsMAXV;MGraph;void Ppath(int path,int i,int v)int k;k=pathi;if(k=v) return;Ppath(path,k,v);printf("%d,",k);void Dispath(int dist,int path,int s,int n,int v)int i;for(i=0;i<n;i+) if(si=1&&disti!=

21、INF) printf("從%d到%d的最短路徑長度為：%dt路徑為：",v,i,disti); printf("%d,",v); Ppath(path,i,v); printf("%dn",i);else printf("從%d到%d不存在路徑n",v,i);void Dijkstra(MGraph g,int v) int distMAXV,pathMAXV;int sMAXV;int mindis,i,j,u;for(i=0;i<g.n;i+) disti=g.edgesvi; si=0; if(g.e

22、dgesvi<INF) pathi=v; else pathi=-1;sv=1;pathv=0;for(i=0;i<g.n;i+) mindis=INF; for(j=0;j<g.n;j+) if(sj=0&&distj<mindis) u=j; mindis=distj; su=1;for(j=0;j<g.n;j+)if(sj=0)if(g.edgesuj<INF&&distu+g.edgesuj<distj)distj=distu+g.edgesuj;pathj=u; Dispath(dist,path,s,g.n,

23、v);void Ppath2(int pathMAXV,int i,int j) int k;k=pathij; if(k=-1)return;Ppath2(path,i,k);printf("%d,",k);Ppath2(path,k,j);void Dispath2(int AMAXV,int pathMAXV,int n) int i,j; printf("請輸入起點(diǎn)和終點(diǎn)(i,j)："); scanf("%d,%d",&i,&j); if(Aij=INF) if(i!=j) printf("從%d到%

24、d沒有路徑n",i,j);elseprintf("從%d到%d路徑為：",i,j); printf("%d,",i); Ppath2(path,i,j); printf("%d",j); printf("t路徑長度為：%dn",Aij);void Floyd(MGraph g) int pathMAXVMAXV,AMAXVMAXV; int i,j,k; for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;

25、k<g.n;k+) for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) if(Aij>Aik+Akj) Aij=Aik+Akj; pathij=k; Dispath2(A,path,g.n); void main()int i,j,z,x;MGraph g;int AMAXV=INF,5,INF,7,INF,INF,INF,INF,4,INF,INF,INF,8,INF,INF,INF,INF,9,INF,INF,5,INF,INF,6,INF,INF,INF,5,INF,INF,3,INF,INF,INF,1,INF;g.n=6;g.e=10;fo

26、r(i=0;i<g.n;i+)for(j=0;j<g.n;j+)g.edgesij=Aij; printf("* 交通咨詢系統(tǒng) *n"); printf("* 1-查看系統(tǒng)中的城市代號 *n"); printf("* 2-一個城市到所有城市的最短路徑 *n"); printf("* 3-任意的兩個城市之間的最短路徑 *n"); printf("* 0-退出 *n"); printf("n"); printf("請選擇：");scanf("%d",&z); while(z!=0) switch(z) case 1: printf("0北京,1天津,2上海,3廣州,4南京,5廈門n"); printf("n"); main(); scanf("%d",&z); break; case 2: printf("請輸入城市代號:"); scanf("%d",&x); switch(x) case 0: pr