导游系统说明书 课设1.doc

兰州理工大学课程设计 0 目录目录 摘要摘要 1 前言前言 2 正文正文 3 1 问题描述 3 a 题目简介 3 b 主要内容 功能及技术指标 3 2 逻辑设计 3 3 详细设计 6 4 程序编码 8 5 程序调试与测试 8 a 测试与编译 8 b 连接 8 c 运行 9 6 结果分析 12 设计总结设计总结 13 参考文献参考文献 14 致谢致谢 15 附件附件 I 程序代码程序代码 16 兰州理工大学课程设计 1 摘要摘要 驻留程序是特殊的中断服务程序 它程序常驻内存 且占用的内存空间受 DOS 的保护 不会被后来装入的程序覆盖 TSR 程序平时 潜伏 在后台 处 于休闲状态 一旦激活 它将中断前台的应用程序 系统中的许多输入 输出驱 动程序都是常驻内存的 用户也可以设计 TSR 程序 驻留程序增加了微机系统 的功能 从宏观上讲 使得 CPU 可以 同时执行 许多程序 其中包括前台程 序 以及其他各种驻留程序 关键词 系统驻留 时钟 中断 显示时间 兰州理工大学课程设计 2 前言前言 微型计算机原理及应用 是一门实践性和实用性都很强的课程 学习的 目的在于应用 本课程设计是配合 微型计算机原理及应用 课堂教学的一个 重要的实践教学环节 在课程设计指导书中列举了一些常用的小型设计系统 但其目的仅仅是为了配合理论教学环节 实验内容也主要是为了验证理论课教 学的内容 在当今大力提倡素质教育和创新能力培养为目标的教学理念下 必 须重新认识实验课的地位和作用 强化实验内容 改进实验手段和方法 建立 一套完整的认知体系 使整个实践环节起到它应有的作用 旨在起到巩固课堂 和书本上所学的知识 加强综合能力 提高系统设计水平 启发创新思想的效 果 掌握这门课程的内容并且具备一定的实际电路设计和编程能力 将会给学 生深刻理解计算机软 硬件关系及在以后的计算机应用开发中打下很好的基础 另外 我国正在加快开发具有自主知识产权的计算机软 硬件产品 并进行大 规模生产技术改造 因此 对既具备软件编程能力 又了解硬件知识的复合型 人才的需求在不断提高 兰州理工大学课程设计 3 正文正文 1 问题描述 a 题目简介 设计一个校园导游程序 为来访的客人提供各种信息查询服务 即查询任意两个景点之 间的一条最短的简单路径 通过该题目的设计过程 可以加深理解图的基本概念 逻辑结构 及存储结构 掌握图的重要应用 最短路径等算法的应用 进一步理解和熟练掌握课本中 所学的各种数据结构 学会如何把学到的知识用于解决实际问题 培养学生的动手能力 b 主要内容 功能及技术指标 1 校园平面图采用邻接矩阵 或邻接表 表示 主要功能有 校园平面图邻接矩阵 或邻接表 的建立 路径的查询 最短路径的查找 显示输出等功能 2 校园内景点不少于 10 个 算法对于合法的输入数据都能产生满足规格说明要求的 结果 3 一般情况下 校园的道路是双向通行的 可设校园平面图是一无向网 网中顶点 表示校内各景点 以边表示路径 边上的权值存放路径长度等相关信息 4 较高要求 显示校园平面图 显示邻接矩阵 或邻接表 显示两地间最短路径 2 逻辑设计 1 首先手动给校园图赋上相关信息 景点名称 代号 简介 路径及路径长度 得到 一个模拟的校园平面图 如图 1 所示 兰州理工大学课程设计 4 18 15 38 8 57 22 68 12 8 36 4 2 图 1 校园平面 9 大学生活动中心 5 核桃树 3 图 书 馆 8 人工湖 7 田径场 6 七号楼 1 科 技 馆 2 一 号 楼 4 电 信 大 楼 10 工 大 后 山 兰州理工大学课程设计 5 2 用邻接矩阵存储校园图 得出邻接矩阵如图 2 所示 1 2 3 4 5 6 7 8 9 10 0 8 68 1 0 12 2 22 2 8 12 0 57 3 0 4 36 4 2 4 0 5 22 0 8 26 6 8 0 18 38 7 68 57 26 0 15 8 18 15 0 9 36 38 0 10 图 2 邻接矩阵 3 用数据结构知识创建校园图 1 先定义节点个数 N 边的值 cost 节点 景点名称 景点信息 邻接点 边 顶点向量 当前顶点数和边数 2 节点和边的相关信息都弄好了后 校园图也就创建好了 4 利用 introduce 函数来设计景点介绍 并利用 switch case 1 case2 语句给 10 个节点赋上相应的名称 给各节点添加相应的介绍信息 5 用 shortestdistance 函数来求任意两景点之间的最短路径 6 用 floyed 函数求两个景点的最短路径 7 用 main 函数来输出结果 用 switch 语句分别输出 查找景点相关信息时调用 introduce 函数 要查找任意两景点之间的最短路径时 先输入你目前所在的位置 再输入你 的目的地 最后调用 shortestdistance 函数 主函数主要是调用这三个函数 实现上述三个功 能 算法和数据结构描述 定义符号常量 define INT MAX 10000 define n 10 兰州理工大学课程设计 6 定义全局变量 int cost n n 边的值 int shortest n n 两点间的最短距离 int path n n 经过的景点 自定义函数原型说明 void introduce 景点介绍 int shortestdistance 要查找的两景点的最短距离 void floyed 用 floyed 算法求两个景点的最短路径 void display int i int j 打印两个景点的路径及最短距离 3 详细设计 软件结构图即函数调用图 如下图 3 图 3 函数调用 main introduceShortestdistancefloyeddisplay 兰州理工大学课程设计 7 流程图即一般流程图 如图 4 所示 N Y N Y 图 4 一般流程图 start 创建无向图 读取文件信息 写入无向图中 景点信息查询 最短路径查询 Case a Case b Case c end 兰州理工大学课程设计 8 4 程序编码 把详细设计的结果进一步求精为程序设计语言程序 见附件 I 5 程序调试与测试 a 测试与编译 结果如图 5 所示 图 5 测试与编译结果 b 连接 如图 6 所示 图 6 链接结果 兰州理工大学课程设计 9 c 运行 1 进入兰州理工大学软件学院导游系统 主界面如图 7 所示 图 7 兰州理工大学软件学院导游系统主界面 2 查询工大后山的景点信息过程如图 8 所示 图 8 查询工大后山的景点信息过程图 兰州理工大学课程设计 10 3 查询科技馆到工大后山两景点的最短路径如图 9 所示 图 9 查询科技馆到工大后山两景点的最短路径图 由图 9 可知科技馆到工大后山得经过核桃树 图书馆 最短路径为 62 米 4 当输入的不是指定的编号时 它会告诉顾客输入信息错误 请重新输入 具体如输入 ff 系统会显示如图 10 所示 图 10 输入错误信息图 兰州理工大学课程设计 11 5 退出兰州理工大学软件学院导游系统 其操作过程如图 11 所示 图 11 退出系统图 兰州理工大学课程设计 12 6 结果分析 1 时间复杂度分析 该程序中涉及了 Floyd Warshall 算法 时间复杂度 O n 3 只要有 存下邻接矩阵的空间 时间一般没问题 并且不必担心负权边的问题 这个算法通过考虑最 佳子路径来得到最佳路径 调试分析 针对该程序 缺点是运行时 每次只能运算一次 没有继续执行的功能 难点是加入循环语句能够每次执行后能继续执行另外的需求 2 在这题中求任意两景点之间的最短路径用是 Floyd Warshall 算法 这个算法的思想 是从任意一条单边路径开始 所有两点之间的距离是边的权 或者无穷大 如果两点之间没 有边相连 对于每一对顶点 u 和 v 看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比 己知的路径更短 如果是更新它 还可以用狄克斯特拉算法来计算任意两景点之间的最短路径 狄克斯特拉具体做法是按 照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到各个顶点的最短路径及长 度 每次求出从源 i 点到一个终点 m 的最短路径及长度后都要以该 m 点作为新考虑的中间 点 用 Vi 到 Vm 的最短路径和最短路径长度对 Vi 到其他尚未求出最短路径的那些终点的当 前最短路径及长度作必要的修改使之成为当前新的最短路径和最短的路径长度 当进行 n 2 次后结束算法 还可以利用广度优先搜索来计算任意两景点之间的最短路径 广度优先搜索按照从起点 到其他点的路径的长度 从短到长一层一层搜索 当某个点第一次被搜索到 那么所搜索的 那个路径就一定是一条最短路径了 兰州理工大学课程设计 13 设计总结设计总结 经过这一个学期对 算法与数据结构 的学习 我们学习了理论知识 了解了算法与数 据结构的设计的思想 这些知识都为我们的下一步学习打下了坚实的基础 通过课程设计 一方面是为了检查我们一个学期来我们学习的成果 另一方面也是为了让我们进一步的掌握 和运用它 同时也让我们认清自己的不足之处和薄弱环节 加以弥补和加强 通过对算法的设计进一步的巩固了用 c 语言编写程序 并且有利于更好的掌握 c 语言 通过本项课程设计也培养了我独立思考 综合运用所学有关相应知识的能力 掌握 工 程软件设计的基本方法 强化上机动手编程能力 闯过理论与实践相结合的难关 但是在设计过程中也学习了很多 掌握了自己以前没有学好的知识 在算法与数据结构 课程设计的过程中也知道了自己在以前的学习中有很大的不足导致在设计过程中出现了很多 的问题 通过这次设计我知道了自己的下个目标 并努力做到 兰州理工大学课程设计 14 参考文献参考文献 1 1 严蔚敏 吴伟民 严蔚敏 吴伟民 数据结构 数据结构 C C 语言版 语言版 清华大学出版社 清华大学出版社 2 2 严蔚敏 吴伟民 严蔚敏 吴伟民 数据结构题集 数据结构题集 C C 语言版 语言版 清华大学出版社 清华大学出版社 3 3 DATA STRUCTURE WITH C William Ford William Topp 清华大学出版社 影印清华大学出版社 影印 版 版 4 4 谭浩强 谭浩强 c c 语言程序设计语言程序设计 清华大学出版社 清华大学出版社 5 5 数据结构与算法分析 数据结构与算法分析 JavaJava 版 版 A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A Shaffer 张铭张铭 刘晓丹译刘晓丹译 电子工业出版社电子工业出版社 20012001 年年 1 1 月 月 兰州理工大学课程设计 15 致谢致谢 在这次课程设计中 首先要感谢学校为我们提供了这个良好的平台来锻炼我们对汇编语 言的实际操作和应用能力 使我们更加充分的吸收和应用所学的知识 其次 感谢张宪立老师的悉心指导 还有同学们的热心帮助 通过本次课程设计 我也 认识到自身的不足 希望能得到大家的宝贵建议和意见 我一定认真听取 积极改进 是自 己的编程能力更上一个台阶 最后 在这里我再次感谢这次课设和我一起努力的同学和老师 谢谢你们的帮助和支持 兰州理工大学课程设计 16 附件附件 I 程序代码程序代码 源代码列在附录中 要求程序风格清晰易理解 有充分的注释 有意义的注释行少于代码的 30 将 不能得分 2012 1 2 include include define INT MAX 10000 define n 10 int cost n n 边的值 int shortest n n 两点间的最短距离 int path n n 经过的景点 void introduce 景点介绍 int a printf 请输入您想查询的景点编号 scanf d getchar printf n switch a case 1 printf 1 科技馆 n n 举行大型会议以及学校来访贵宾居住的地方 n n break case 2 printf 2 一号楼 n n 计算机活动中心人工湖 n n 学校唯一可以赏鱼的地方 n n break case 3 printf 3 图书馆 n n 学校信息资源中心 内设大量的自习室 n n break case 4 printf 4 电信大楼 n n 学校最高的楼 也是最具文化的中心 n n break case 5 printf 5 核桃树下 n n 是早晨最美的地方 也是最适合背书的地方 n n break case 6 printf 6 七号楼 n n 艺术文化中心 是学校最具有艺术风格的地方 n n break case 7 printf 7 田径场 n n 学校举行运动会的地方 n n break case 8 printf 8 人工湖 n n 学校唯一可以赏鱼的地方 n n break case 9 printf 9 大学生活动中心 n n 各学院举行各种联欢晚会的地方 也是对于我们来说最容易放松 的地方 n n n break case 10 printf 10 工大后山 n n 进行体育活动和休闲娱乐的地方 n n break default printf 景点编号输入错误 请输入 1 10 的数字编号 n n break 兰州理工大学课程设计 17 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 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 最短距离是 d 米 n n a b shortest a b else printf d a while path i j 0 把 i 到 j 的路径上所有经过的景点按顺序打印出来 printf d path i j if i d b printf n n printf d d 最短距离是 5d 米 n n a b shortest a b else printf 输入错误 不存在此路 n n printf n int shortestdistance 要查找的两景点的最短距离 int i j printf 请输入要查询的两个景点的编号 scanf d d if i n in j 0 printf 输入信息错误 n n printf 请输入要查询的两个景点的编号 scanf d d else floyed display i j return 1 void main 主函数 int i j char k for i 0 i n i for j 0 j n j cost i j INT MAX cost 1 2 cost 2 1 12 cost 1 3 cost 3 1 38 cost 3 4 cost 4 3 32 cost 2 4 cost 4 2 21 cost 2 10 cost 1