数据结构课程设计--交通咨询系统设计

信息科学与工程学院课程设计任务书题 目：交通咨询系统设计学 号：姓 名：年 级：专 业：计算机应用与技术课 程：数据结构指导教师：职 称：完成时间：课程设计任务书及成绩评定课程设计的任务和具体要求设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短 路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程 或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三 是实现任两个城市顶点之间的最短路径问题。指导教师签字： 日期：指导教师评语:成绩： 指导教师签字： 日期：课程设计所需软件、硬件等PC兼容机、Windows操作系统、Turbo C/Win t、Vc+软件等。课程设计进度计划起止日期工作内容备注参考文献、资料索引（序号、文献名称、编著者、出版单位）数据结构（C语言版）编著严蔚敏吴伟民清华大学出版社1997数据结构中国石油大学出版社一、需求分析 设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之 间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可 输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路 径问题；三是实现任两个城市顶点之间的最短路径问题。1.1.1建立图的存储结构 邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下 的n阶方阵：设G二（V, E）是一个图，结点集为V二匕,v2，V”L（w ）,当（v ,v ） 或 < v ,v >G EG 的邻接矩阵 A = （a ） , a = < Jj nxn1 jz' j ,ij nxn可 |0或, 当（v , v ）或 < v , v >Eijij当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。 图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接 矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下 标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#defi nf MVNum 50 /最大顶点数typedef structVertexType vexsMVNum;/顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum;/邻接矩阵，假定为 int 型MGraph;1.1.2单源最短路径 最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带 权），我们希望找出从某个源点Se V到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终 点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉D ijkstra ）提 出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G二（V，E）是一个有向图，结点集为，V二v ,v , .,v , cost是表示G的邻接矩阵，costij表示有向1 2 n边i,j的权。若不存在有向边i,j,则costij的权为无穷大（这里取值 为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶 点的最短距离已经求出。设顶点v为源点，集合S的初态只包含一个元素，即1顶点v。数组dist记录从源点到其他顶点当前的最短距离，其初值为1disti=costv i,i=1,2,n。从S之外的顶点集合V-S中选出一顶点1w,使distw的值最小。于是从源点到达w只通过S中顶点，把w加入集合S 中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv 和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到 V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist 记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组， 其中path订表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D，置空最短路径终点集，置初始的最短路径值；Sv =TRUE; Dv=0；/S集初始时只有源点,源点到源点的距离为0；1 1While （S集中顶点数n）开始循环，每次求得v到某个v顶点的最短路径，并加v到S集中；1Sv二TRUE；更新当前最短路径及距离；1.1.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G二（V，E），要对 G中任意一对顶点有序对“v,w（v丰w） ” ,找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执 行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点v到v的最短路ij径。如果从v到v存在一条长度为arcsij的路径，该路径不一定是最短路 ij径，还需要进行n次试探。首先考虑路径v,v和v,v是否存在。如果存在，i 11 j则比较v,v和 v,v,v 的路径长度，取长度较短者为当前所求得的最短路i ji 1 j径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从v到v是否包 ij含有顶点v为中间顶点的路径v,v,v，若没有，则说明从v到v的当2i2ji j前最短路径就是前一步求出的；若有，那么V,V,V可分解为V,vi2ji2和v ,v ,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径， 2j将这两条路径长度相加就得到路径v ,V ,V 的长度。将该长度与前一次 i2j中求出的从V到V的中间顶点序号不大于1的最短路径比较，取其长度较短者 ij作为当前求得的从V到V的中间顶点序号不大于2的最短路径。依此类推，直 ij到顶点V加入当前从V到V的最短路径后，选出从V到V的中间顶点序号不大ni ji j于n的最短路径为止。由于图G中顶点序号不大于n，所以V到V的中间顶点序 ij号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是V到V的最短路径。ij1.2 程序流程图二、详细设计2.1建立有向图的存储结构 void CreateMGraph(MGraph * G, int n, int e)int i,j,k,w;for (i=1;i<=n;i+)G->vexsi = (char)i;for (i=1;i<=n;i+)for (j=1;j<=n;j+)G->arcsij=Max int;pri ntf("输入%d 条边的 i,j 及 w:n",e);for (k=1;k<=e;k+)scanf("%d,%d,%d", & i, &j, &w);G->arcsij=w;pri ntf("有向图建立完毕n");2.2迪杰斯特拉算法void Dijkstra(MGraph *G,int v1,int n) int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum; for(v=1;v<=n;v+)Sv=FALSE; D2v=G->arcsv1v; if(D2v<Maxint)P2v=v1;elseP2v=0;D2v1=0;Sv1=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=1;w<=n;w+) if(!Sw&&D2w<min) v=w;min=D2w;Sv=TRUE;for(w=1;w<=n;w+)if(!Sw&&(D2v+G->arcsvw<D2w) D2w=D2v+G->arcsvw;P2w=v;pri ntf("路径长度路径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");2.3 费洛伊德算法void Floyd(MGraph *G,int n) int i,j,k,v,w;for(i=1;i<=n;i+)for(j=1;j<=n;j+) if(G->arcsij!=Maxint)Pij=j;elsePij=0;Dij=G->arcsij;for(k=1;k<=n;k+)for(i=1;i<=n;i+)for(j=1;j<=n;j+) if(Dik+Dkj<Dij)Dij=Dik+Dkj; Pij=Pik;2.4 运行主控程序void main() MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);pri ntf ("输入图中顶点个数和边数n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while (xz!=0) pri ntf("*求城市间的最短路径*、n");printf("1.求一城市到所有城市的最短路径n"); printf(“2.求任意的两个城市之间的最短路径n"); printf(" 请选择：1 或 2,选择 0 退出:"); scanf("%d",&xz);if(xz=2)Floyd(G,n);pri ntf("输入起点和终点:v,w:"); scanf("%d,%d",&v,&w);k=Pvw;if(k=0)printf("顶点 %d 到 %d 无路径!n",v,w);else pri ntf("从顶点%d到%4的最短路径是:%d",v,w,v); while(k!=w)pri ntf("T2 %d",k); k=Pkw;pri ntf("T2 %d",w);pri ntf("路径长度:%dn",Dvw);else if(xz=1)pri ntf("求单源路径，输入源点v :"); scanf("%d",&v);Dijkstra(G,v,n);pri ntf("结束求最短路径")；三、调试分析