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

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

榆林学院

数据结构课程设计报告

题目城市交通咨询系统

作者杨朝

专业信息管理与信息系统

学号 1514210121 指导老师张慧

答辩时间 2016.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建立邻接矩阵交通网络： (5)

2.2.3查询指定城市到其他城市自己建的最短路程： (6)

2.2.4查询任意两个城市之间的一条最短路径： (8)

2.3主函数的调用关系图 (9)

3.系统测试 (11)

3.1操作说明 (11)

3.2测试数据 (11)

3.2.1用户进入界面： (11)

3.2.2、具体功能的实现 (12)

3.2.3、结束程序 (14)

4.总结 (15)

5.致谢 (15)

6.附录 (16)

1.系统需求分析

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

对系统分析，主要从以下几个方面进行分析。

1.用户需求分析

2.功能需求分析

3.数据需求分析

1.1用户需求分析

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

当要查询某两个城市之间的最短交通路线或者其中一个城市到达其余城市的最短路线时，是一个很繁琐的过程。

根据用户自己的需求，可以自定义地图，此程序就是主要以满足用户自己的环境与实际情况，在难以计算路程时，可将地图输入进行计算，系统将会为用户提供所用路径最短的出现路线，更好的满足用户需求。以下是针对咨询用户说明其最基本的模块功能。

（1）进入程序后，用户可自己设置城市的个数，以及所有城市之间总共的路径，且分别用顶点和边表示城市与路径

（2）用户根据自己设置的城市个数和路径数，具体输入每个路径的起始点以及每条路径的长度。

（3）进入菜单选择界面

（4）选择2，系统为用户进行提供任意城市的交通查询,即查询任意两个城

市之间的一条最短路径。

（5）选择1，系统为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路径。如若输入顶点超出范围显示错误，系统回到菜单重新选择

（6）选择0，系统推出程序。

1.2功能需求分析

城市交通咨询系统总体的设计目标：用《数据结构》中的邻接矩阵作数据结构，并结合数据结构有向图的最短路径计算方法，结合相应的数据算法以及c 语言的相关知识，编写一个良好的，具有可操作性的，以及能方便用户的使用，包括自定义地图，路径与城市个数可结合实际情况而言，相对操作，简便易懂并无难度。系统在菜单可根据命令进行相应的操作，已满足用户的需求。

城市交通系统基本功能

根据以上分析，此系统具备以下功能：

（1）用户进入后的地图创建界面（明确地图中城市的个数以及路径的个数）（2）地图完善界面（用户自己输入地图中相关路径的起始点以及路径长度）（3）菜单界面包含两条命令

（4）命令1求一个城市到所有城市的最短距离

（5）命令2求任意的两个城市之间的最短距离

（6）回复命令0可推出程序。

1.3数据需求分析

∙用邻接矩阵建立交通网络模块

VertexType vexs[MVNum];//顶点数组，类型假定为char

Adjmatrix arcs[MVNum][MVNum];//邻接矩阵，类型假定为int型

建立邻接矩阵，用函数void CreateMGraph(MGraph * G,int n,int

e) {//采用邻接矩阵表示法构造有向图G，n、e表示图的当前顶

点数和边数

∙用迪杰斯特拉算法计算某顶点到其余顶点的最短路径

用函数void Dijkstra (MGraph * G,int n,int e) 来定义此函数

采用邻接矩阵表示法构造有向图G，n、e表示图的当前顶点数和边数

∙用弗洛伊德算法求任意一对顶点的最短路径

用函数 void Floyd(MGraph *G,int n) 来定义。利用费洛伊德算法，

求出最短路径。

1.4 小结

从各种需求方面下手改编代码，并不断调试，让界面更加友好。不断地尝试上，在各种问题上不断突破，慢慢的完善代码，等最大限度的满足用户需求。这几天短时间的课程设计也让我认识到了自己在这门课程上还面临着许许多多的问题，为以后的具体实践明确了努力方向。同时，城市交通咨询系统的实现，为用户更好的解决了再实际出行时遇到的路径问题，最初的设计也为代码敲定了编写方向。再三考虑后确定了系统的功能，确定什么功能有实现必要，什么功能可有可无。在这样的基础之下使得思路更加清晰。

2.系统设计

本程序首先是用户编辑界面，用户根据自己的需求编写地图，从而加入顶点的数组之中，创建的地图用邻接矩阵存储，在从主函数之中进行调用，实现对两个算法的调用。

用户在输入顶点以及边的信息都会存储，在存储成功之后会提示用户存储成功，之后进入到菜单界面，菜单界面提供两种选择口令，分别可以调运Dijkstra和Floyd算法，调用之后输入相应的口令以及要查询的城市编号，算法会根据邻接矩阵存储的地图进行计算，求出最短路径。

在以后使用完系统后，可输入口令0，系统会结束一切运算，退出程序。2.1系统设计功能

菜单界面的主要功能有两个:

（1）、求一个城市到所有城市的最短距离

（2）、求任意的两个城市之间的最短距离

城市交通咨询系统主要有三个模块分别为：

（1）、邻接矩阵的输入与存储构建交通网络

（2）、任意两个城市的最短距离查询

（3）、两个指定城市的最短距离查询