公园导游管理系统

计算机信息工程学院 数数 据据 结结 构构 课课 程程 设设 计计 报报 告告 题 目 公园导游系统 专 业 计算机科学与技术 软件方向 班 级 学 号 姓 名 指导教师 完成日期 目目 录录 一 概要设计一 概要设计 1 1 题目的内容与要求 1 1 1 程序模块 6 1 2 系统涉及的数据结构 6 1 2 1 程序数据结构 7 1 2 2 具体数据类型定义 7 二 详细设计二 详细设计 2 2 1 创建图 FPRINT LINK 9 2 2 寻找最佳路径 DFSTRAVERSE 9 2 3 最短路径 SHORTPATH 10 2 4 遍历出某一起点到终点的所有路径 SEARCHALLPATH 12 2 5 导入新文件 LOADNEWMAP 13 三 测试分析三 测试分析 5 3 1 可行性分析 4 3 1 1 技术可行性 4 3 1 2 工具可行性 4 3 1 3 经济可行性 4 3 1 4 操作可行性 5 3 2 需求分析 5 3 2 1 功能需求 5 3 2 2 输入输出的要求 5 四 使用说明与执行结果四 使用说明与执行结果 6 4 1 主界面 14 4 2 游客界面 15 4 3 系统用户界面 15 附附 录 程序清单 录 程序清单 8 一 概要设计 1 题目的内容与要求题目的内容与要求 1 1 课题的研究背景 要求和意义 现代公园范围的广阔 内容不断的增加 使得公园整个系统变得复杂 使 用电脑对游客进行导游成为发展的趋势 以达到更好的为游客服务的目的 对于公园的游客来说 他们要求 能够浏览整个公园的信息 查询每一个 景点的信息 从任意景点遍历全部的景点 能够查找最短路径 对于系统用户 来说 他们要求 删除地点 添加地点 添加路径 删除路径 保存修改 导 入文件数据 采用图这么一种数据结构 采用邻接表的存储方式 用一个二维数组来记 录所有的边 为了实现地图的随时更新 采用了静态链表实现对图的接点的添 加 删除 应用文件的读写来进行文件操作 查找最短路径采用迪杰特斯拉算法实现 从任意景点遍历全部的景点采用 深度优先遍历实现 对于界面设计 游客不能进行地图的修改 更换 所以首先要验证身份 再出现对应的界面 2 总体设计总体设计 程序模块 从文件中对出数据 Fprint Link 通过调用 Update L g 先将链表 L 的信 息赋值给邻接数组 g 中 进行更新 建立无向图 把公园的景点及景点的信 息 连接起来建立邻接表采用链式加顺式存储 浏览学校的全景 Browser 列出学校的所有的景点 寻找最佳路径 DFSTraverse 输入一个景点 会吧所有都浏览一边 并找出最佳的路径 最短路径 ShortPath 求出起点和终点的最佳路径 并求出最佳路径的长 度 遍历出某一起点到终点的所有路径 SearchAllPath 找出所有路径 利 用深度优先遍历 删除地点 添加地点 添加路径 删除路径 保存修改 导入文件数据 对应代码函数如下 DeleteAdv L g InsertAdv L g InsertEdge DeleteEdge SaveMap g Loadnewmap p g 总体结构设计如图 1 1 所示 图 1 1 系统框架图 3 系统数据结构系统数据结构 3 1 程序数据结构 程序主要用了图和静态链表两种数据结构 采用矩阵来保存图形结构的地 图 用数组来保存遍历经过的结点用以遍历回溯 以及存储最最终路径 图的抽象数据类型 ADT Graph 数据对象 V V 是具有相同特性的数据元素的集合 称为顶点集 数据关系 R VR VR v w v 且 P v w 表示从 v 到 w 的弧 谓词 P v w 定义了弧的意义或信息 基本操作 P PrintMap g Serach g 删删 除除 地地 点点 主模块主模块 系统用户系统用户游客模块游客模块 添添 加加 地地 点点 添添 加加 路路 径径 删删 除除 路路 径径 保保 存存 存存 修修 改改 入入 文文 件件 数数 据据 任任 意意 景景 点点 遍遍 历历 查询查询 景点景点 信息信息 和浏和浏 览公览公 园简园简 图图 查询查询 任意任意 两个两个 景点景点 最短最短 的路的路 径径 遍历遍历 输出输出 任意任意 一个一个 景点景点 的所的所 有路有路 径径 DFSTraverse g ShortPath g ADT Graph 线性链表的抽象数据类型 ADT List 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 DeleteAdv L g InsertAdv L g InsertEdge DeleteEdge SaveMap g Loadnewmap p g ADT List 3 2 2 具体数据类型定义 typedef struct LNode char name 30 int num char introduction 100 struct LNode next LNode Link typedef struct ArcNode int data 该弧所得指向的顶点的位置 ArcNode nextarc 指向下一条弧的指针 ArcNode ArcLink typedef struct VNode 顶点信息 char name 30 int num char introduction 100 ArcLink firstarc 指向第一条依附该顶点的弧的指针 VNode AdjList MAX 1 typedef struct ALGraph AdjList vdata int vexnum arcnum 图的顶点数和弧数 ALGraph int Edge MAX MAX 用来存放路径的权值 int n e 存放结点数和边数 读取文件信息代码如下 for i 1 i n i fscanf fp d fscanf fp s name fscanf fp s information ListInsert L num name information Update L g for j 1 jdata a p nextarc g b firstarc g b firstarc p 把 p 插进来 q ArcLink malloc sizeof ArcNode q data b q nextarc g a firstarc g a firstarc q 二 详细设计 2 1 创建图 Fprint Link 从文件中读出数据 函数流程图 2 1 所示 结束结束 j 开始开始 读入读入 n e ArcLink p q 初始化链表 邻接表 初始化链表 邻接表 Eage i 1 j 1 p q ArcLink malloc sizeof ArcNode inextarc g b firstarc g b firstarc p 把把 p 插进来插进来 q nextarc g a firstarc g a firstarc q j e N Update L g 给给 g 赋值赋值 图 2 1 Fprint Link 函数流程图 2 2 寻找最佳路径 DFSTraverse 利用深度优先的思想 遍历图找出一条最佳最佳的的路径 让它遍历所有 景点 利用递归的思想 往下遍历 访问标志位 若访问过在下次就不用访问 若找完一个分支在下次重新遍历 函数流程如图 2 2 所示 开始开始 初始化初始化 visit v 0 初始化初始化 标标志位 If visit v 0 DFS g v visited v Count Count n 结束结束 Y 图 2 2 寻找最佳路径流程图 2 3 最短路径 ShortPath 利用迪杰特斯拉算法 求 v0 到其余顶点的最短路径 path distance 是用来 存放各路径的权值 借助辅助数组 s 标志 是否当前顶点属于 S 1 属于 函数流 程 图 2 3 所示 开始开始 初始化初始化 distence s path 开始主循环开始主循环 每次求得 每次求得 v0 到某顶点到某顶点 v 的最短距离 并将的最短距离 并将 v 并入中并入中 minDis MAXEDGE 当前所知当前所知 v0 的最短距离并设初值为的最短距离并设初值为 MAXEAGE int i 1 j 1 u v0 s j 在在 s 下一直往下找下一直往下找 minDis distance j j n j 0 更新当前最短路径及距离 更新当前最短路径及距离 newDist distance u GetWeight u distance j newDist path j u 记录寻找的最短记录寻找的最短 的路径的路径 i n 结束结束 If newDist distance j J n Y N Y N Y Y N 图 2 3 寻找最短路径流程图 2 4 遍历出某一起点到终点的所有路径 SearchAllPath 利用图的深度优先遍历 利用访问标志位 path 记录路径 visited 设访问标志 v 起点 des 终点 length 代表的是访问景点的长度 若碰见死 路或者不同的路 则从上一个景点 从新扫描 searchAllPath 流程如图 2 4 所 示 If visited V returen 若所有景点若所有景点 都访问过 则终止都访问过 则终止 v des PrintfPath G path length visited v 1 GetWeight v i MAXE DG N Y 图 2 4 searchAllPath 流程图 2 5 导入新文件 Loadnewmap 将指定文件导入到邻接表中 再保存到 zheke1 txt 中 具体实现如图 2 5 所示 开始 初始化Link p 输入文件名 filename 20 Fprint Link p g filename SaveMap g L P 结束 图 2 5 导入新文件结构示图 三 测试分析 3 1 可行性分析 所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够 解决 这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程 也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程 可行性研 究的最根本任务是对以后的行动方针提出建议 以避免时间 资源 人力和金 钱的浪费 推荐一个较好的解决方案 并且为工程制定一个初步的计划 3 1 1 技术可行性 查找最短路径以及查询任意两景点之间的所有路径采用迪杰特斯拉算法或 弗洛伊德算法实现 解决这个问题的一个方法是 每次以一个顶点为源点 重 复执行迪杰斯特拉算法 n 次 这样 便可求得每一对顶点之间的最短路径 总 的执行时间为 O n3 虽然弗洛伊德算法时间复杂度也是 O n3 但形式简 单些 从任意景点遍历全部的景点采用深度优先遍历或广度优先搜索遍历图实现 所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够 解决 这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程 也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程 可行性研 究的最根本任务是对以后的行动方针提出建议 以避免时间 资源 人力和金 钱的浪费 推荐一个较好的解决方案 并且为工程制定一个初步的计划 本系统采用人机操作进行管理 用 visual C 6 0 进行前台设计 系统随机 产生数据 用户通过界面操作 系统自动给予合理分析 由于 visual C 6 0 功 能强大 使用的灵活 良好的可扩展性 以及广泛实际应用 充分说明本系统 在技术方面的可行性 3 1 2 工具可行性 软件方面 信息时代对于软件的应用已不是人们的难题 人们在日常办公中用的计算 机操作的系统等都属于软件部分 硬件方面 计算机普及到今天 人们对于它的拥有已不少见 它的硬件设备完全能够 满足人们的需求 而价格也能被人们所接受 3 1 3 经济可行性 线在大多数的公园景点及内容不断的增多和丰富 这也就使得整个公园系 统不得不建立的更大 这也就为人们逛公园造成了很大的不便 人们往往不熟 悉公园 找个东西 或某处带来了极大的不便 往往要花很多时间在这一方面 然而要是有一个公园导游系统这将给乘客带来极大的方便 使人们一下就能了 解到这个公园的大致的情况 这是个超小型的性能分析系统 从投入的人力 财力与物力来讲是非常之 小的 只要一台电脑 一台打印机 这个系统就可以搞起来 考虑到学校里有 电脑 现只要购置一台打印机就可以了 从节省人力方面 可以让管理人员从 繁与复杂的工作中解脱出来 做更多的工作 可以给读者提高到更深的一个层 次 3 1 4 操作可行性 本系统设计清晰 有良好的用户接口 操作简洁 完全可以给用户解决 并达到操作过程中的直观 方便 实用 安全等要求 因此操作方面具有可行 性 3 2 需求分析 3 2 1 功能需求 对于游客 系统功能需求如下 能够浏览整个公园的信息 查询每一个景 点的信息 从任意景点遍历全部的景点 能够查找最短路径 对于系统后台操作功能需求如下 删除地点 添加地点 添加路径 删除 路径 保存修改 导入文件数据 3 2 2 输入输出的要求 程序执行是需要有描述地图的文件 并放在相应的位置 文件中开始位置 存放景点个数 图存在多少条边 接着是存放景点序号 名称 相关信息 对 后是存放着各个景点之间的距离矩阵 执行程序先要先要进行选择 修改地图是要验证密码 查找任意两个景点的最短路径时 输入查找最短路径的两个点 运行各个 小过程要求要输出的暂时的结果 四 使用说明与执行结果 4 1 主界面 图 4 1 主界面 4 2 游客界面 图 4 2 游客界面 4 3 系统用户界面 图 4 3 系统用户登录界面 图 4 4 系统用户界面 4 5 浏览公园全景简图 4 5 涉外公园简图 4 6 详细信息表 4 6 寻找某一起点的最佳路径和指定起点 终点的最短路径 图 4 7 查询最佳路径 图 4 8 查询最短路径 4 7 寻找指定起点 终点的所有路径 图 4 9 输入两点之间的所有路径 4 8 删除 添加结点 保存和导入新地图 图 4 10 删除结点 图 4 10 导入新的地图 附 录 程序清单 include include define INT MAX 10000 define n 10 int cost n n 边的值 int shortest n n 两点间的最短距离 int path n n 经过的景点 void welcome printf n 欢迎光临 n printf n 凝香公园 n n n n n printf n 给您最纯净的享受 n printf n Pure as the south polar snow n n printf n system pause void Menu 函数的主显示界面 system cls system color 70 printf n printf 凝香公园导游系统 n printf n printf n printf n printf n printf 1 浏览公园全景 n printf n printf 2 最佳游览路线 n printf 主 n printf 3 查看单个景点 n printf 菜 n printf 4 游览线路查询 n printf 单 n printf 5 凝香公园简介 n printf n printf 6 退出导游系统 n printf n printf n printf n printf n printf n printf n n 请按键选择 void Browser printf n 公园全景图 n printf n printf n printf 紫金大道 n printf 北 n printf n printf 1 沁园 2 公园大门 n printf n printf n printf 3 梨园 4 春 园 10 夏园 n printf n printf n printf 5 鼎湖 8 秋园 9 冬园 n printf n printf n printf n printf 6 聚缘阁 7 凝香园 n printf n printf n printf 2012 年 7 月 4 日 n printf n void place char z printf n n n 公园简介 n printf n n 凝香园也称 正春园 位于菏泽城东岳程办事处岳楼行政村 n n printf 始建于元末明初 原为袁姓所有 称 袁家堂 花园 n n printf 凝香园是我国古代北方八大名园之一 俗称 何家花园 距今有近 1000 余年 的历史 n n printf 园中有百多年的刺柏 几百年的腊梅 紫丁香 千年翠兰松和一块假山石 n n printf 凝香园 附近的何应瑞墓地古柏成林 苍郁参天 n n printf n 注 本公园和真正的 凝香园 是同名 而非真实园林 n printf n n n printf n n n 请输入任意字符 返回主菜单 n z getchar z getchar void go printf n n n n n n 感谢使用 n printf n printf n printf n printf 请按任意键退出 n printf n printf n printf 程序制作 陈 明 n printf 学号 3100931036 n printf n n n n n n exit 0 void way char z printf n n printf 本公园的最佳全景游览路线为 n n printf 2 公园大门 1 沁园 3 梨园 5 鼎湖 6 聚缘阁 7 凝香园 4 春园 8 秋 园 9 冬园 10 夏园 2 公园大门 n printf 全程所需行程 276 米 n n printf 如需其他路线请返回主菜单进入 浏览路线查询 n printf n n n printf n n n 请输入任意字符 返回主菜单 n z getchar z getchar void introduce 景点介绍 int a char z printf 请输入您想查询的景点编号 scanf d getchar printf n n 查询结果 n n switch a case 1 printf 1 沁园 n n 一首 沁园春 雪 让您对眼前的梅花感慨万千 n break case 2 printf 2 公园大门 n n 仿古的气势宏伟建筑仿佛置身于 100 年前 n break case 3 printf 3 梨园 n n 丛林间嬉戏的小鸟不禁让你回头倾听 n break case 4 printf 4 春园 n n 广阔的草地伴着阵阵花香 躺在上面可以仰望南天 n break case 5 printf 5 鼎湖 n n 圆滑的湖面仿佛一面大鼎将湖水撑起来 n break case 6 printf 6 聚缘阁 n n 来自大江南北的古玩古画齐聚一堂 n break case 7 printf 7 凝香园 n n 神奇的南方小筑隐匿在桂花林中 聚香也 n break case 8 printf 8 秋园 n n 当你独自一人行走在大片阔叶林里 才能感受自然的气息 n break case 9 printf 9 冬园 n n 冬日恋歌在这里尽情唱响 High 起来吧 n break case 10 printf 10 夏园 n n 荷花池中一抹红 荷塘月色任你赏 n break default printf Error 景点编号输入错误 请输入 1 10 的数字编号 n n break printf n n void floyed 用 floyed 算法求两个景点的最短路径 int i j k for i 1 i n i for j 1 j n j shortest i j cost i j path i j 0 for k 1 k n k for j 1 j n j for i 1 i shortest i k shortest k j 用 path 记录从 i 到 j 的最短路径上点 j 的前驱景点的序号 shortest i j shortest i k shortest k j path i j k path j i k void display int i int j 打印两个景点的路径及最短距离 int a b a i b j printf n 查询结果 n n printf 路径 if shortest i j INT MAX if i j printf d b while path i j 0 把 i 到 j 的路径上所有经过的景点按逆序打印出来 printf d path i j if i j j path i j else i path j i printf d a printf n n printf 距离 您需要步行 dm 才能到达目的地 shortest a b else printf d a while path i j 0 把 i 到 j 的路径上所有经过的景点按顺序打印出来 printf d path i j