数据结构课程设计—城市道路交通咨询系统

《数据结构课程设计—城市道路交通咨询系统》由会员分享，可在线阅读，更多相关《数据结构课程设计—城市道路交通咨询系统（21页珍藏版）》请在金锄头文库上搜索。

1、榆 林 学 院数据结构课程设计报告题题 目目 城市交通咨询系统城市交通咨询系统 作作 者者 杨朝杨朝 专专 业业 信息管理与信息系统信息管理与信息系统 学学 号号 15142101211514210121 指导老师指导老师 张慧张慧 答辩时间答辩时间 2016.12.182016.12.18 目录1.系统需求分析 .1 1.1 用户需求分析.1 1.2 功能需求分析.2 1.3 数据需求分析.2 1.4 小结 3 2.系统设计3 2.1 系统设计功能.3 2.2 每个模块的具体功能。.4 2.2.1 采用 C 语言定义相关数据类型 .4 2.2.2 建立邻接矩阵交通网络： .4 2.2.3 查

2、询指定城市到其他城市自己建的最短路程： .6 2.2.4 查询任意两个城市之间的一条最短路径： .7 2.3 主函数的调用关系图.8 3.系统测试9 3.1 操作说明.9 3.2 测试数据10 3.2.1 用户进入界面： 10 3.2.2、具体功能的实现.11 3.2.3、结束程序.12 4.总结.13 5.致谢.13 6.附录.14数据结构课程设计11.系统需求分析现如今网络非常发达，无论人们出差，旅游或者做其他的出行之时，都会想到道路问题，切不仅仅关心的是交通费用，而且对于里程和所需要的时间等的问题也是同样的关心，在此系统中，完全面向用户，可以用一个图结构来表示交通网络系统，利用计算机建立

3、一个交通咨询系统。且在图中，顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能够让旅客咨询从任一城市顶点到达另外一个城市之间顶点的最短路径问题（最短里程问题） 。对系统分析，主要从以下几个方面进行分析。1.用户需求分析2.功能需求分析3.数据需求分析1.1 用户需求分析现如今网络非常发达，无论人们出差，旅游或者做其他的出行之时，都会想到道路问题，切不仅仅关心的是交通费用，而且对于里程和所需要的时间等的问题也是同样的关心，在此系统中，完全面向用户，可以用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。且在图中，顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系

4、统，能够让旅客咨询从任一城市顶点到达另外一个城市之间顶点的最短路径问题（最短里程问题） 。当要查询某两个城市之间的最短交通路线或者其中一个城市到达其余城市的最短路线时，是一个很繁琐的过程。根据用户自己的需求，可以自定义地图，此程序就是主要以满足用户自己的环境与实际情况，在难以计算路程时，可将地图输入进行计算，系统将会为用户提供所用路径最短的出现路线，更好的满足用户需求。以下是针对咨询用户说明其最基本的模块功能。（1） 进入程序后，用户可自己设置城市的个数，以及所有城市之间总共的路径，且分别用顶点和边表示城市与路径（2） 用户根据自己设置的城市个数和路径数，具体输入每个路径的起始点以及每条路径的

5、长度。（3）进入菜单选择界面（4）选择 2，系统为用户进行提供任意城市的交通查询,即查询任意两个城市交通咨询系统2城市之间的一条最短路径。（5）选择 1，系统为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路径。如若输入顶点超出范围显示错误，系统回到菜单重新选择（6）选择 0，系统推出程序。1.2 功能需求分析城市交通咨询系统总体的设计目标：用数据结构中的邻接矩阵作数据结构，并结合数据结构有向图的最短路径计算方法，结合相应的数据算法以及c 语言的相关知识，编写一个良好的，具有可操作性的，以及能方便用户的使用，包括自定义地图，路径与城市个数可结合实际情况而言，相对操作，简便易懂并

6、无难度。系统在菜单可根据命令进行相应的操作，已满足用户的需求。城市交通系统基本功能根据以上分析，此系统具备以下功能：（1）用户进入后的地图创建界面（明确地图中城市的个数以及路径的个数）（2）地图完善界面（用户自己输入地图中相关路径的起始点以及路径长度）（3）菜单界面包含两条命令（4）命令 1 求一个城市到所有城市的最短距离（5）命令 2 求任意的两个城市之间的最短距离（6）回复命令 0 可推出程序。1.3 数据需求分析用邻接矩阵建立交通网络模块VertexType vexsMVNum;/顶点数组，类型假定为 char Adjmatrix arcsMVNumMVNum;/邻接矩阵，类型假定为 i

7、nt 型建立邻接矩阵，用函数 void CreateMGraph(MGraph * G,int n,int e) /采用邻接矩阵表示法构造有向图 G，n、e 表示图的当前顶点数和边数用迪杰斯特拉算法计算某顶点到其余顶点的最短路径用函数 void Dijkstra (MGraph * G,int n,int e) 来定义此函数采用邻接矩阵表示法构造有向图 G，n、e 表示图的当前顶点数和边数用弗洛伊德算法求任意一对顶点的最短路径数据结构课程设计3用函数 void Floyd(MGraph *G,int n) 来定义。利用费洛伊德算法，求出最短路径。1.4 小结 从各种需求方面下手改编代码，并不断

