兰州道路交通网络信息查询设计说明书

*******************

实践教学

*******************

兰州理工大学

2010年春季学期

数据结构 课程设计

题 目：兰州道路交通网络信息查询

专业班级：08信息与计算科学

姓 名： 杨学勤 学 号： 08500115 指导教师： 李睿

成 绩： _______________

1

目 录

中 文 摘 要 ............................................................................................................ 3 序 言 ...................................................................................................................... 4 1. 采用类C语言定义相关数据类型...................................................................... 5 2.各模块流程图及伪码算法 .................................................................................. 6 3.函数的调用关系图 ............................................................................................... 8 4.调试分析 .............................................................................................................. 9 1. 2.

调试中遇到的问题及对问题的解决方法 ................................................. 9 算法的时间复杂度和空间复杂度 ............................................................. 9

5.测试结果 ............................................................................................................... 9 设 计 总 结 .................................................................................................... 13 参考文献 ................................................................................................................ 14 致 谢 .................................................................................................................... 15 附录：源程序（带注释） .................................................................................... 16

2

中 文 摘 要

在本设计实验中，我所采用的是邻接矩阵作为数据的存储结构，用不同的功能模块对两地距离和道路交通信息进行编辑。

兰州道路交通网络信息查询程序的目的是为人们提供各种信息查询服务：即查询任意两地之间的一条最短的简单路径、还有两地之间的距离等。最短路径的输出有各种方法，此程序中采用迪杰斯特拉算法。迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。

关键词：交通网络，邻接矩阵，迪杰斯特拉。

3

序 言

我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。

图是一种复杂的非线性结构，在人工智能，工程，数学，物理，化学，计算机学科等领域中，都有着广泛的应用。我们用最短路径问题，通过一个人们熟悉的交通咨询系统实例来验证迪杰斯特拉算法。

兰州道路交通网络信息查询是以兰州道路交通网络为背景，设计出的一个简单的能够实现兰州道路交通网络信息查询功能的c语言程序系统，对兰州道路交通信息进行编辑，为旅客提供了两地之间的最短路径及距离。

查询的实现以用户和计算机对话的方式进行，要注意人机交互的屏幕界面，由用户选择要查询的地点，输入要查询路径的起点和终点。

4