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

信息科学与工程学院 课 程 设 计 任 务 书 题 目： 交通咨询系统设计 学 号： 201112220141 姓 名： 年 级： 专 业： 计算机应用与技术 课 程： 数据结构 指导教师： 职 称： 完成时间：  课程设计任务书及成绩评定 课程设计的任务和具体要求 设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。 本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。 指导教师签字： 日期： 指导教师评语： 成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等 PC兼容机、Windows操作系统、Turbo C/Win t、Vc++软件等。 课 程 设 计 进 度 计 划 起止日期 工作内容 备注 参考文献、资料索引（序号、文献名称、编著者、出版单位） 数据结构（C语言版） 编著 严蔚敏 吴伟民 清华大学出版社 1997 数据结构 中国石油大学出版社 一、需求分析 设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。 本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。 1.1.1建立图的存储结构 邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵： 设G=（V，E）是一个图，结点集为。 G的邻接矩阵 当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。 图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下： #definf MVNum 50 //最大顶点数 typedef struct { VertexType vexs[MVNum]; //顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵，假定为int型 }MGraph; 1.1.2 单源最短路径 最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到G中其余各顶点的最短路径。 为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。 迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，，cost是表示G的邻接矩阵，cost[i][j]表示有向边i,j的权。若不存在有向边i,j，则cost[i][j]的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为dist[i]=cost[v1][i],i=1,2,……,n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到V-S为空。 最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。 因此，迪杰斯特拉算法可用自然语言描述