《数据结构课程设计-城市交通咨询系统》由会员分享，可在线阅读，更多相关《数据结构课程设计-城市交通咨询系统（19页珍藏版）》请在金锄头文库上搜索。
1、榆 林 学 院数据结构课程设计报告题题 目目 城市交通咨询系统城市交通咨询系统 作作 者者 杨朝杨朝 专专 业业 信息管理与信息系统信息管理与信息系统 学学 号号 15142101211514210121 指导老师指导老师 张慧张慧 答辩时间答辩时间 2016.12.182016.12.18 数据结构课程设计报告1目录目录目录1 11 系统需求分析21.1用户需求分析21.2 功能需求分析31.3 数据需求分析31.4 小结32 系统设计42.1 系统设计思路42.2 系统设计功能42.3 每个模块的具体能52.4 主函数的调用关图103 系统测试113.1 操作说明113.2 测试数据113
2、.2.1 用户进入界面113.2.2 具体功能的实现123.2.3 选择 0 结束程序144 总结145 致谢146 6 附录附录1515课程设计题目21.系统需求分析描述：描述：现如今网络非常发达，无论人们出差，旅游或者做其他的出行之时，都会想到道路问题，切不仅仅关心的是交通费用，而且对于里程和所需要的时间等的问题也是同样的关心，在此系统中，完全面向用户，可以用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。且在图中，顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能够让旅客咨询从任一城市顶点到达另外一个城市之间顶点的最短路径问题（最短里程问题） 。对系统分析，主
3、要从以下几个方面进行分析。1.用户需求分析用户需求分析2.功能需求分析功能需求分析3.数据需求分析数据需求分析1.1 用户需求分析现如今网络非常发达，无论人们出差，旅游或者做其他的出行之时，都会想到道路问题，切不仅仅关心的是交通费用，而且对于里程和所需要的时间等的问题也是同样的关心，在此系统中，完全面向用户，可以用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。且在图中，顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能够让旅客咨询从任一城市顶点到达另外一个城市之间顶点的最短路径问题（最短里程问题） 。当要查询某两个城市之间的最短交通路线或者其中一个城市到达其余城市
4、的最 短路线时，是一个很繁琐的过程。根据用户自己的需求，可以自定义地图，此程序就是主要以满足用户自己 的环境与实际情况，在难以计算路程时，可将地图输入进行计算，系统将会为 用户提供所用路径最短的出现路线，更好的满足用户需求。以下是针对咨询用 户说明其最基本的模块功能。（1） 进入程序后，用户可自己设置城市的个数，以及所有城市之间总共 的路径，且分别用顶点和边表示城市与路径（2） 用户根据自己设置的城市个数和路径数，具体输入每个路径的起始点以及每条路径的长度。数据结构课程设计报告3（3）进入菜单选择界面 （4）选择 2，系统为用户进行提供任意城市的交通查询,即查询任意两个 城市之间的一条最短路径
5、。 （5）选择 1，系统为用户提供指定城市的交通查询，即查询指定城市到其 他城市之间的最短路径。如若输入顶点超出范围显示错误，系统回到菜单重新 选择 （6）选择 0，系统推出程序。1.2 功能需求分析城市交通咨询系统总体的设计目标：用数据结构中的邻接矩阵作数据结构，并结 合数据结构有向图的最短路径计算方法，结合相应的数据算法以及 c 语言的相关知识，编 写一个良好的，具有可操作性的，以及能方便用户的使用，包括自定义地图，路径与城市 个数可结合实际情况而言，相对操作，简便易懂并无难度。系统在菜单可根据命令进行相 应的操作，已满足用户的需求。 1.2.1 城市交通系统基本功能 根据以上分析，此系统
6、具备以下功能： （1）用户进入后的地图创建界面（明确地图中城市的个数以及路径的个数）（2）地图完善界面（用户自己输入地图中相关路径的起始点以及路径长度）（3）菜单界面包含两条命令 （4）命令 1 求一个城市到所有城市的最短距离 （5）命令 2 求任意的两个城市之间的最短距离 （6）回复命令 0 可推出程序。1.3 数据需求分析用邻接矩阵建立交通网络模块 VertexType vexsMVNum;/顶点数组，类型假定为 char Adjmatrix arcsMVNumMVNum;/邻接矩阵，类型假定为 int 型 建立邻接矩阵，用函数 void CreateMGraph(MGraph * G,i
7、nt n,int e) / 采用邻接矩阵表示法构造有向图 G，n、e 表示图的当前顶点数和边 数 用迪杰斯特拉算法计算某顶点到其余顶点的最短路径 用函数 void Dijkstra (MGraph * G,int n,int e) 来定义此函数 采用邻接矩阵表示法构造有向图 G，n、e 表示图的当前顶点数和边数 用弗洛伊德算法求任意一对顶点的最短路径用函数 void Floyd(MGraph *G,int n) 来定义。利用费洛伊德算法， 求出最短路径。课程设计题目41.4 小结 从各种需求方面下手改编代码，并不断调试，让界面更加友好。不断地 尝试上，在各种问题上不断突破，慢慢的完善代码，等最
8、大限度的满足用户需 求。这几天短时间的课程设计也让我认识到了自己在这门课程上还面临着许许 多多的问题，为以后的具体实践明确了努力方向。同时，城市交通咨询系统的 实现，为用户更好的解决了再实际出行时遇到的路径问题，最初的设计也为代 码敲定了编写方向。再三考虑后确定了系统的功能，确定什么功能有实现必要， 什么功能可有可无。在这样的基础之下使得思路更加清晰。2.系统设计2.1系统设计思路本程序首先是用户编辑界面，用户根据自己的需求编写地图，从 而加入顶点的数组之中，创建的地图用邻接矩阵存储，在从主函数之中 进行调用，实现对两个算法的调用。 用户在输入顶点以及边的信息都会存储，在存储成功之后会提示 用
9、户存储成功，之后进入到菜单界面，菜单界面提供两种选择口令，分 别可以调运 Dijkstra 和 Floyd 算法，调用之后输入相应的口令以及要查 询的城市编号，算法会根据邻接矩阵存储的地图进行计算，求出最短路 径。 在以后使用完系统后，可输入口令 0，系统会结束一切运算，退 出程序。2.2 系统设计功能菜单界面的主要功能有两个: （1） 、求一个城市到所有城市的最短距离 （2） 、求任意的两个城市之间的最短距离 城市交通咨询系统主要有三个模块 分别为： （1） 、邻接矩阵的输入与存储构建交通网络 （2） 、任意两个城市的最短距离查询 （3） 、两个指定城市的最短距离查询 主界面的模块概念图如下
10、：数据结构课程设计报告5任意两个城市的最短距离查询两个指定城市的 最短距离查询图 2.12.3每个模块的具体功能。（1） 、采用 C 语言定义相关数据类型1定义一个，用来存储顶点信息。typedef struct VertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph; 2定义一个 Dijkstra 函数void Dijkstra(MGraph *G,int v,int n);3定义一个 Floyd 函数用户进入系统交通网络构建结果，退出系统课程设计题目6void Floyd(MGraph *G,int n);（2） 、建立邻接矩阵交通网络：Y图 2.2邻
11、接矩阵构造图结构函数数据类型定义：typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;void CreateMGraph(MGraph *G,int n,int e)/邻接矩阵构成有向图 int i,j,k,w;开始输入顶点和边数 n,e输入 i,j,wkvexsi=(char)i;for(i=1;iarcsij=IDF;printf(“输入%d 条边的 i,j 及 w: n“,e);for(k=1;karcsij=w;printf(“有向图的存储结构建立完毕!n“);其中 vexsMAX保存顶点信息，arcsMAXMAX用
12、于保存边与边之 间的信息。在构建时通过输入的边数 i，j 作为矩阵的行、列确定顶点的出 度和入度。用邻接矩阵方法存储图。（3） 、查询指定城市到其他城市自己建的最短路程：图 2.3应用狄克斯特拉算法来具体实现这一步的需求。开始输入顶点 v狄克斯特拉算法输出路径,距离结束课程设计题目8基本思想：设 G（V,E）是一个带权有向图，把图中的顶点集合 V 分成 两组，第一组为已经求出的最短路径的顶点集合（用 S 表示，初始时 S 中只有 一个原点，以后每求得一条最短路径就加入的集合 S 中，知道全部顶点都加入 到集合中） ，第二组，为其余未确定最短路径的顶点集合（用 U 表示） ，按最短 路径长度的递
13、增次序依次把第二组的顶点就如 S 中。如果两个顶点之间有权值， 并且各个路径的权值不同，就把最小的作为顶点与顶点的最短距离。yx z图 2.4如图所示 若 x+yk=u。同理若 x+yu，D v1=0;Sv1=1; /原点编号放入 s 中for(i=2;iarcsvwarcsvw;P w=v;（4） 、查询任意两个城市之间的一条最短路径：kvu数据结构课程设计报告9图 2.5此过程需要应用弗洛伊德算法来具体实现。用邻接矩阵保存图存储后，另外需要存一个二维数组 A 存放当前顶点之间的最短路径长度。分量 Aij表示当前顶点 i 到 j 的最短路径长度。弗洛伊德算法的基本思维是递推产生一个矩阵序列 A0，A1，A2，.Ak， An，其中 Akij表示从顶点到 vi 到顶点 vj 的路径上所经过的顶点编号不大于 k 的最短路径长度。Aij=costijA(k+1)ij=minAkij,Aki+1k+1+Akk+1j开始输入起点 v， 终点 w调用弗洛伊德 算法输出路径,距离结束课程设计题目10弗洛伊德主要算法，若 Akij已求出，顶点 i 到顶点 k+1 的路径长度为Akik+1，顶点路径长度为 Akij，顶点 k+1 到顶点 j 的路径长度为 Akk+1j，如果此时 Akik+1+Akk+1j1 长度=0
