数据结构课程设计报告老鼠走迷宫_毕业论文.doc

课程设计说明书 课程名称： 数 据 结 构 与 算 法 专业： 软件工程 班级： 15-2 姓名： xx 学号：2xxxxxx2 指导教师： xx 完成日期： 2017 年 1 月 3 日 任 务 书 题目：老鼠走迷宫 设计内容及要求： 1. 课程设计任务内容 程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。 2.课程设计要求 1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2)迷宫的墙足够结实，老鼠不能穿墙而过； 3)正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4)添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5)找出走出迷宫的所有路径，以及最短路径； 6)利用序列化功能实现迷宫地图文件的存盘和读出等功能。 开发环境：QT Creator、 QT5.6 目 录 1.引 言 2 2.课题分析 3 3.具体设计过程 4 3.1设计思路 4 3.2程序设计流程图 5 3.3.函数实现说明 6 4.程序运行结果 7 5.软件使用说明 11 6.结论 11 参 考 文 献 13 1.引 言 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。通常，课程设计中的问题比平时的习题复杂的多，也更接近实际。课程设计着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的习题较偏重于如何编写功能单一的“小”算法，局限于一个或两个知识点，而课程设计题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：计算机是比任何教师更严厉的检查者。 为达到上述目的，使学生更好地掌握程序设计的基本方法和C++语言的应用，本课程安排了课程设计环节，提供了各类题目供学生选择。每个设计题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等五个部分组成。问题描述旨在为学生建立问题提出的背景，指明问题“是什么”。基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求。测试数据部分旨在为检查学生上机作业提供方便。在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示，提示的实现方法未必是最好的，学生不应拘泥与此，而应努力设计和开发更好的方法和结构。选做部分向那些尚有余力的读者提出了更高的要求，同时也能开拓其它读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改、扩充和重用。 2.课题分析 编写一个《老鼠走迷宫》的C++程序，包括以下功能： 初始状态：迷宫处为空白，输入长宽设定迷宫大小，时间剩余为300s。 具体要求如下： 1. 点击生成迷宫，窗口左上方生成一个指定大小的迷宫，老鼠位于迷宫中央，粮仓位于迷宫右下角，开始计时。 2. 可以通过键盘上的方向键控制老鼠移动。 3. 点击显示路径按钮时，显示一条绿色的通道通向粮仓。 4. 点击最短路径按钮时，显示一条绿色的通道（最短）通向粮仓。 5. 点击拆墙/补墙时，老鼠可在迷宫内自由移动，老鼠所走过的墙将变成路/路将变成墙。 6. 点击取消作弊，恢复原始状态。即老鼠只能通过路。 7. 当剩余时间为0时，弹出对话框，游戏失败，游戏结束。 8. 当老鼠走到粮仓处时，弹出对话框，找到出口，游戏结束。 9. 点击储存地图时，将当前地图以矩阵形势存于文件中；点击读取地图时，将文件中的数据赋予迷宫矩阵，创建迷宫。 3.具体设计过程 3.1设计思路 定义迷宫节点，包含x，y（坐标）与state（0为墙，1为通路），使用迷宫节点矩阵表示迷宫，使用回溯法创建迷宫节点矩阵。利用深度优先遍历寻找出老鼠到粮仓的所有路径，利用广度优先遍历寻找老鼠到粮仓的最短路径，将路径中的节点的state置为2，在普通模式下，老鼠仅可通过state为1的节点，当作弊模式开启时，老鼠可通过任意state的节点并且通过的节点的state值会相应的改变。打印迷宫时，state为0的节点使用黑色矩形填充，state为1的节点不填充，state为2的使用绿色矩形填充。 3.2程序设计流程图 _maze //迷宫节点 box //路径节点 box1 //最短路径节点 int i; int j; int