公园的导游图

《公园的导游图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《用C++语言设计一个公园的导游图》第26页共26页用C++语言设计一个公园的导游图摘要现实生活中，常常会遇到求最短路径的问题。本课程设计旨在提供一种解决这类问题的实例，把某一公园的景点与路线抽象成顶点和边，从而构成图，进而解决一系列相关的最短路径，最佳路线等问题。在课程设计中，系统开发平台为WindowsXP，程序设计设计语言采用C++，程序运行平台为Windows98/2000/XP。对于求解最短路径，使用了著名的Dijkstra算法。对于求最佳路径，采用了常用于解决TSP问题的贪心法。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，这一导游图系统将同样适用于其他公园

2、。关键词程序设计；数据结构；图；最短路径；Dijkstra算法；TSP问题《用C++语言设计一个公园的导游图》第26页共26页1引言现实生活中，常常会遇到求最短路径的问题，本课程设计将把这类问题实例化，把一个公园的景点顶点化、路径边化，建成一个图，再通过比较对图中各边及顶点的关系，实现对公园各个景点进行访问，并能根据要求，求出任意两个顶点的最短路径，还能给出一条依次不重复访问各点的最短路径。【这部分应写明前人相关的研究成果、理论与实践依据，内容可包括研究的目的、意义、主要方法、范围和背景等。】随着计算机科学的迅速发展，计算机已深入到揉社会的各个领域，它的应用已不再局限于科学计算，以

3、解决一些数学问题，而且可以解决一些抽象化的具体问题，更多地用于控制，管理及数据处理等非数值计算的处理工作，这便为我们的日常生活提供了很多的方便，譬如说火车售票系统，学生成绩管理，车厢调度等实际问题。如今程序设计的语言很多，有发展比较完善高级语言，也有最基本的低级语言，然而再好的程序设计也要有一个比较清晰的思路——算法。为了编写好一个好程序，必须分析待处理对象的特性以及各处理对象之间的关系，于是数据结构便成为我们绝佳的选择。数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。《用C++语言设计一个公园的导游图》第26页共26页

4、2程序的功能需求分析2.1程序的功能分析一个公园的导游图，至少应该有一个简单的景点分布图，让游客能对公园概况一目了然。其次，应该能提供相关的景点信息：包括景点名称，景点简介等。以上功能是基础，在此基础上，使公园的导游图系统更具人性化，更具有实用性：为导游图系统添加景点最短路径的计算，提供依次不重复访问所有景点的最佳旅游路线。2.2菜单项及其基本操作拥有了完整的功能的导游图系统，还需要有清爽，简易的操作界面，让游客一目了然，操作方便。本导游图用数字键的选择方式，加以提示，提供给用户如图2.1的简单方便的操作。图2.1抽象化的公园导游图至此，已经规划好导游图系统的功能和操作的基本构架，

5、下一步就是着手为每一个操作的实现做程序实现的考虑了。《用C++语言设计一个公园的导游图》第26页共26页3程序的算法分析要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。为此，可把系统分为以下几个核心：图的初始化、图的遍历、求两点间的最短路径、求最佳路线。3.1图的初始化图是一种复杂的数据结构，表现在不仅各个顶点的度可以相差很多，而且顶点之间的逻辑关系——邻接关系也错综复杂[1]。从图的定义可知，一个图包括两部分信息：顶点的信息以及描述顶点之间关系（边

6、或弧）的信息。图的初始化是所有相关操作的基础，其存储结构将直接影响到程序的实现的难易度、空间性能和时间性能，因此选择适合本次程序的存储结构至关重要。图的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等多种，较常用的有邻接矩阵和邻接表，而这两者的存储方式的比较如表3-1。表3-1邻接矩阵与邻接表存储结构的比较存储方式空间性能比较时间性能比较唯一性比较邻接矩阵O(n2)O(n2)唯一邻接表O(n+e)O(n+e)非唯一图的邻接矩阵和邻接表存储各有利弊，应用时要根据图的稠密和稀疏程度以及问题的需求进行选择[2]。仔细比较这两种存储方式容易知道，由于邻接矩阵特殊的存储方式，如图

7、2.2所示，它非常便于快速的查找两个顶点之间的边上的权值。所以，图采用带权的邻接矩阵存储。《用C++语言设计一个公园的导游图》第26页共26页V2V1V4V3V04375792Vertex[5]=V0V1V2V3V4∞∞957∞∞34∞Arc[5][5]=93∞72547∞∞7∞2∞∞《用C++语言设计一个公园的导游图》第26页共26页图3.1无向图及其邻接矩阵存储示意图《用C++语言设计一个公园的导游图》第26页共26页决定了图的存储方式后，需要有一个公园的实例，本