数据结构三级项目报告北京市旅游景点导航程序设计学生 姓名： 冯星伟 学 号： 120104070017 指导 教师： 窦燕 李季辉 李可 日 期： 2014 年 1 月 1 号摘要本程序通过字符数组、图的数组表示法两种方法，呈现了包括景点名称、景点介绍、各景点间距离等相关数据的北京市旅游景点平面图。进入导航程序后，可根据需要分别实现北京市旅游景点总览、景点介绍、最短路径查询三大功能。其中计算最短路径使用了弗洛伊德算法。北京市旅游景点导航图共包括14个著名旅游景点，方便游客根据自身兴趣浏览景点信息，进而选择想要参观的景点，并可通过最短路径查询的功能设计出最佳的旅游路线。这也是设计小组的成员根据自身的旅游经验设计的功能，总体来讲，本小组力图通过自身知识对我国的旅游行业贡献绵薄之力。关键词：旅游导航、图、最短路径、弗洛伊德算法目录摘要 .2目录 .3前言 .4正文 .5(a) 研究内容的基本原理 .5(b) 所采用的研究方法及相关工具 .5(c) 项目的方案设计 .5(d) 研究结果并讨论 .5结论 .6参考文献 .7前言北京作为中国首都是不可忽略的旅游胜地，它不仅充满着古城的气息而且还包含着现代化最先进的科技艺术，这种形式造成了人们极想要一饱此都的风韵。身为一位旅游者在北京旅途中不小心就会错过许多的特色景点。对与一个游客来说，最首要的要求就是知道他所在的景区有多少可以参观的地方并且能够知晓这些景点的简写。在这种情况下，我们的程序应运而生。本程序旨在考察本小组成员在本学期关于数据结构课程的知识的学习情况，同时加强我们对于 C 语言的理解和熟练运用。本程序可以为游客提供详尽的景点清单，同时为游客提供每个景点的基本介绍以及最佳的旅游路线。目的：1、考察本学期数据结构课程的学习情况2、设计出方便游客旅游的北京市旅游导航程序范围：1.通过小组成员的旅游经验确定了该导航程序应该具备的功能，以便确定设计该程序大方向，以及所需准备的各种材料。2.通过网络查询了北京市的若干著名旅游景点以及各旅游景点的介绍。3.通过网络查询已有的旅游地图所包含的功能，取其精华，补其不足。预期结果：本小组成员预想通过设计该导航程序方便游客了解北京市的著名旅游景点的信息以及以设计旅游路线。项目分工：小组成员先是就实际问题做了分析研究，并结合所学知识确定了程序所要实现的具体功能，并设计出导航图的基本模型。王帅男同学主要负责对程序进行调试及函数编写，冯星伟同学主要负则查询以及编辑景点资料资料和后期程序的界面进行完善，王星洁主要负责对程序进行后期调试。正文(a) 研究内容的基本原理本程序需要存储景点名称及景点间的距离关系，所以我们自然而然的选择了图结构。考虑到图由顶点及弧或边构成，和在一起较困难，自然的就分为两个结构来分别存储。顶点不分大小、主次，所以我们选择一位字符数组来进行存储，而弧是顶点与顶点间的关系，所以我们采取二位数组。于是邻接矩阵方案就诞生了。图的邻接矩阵存储方式（Adjacency Matrix）存储方式使用两个数组来表示图。一个一位数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。例如，以二维数组存储有 4 个顶点的的邻接矩阵（图一）,需存放 42个弧信息的存储量。若考虑无向图的邻接矩阵的对称性，则可采用压缩存储的方式只存入矩阵的下三角（或上三角）元素。在程序中我们采取的是有向图的运用。 （矩阵可见图二）构造一个具有 n 个顶点和 e 条边的无向图 G 的时间复杂度是 O(n2+e*n),其中对邻接矩阵 G 的初始化耗费了 O（n 2）的时间。通过图二可见，邻接链表的顶点数越高数据量越大。在数据量达到一定数量的时候并不建议使用邻接链表方法。(b) 所采用的研究方法及相关工具本程序以 Visual C+ 6.0 平台下的控制台程序为基础进行开发，Visual C+ 6.0 平台是为开发大型程序而研制的，它比 C语言困难得多，它功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高、可移植性好，既具有高级语言的优点，又具有低级语言的许多特点，完全适合于编写系统软件。本组通过其控制台程序，建立了菜单函数，使用者可通过阅读菜单来进行不同需求的操作。(c) 项目的方案设计1.读取使用者所输入的地图 TXT 文本文件名称，在本程序的存储目录下进行查找匹配，若查找到则打开文件准备读取。2.读取文件中的顶点个数，并且依照顶点个数大小为顶点名称字符数组、顶点描述字符数组与邻接矩阵分配足够的空间。 3.依次序读取顶面名称及其描述与邻接矩阵。4.进入功能菜单，依照使用者要求分别调用函数进行计算。(d) 研究结果并讨论 1. 导入成功画面2.菜单界面3.输出所有景点名称画面4.景点信息查询5.最短路径及所经路径结论在本项目中我们进行的主要工作是对北京景点图结构的建立（定义顶点及边的结构体，运用文件将图的信息导入程序）以及界面函数、搜索函数、佛罗伊得函数的定义和调用。通过我们的努力，北京旅游导游系统最后完成，并将该程序打造成为试用于任何城市的导游系统（前提是将需要被导航的学校的信息存入文件）。我们从这次三级项目中进步很多，三级项目开始之前，我们参考了一些别的系统，认真的分析了别人的代码，了解在我们的项目中需要实现的功能和涉及到的函数，然后从网上找到北京城的信息（各景点的介绍，和连接各学院的路径及长度）。首先明确大概思路，利用 if 语句实现需要的功能选择：退出程序，输出所有景点的名称，查询景点信息，求两景点间的最短路径，重新导入新的地图信息。输出所有景点名称部分，利用 for 循环，将存储顶点信息的数组 G.vexsi.name 输出查询景点信息利用 strcmp 函数使得输入景点名称和文件中的相匹配，然后输出该顶点信息。求两景点的最短路径，相较于迪杰斯特拉函数，调用弗洛伊德函数求任意两点的最短路径。程序虽有需要改进的地方，但功能齐全，界面大方简约，是一次比较成功的作业。参考文献数据结构（C 语言版）清华大学出版社 严蔚敏 吴伟民 编著大话数据结构 清华大学出版社 程杰 编著