公园导游图数据结构课程设计

课程名称：数据结构湖南涉外经济学院本科学生课程设计（论文）题目公园导游图姓名唐哲学号学部计算机科学与技术专业、年级指导教师2011年12月8日湖南涉外经济学院本科学生课程设计（论文）摘要随着中国经济不断的发展，城市发展的越来越好，越来越多的人融入了城市生活。公园成为人们散心，娱乐的场所，公园也随即也在不断的扩张，变得越来越全面，但是这不利于逛公园的人寻找自己想要去的地方，尤其是对公园陌生的游客，更是不知道如何走，才能更好的游玩公园，达到的最好经济效益。所以针对这种现象，为了方便游客，开发这么一款公园导游系统软件。系统是用C语言实现，基于visualc++6.0开发的，采用图这么一种数据结构，采用邻接矩阵的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。本系统设计基于图的结构，创建一个无向图，针对游客的需求，将涉外公园的景点编号、名称、介绍等信息放入到图的顶点当中并保存景点文本文件中，将两个景点的编号和它们之间的距离当权值也保存在相同的文本文件中，利用迪杰特斯拉算法来求从一个景点到另一个景点的最短距离，利用Serach（）；查找景点，本显示他的信息，从而解决了要查找景点信息和两个景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。关键词：公园导游；图；邻接矩阵；二维数组；静态链湖南涉外经济学院本科学生课程设计（论文）目录第一章前言...................................................11.1课题的研究背景、要求和意义..................................11.2课题的目标、研究范围........................................11.3理论技术方案的选取..........................................21.4研究方法....................................................21.5结构与安排..................................................2第二章系统功能分析............................................42.1可行性分析.................................................42.1.1技术可行性............................................42.1.2工具可行性...........................................42.1.3经济可行性...........................................42.1.4操作可行性...........................................52.2需求分析...................................................52.2.1功能需求.............................................52.2.2输入输出的要求.......................................5第三章总体设计................................................63.1程序模块...................................................63.2系统涉及的数据结构.........................................63.2.1程序数据结构.........................................73.2.2具体数据类型定义.....................................7第四章详细设计................................................94.1创建图（FPRINT-LINK）........................................94.2寻找最佳路径（DFSTRAVERSE）..................................94.3最短路径（SHORTPATH）.......................................104.4遍历出某一起点到终点的所有路径（SEARCHALLPATH）.............124.5导入新文件（LOADNEWMAP）....................................13第五章系统实现...............................................145.1程序执行之前的准备........................................145.2主界面....................................................145.3游客界面..................................................155.4系统用户界面..............................................15湖南涉外经济学院本科学生课程设计（论文）5.5浏览公园全景简图..........................................165.6寻找某一起点的最佳路径和指定起点、终点的最短路径..........165.7寻找指定起点、终点的所有路径..............................175.8删除，添加结点，保存和导入新地图..........................17第六章解决的关键问题.........................................186.1如何实现寻找最短路径功能..................................186.2如何实现深度优先搜索......................................186.3如何修改地图..............................................186.4如何导入其他文件信息.......................................18第七章结论..................................................19结束语......................................................20参考文献......................................................21１.２求最短路径给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1.2.1单源最短路径问题DIJKSTRA提出按各顶点与源点V间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点V到其它各顶点的最短路径全部求出为止。１.３求最小生成树对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：湖南涉外经济学院本科学生课程设计（论文）TE,W(U,V)TE表示T的边集W(U，V)表示边(U，V)的权。权最小的生成树称为G的最小生成树(MINIMUMSPANNINGTREE)。最小生成树可简记为MST。最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(U，V)是G中一条“一个端点在U中(例如：U∈U)，另一个端点不在U中的边(例如：V∈V-U)，且(U，V)具有最小权值，则一定存在G的一棵最小生成树包括此边(U，V)。公园导游图第一章前言1第一章前言1.1课题的研究背景、要求和意义现代公园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。应用文件的读写来进行文件操作。查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用深度优先遍历实现。对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份，再出现对应的界面。1.2课题的目标、研究范围实现的目标：实现对某一个公园导游及地图的修改与更新的系统。通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。综合运用数据结构课程中学到的几种典型数据结构，如链表，栈，队列，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发，对自己学过的知识进一步的加深理解，对数据结构的算法思想要有更深的理解。图（Graph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树公园导游图第一章前言2形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其该子结点）相关，但只能和上一层中一个元素（即其双亲结点）相关，而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。1.3理论技术方案的选取邻接矩阵存储结构对图的构造操作的实现框架，他根据图G的种类调用具体构造算法。如果G是无向图，则构造一个具有n个顶点和e条边的无向网G的时间复杂度是O（n2+e*n），其中对邻接矩阵G.arcs的初始化耗费了O（n2）的时间。这个存储结构上易于实现课题所需的基本操作，在建立邻接表或逆邻接表，时间复杂度为（n+e），需要通过查找才能得到顶点图中位置，时间复杂度为O（n*e）。在邻接表上容易找到任一顶点的的第一个邻接点和下一邻接点，但要判定任意两个顶点（vi和vj）之间是否有边或弧相连，则需要搜索第i个或第j个链表，因此，不及邻接矩阵方便。1.4研究方法基于VisualC++6.0平台编程是当今程序者的青睐，它有着强大的性能、完全丰富的工具及高速的处理速度和完备的兼容性。不仅可以简化编程的设计并且算法应用灵活，使应用程序的开发更为简便。C++是为开发大型程序而研制的，它比C语言困难得多，它功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高、可移植性好，既具有高级语言的优点，又具有低级语言的许多特点，完全适合于编写系统软件；本人就利用上述C++开发软件编写了《公园导游系统》，采用人机互动的操作模式，系统经过显示主界面功能，然后用户的需要操作。1.5结构与安排首先“前言”对研究背景和研究目的作了简单的介绍；其次“系统功能分析”公园导游图第一章前言3对本系的说明和讲解；再次“总体设计”对本系统做了一个简要引导，并且通过“总体设计”对该系统的运行懂得差不