课程名称：数据结构
湖南涉外经济学院
本科学生课程设计（论文）
题 目 公园导游图 姓 名 唐 哲 学 号 学 部 计算机科学与技术 专业、年级
指 导 教 师
2011 年 12 月 8 日
湖南涉外经济学院本科学生课程设计（论文）
摘 要
随着中国经济不断的发展，城市发展的越来越好，越来越多的人融入了城市生活。公园成为人们散心，娱乐的场所，公园也随即也在不断的扩张，变得越来越全面，但是这不利于逛公园的人寻找自己想要去的地方，尤其是对公园陌生的游客，更是不知道如何走，才能更好的游玩公园，达到的最好经济效益。所以针对这种现象，为了方便游客，开发这么一款公园导游系统软件。
系统是用C语言实现，基于visual c++6.0 开发的，采用图这么一种数据结构，采用邻接矩阵的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。
本系统设计基于图的结构，创建一个无向图，针对游客的需求，将涉外公园的景点编号、名称、介绍等信息放入到图的顶点当中并保存景点文本文件中，将两个景点的编号和它们之间的距离当权值也保存在相同的文本文件中，利用迪杰特斯拉算法来求从一个景点到另一个景点的最短距离，利用Serach（）；查找景点，本显示他的信息，从而解决了要查找景点信息和两个景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。
关键词： 公园导游；图；邻接矩阵；二维数组；静态链
湖南涉外经济学院本科学生课程设计（论文）
目 录
第一章 前 言 ................................................... 1 1.1课题的研究背景、要求和意义 .................................. 1 1.2课题的目标、研究范围 ........................................ 1 1.3理论技术方案的选取 .......................................... 2 1.4研究方法 .................................................... 2 1.5结构与安排 .................................................. 2 第二章 系统功能分析 ............................................ 4 2.1 可行性分析 ................................................. 4
2.1.1技术可行性 ............................................ 4 2.1.2 工具可行性 ........................................... 4 2.1.3 经济可行性 ........................................... 4 2.1.4 操作可行性 ........................................... 5 2.2 需求分析 ................................................... 5
2.2.1 功能需求 ............................................. 5 2.2.2 输入输出的要求 ....................................... 5 第三章 总体设计 ................................................ 6 3.1 程序模块 ................................................... 6 3.2 系统涉及的数据结构 ......................................... 6
3.2.1 程序数据结构 ......................................... 7 3.2.2 具体数据类型定义 ..................................... 7 第四章 详细设计 ................................................ 9 4.1 创建图（FPRINT-LINK） ........................................ 9 4.2 寻找最佳路径（DFSTRAVERSE） .................................. 9 4.3 最短路径（SHORTPATH） ....................................... 10 4.4 遍历出某一起点到终点的所有路径（SEARCHALLPATH） ............. 12 4.5 导入新文件（LOADNEWMAP） .................................... 13 第五章 系统实现 ............................................... 14 5.1 程序执行之前的准备 ........................................ 14 5.2 主界面 .................................................... 14 5.3 游客界面 .................................................. 15 5.4 系统用户界面 .............................................. 15
湖南涉外经济学院本科学生课程设计（论文）
5.5 浏览公园全景简图 .......................................... 16 5.6 寻找某一起点的最佳路径和指定起点、终点的最短路径 .......... 16 5.7 寻找指定起点、终点的所有路径 .............................. 17 5.8 删除，添加结点，保存和导入新地图 .......................... 17 第六章 解决的关键问题 ......................................... 18 6.1 如何实现寻找最短路径功能 .................................. 18 6.2 如何实现深度优先搜索 ...................................... 18 6.3 如何修改地图 .............................................. 18 6.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的最小生成树(MINIMUM SPANNING TREE)。最小生成树可简记为MST。
最小生成树性质：
设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(U，V)是G中一条“一个端点在U中(例如：U∈U)，另一个端点不在U中的边(例如：V∈V-U)，且(U，V)具有最小权值，则一定存在G的一棵最小生成树包括此边(U，V)。
公园导游图数据结构课程设计
