1、 数据结构课程设计报告 题 目 交通旅游图的最短路径问题 学生姓名 * 指导教师 * 学 院 * 专业班级 * 完成时间 * 摘摘 要要 数据结构主要是一门研究非数值计算的程序设计问题中的计算 机操作对象以及它们之间的关系和操作等的学科。 数据结构在计算机 科学与技术中是一门综合性的专业基础课， 其研究不仅涉及到计算机 硬件的研究范围，而且和计算机软件的研究有着更密切的关系。不论 是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配 问题。在计算机科学与技术中，数据结构不仅是一般程序性的基础， 而且也是其他系统程序和大型程序的重要基础。 在交通网络非常发达， 交通工具和交通方式不断更新的
2、今天，人 们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和 所需时间等问题也感兴趣。对于这样一个人们关心的问题， 可用一个 图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。 图 中顶点表示站点之间的交通关系。 这个交通系统可以回答旅客提出的 各种问题。比如任意一个站点到其他站点的最短路径，任意两个站点 之间的最短路径问题。 本次设计的交通咨询系统主要是运用 C 语言来完成交通图的存 储、图中顶点的最短路径和任意一对顶点间的最短路径问题。 关键字关键字：数据结构 课程设计 交通咨询系统 目目 录录 前言 1 第一章 设计要求 2 1.1 设计内容. 2 1.2 设计目的.
3、3 1.3 设计分析. 4 第二章系统功能模块的设计 5 2.1 系统功能分析与设计 5 2.1.1 系统简介5 2.1.2 系统流程图.5 2.2 各功能模块简介 6 2.2.1 结构体的建立. 6 2.2.2 图的建立与初始化 . 6 2.2.3 邻接矩阵的输出 8 2.2.4 显示函数.8 2.2.5 最短路径算法.9 2.2.6 主函数.10 第三章 实践结果与调试12 3.1 运行结果.12 3.1.1 主界面.12 3.1.2 查询站点编号模块.12 3.1.3 邻接矩阵查询模块.12 3.1.4 最短路径查询模块.13 3.2 运行调试及发现问题.15 3.2.1 调试过程.15
4、 3.2.2 发现问题.15 第四章设计总结与心得16 附录：程序源代码.18 数据结构课程设计：交通旅游图的最短路径问题 前 言 1 前前 言言 乘汽车旅行的人总希望找出到目的地的尽可能短的行程。 如果有一张地图并 在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址 的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？ 这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模， 寻找最优路的需求可转换为带权图的最短路径问题。 最短路径问题是图论研究中 的一个经典算法问题， 旨在寻找图（由结点和边组
5、成的）中两结点之间的最短 路径。 问题具体的形式包括： 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。适合使用 Dijkstra算法。 确定终点的最短路径问题， 与确定起点的问题相反， 该问题是已知终结结点， 求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中 该问题等同于把所有路径方向反转的确定起点的问题。 确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路 径。 全局最短路径问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。 数据结构课程设计：交通旅游图的最短路径问题 第一章 设计要求 2 第一章第一章 设计要求设计要求
6、1.1 设计内容设计内容 一问题描述： 已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在 任一车站通过终端询问知道： 是否有公共汽车到达指定的目的地? 若有，告诉乘车路线。如需中途换车，应指示再那里换车 二基本要求： （1）自己提出一个公共汽车路线图，可以在网上搜索现实城市公交路线图 （如长沙市的） ，至少要有 7 条公交线路，每条线路至少要有 7 个公共汽车站。 （2）数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结 构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站 之间可能存在往返两个方向，每个方向又可能对应多个路线号。 （3）算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的 站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。 数据结构可以采用链接结构： structNODE char* stname; struct NODE* link; ; struct N
