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

1、信息科学与工程学院课程设计任务书题 目：交通咨询系统设计学 号:201112220141姓 名：年 级：专 业：计算机应用与技术课 程：数据结构指导教师：职 称：完成时间：课程设计任务书及成绩评定课程设计的任务和具体要求设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短 路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程 或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。指导教师签字： 日期： 指导教师评语:成绩：指导教师签字：日期： 课程设计所需软件、硬

2、件等PC 兼容机、Windows操作系统、Turbo C/Win t、Vc+啾件等。课程设计进度计划起止日期工作内容备注参考文献、资料索引（序号、文献名称、编著者、出版单位）数据结构（C语言版）编著 严蔚敏 吴伟民清华大学出版社1997数据结构中国石油大学出版社一、需求分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之 间的最短路径(里程)或最低花费或最少时间等问题。对于不同的咨询要求，可 输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路 径问题；三是实现任两个城市顶点之间的最短路径问题。1.1.1 建立图的存储结构邻

3、接矩阵是表示图形中顶点之间相邻关系的矩阵。 图的邻接矩阵是定义如下 的n阶方阵：设6= (V, E)是一个图，结点集为V =*,，vnLG的邻接矩阵A = (aj)n aj =(Wij)nM，当(Vi,vjvj)或：二vi ,vj不三E 或:Vi ,Vj - E E当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接 矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下 标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 / 最大顶点数typed

4、ef structVertexType vexsMVNum; /顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为 int 型MGraph;1.1.2 单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终 点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉( Dijkstra )提 出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=

5、(V, E)是一个有向图，结点集为，V =v 1，V2,，Vn , cost是表示G的邻接矩阵，costij表示有向边川 的权。若不存在有向边i,j ,则cost皿的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶 点的最短距离已经求出。设顶点vi为源点，集合S的初态只包含一个元素，即顶点vi。数组dist记录从源点到其他顶点当前的最短距离，其初值为 disti=costv ii,i=1,2,n。从S之外的顶点集合V-S中选出一个顶点w,使distw的值最小。于是从源点到达 w只通过S中顶点，把w加入集合S 中，调整dist中记录的从源点到 V-S

6、中每个顶点v的距离：从原来的distv 和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组， 其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值； Svi=TRUE; Dvi=0; /S集初始时只有源点，源点到源点的距离为0;While （S集中顶点数n） 开始循环，每次求得vi到某个v顶点的最短路径，并加v到S集中

7、； Sv=TRUE;更新当前最短路径及距离； 1.1.3 任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V, E）,要对G中任意一对顶点有序对“ v,w（v #w），找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法 n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd ）算法算法的基本思想是：假设求从顶点v i到vj的最短路径。如果从vi 到 vj 存在一条长度为arcsij 的路径，该路径不一定是最短路径，还需要进行n次试探。首先

8、考虑路径,丫1和丫上是否存在。如果存在， 则比较 切,丫）和 Vi,Vi,Vj 的路径长度，取长度较短者为当前所求得的最短路 径。该路径是中间顶点序号不大于1 的最短路径。其次，考虑从vi 到vj 是否包含有顶点V2为中间顶点的路径Vi,V2,Vj,若没有，则说明从Vi到Vj的当 前最短路径就是前一步求出的；若有，那么Vi,，丫?,，丫上可分解为Vi,丫?和V2,V j,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径 Vi,V 2,V j的长度。将该长度与前一次 中求出的从Vi 到 Vj 的中间顶点序号不大于1 的最短路径比较，取其长度较短者作为当前求

