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

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

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

3、 輸出各條最短路徑void Floyd() 采用弗洛伊德算法求所有頂點之間的最短路徑void DisPath2() 由path計算最短路徑void Ppath2() 輸出各條最短路徑2.3相關數(shù)據(jù)結構設計 1.數(shù)據(jù)結構 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ù)庫結構：下表構成該系統(tǒng)的基本數(shù)據(jù)庫城市代號鄰接矩陣邊數(shù)組城市

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

5、城市代號z=0退出程序z=3;調(diào)用Floyd函數(shù)求所有定點之間的最短路徑z=2;調(diào)用Dijkstra函數(shù)求v到其余各頂點的最短路徑調(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置為空。將遠點編號v放入s中,循環(huán)直到所有頂點的最短路徑都求出，將mindis置最小長度初值，選取不在s中且具有最小距離的頂點u將頂點u加入s中，修改不在s中的頂點的距離，輸出最短路徑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ù) 前向遞歸查找路徑上的頂點，找到起點則返回，找頂點k的前一個頂點，輸出頂點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ù)計算最短路徑，搜索最短路徑的所有邊，輸出路徑上的起點，輸出路徑上的中間點，輸出路徑上的終點。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ù) 設置路徑長度A和路徑path初值。做k次迭代，每次均試圖將頂點K擴充到點錢球得的從i到j的最短路徑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ù) 向前遞歸查找路徑上的頂點，找到了起點則返回，找頂點i的前一個頂點k，找頂點k的前一個頂點j。在path中遞歸輸出從頂點i到頂點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計算最短路徑，若頂點i和頂點j之間沒有邊，則輸出i到j沒有路徑，若有邊則輸出路勁上的起點、中間點和終點。void Dispath2(int AMAXV,int pathMAXV,int n) int i,j; printf("請輸入起點和終點(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ù)庫和標點：在存儲文件時，沒有<stdlib.h>頭文件；在程序

17、中，有部分；和遺漏。（2） 控制程序功能，只能使用一次，導致整個程序無實際作用；對圖的存儲結構不太熟悉;沒有初始化路徑，致使出現(xiàn)了亂碼；使用單個字符輸入一個字符串，導致字符串輸入異常；5.運行結果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.心得體會 這次的任務分配，從難度上來說，我這個

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

19、所以在編程中和調(diào)試過程中要認真分析和善于發(fā)現(xiàn)問題并及時解決的習慣，不懂得及時問老師或其他同學通過本次實驗，掌握了最短路徑的問題，并結合圖的存儲結構，狄克斯特拉算法、弗洛伊德算法等解決交通資訊系統(tǒng)的設計問題，源程序打出來后有多處錯誤，大小寫錯誤、符號錯誤、遺漏錯誤。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("請輸入起點和終點(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