数据结构课程实践报告城市道路交通.docVIP

哈尔滨理工大学管理学院 数据结构课程设计 实验题目：交通咨询系统设计 学 院： 专 业： 信息管理与信息系统 班 级： 11-2班 姓 名： 学 号： 完成时间：2013年6月28日 指导老师：  数据结构实验项目任务书 实验题目 交通咨询系统设计 学院 管理学院 专业 信管专业 年级 11-2班 任务描述： 综合运用C++编程技术和Dijkstra算法和Floyd算法，设计实现最后提交完整的设计报告和软件程序拷贝。 《课程设计实验教材 》 《数据结构（ C 语言版）》，严蔚敏，吴伟民编著，清华大学出版社，2007年第1版 任务下达日期 2013 年6 月 24 日 完成日期2013年 6 月 28日  目 录 第一章：问题描述 4 第二章：算法设计 4 2.1算法设计分析 4 2.2模块图 4 2.2.2迪杰斯特拉算法 5 2.2.3费洛伊德算法 5 三． 关键代码描述 6 3.1完整的程序代码 6 3.2代码改写 9 四、运行结果截图展示 14 五、实验心得 15  第一章：问题描述 在交通网络发达，交通工具和交通方式不断更新的今天，人们在出差，旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题更感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，并利用计算机建立一个交通咨询系统。 设计实现一个简单的城市之间最短路径管理咨询系统，能够模拟实现以下功能： 1.帮助旅行者了解从一个城市到另一个城市之间的最短路径。 2.用户可以根据需要指定一个源点，软件需计算出该源点到其他剩余节点之间的最短距离和详细路径。 3.用户可以直接查看所有城市之间的最短距离。 第二章：算法设计 2.1算法设计分析 该设计共分三个部分：一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现两个城市顶点之间的最短路径问题。 其中，单源最短路径，需要用到迪杰斯特拉（Dijkstra）算法（即迪杰斯特拉提出按路径长度递增产生各定点的最短路径算法）。 任意一对顶点间的最短路径，可以依次把有向网络图中的每个顶点作为源点，重复执行前面讨论过的迪杰斯特拉算法n次，即可求得每对之间的最短路径。这里用另一种算法，费洛依德（Floyd）算法求得。 2.2模块图 2.2.1功能的实现 2.2.2迪杰斯特拉算法 2.2.3费洛伊德算法 关键代码描述 3.1完整的程序代码 //主控程序 #includestdio.h #includestdlib.h #define MVNum 100 //最大顶点数 #define Maxint 32767 typedef char VertexType; typedef int Adjmatrix; typedef enum {FALSE,TRUE} boolean; //定义布尔型 typedef struct{ VertexType vexs[MVNum]; //顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵，假定为int型 }MGraph; int Dl[MVNum],P1[MVNum]; int D[MVNum][MVNum],P[MVNum][MVNum]; #includesave.c #includedijkstra.c #includefloyd.c void main( ) { MGraph G; int n,e,v,w,k; int xz=1; printf(输入图中顶点个数和边数n,e: ); scanf(%d,%d,n,e); CreateMGraph(G,n,e); //建立图的存储结构 while (xz!=0){ printf(******求城市之间的最短路径******\n); printf(=================================\n); printf(1.求一个城市到所有城市的最短路径\n); printf(2.求任意的两个城市之间的最短路径\n); printf( 0.退出程序 \n); printf(==================================\n);