9、得的从Vi 到 Vj 的中间顶点序号不大于2 的最短路径。依此类推，直到顶点Vn加入当前从V到Vj的最短路径后，选出从Vi到Vj的中间顶点序号不大于 n 的最短路径为止。由于图G 中顶点序号不大于n， 所以Vi 到 Vj 的中间顶点序号不大于n 的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此， 它就是 Vi 到 Vj 的最短路径。1.2 程序流程图5 / 22输入在城巾 项点信息9 / 22、详细设计2.1 建立有向图的存储结构void CreateMGraph(MGraph * G, int n, int e)int i,j,k,w；for (i=1;ivexsi=( char)i;

10、for (i=1;i=n;i+)for (j=1；jarcsij=Maxint;printf(输入舔边的 i,j 及 w:n ,e);for (k=1;karcsij=w;printf( 有向图建立完毕n );2.2 迪杰斯特拉算法void Dijkstra(MGraph *G, int v1, int n)int D2MVNum,P2MVNum;int v,i,w,min;enumboolean SMVNum;for (v=1;varcsv1v;if (D2vMaxint)P2v=v1;elseP2v=0;D2v1=0;Sv1=TRUE;for (i=2;in;i+)min=Maxint;f

11、or (w=1;w=n;w+)if (!Sw&D2wmin)v=w;min=D2w;Sv=TRUE;for (w=1;warcsvwarcsvw;P2w=v;printf( 路径长度路径 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;jarcsij!=Maxint)Pij=j;elseP

12、ij=0;Dij=G-arcsij;for (k=1;k=n;k+)for (i=1;i=n;i+)for (j=1;j=n;j+)if (Dik+DkjDij)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);printf( 输入图中顶点个数和边数n,e: );scanf( %d,%d,&n,&e);CreateMGraph(G,n,e);while (xz!=0) printf( * 求城市间的最短路径*n );pr

13、intf( 1. 求一个城市到所有城市的最短路径n );printf( “ 2. 求任意的两个城市之间的最短路径n );printf( 请选择：1 或 2, 选择 0 退出 : );scanf( %d,&xz);11 / 22if (xz=2)Floyd(G,n);printf( 输入起点和终点:v,w: );scanf( %d,%d,&v,&w);k=Pvw;if (k=0)printf( 顶点 %d 到 %d 无路径 !n ,v,w);else printf(从顶点到的最短路径是：:%d ,v,w,v);while (k!=w)printf(、 2 %d,k);k=Pkw;printf(

14、、 2 %d：w);printf( 路径长度:%dn ,Dvw);else if (xz=1)printf( 求单源路径，输入源点v : );scanf( %d,&v);Dijkstra(G,v,n);printf( 结束求最短路径);三、调试分析编译：在第一次编译时出现了很多错误，是因为我对C语言的不熟练，比如 调用费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是 for 语句的运用，由于本次程序要用很多 for循环，我把一次for循环放到了上面 for循环中，导致程序不能正确输出结果。最后把调到外面才 OK四、测试结果交通咨询系统通过迪杰斯特拉算法得出每一个城市到所有城市的最

15、短路径，然后通过费洛伊德算法得出任意两个城市间最短路径。本程序的运行环境为DOSS作系统，执行文件为 交通咨询.exe。进入程序后，即显示文本的操作界面：输入定点数和边数后，依次输入有向边，以及两点间的距离，用逗号间隔开, 回车换行，当有向图输入完全时，进入菜单J Ch41OT224!iij)iurin1exe,;建贽蟹歌邂 请园单：1或2,选择。：退出：选择你要进行的模式，求一个城市到所有城市的最短路径输入1,回车进入该模式，输入你所要求的城市代表的顶点数，回车确认。求任意的两个城市之间的最短路径输入 2,回车确认进入该模式，输入两座 城市代表的顶点数，以逗号间隔开，回车确认。运行结果：下面

16、是城市交通图23 / 22求城市之间的最断路径 D:4100 2 24li uliulir.exe3-14-15-2-3-16-3234一7 路径长度;加23Z D:41002 24l I u1iu1ip.exe227413557-42-3-4-7 求域市之间的冕断路径路径长度:23231 患 日譬取 市间 城之 有市 襄 到个 市两 替 窜 -任 1151 ?:鼎 耕源长 主0 U 举 避点起 2.1A 或溟r出 展 、X35112-33494-313235-2-315796y10 呢7-4-3求城市之间的最断路径12 3-64-3-65-67-6、 、-=F路径长度SUF D:410022

17、4liuliulin.eMe城市到所有城市的曩二豆筋卷淄两个城市芝间的最短啕至请选I制1噩2,选择由：退出:跣噫黜翻蠡A市间 城之 有市 到个 需 翳 J 一任 jKR 5,中，i 生F.仃 VB-ot 后=唱一 t请箕择：工削2,选择V ：退出:1 求单源躇径，输入起点u ：6 蛤径长置路径2274209015791928236H B13R5旦i五、附录#include#include#define MVNum 100/最大顶点数#define Maxint 35000enum booleanFALSE,TRUE;typedef char Vertextype;typedef int Adj

18、matrix;typedef structVertextype vexsMVNum; / 顶点数组，类型假定为char型Adjmatrix arcsMVNum MVNum; / 邻接矩阵， 假定为 int 型 MGraph;int D1MVNum, p1MVNum;int DMVNumMVNum,pMVNumMVNum;/文件名save.cvoid CreateMGraph(MGraph *G,int n,int e) / 采用邻接矩阵表示法构造有向图G,n,e 表示图的当前顶点数和边数int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(

19、j=1;jarcsij=Maxint; /初始化邻接矩阵printf (输入 豚边的 i,j 及 w: n,e);for(k=1;karcsij=w;printf ( 有向图的存储结构建立完毕！n);/ 文件名 :dijkstra.c( 迪杰斯特拉算法)void Dijkstra(MGraph *G, int v1,int n) /用Dijkstra 算法求有向图G的v1顶点到其他顶点v的最短路径pv及其权 Dv/设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint/Sv为真当且仅当v属于S,及以求的从v1到v的最短路径int D2MVNum, p2MVNum;int v,i,w,min

20、;enum boolean SMVNum;for(v=1;varcsv1v; / 置初始的最短路径值if(D2v Maxint)p2v=v1;/v1是的前趋（双亲）elsep2v=0;/v 无前趋 / End_forD2v1=0;Sv1=TRUE; /S 集初始时只有源点，源点到源点的距离为0/开始循环，每次求的V1到某个V顶点的最短路径，并加V到S集中 for(i=2;in;i+) / 其余 n-1 个顶点min=Maxint; / 当前所知离v1顶点的最近距离，设初值为00 for(w=1;w=n;w+) / 对所有顶点检查if(!Sw & D2wmin) / 找离v1最近的顶点w,并将其

21、赋给v,距离赋给min v=w; / 在S集之外的离v1最近的顶点序号 min=D2w; / 最近的距离/W顶点距离V1 顶点更近Sv=TRUE; / 将 v 并入 S集 for(w=1;warcsvwarcsvw; / 更新 D2w p2w=v; /End_if /End_forprintf ( 路径长度路径 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( 费洛伊德算法) void Floyd(MGraph *G, int n) int i, j, k;for(i=1;i=n;i+) /设置路径长度D和路径path初值for(j=1;jarcsij!=Maxint) pij=j; /j是 i 的后继elsepij=0;Dij=G-arcsij;f