校园导游系统

精品文档 1欢迎下载 课课 程程 设设 计计 说说 明明 书书 课程名称 数据结构与算法 设计题目 校园导游系统 院 系 计算机科学与信息工程学院 学生姓名 学 号 专业班级 计算机科学与技术信息技术方向 11 1 指导教师 2013 年 6 月 21 日 精品文档 11欢迎下载 课课 程程 设设 计计 任任 务务 书书 设计题目校园导游系统 学生姓名孙玮所在院系 计算机科学与 信息工程学院 专业 年级 班 11 计科信息技 术方向 设计要求 设计要求 用无向网表示你所在学校的校园景点平面图 图中顶点表示主要景点 存放景点 的编号 名称 简介等信息 图中的边表示景点间的道路 存放路径长度等信息 要 求能够回答有关景点介绍 游览路径等问题 学生应完成的工作 学生应完成的工作 孙 玮 图的结构以及初始化 徐开放 一个景点到其他所有景点的最短路径 王彩霞 景点的输出以及查询 梁梦莉 两个景点之间的所有路径 何冉冉 两个景点之间的最短路径 郑银凤 增加 删除 修改景点信息 参考文献阅读 参考文献阅读 1 数据结构 C 语言版 严蔚敏 吴伟民 编著 清华大学出版社 2011 2 C 程序设计 第四版 谭浩强 主编 清华大学出版 工作计划 工作计划 1 第一周的第一天 小组布置设计题目 说明进度安排 2 第一周的第二天 小组审题 查阅资料 进行设计前的必要资料准备 3 第一周的第三天 第四天 第五天 程序编写 上机调试 4 第二周的第一天至第三天 上机调试程序 结果分析 5 第二周的第四天 撰写设计报告 6 第二周的第五天 设计答辩及成绩评定 任务下达日期 2013 年 6 月 10 日 任务完成日期 2013 年 6 月 21 日 指导教师 签名 学生 签名 校园导游系统校园导游系统 精品文档 22欢迎下载 摘摘 要 要 随着社会经济的发展 人们接近自然的机会就越多 因此外出旅游现在被越来越 多的都市人所看中 所以如何快速方便的找到我们想要的旅游景点的信息和最短路径 如何简单的修改相关的信息 就成了很重要的问题 本设计基于图的结构 用数组表示法创建一个无向图 针对游客的实际需求 将 安阳工学院的景点编号 名称 介绍等信息放入到图的顶点当中 将路径长度的信息 存放在弧当中 利用弗洛伊德算法求出两个景点之间的最短路径 利用迪杰斯特拉算 法来求从一个景点到其他剩余的所有景点的最短距离 用相应的函数来查找景点 并 显示出它的编号 信息 简介 并进行一定的界面美化 更贴近用户 相应的提示使 用户操作起来更容易 关键词 关键词 最短路径 查找景点信息 无向图 目目 录录 精品文档 33欢迎下载 1 设计背景 4 1 1 程序设计内容 4 1 2 程序设计要求 4 2 设计方案 5 2 1 校园景点图 5 2 2 程序模块图 5 2 3 主函数设计简要 6 2 4 各函数模块的功能 6 3 方案实施 7 3 1 程序执行流程图 7 3 2 主函数设计思想 7 4 结果测试 9 4 1 主函数功能模块测试 9 4 2 主函数功能测试 9 4 3 各功能所执行的操作 12 5 结论 13 6 收获与致谢 14 7 参考文献 14 8 附件 14 1 1 设计背景设计背景 精品文档 44欢迎下载 1 11 1 程序设计内容程序设计内容 根据设计要求 利用无向图将学校的景点作为图的顶点 顶点的边作为景点之间 的距离进行存储 根据游客的需求 查找各个景点的信息 找出两个景点的最短路径 实现校园的导游目的 1 21 2 程序设计要求程序设计要求 用无向网表示你所在学校的校园景点平面图 图中顶点表示主要景点 存放景点 的编号 名称 简介等信息 图中的边表示景点间的道路 存放路径长度等信息 要 求能够回答有关景点介绍 游览路径等问题 1 景点信息和路径信息保存在文本文件 景点个数不少于 20 个 2 查询各景点的相关信息 3 查询图中任意两个景点间的最短路径 4 查询图中任意两个景点间的所有路径 5 增加 删除 更新有关景点和道路的信息 6 求多个景点的最佳 最短 游览路径 2 设计方案 精品文档 55欢迎下载 2 12 1 景点抽象图景点抽象图 校园景点抽象图比较直观的反应的校园景点的总体布局 图中顶点代表校园景点 顶点之间的边代表景点之间的路径 权值代表景点间的距离 两个顶点间没有边 表 明两个景点不能直接到达 景点抽象图如图 1 所示 1 2 3 4 5 6 7 9 12 11 13 10 14 8 17 15 16 21 19 20 18 200 50 50 50 50 50 60 70 70 20 20 20 20 20 20 10 140 40 120 90 160 30 280 100 40 120 30 80 90 图 1 景点抽象图 2 22 2 程序模块图程序模块图 图中在初始化阶段对无向图进行初始化 通过查找函数查找各个景点的信息 以 及所有景点之间的最短距离 查找景点的位置和此景点在无向图中顶点的编号 最后 就能退出程序 程序模块图如图 2 所示 精品文档 66欢迎下载 开始 景 点 信 息 查 询 两 景 点 最 短 路 径 两 景 点 所 有 路 径 增 加 删 除 更 新 两 景 点 信 息 一 景 点 到 其 它 景 点 的 最 短 路 径 清 屏 初始化 退 出 程 序 景 点 信 息 一 览 表 图2程序功能模块图 2 32 3 主函数设计简要主函数设计简要 在程序的操作要求以及客户的需求下 在主函数设计中首先调用 system cls 函数显示第一个界面 此后显示出一个可视化的操作界面 可以为游客提供相关的景 点的各种信息 并且提示游客做出最好的选择 便于其在后面的操作过程当中能够快 速方便的找到其需要查找的景点 然后就要用到一个 switch 的选择函数 并用此 函数实现程序的所有功能 景点信息一览表 景点信息的查询 两个景点之间的最短 距离 两个景点之间的所有路径 增加 删除 修改景点信息 一个景点到所有景点 的最短路径 清屏和退出程序 完成相关的选择操作后进入到选择的操作界面当中 从而实现所需要的功能 2 42 4 各函数模块的功能各函数模块的功能 1 调用无向网的初始化信息实现景点信息的查询以及全部输出 2 用弗洛伊德算法实现两个景点的最短路径的查询 3 用迪杰斯特拉算法实现一个景点到其余所有景点的最短路径的输出 4 用 system cls 函数实现清屏功能 5 用 exit 函数实现退出程序的功能 精品文档 77欢迎下载 3 方案实施 3 13 1 程序执行流程图程序执行流程图 流程图是算法设计中不可缺少的一部分 通过流程图 可以更加清晰的理解程序 算法的过程 清楚算法的进程 使算法一目了然 流程图如图 3 1 图 3 程序流程图 3 23 2 主函数设计思想主函数设计思想 while 1 无限循环完成程序的循环执行 switch choise case 0 printall G break 0 所有景点信息一览表 case 1 searchinfo G break 1 景点信息查询 case 2 shortpath G break 2 查询两个顶点间的最短路径 case 3 oubleall G break 3 查询两个景点间所有的路径 case 4 changevex G break 4 增加 删除 更新有关景点的信息 case 5 shortallpath G break 5 一个景点到其他所有景点 的 最短路径 迪杰斯特拉 case 6 system cls break 清屏 精品文档 88欢迎下载 case 7 exit 0 退出程序 default break 用一个无限循环实现程序的循环执行 但是死循环是无法自动退出的 因此增加 7 号功能 调用 exit 函数实现退出程序的操作 主函数采用模块化设计 将函数 的功能放在函数中实现 简化主函数 相应的函数模块实现对应的功能 1 0 号 景点信息一览表 1 号功能 查询景点信息 调用无向网的初始化信息 实现景点信息的查询以及全部输出 2 2 号功能 查询两个景点的最短路径 应用弗洛伊德算法实现两个景点的最短 路径的查询 3 3 号功能 查询两个景点之间的所有路径 应用图的遍历查询两个景点间所有 的路径 4 4 号功能 增加 删除 更新有关景点信息 更改无向网的初始化实现更改景 点信息 5 5 号功能 一个景点到其他景点的最短路径 实现一个景点到其他所有景点的 最短路径 迪杰斯特拉 6 6 号功能 清屏 调用 system cls 函数实现清屏功能 7 7 号功能 退出程序 调用 exit 函数实现退出程序的功能 精品文档 99欢迎下载 4 结果测试 4 14 1 主函数功能模块测试主函数功能模块测试 主函数的执行界面 测试结果如图 4 所示 图4 主函数界面的运行结果 4 24 2 主函数功能测试主函数功能测试 1 在请选择查询的项目后输入 0 按 enter 键 即完成 0 号功能测试 0 号功能 测试结果如图 5 所示 精品文档 1010欢迎下载 图5 0号功能运行结果 2 在请选择查询的项目后面输入 1 按 enter 键 即完成 1 号功能测试 1 号功 能测试结果如图 6 所示 图6 1号功能运行结果 3 在选择项目后输入 2 完成 2 号功能 2 号功能的运行结果如图 7 所示 图7 2号功能的运行结果 4 在请选择查询的项目后输入3 按 enter 键 即完成3号功能的测试 3号功能 测试结果如图8所示 精品文档 1111欢迎下载 图8 3号功能运行结果 5 在选择查询的项目后输入4 即完成4号功能的测试 4号功能的运行结果如图9 所示 图9 4号功能的运行结果 6 在选择的项目后输入5 即完成5号功能的测试 5号功能的测试结果如图10所示 精品文档 1212欢迎下载 图10 5号功能的运行结果 4 34 3 各功能所执行的操作各功能所执行的操作 共有 8 个功能 各个功能所执行的操作如下所示 0 号功能 景点信息一览表 1 号功能 查询景点信息 2 号功能 查询两个景点的最短路径 3 号功能 查询两个景点之间的所有路径 4 号功能 增加 删除 更新有关景点信息 5 号功能 一个景点到其他景点的最短路径 6 号功能 清屏 7 号功能 退出程序 5 结论 精品文档 1313欢迎下载 经过这次课程设计 我对程序中算法的概念理解的更加透彻 算法是程序中必不 可少的部分 它是指解题方案的准确而完整的描述 是一系列解决问题的清晰指令 算法代表着用系统的方法描述解决问题的策略机制 也就是说 能够对一定规范的输 入 在有限时间内获得所要求的输出 如果一个算法有缺陷 或不适合于某个问题 执行这个算法将不会解决这个问题 不同的算法可能用不同的时间 空间或效率来完 成同样的任务 同时 在选择算法时必须考虑算法的时间复杂度和空间复杂度 这样 才能让程序正常 高效的运行 数据结构 在计算机科学中是一门综合性的专业基础课 数据结构的研究不仅 涉及到计算机的硬 特别是编码理论 存储装置和存取方法 的研究范围 而且和计算机 软件的研究有着更密切的关系 无论是编译程序还是操作系统 都涉及到数据元素在存 储器中的分配问题 在研究信息检索时也必须考虑如何组织数据 以便查找和存取数据 元素更为方面 因此 可以认为数据结构是介于数学 计算机硬件和计算机软件三者之 间的一门核心课程 在计算机科学中 数据结构不仅是一般程序设计 特别是非数值计算 的程序设计 的基础 而且是设计和实现编译程序 操作系统 数据库系统及其它系统 程序和大型应用程序的重要基础 6 收获与致谢 精品文档 1414欢迎下载 首先 在本次作业中 通过运行程序 我对无向图的运用有了更深的理解 对它 的方法又加以掌握 为以后的学习增加了基础 小组内成员的分工不同 负责的模块不同 但大家能够齐心协力 共同努力 感 谢成员的不懈努力 正有了成员的配合 才顺利完成做业 还要感谢孙高飞老师的教 导 正因为有他的帮助 有他知识的教育 我们才能够运用无向图将学校景点化 顺 利完成作业 7 参考文献 1 谭浩强 C 程序设计 第四版 J 清华大学出版 2010 2 严蔚敏 吴伟民 数据结构 C 语言版 J 清华大学出版社 2011 8 附件 精品文档 1515欢迎下载 指导教师评语 指导教师评语 1 课程设计报告 a 内容 不完整 完整 详细 b 方案设计 较差 合理 非常合理 c 实现 未实现 部分实现 全部实现 d 文档格式 不规范 基