公园的导游图样本.doc

用C++语言设计一个公园导游图摘要现实生活中,常常会碰到求最短路径问题。本课程设计意在提供一个处理这类问题实例,把某一公园景点和路线抽象成顶点和边,从而组成图,进而处理一系列相关最短路径,最好路线等问题。在课程设计中,系统开发平台为WindowsXP,程序设计设计语言采取C++,程序运行平台为Windows98//XP。对于求解最短路径,使用了著名Dijkstra算法。对于求最好路径,采取了常见于处理TSP问题贪心法。程序经过调试运行,初步实现了设计目标,而且经过合适完善后,这一导游图系统将一样适适用于其它公园。关键词程序设计;数据结构;图;最短路径;Dijkstra算法;TSP问题1引言现实生活中,常常会碰到求最短路径问题,本课程设计将把这类问题实例化,把一个公园景点顶点化、路径边化,建成一个图,再经过比较对图中各边及顶点关系,实现对公园各个景点进行访问,并能依据要求,求出任意两个顶点最短路径,还能给出一条依次不反复访问各点最短路径。【这部分应写明前人相关研究结果、理论和实践依据,内容可包含研究目标、意义、关键方法、范围和背景等。】伴随计算机科学快速发展,计算机已深入到揉社会各个领域,它应用已不再局限于科学计算,以处理部分数学问题,而且能够处理部分抽象化具体问题,更多地用于控制,管理及数据处理等非数值计算处理工作,这便为我们日常生活提供了很多方便,譬如说火车售票系统,学生成绩管理,车厢调度等实际问题。现在程序设计语言很多,有发展比较完善高级语言,也有最基础低级语言,然而再好程序设计也要有一个比较清楚思绪——算法。为了编写好一个好程序,必需分析待处理对象特征和各处理对象之间关系,于是数据结构便成为我们绝佳选择。数据结构是计算机程序设计关键理论技术基础,它不仅是计算机科学关键课程,而且已成为其它理工专业热门选修课。,最少应该有一个简单景点分布图,让游客能对公园概况一目了然。其次,应该能提供相关景点信息:包含景点名称,景点介绍等。以上功效是基础,在此基础上,使公园导游图系统更具人性化,更含有实用性:为导游图系统添加景点最短路径计算,提供依次不反复访问全部景点最好旅游路线。,还需要有清爽,简易操作界面,让游客一目了然,操作方便。本导游图用数字键选择方法,加以提醒,。,已经计划好导游图系统功效和操作基础构架,下一步就是着手为每一个操作实现做程序实现考虑了。3程序算法分析要完成对整个导游图系统功效实现,需要正确每一项功效全部有清楚设想和认识,了解并明确每一项功效实现需要处理问题,选择正确而且高效算法把问题逐一处理,最终实现程序正确调试运行。为此,可把系统分为以下多个关键:图初始化、图遍历、求两点间最短路径、求最好路线。,表现在不仅各个顶点度能够相差很多,而且顶点之间逻辑关系——邻接关系也错综复杂[1]。从图定义可知,一个图包含两部分信息:顶点信息和描述顶点之间关系(边或弧)信息。图初始化是全部相关操作基础,其存放结构将直接影响到程序实现难易度、空间性能和时间性能,所以选择适合此次程序存放结构至关关键。图存放结构有邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等多个,较常见有邻接矩阵和邻接表,而这二者存放方法比较如表3-1。表3-1邻接矩阵和邻接表存放结构比较存放方法空间性能比较时间性能比较唯一性比较邻接矩阵O(n2)O(n2)唯一邻接表O(n+e)O(n+e)非唯一图邻接矩阵和邻接表存放各有利弊,应用时要依据图稠密和稀疏程度和问题需求进行选择[2]。仔细比较这两种存放方法轻易知道,因为邻接矩阵特殊存放方法,,它很便于快速查找两个顶点之间边上权值。所以,图采取带权邻接矩阵存放。V2V1V4V3V04375792Vertex[5]=V0V1V2V3V4∞∞957∞∞34∞Arc[5][5]=93∞72547∞∞7∞2∞∞,需要有一个公园实例,本程序选择本人所在地姑婆山国家森林公园游览地图作为蓝本,把公园地图抽象化成顶点和边组成图形式,,途中红色数字代表线权值。。图遍历是指从图中某一顶点出发,对图中全部顶点访问一次且仅访问一次。导游图需要把每条路径信息全部向游客展示,就需要读取每两个顶点间路径信息。因为采取了带权邻接矩阵存放结构进行存放,所以需要针对这一存放结构对路线进行遍历操作。,。选择图片控件For循环语句(i=0;i<顶点数;i+