《交通咨询系统设计方案数据结构课程设计方案任务书》由会员分享，可在线阅读，更多相关《交通咨询系统设计方案数据结构课程设计方案任务书（22页珍藏版）》请在金锄头文库上搜索。
1、交通资讯系统1. 系统需求分析1.1问题描述在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通 费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题， 可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶 点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询 从任一个城市顶点到达另外一个城市顶点之间的最短路径(里程)的问题。1.2功能要求1. 交通资讯系统提供用户三种决策方案：一是建立交通网络图的存储结构。二 是某个城市到达其余各城市的最短路径。三是实现两个城市之间最短路径的 问题。主要目的是给用户提供路径咨询。2
2、. 本系统规定：(1) 在程序中输入城市名称时，需输入 0到5的城市代号(2) 在选择功 能是，应输入与所选功能对应的一个整形数据。(3) 程序的输出信息主要是：城市代号，某城市到达其余各城市的最短路径， 两城市之间最短路径2. 概要设计2.1系统总体设计交通资讯系统2.2各模块的功能void mai n() 主函数void Dijkstr()采用狄克斯特拉算法求从顶点 v到其余个顶点的最短路径void DisPath()由path计算最短路径void Ppath() 输出各条最短路径void Floyd()采用弗洛伊德算法求所有顶点之间的最短路径void DisPath2()由path计算最
3、短路径void Ppath2()输出各条最短路径2.3相关数据结构设计1数据结构typedef int In foType。typedef structchar cit yn ame。int no。In foType info。VertexType。typedef structint edgesMAXVMAXV。int n ,e。VertexType vxsMAXV。MGraph。2数据库结构：下表构成该系统的基本数据库城市代号邻接矩阵边数组城市个数路径城市名称intintintintchar3. 详细设计3.1采用c语言定义相关的数据结构本系统定义了整形int,字符型char,还有结构体定义
4、，建立图的存储结构首先定义交通图的存储结构，邻接矩阵是表示图形中顶点之间相邻关系的矩阵设G= (V，E)是具有n(n0)个顶点的图，则邻接矩阵具有如下定义的n阶方阵广 Wij 若 vi 工 vj 且 E(G)Aij=g 其他一个图的邻接矩阵表示是唯一的，除了许用一个二维数组存储顶点之间相邻关系的 邻接矩阵外，通常还需要使用一个具有 n个元素的一维数组来存储顶点信息3.2函数调用关系图3.2.1主函数int i,j,z,x MGraph g。intAMAXV=INF,5,INF,7,INF,INF,INF,INF,4,INF,INF,INF,8,INF,INF,INF,INF,9,INF,INF
5、,5,INF,INF,6,INF,INF,INF,5,INF,INF, 3,INF,INF,INF,1,INF 。g.n=6。g.e=10。for（i=0 。 ig.n 。 i+）for（j=0 。 jg.n 。 j+）g.edgesij=Aij*printf( *n)printf( *n)printf( *printf( *1- 查 看 系 统 中 的 城 市 代 号2- 一 个 城 市 到 所 有 城 市 的 最 短 路 径3- 任 意 的 两 个 城 市 之 间 的 最 短 路 径0- 退 出*n)printf(n)printf( 请选择：IIscanf(%d,&z) 。while(z!
6、=0)switch(z)case 1:printf(0州,4 南京,5 厦门 n) 。北京 ,1 天津 ,2 上海 ,3 广printf(n) 。main() 。scanf(%d,&z) 。break 。case 2:printf( 请输入城市代号 :)scanf(%d,&x) 。switch(x)case 0:printf(以下 是最 短路径 ：n) 。 Dijkstra(g,x)break 。case 1:printf(以下是最短路径：n) 。 Dijkstra(g,x)break 。case 2:printf(以下是最短路径：n) 。 Dijkstra(g,x)break 。case 3
7、:printf(以下是最短路径：n) 。 Dijkstra(g,x)break 。case 4:printf(以下是最短路径：n) 。 Dijkstra(g,x)break 。case 5:printf(以下是最短路径：n) 。 Dijkstra(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 。ca
8、se 0:exit(-1)break 。default:printf( 输入有误，请重新输入 n) printf(n)main()3.2.2 狄克斯特拉函数初始化距离和路径，将 s 置为空。将远点编号 v 放入 s 中, 循环直到所有顶 点的最短路径都求出，将 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 。 ig.n
9、。 i+) disti=g.edgesvi。si=0。if(g.edgesviINF) pathi=v 。else pathi=-1 。sv=1pathv=0for(i=0ig.n 。 i+)mindis=INFfor(j=0jg.n 。 j+)if(sj=0&distjmindis)u=jmindis=distjsu=1 。for(j=0 。 jvg .n 。 j+) if(sj=0)if(g.edgesujINF&distu+g.edgesujdistj) distj=distu+g.edgesuj。pathj=u 。Dispath(dist,path,s,g.n,v) 。3.2.3 Pp
10、ath 函数前向递归查找路径上的顶点，找到起点则返回，找顶点 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 函数有 path 函数计算最短路径，搜索最短路径的所有边，输出路径上的起点，输出路径上的中间点，输出路径上的终点。void Dispath(int dist,int path,int s,int n,int v)int ifor（i=0 。 in 。 i+）if（si=1&disti!=I
11、NF）printf（ 从 %d 到 %d 的 最 短 路 径 长 度 为 ： %dt 路 径 为 ： ,v,i,disti） 。printf（%d,v）。Ppath（path,i,v）。printf（%dn,i） 。else printf（从%dij%d不存在路径 n,v,i）。3.2.5 弗洛伊德函数设置路径长度 A和路径path初值。做k次迭代，每次均试图将顶点K扩充到点钱球得的从 i 到 j 的最短路径 Pij 上，修开路径长度，输出最短路径。 void Floyd（MGraph g） int pathMAXVMAXV,AMAXVMAXV 。int i,j,k 。for（i=0 。 ig
12、.n 。 i+）for（j=0 。 jg.n 。 j+）Aij=g.edgesij。pathij=-1。for（k=0 。 kg.n 。 k+） for（i=0。 ig.n 。 i+）for（j=0。 jAik+Akj） Aij=Aik+Akj。pathij=k 。3.2.6 Ppath2 函数向前递归查找路径上的顶点，找到了起点则返回，找顶点 i 的前一个顶点 k，找顶点k的前一个顶点j。在path中递归输出从顶点i到顶点j的最短路径 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) 。3.2.7 DisPath2 函数由 path 计算最短路径，若顶点 i 和顶点 j 之间没有边，则输出 i 到 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(从%dU%4没有路径 n,i,j)。elseprintf(从(到 醐径
