C语言算法与数据结构,旅游景区地图求最短路径 |
您所在的位置:网站首页 › 旅游景点表达心情的语言 › C语言算法与数据结构,旅游景区地图求最短路径 |
背景:
本次作业要求完成一个编程项目。请虚构一张旅游景区地图,景区地图包括景点(结点)和道路(边):地图上用字母标注出一些点,表示景点(比如,以点 A、B、C、D、E、F等(至少6个点)多个表示,其中的两个字母 A 和 B 分别表示景区的入口和出口);点与点之间的连线表示各景点之间的道路,连线的权重表示两景点间的距离。在程序里,请选择适当的数据结构表达你设计的景区地图,请通过编程实现以下功能: 1) 用 printf 语句打印出景区地图:(在word里绘制地图) 2) 为游客提供地图中任意景点相关信息的查询:设计查询指令,用户可以输入这些指令查询每个景点的信息; 3) 计算从某一景点到另一个景点的最短路径:用户输入两个景点的字母代号,程序可以在地图中使用不同于已使用的颜色表达出最短路径; 4) 计算从入口 A 到出口 B 的最短路径; 5) 【选做 1】游客甲从景区入口进入,请用程序帮他自动计算出一条最佳游览路线(通过所有景点且距离最短),最后到达出口。【完成】 6) 【选做 2】某旅游团时间有限,导致其游览的总距离受限,请设计算法,产生一个从入口开始最后回到入口的环路,让他们可以在有限的总距离内游览尽量多的景点。【未做】 姊妹题1【注意下面未给出实现效果图】题目5.景区旅游信息管理系统 【问题描述】 在旅游景区,经常会遇到游客打听从一个景点到另一个景点的最短路径和最短距离, 这类游客不喜欢按照导游图的线路来游览,而是挑选自己感兴趣的景点游览。 为于帮助这类游客信息查询,就需要计算出所有景点之间最短路径和最短距离。 算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一个景区旅游信息管理系统, 实现的主要功能包括制订旅游景点导游线路策略和制订景区道路铺设策略。 【任务要求】 (1)设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息: 以边表示路径,存放路径长度等相关信息。任务中景点分布是一个无向带权连通图, 图中边的权值是景点之间的距离。景区旅游信息管理系统中制订旅游景点导游线路策略,首先通过遍历景点,给出一个入口景点, 建立一个导游线路图,导游线路图用有向图表示。遍历采用深度优先策略,这也比较符合游客心理。 (2)为了使导游线路图能够优化,可通过拓朴排序判断图中有无回路,若有回路,则打印输出回路中的景点,供人工优化。 (3)在导游线路图中,还为一些不愿按线路走的游客提供信息服务,比如从一个景点到另一个景点的最短路径和最短距离。 在本线路图中将输出任意景点间的最短路径和最短距离。 (4)在景区建设中,道路建设是其中一个重要内容。道路建设首先要保证能连通所有景点,但又要花最小的代价, 可以通过求最小生成树来解决这个问题。本任务中假设修建道路的代价只与它的里程相关。 因此归纳起来,本任务有如下功能模块: 1)创建景区景点分布图; 2)输出景区景点分布图(邻接矩阵) 3)输出导游线路图; 4)判断导游线路图有无回路: 效果: 要求1-4 要求5[选做1] 源码获取欢迎大家点赞、收藏、关注、评论、批评啦 、查看👇🏻👇🏻获取联系方式👇🏻👇🏻 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |