CENTRAL SOUTH UNIVERSITY数据结构课程设计报告题 目交通旅游图的最短路径问题学生姓名*指导教师*学 院*专业班级*完成时间*摘 要数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的关系和操作等的学科。数据结构在计算机科学与技术中是一门综合性的专业基础课，其研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系。不论是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配问题。在计算机科学与技术中，数据结构不仅是一般程序性的基础，而且也是其他系统程序和大型程序的重要基础。在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示站点之间的交通关系。这个交通系统可以回答旅客提出的各种问题。比如任意一个站点到其他站点的最短路径，任意两个站点之间的最短路径问题。本次设计的交通咨询系统主要是运用C语言来完成交通图的存储、图中顶点的最短路径和任意一对顶点间的最短路径问题。关键字：数据结构 课程设计 交通咨询系统目 录前言1第一章 设计要求21.1设计内容21.2设计目的31.3设计分析4第二章系统功能模块的设计52.1 系统功能分析与设计5 2.1.1系统简介.52.1.2 系统流程图.52.2 各功能模块简介62.2.1结构体的建立62.2.2 图的建立与初始化62.2.3 邻接矩阵的输出8 2.2.4 显示函数.8 2.2.5 最短路径算法.9 2.2.6主函数.10第三章 实践结果与调试.123.1运行结果.123.1.1主界面.12 3.1.2查询站点编号模块.12 3.1.3邻接矩阵查询模块.12 3.1.4最短路径查询模块.133.2运行调试及发现问题.15 3.2.1调试过程.15 3.2.2发现问题.15第四章设计总结与心得.16附录：程序源代码.18前 言乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和边组成的）中两结点之间的最短路径。问题具体的形式包括：确定起点的最短路径问题，即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。确定终点的最短路径问题，与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。全局最短路径问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。第一章 设计要求1.1 设计内容一问题描述：已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道：是否有公共汽车到达指定的目的地? 若有，告诉乘车路线。如需中途换车，应指示再那里换车 二基本要求：（1）自己提出一个公共汽车路线图，可以在网上搜索现实城市公交路线图（如长沙市的），至少要有7条公交线路，每条线路至少要有7个公共汽车站。（2）数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。 （3）算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。 数据结构可以采用链接结构：structNODEchar* stname;struct NODE* link;struct NODE hdtpMAX+1；数据结构也可以采用顺序结构：struct NODEint go,back;struct NODE amax+1,max+1;其中，aI，j.go0 表示第i条线路上，向站j 去方向的下一站号；ai，j.back0表示第i条线路上，站j回来的下一站号。若站j不在第i条线路上，ai，j.go 和ai，j.back 均为0。（4）另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；另一个是站号和站名对照表。（5）对所采用的算法进行算法分析 三. 实现提示假定顶点编号为1.n，数据结构采用连接结构。设置表头数组为head1.n，headi包含站i的名字和一指针，该指针指向i的所有邻接顶点组成的单链表。单链表中的每个结点包含3个域：一个站号域，两个指针域。一个指针指向i的下一个邻接顶点，另一个指针指向从i到该结点的所有线路号组成的链表。 struct LINENODEint lineno;struct LINENODE* next;struct STNODEint stno;struct LINENODE* Link1,*Link2;如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用Djkstra算法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。1.2 设计目的一.设计思想：用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。 二.设计要求：该交通咨询系统要完成城市网络图的存储，并要实现求任意一个顶点到其他顶点的最短路径问题，还要实现任意两个车站顶点间的最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决路径问题；最后再实现两个车站之间的最短路径问题。三.设计目的：通过课程设计我们不仅可以巩固已学到的书本知识，还可以从亲自动手设计这项课程设计的过程中发现问题，并学会用自己所学的知识解决问题。这不仅使我们能学会很多书本中学不到的知识、经验，还能提高我们自己的动手能力，同时开发自身的创新思想，拓展思维。1.3 设计分析一通过对题目的分析知，是要让我们能够通过利用所学的数据结构的基本知识和技能来解决程序设计问，因此在搞程序设计之前先好好的把书复习一遍，弄清楚各个知识之间的联系。二根据这些功能和基本要求，可充分运用我们所学的数据结构的基本知识和技能去逐步的解决。其中将函数进行模块化。在数据结构中，通过队列，栈，图的声明来实现系统的各种功能的存储各站点之间乘车的时间，距离，以及最少的中转站。利用结点来实现站点之间各种操作，而这些知识点都是我们学习数据结构必须