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

题目公园导游图
题目公园导游图
课程名称：数据结构
本科学生课程设计（论文）
湖南涉外经济学院本科学生课程设计（论文）
湖南涉外经济学院本科学生课程设计(论文)
摘要
随着中国经济不断的发展，城市发园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。
对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。
采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。应用文件的读写来进行文件操作。
查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用深度优先遍历实现。
对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份，再出现对应的界面。
、研究范围
实现的目标：实现对某一个公园导游及地图的修改与更新的系统。
通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。
综合运用数据结构课程中学到的几种典型数据结构，如链表，栈，队列，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发，对自己学过的知识进一步的加深理解，对数据结构的算法思想要有更深的理解。
图（Graph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其该子结点）相关，但只能和上一层中一个元素（即其双亲结点）相关，而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。
公园导游图第一章前言
公园导游图第一章前言
2
3

邻接矩阵存储结构对图的构造操作的实现框架，他根据图G的种类调用具体构造算法。如果G是无向图，则构造一个具有n个顶点和e条边的无向网G的时间复杂度是O（n2+e*n）,其中对邻接矩阵Garcs的初始化耗费了O（n2）的时间。这个存储结构上易于实现课题所需的基本操作，在建立邻接表或逆邻接表，时间复杂度为（n+e），需要通过查找才能得到顶点图中位置，时间复杂度为O（n*e）。
在邻接表上容易找到任一顶点的的第一个邻接点和下一邻接点，但要判定任意两个顶点（vi和vj）之间是否有边或弧相连，则需要搜索第i个或第j个链表，因此，不及邻接矩阵方便。

基于VisualC++，它有着强大的性能、完全丰富的工具及高速的处理速度和完备的兼容性。不仅可以简化编程的设计并且算法应用灵活，使应用程序的开发更为简便。C++是为开发大型程序而研制的，它比C语言困难得多，它功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高、可移植性好，既具有高级语言的优点，又具有低级语言的许多特点，完全适合于编写系统软件；本人就利用上述C++开发软件编写了《公园导游系统》采用人机互动的操作模式，系统经过显示主界面功能，然后用户的需要操作。

首先“前言”对研究背景和研究目的作了简单的介绍；其次“系统功能分析”
公园导游图第一章前言
公园导游图第一章前言
2
3
对本系的说明和讲解；再次“总体设计”对本系统做了一个简要引导，并且通过“总体设计”对该系统的运行懂得差不多了；“详细设计”就是对系统有了详细的设计过程，更进一步知道设计原理；“排序算法的改进”介绍传统算法的不足，经过设想对原算法加以改进“系统实现”不但让我们知道了系统的界面和一些操作的实施，让你知道整个算法的设计并且加以理解。
公园导游图第二章系统功能分析
公园导游图第二章系统功能分析
4
5
第二章系统功能分析

所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并