8、调试，让界面更加友好。不断地尝试上，在各种问题上不断突破，慢慢的完善代码，等最大限度的满足用户需求。这几天短时间的课程设计也让我认识到了自己在这门课程上还面临着许许多多的问题，为以后的具体实践明确了努力方向。同时，城市交通咨询系统的实现，为用户更好的解决了再实际出行时遇到的路径问题，最初的设计也为代码敲定了编写方向。再三考虑后确定了系统的功能，确定什么功能有实现必要，什么功能可有可无。在这样的基础之下使得思路更加清晰。2.系统设计 本程序首先是用户编辑界面，用户根据自己的需求编写地图，从而加入顶点的数组之中，创建的地图用邻接矩阵存储，在从主函数之中进行调用，实现对两个算法的调用。用户在输入顶点

9、以及边的信息都会存储，在存储成功之后会提示用户存储成功，之后进入到菜单界面，菜单界面提供两种选择口令，分别可以调运Dijkstra 和 Floyd 算法，调用之后输入相应的口令以及要查询的城市编号，算法会根据邻接矩阵存储的地图进行计算，求出最短路径。在以后使用完系统后，可输入口令 0，系统会结束一切运算，退出程序。2.1 系统设计功能菜单界面的主要功能有两个:（1） 、求一个城市到所有城市的最短距离（2） 、求任意的两个城市之间的最短距离城市交通咨询系统主要有三个模块分别为：（1） 、邻接矩阵的输入与存储构建交通网络（2） 、任意两个城市的最短距离查询（3） 、两个指定城市的最短距离查询城市交

10、通咨询系统4主界面的模块概念图如图 2-1：任意两个城市的最短距离查询两个指定城市的 最短距离查询图 2.12.2 每个模块的具体功能。2.2.1 采用采用 C 语言定义相关数据类型语言定义相关数据类型1定义一个，用来存储顶点信息。typedef struct VertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph; 2定义一个 Dijkstra 函数void Dijkstra(MGraph *G,int v,int n);3定义一个 Floyd 函数void Floyd(MGraph *G,int n);用户进入系统交通网络构建结果，退出系统数据结构课程

11、设计52.2.2 建立邻接矩阵交通网络：建立邻接矩阵交通网络：图 2-2邻接矩阵构造图结构函数数据类型定义：typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;void CreateMGraph(MGraph *G,int n,int e)/邻接矩阵构成有向图int i,j,k,w;for(i=1;ivexsi=(char)i;N开始输入顶点和边数 n,e输入 i,j,wkarcsij=IDF;printf(“输入%d 条边的 i,j 及 w: n“,e);for(k=1;karcsij=w;printf(“有向图的存储结构

12、建立完毕!n“);其中 vexsMAX保存顶点信息，arcsMAXMAX用于保存边与边之间的信息。在构建时通过输入的边数 i，j 作为矩阵的行、列确定顶点的出度和入度。用邻接矩阵方法存储图。2.2.3 查询指定城市到其他城市自己建的最短路程：查询指定城市到其他城市自己建的最短路程：图 2-3应用狄克斯特拉算法来具体实现这一步的需求。基本思想：设 G（V,E）是一个带权有向图，把图中的顶点集合 V 分成两组，第一组为已经求出的最短路径的顶点集合（用 S 表示，初始时 S 中只有一个原点，以后每求得一条最短路径就加入的集合 S 中，知道全部顶点都加入到集合中） ，第二组，为其余未确定最短路径的顶点

13、集合（用 U 表示） ，按最短路径长度的递增次序依次把第二组的顶点就如 S 中。如果两个顶点之间有权值，并且各个路径的权值不同，就把最小的作为顶点与顶点的最短距离。开 始输入顶点 v狄 克 斯 特 拉 算 法输出路径,距离结 束k数据结构课程设计7yx z图 2-4如图所示 若 x+yk=u。同理若 x+yu，D v1=0;Sv1=1; /原点编号放入 s 中for(i=2;iarcsvwarcsvw;P w=v;2.2.4 查询任意两个城市之间的一条最短路径：查询任意两个城市之间的一条最短路径：其具体的流程图如图 2-5 所示：vu开 始输入起点 v，终点 w调 用 弗 洛 伊 德 算 法输

14、出路径,距离结 束城市交通咨询系统8图 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弗洛伊德主要算法，若 Akij已求出，顶点 i 到顶点 k+1 的路径长度为Akik+1，顶点路径长度为 Akij，

15、顶点 k+1 到顶点 j 的路径长度为 Akk+1j，如果此时 Akik+1+Akk+1j1 长度=0，1=2 长度=8，1=3 长度=8+6=14，1=4 长度=8+5=13；和下图完全一致图3-4城市交通咨询系统12为保证结果正确换一个顶点进行：如顶点 2 到其他的距离经过手工计算：2=1 长度=6+4=10，2=2 长度=0，2=3 长度=6，2=4 长度=5；和下图完全一致图 3-52、求任意的两个城市之间的最短距离例 1 到 3 之间的最短距离，经过计算可得最短距离为 1=2=3，且路径为 14，与下图结果相同。图 3-6为保证结果正确换一个顶点进行：如顶点 2 到 4 之间的最短路径以及距离经过计算可得 2 到 4 的最短路径是 2=4,且最短路径为 5数据结构课程设计13图 3-73.2.3、结束程序当用户输入命令 0 时，结束程序图 3-84.总结通过这次数据结构课程设计，我对数据结构这门课程有了更深一步的了解，