数据结构课程设计---交通旅游图的最短路径问题

据结构课程设计 报告 题 目 交通旅游图的最短路径问题 学生姓名 * 指导教师 * 学 院 * 专业班级 * 完成时间 * 摘 要 数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的关系和操作等的学科。数据结构在计算机科学与技术中是一门综合性的专业基础课，其研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的 关系。不论是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配问题。在计算机科学与技术中，数据结构不仅是一般程序性的基础，而且也是其他系统程序和大型程序的重要基础。 在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示 站点 之间的交通关系。这个交通系统可以回答旅客提出的各种问题。比如任意一个 站点 到其他 站点 的最短路 径，任意两个 站点之间的最短路径问题。 本次设计的交通咨询系统主要是运用 C 语言来完成交通图的存储、图中顶点的最短路径和任意一对顶点间的最短路径问题。 关键字 ：数据结构 课程设计 交通咨询系统 目 录 前言 . 1 第一章 设计要求 . 2 计内容 . 2 计 目的 . 3 计分析 . 4 第二章 系统功能模块的设计 . 5 统功能分析与设计 . 5 统 简介 . 系统流程图 .功能模块简介 . 6 构体的建立 . 6 的建立与初始化 . 6 接矩阵的输出 . 8 示函数 . 最短路径算法 . 主函数 .三章 实践结果与调试 .行结果 . 主界面 . 查询站点编号模块 . 邻接矩阵查询模块 . 最短路径查询模块 .行调试及发现问题 . 调试过程 . 发现问题 .四章 设计总结与心得 .录：程序源代码 .据结构课程设计：交通旅游图的最短路径问题 前 言 1 前 言 乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 计 算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？ 这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和边组成的）中两结点之间的最短路径。 问题具体的形式包括： 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。适合使用 确定终点的最短路径问题，与确定起点的问题相反，该问题是 已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题，求图中所有的最短路径。适合使用 数据结构课程设计：交通旅游图的最短路径问题 第一章 设计要求 2 第一章 设计要求 计内容 一 问题描述： 已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道： 是否有公共汽车到达指定的目的地 ? 若有，告诉乘车路线。如需中途换车，应指 示再那里换车 二 基本要求： （ 1）自己提出一个公共汽车路线图，可以在网上搜索现实城市公交路线图（如长沙市的），至少要有 7 条公交线路，每条线路至少要有 7 个公共汽车站。 （ 2）数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶点 (站 )之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。 （ 3）算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。 数据 结构可以采用链接结构： ; ； 数据结构也可以采用顺序结构： go,; a,; 其中， aI， j 表示第 i 条线路上，向站 j 去方向的下一站号； ai， j表示第 i 条线路上，站 j 回来的下一站号。若站 j 不在第 i 条线路上， ai， jai， j为 0。 （ 4）另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；数据结构课程设计：交通旅游图的最短路径问题 第一章 设计要求 3 另一个是站号和站名对照表。 （ 5）对所采用的算法进行算法分析 三 . 实现提示 假定顶点编号为 1.据结构采用连接结构。设置表头数组为 .i包含站 i 的名字和一指针，该指针指向 i 的所有邻接顶点组成的单链表。单链表中的每个结点包含 3 个域：一个站号域，两个指针域。一个指针指向 i 的下一个邻接顶点，另一个指针指向从 i 到该结点的所有线路号组成的链表。 ; ; 如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用 法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。 计目的 一 邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛 伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。 二 交通咨询系统要完成城市网络图的存储，并要实现求任意一个 顶点到其他 顶点的最短路径问题，还要实现任意两个 车站 顶点间的最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决路径问题；最后再实现两个 车站 之间的最短路径问题。 三 过课程设计我们不仅可以巩固已学到的书本知识，还可以从亲自动手设计这项课程设计的过程中发现问题，并学会用自己所学的知识解决问题。这不仅使我们能学会很多书本 中学不到的知识、经验，还能 提高我们自己数据结构课程设计：交通旅游图的最短路径问题 第一章 设计要求 4 的动手能力，同时开发自身的创新思想，拓展思维。 计分析 一 通过对题目的分析知，是要让我们能够通过利用所学的数据结构的基本知识和技能来解决程序设计问，因此在搞程序设计之前先好好的把书复习一遍，弄清楚各个知识之间的联系。 二 根据这些功能和基本要求，可充分运用我们所学的数据结构的基本知识和技能去逐步的解决。其中将函数进行模块化。在数 据结构中，通过队列，栈，图的声明来实现系统的各种功能的存储各站点之间乘车的时间，距离，以及最少的中转站。利用结点来实现站点 之间各 种操作，而这些知识点都是我们学习数据结构必须掌握和学会运用的。 三 完成程序功能的设置后，应对程序进行调试，以便在调试中能及时地找出错误并加以更正，这样能使程序功能进一步的完善和正确。这就要求我们在编程和调试过程中养成认真分析和善于发现问题并及时解决的习惯，不懂的及时问老师或者其他同学。数据结构课程设计：交通旅游图的最短路径问题 第二章 系统功能模块的设计 5 第二章 系统功能模块的设计 统功能分析及设计 统简介 该课题可以分为如下几个模块：控制选择功能项的 数、 定义各类抽象结构体的模块 、 有向图的建立与初始化函数 邻接矩阵的输出函数 g)、 显示输出 函数 、求最小路径的函数 g)、 以及中转站 的 输出函数 i,j)。 统流程图 数据结构课程设计：交通旅游图的最短路径问题 第二章 系统功能模块的设计 6 功能模块简介 构体的建立 本次设计中需要运用有向图来显示交通网络图，顾建立抽象数据结构体便是很重要的一项工序。首先要先建立顶点的结构体， 边的结构体以及图的结构体。这些均是为了以后的数据存储和算法的实现做的基本定义。此模块如下： /假设 型 /顶点编号 /顶点其他信息，这里用于存放边的权值 0; /顶点名称 /顶点类型 /边的权值，表示路径长度 /边得两端顶点号 /边的类型 /图的定义 /邻接矩阵 n,e; /顶点数，弧数 /存放顶点信息 /图的邻接矩阵类型 的建立与初始化 图是这个题目课程设计的核心。所以对图的建立是必要的，并且 对图的初始化赋值也同样 重要。在创建图是，同时进行对顶点的编号，名称的填写以及邻接矩阵的输入。这样才能构成完整的有向图，才能建立确切的交通网络图，以便实现交通的查询。此函数为： ; ; i,j; 数据结构课程设计：交通旅游图的最短路径问题 第二章 系统功能模块的设计 7 4; 4; 1414=32767,32767,32767,32767,32767,32767,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,5,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,9,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,6,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,32767,32767,5,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,6,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,9,8,32767,32767,32767,32767,32767,32767,32767,32767; i=0;i(Aik+Akj) Aij=Aik+Akj; ij=k; 请输入需要查找的两个站点 (站点编号为 0n); ; 起点 :);%3d,&f); f=n) 该站不存在，请重新输入！ n); 起点 :);%3d,&f); ; 终点 :);%3d,&r); r=n) 数据结构课程设计：交通旅游图的最短路径问题 第二章 系统功能模块的设计 10 该站不存在，请重新输入！ n); 终点 :);%3d,&r); ; r=f) 不能等于起点，请重新输入！ n); 终点 :);%3d,&r); n 输出最短路径 :n); Afr= if(f!=r)从 %3d 到 %3d 没有路径 nnn,f,r); 从 %3d 到 %3d 路径为 :,f,r); %3d,f); f,r); %3d,r); n 路径长度为 :%3d nnn,Afr); 函数 主函数在此系统中主 要实现主界面的设置，菜单功能的实现。同时使其他模块函数的功能连接起来，共同组成一个完整的咨询系统。顾主函数如下： i,j,n,k=1; k=1) *欢迎进入公交查询系统 * n); 制作人：韦千慧 周韵 n); 请输入选择： n); n); n); n); n); * n); %d,&n); 数据结构课程设计：交通旅游图的最短路径问题 第二章 系统功能模块的设计 11 n) :;: ; 交通网路的邻接矩阵为 n); ); : ; );:k=2;输入错误！请重新输入！ ); 数据结构课程设计：交通旅游图的最短路径问题 第三章 实践结果与调试 . 12 第三章 实践结果与调试 行结果 界面 主界面运行结果如下图： 输入选项编号后即可进入功能输出！ 询站点编号模块 查询站点编号模块运行如下图： 此模块为输出顶点即站点的编号与名称所对应的列表。 接矩阵查询模块 邻接矩阵查询模块运行如下图： 数据结构课程设计：交通旅游图的最短路径问题 第三章 实践结果与调试 . 13 此为邻接矩阵的数值输入状况。 短路径 查询模块 最短路径查询模块运行如下图： （ 1）两点之间没有路径： 此图为输入的起点与终点之间没有路径可以到达。 （ 2）两点之间有直接通路： 数据结构课程设计：交通旅游图的最短路径问题 第三章 实践结果与调试 . 14 此图为两点之间的通路是直接通路，并输出了路径长度。 （ 3）两点之间间接通路： 此图为两点之间的通路是间接的，不仅输出了路径长度，并且将中转站点的编号也一同输出，方便旅客转车。 数据结构课程设计：交通旅游图的最短路径问题 第三章 实践结果与调试 . 15 行调试及发现问题 试过程 一开始运行此系统，会发现很多错误而无法运行。在不断的查找资料与复习书本上所学习过的内容不断改正后正式运行成功。然而，每个模块都有小小的不足之处，运行出的结果也并不与我们所想象的一样。 首先，主界面的运行就需要许多的调试，比如并未对齐，或词语串行等等，都需要我们不断调整空格格数以及语句的筛选才能实现理想的结果。 其 次，对于显示的函数同样存在着与主界面同样的问题，我们需要一点一点的调整才可以完全输出想要的结果。 另外，最短路径的输出函数，一开始并未正确的输出，这需要我们不断的查找问题并解决，最后再进行一步步的调整，才可以正确的输出。并且在没有直通路径的时候还需要输出所经站点的编号，这也需要我们调整。一切完成后才可正常工作。 最后，退出系统的功能也需要自己编译以及调试。有时候无法跳出主函数的循环，或者无法跳出系统的循环，这都是编译出了问题，均需要一点点调试才可。 现问题 这次课程设计的系统并不完善，只实现了 最基本的功能。其实还可以更加完善，多添加几个模块功能，使其更加完整，比如：管理员身份登录后可以修改线路的权值，站点的名称，可以添加、删除、修改这些信息。这样就使得这个系统更加的人性化，并且更加先进，可以及时更新最新信息。另外在用户查询中，也可多添加几项为旅游服务的项目，比如：为站点做简介，介绍当地的特色以及景点，还可以提供查询路径时不仅可查出距离的长短，还有时间花费等均可以查询。 以上仅仅只是发现这次所做系统的不足，功能的缺少，但并未能真正的实现。然而在已有的功能中，查询最短路径函数中，也有小小的不足：在查 询后显示出的并非站点名称而是编号，这还需用户自己对照列表进行查找，这便不是很直观方便了。我们想了很多种方法想要更正这一点，但怎么都无法实现。我想我们学习的还是不够，动手能力还是没有真正的达到随心所欲的境界，这还需要我们不断的积累经验，不断的动手实践才能完成心中所想得效果吧。 数据结构课程设计：交通旅游图的最短路径问题 第四章 设计总结及心得 16 第四章 设计总结与心得 做了一个星期的程序设计终于做完了，在这次程序设计课中，真是让我获益匪浅，我突然发现写程序还挺有意思的。 由于上学期的 C 语言跟数据结构都算不上真正的懂，对于书上的稍微难点的知识就是是而非的，所以我只是对老师的程序 理解，我也试着去改变了一些变量，自己也尽量多的去理解老师做程序的思路。当我第一天坐在那里的时候，我就不知道该做些什么，后来我只有下来自己看了一遍书来熟悉下以前学过的知识。 通过这次的程序设计，发现一个程序设计就是算法与数据结构的结合体，自己也开始对程序产生了前所未有的兴趣，以前偷工减料的学习也不可能一下子写出一个程序出来，于是我就认真看老师写的程序，发现我们看懂了一个程序其实不难，难的是对于一个程序的思想的理解，我们要掌握一个算法，不仅仅限于读懂，主要的是要理解老师的思路，学习老师的解决问题的方法。 这次试 验中，我发现书本上的知识是一个基础，但是我基础都没掌握，更别说写出一个整整的程序了。自己在写程序的时候，也发现自己的知识太少了，特别是基础知识很多都是模模糊糊的一个概念，没有落实到真正的程序，所以自己写的时候也感到万分痛苦，基本上涉及一个知识我就会去看看书，对于书本上的知识没掌握好。在饭后闲暇时间我也总结了一下，自己以前上课也认真的听了，但是还是写不出来，这主要归结于自己的练习太少了，而且也总是半懂就不管了。在改写老师的程序中也出现了很多的问题，不断的修改就是不断的学习过程，当我们全身心的投入其中时，实际上 是一件很有乐趣的事情。 通过此次课程设计，使我更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也 暴露出了前期我在这方面的知识欠缺和经验不足。 实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。 过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行 “ 过而能改，善莫大焉 ” 的知行观。 这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师的指导下， 终于游逆而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！ 数据结构课程设计：交通旅游图的最短路径问题 第四章 设计总结及心得 17 课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。 同时，设计让我感触很深。使我对抽象的理论有了具体的认识。 我认为，在这学期的实验中 ，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。这对于我们的将来也有很大的帮助。以后，不管有多苦，我想我们都能变苦为乐，找寻有趣的事情，发现其中珍贵的事情。就像中国提倡的艰苦奋斗一样，我们都可以在实验结束之后变的更加成熟，会面对需要面对的事情。 实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就 是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。 此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获颇丰。 数据结构课程设计：交通旅游图的最短路径问题 附录：程序源代码 18 附录 ：程序源代码 #20 /最大顶点个数 #2767 /用 32767表 示 /假设 /顶点编号 /顶点其他信息，这里用于存放边的权值 0; /顶点名称 /顶点类型 /边的权值，表示路径长度 /边得两端顶点号 /边的类型 /图的定义 /邻接矩阵 n,e; /顶点数，弧数 /存放顶点信息 /图的邻接矩阵类型 ; 数据结构课程设计：交通旅游图的最短路径问题 附录：程序源代码 19 ; i,j; 4; 4; i=0;i(Aik+Akj) Aij=Aik+Akj; ij=k; 请输入需要查找的两个站点 (站点编号为 0n); ; 数据结构课程设计：交通旅游图的最短路径问题 附录：程序源代码 21 起点 :);%3d,&f); f=n) 该站不 存在，请重新输入！ n); 起点 :);%3d,&f); ; 终点 :);%3d,&r); r=n) 该站不存在，请重新输入！ n); 终点 :);%3d,&r); ; r=f) 不能等于起点，请重新输入！ n); 终点 :);%3d,&r); n); Afr= if(f!=r)从 %33nnn,f,r); 从 %33,f,r); %3d,f); f,r); %3d,r); %3d nnn,Afr); i,j,n,k=1; 1414=32767,32767,32767,32767,32767,32767,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,5,3