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

课程名称:数据结构
湖南涉外经济学院
本科学生课程设计(论文)
题目公园导游图
姓名唐哲
学号
学部计算机科学与技术
专业、年级
指导教师
2011 年 12 月 8 日
摘要
随着中国经济不断的发展,城市发展的越来越好,越来越多的人融入了城市生活。公园成为人们散心,娱乐的场所,公园也随即也在不断的扩张,变得越来越全面,但是这不利于逛公园的人寻找自己想要去的地方,尤其是对公园陌生的游客,更是不知道如何走,才能更好的游玩公园,达到的最好经济效益。所以针对这种现象,为了方便游客,开发这么一款公园导游系统软件。
系统是用C语言实现,基于visual c++ 开发的,采用图这么一种数据结构,采用邻接矩阵的存储方式,用一个二维数组来记录所有的边,为了实现地图的随时更新,采用了静态链表实现对图的接点的添加,删除。
本系统设计基于图的结构,创建一个无向图,针对游客的需求,将涉外公园的景点编号、名称、介绍等信息放入到图的顶点当中并保存景点文本文件中,将两个景点的编号和它们之间的距离当权值也保存在相同的文本文件中,利用迪杰特斯拉算法来求从一个景点到另一个景点的最短距离,利用Serach();查找景点,本显示他的信息,从而解决了要查找景点信息和两个景点之间的最短路径的问题,最后按照显示屏上的提示进行相关的操作。
关键词: 公园导游;图;邻接矩阵;二维数组;静态链
目录
第一章前言 1
、要求和意义 1
、研究范围 1
2
2
2
第二章系统功能分析 4
可行性分析 4
4
工具可行性 4
经济可行性 4
操作可行性 5
需求分析 5
功能需求 5
输入输出的要求 5
第三章总体设计 6
程序模块 6
系统涉及的数据结构 6
程序数据结构 7
具体数据类型定义 7
第四章详细设计 9
创建图(Fprint-Link) 9
寻找最佳路径(DFSTraverse) 9
最短路径(ShortPath) 10
遍历出某一起点到终点的所有路径(SearchAllPath) 12
导入新文件(Loadnewmap) 13
第五章系统实现 14
程序执行之前的准备 14
主界面 14
游客界面 15
系统用户界面 15
浏览公园全景简图 16
寻找某一起点的最佳路径和指定起点、终点的最短路径 16
寻找指定起点、终点的所有路径 17
删除,添加结点,保存和导入新地图 17
第六章解决的关键问题 18
如何实现寻找最短路径功能 18
如何实现深度优先搜索 18
如何修改地图 18
18
第七章结论 19
结束语 20
参考文献 21
第一章前言
、要求和意义
现代公园范围的广阔,内容不断的增加,使得公园整个系统变得复杂。使用电脑对游客进行导游成为发展的趋势,以达到更好的为游客服务的目的。
对于公园的游客来说,他们要求:能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户来说,他们要求:删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。
采用图这么一种数据结构,采用邻接表的存储方式,用一个二维数组来记录所有的边,为了实现地图的随时更新,采用了静态链表实现对图的接点的添加,删除。应用文件的读写来进行文件操作。
查找最短路径采用迪杰特斯拉算法实现,从任意景点遍历全部的景点采用深度优先遍历实现。
对于界面设计,游客不能进行地图的修改,更换,所以首先要验证身份,再出现对应的界面。
、研究范围
实现的目标:实现对某一个公园导游及地图的修改与更新的系统。
通过系统分析、系统设计、编程调试,写实验报告等环节,进一步掌握应用系统设计的方法和步骤,灵活运用并深刻理解典型数据结构在软件开发中的应用。
综合运用数据结构课程中学到的几种典型数据结构,如链表,栈,队列,以及程序设计语言(C语言),自行实现一个较为完整的应用系统的设计与开发,对自己学过的知识进一步的加深理解,对数据结构的算法思想要有更深的理解。
图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素