《数据结构迷宫求解课程设计报告》由会员分享，可在线阅读，更多相关《数据结构迷宫求解课程设计报告（19页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告课程名称： 数据结构 报告题目： 迷宫求解 学生姓名： XX 所在学院： 信息科学与工程 专业班级： 软件工程 学生学号：XXXXXXXXXXX 指导教师： XXX 2017 年 12 月 29 日课程设计任务书报告题目迷宫求解程序设计完成时间2017.12.29学生姓名 专业班级指导教师XXX职 称总体设计要求和技术要点课程设计要求1.可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；2.在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；工作内容及时间进度安排第17
2、周：周1-周3 ：立题、论证方案设计周4-周5 ：完成项目一,项目二的整体设计第18周：周1-周2：调试程序，解决问题周3-周5 ：写实验报告 课程设计成果1程序设计内容以及对应的软件程序2课程设计总结报告摘 要 本程序主要是求迷宫中从人口到出口的所有路径是一个经典的程序设计问题。计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向在继续探索，直至所有可能的通路都探索完为止。当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换为“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，
3、则应顺着“来的方向”退回到“前一通道块”，若该通道块的四周4个方块均“不可通”则应从当前路径删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东、南、西、北）上相邻的方块。以栈S来记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。所以即为“当前路径入栈”；“从当前路径上删除前一通道块”为“出栈”。在这个过程中可以输出迷宫所走通的路径，在这次课程设计中迷宫是由数组预先定义好的，不能由用户定义生成，可以加入随机函数，自动生成二维数组，还可以用户自己输入迷宫。关键词：栈；存储结构；数组目 录一、课题分析1二、需求分析11. 主模块功能描述12. 子程序模块设计1三、设计方案
4、11.类设计12.程序模块设计2设计方案与实施与总体设计思想23. 主模块33.1 子模块43.1 主菜单53.2 功能A模块53.3 功能B模块53.4 功能C模块6四、详细设计71.用结构体构建栈72.构建类73.用数组构建一个迷宫84.游戏移动控制指令95.游戏移动控制指令四个方向的实现106.游戏移动过程中若是未找到通路，需要返回的指令117.游戏的主循环118.游戏的开始于结束129.迷宫地图的查看与通关后的路径查询13五、设计总结13结论与心得13五、参考文献15 一、课题分析（1）该题目为迷宫求解。（2）此课题是对迷宫问题的求解。包括用数组生成迷宫，显示输出路径因此，本程序设计共
5、需设计一个主程序以及若干个子程序。（3）在本课程设计程序里，主程序主要是以一个mn的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对设定的迷宫，求出一条从入口到出口的通路，子程序实现迷宫地图的查看和通过迷宫后的路径查询。二、需求分析1. 主模块功能描述 显示提示语句提示用用户选择输入执行的功能。（1）开始迷宫求解游戏 （2）查询迷宫地图（3）查询通过迷宫后的路径 2. 子程序模块设计（1）迷宫求解游戏 输入1开始游戏（2）查询迷宫地图 在菜单中输入2查看迷宫求解的地图（3）查询通过迷宫后的路径 输入2查询通关路径三、设计方案1.类设计构建一个Hidding类，并有私有成员：x
6、坐标，y坐标，位置标志，初始方向；共有成员：PrintMap打印地图，GameFunction游戏主循环，Move_up向上移动，Move_down向下移动，Move_left向左移动，Move_right向右移动，IsGameOver判断游戏是否结束，Move_Keys接收移动的指令，InDirection相反方向输出，dir_flage方向标志，Hidding:Start()开始游戏等等类，在通过类的实现来执行相应的功能，具体代码如下：class Hiddingprivate:int point_x; /控制运动的点的x坐标int point_y; /控制运动的点的y坐标int flage
7、; /判断标志int direction; /初始方向public:Hidding();int PrintMap(int mapHH); /打印地图int GameFunction(int mapHH, SqStack &S);/游戏主循环int Move_up(int mapHH,SqStack &S); /向上移动int Move_down(int mapHH, SqStack &S); /向下移动int Move_left(int mapHH, SqStack &S); /向左移动int Move_right(int mapHH, SqStack &S); /向右移动bool IsGam
8、eOver(int mapHH); /判断游戏是否结束int Move_Keys(int key, int mapHH, SqStack &S); /接收移动的指令int InDirection(int key); /相反方向输出int dir_flage; /方向标志int Out(int mapHH);/显示通关路径int Outa(int mapHH);int Hidding:menu();/菜单int Hidding:Start();/开始游戏;2.程序模块设计设计方案与实施与总体设计思想（1） 迷宫形状由0表示可通过，用1表示障碍。为方便用0,1输入，2表示起点，3表示终点。并把迷宫
9、图形保存在二维数组Map中，而打印出的图形中“”表示能通过，“”表示障碍。对探索过的位置加以标记“”，起点和终点分别由“”，“”表示，“”表示为当前目标位置。（2） 根据二位字符数组和加标记的位置坐标，输出迷宫的图形。（3） 该程序在获取迷宫图形结构后，目标点从起点开始搜索可通过的路径，目标点通过判断身边上下左右四个位置是否有障碍而选择前进路径，如果判断之后遇到没有可以通过的方向，将会退回之前的位置，另行判断。直至目标点找到出口后，输出通过的路径，程序结束。1.2程序设计流程图入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向在继续探索，直至所有可能的通路都探索完
10、为止。图1游戏的主循环 3. 主模块若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换为“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”则应从当前路径删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东、南、西、北）上相邻的方块。以栈S来记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。所以即为“当前路径入栈”；“从当前路径上删除前一通道块”为“出栈”。图2游戏的主框架3.1 子模块图3实现迷宫游戏地图查
11、询后开始游戏3.程序调试结果及分析3.1 主菜单这是主界面，提示A、B、C各自代表的功能，输入1或2或3会跳转到相应的功能模块，输入1开始游戏，输入2可查看需要通关的游戏地图，输入3返回。 图4程序界面图3.2 功能A模块当从键盘输入1进入A功能模块，此图是寻找迷宫路径，游戏会由电脑自动完成，入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向在继续探索，直至所有可能的通路都探索完为止，若是成功找到路径，则输出恭喜过关，并且提示是否查看通关路径。图5程序正在运行图3.3 功能B模块从键盘输入2查询迷宫地图，可显示游戏需要通关的迷宫地图，继续输入1可以开始游戏。图6迷
12、宫地图 3.4 功能C模块游戏的主循环的类的实现表示游戏的开始，判断当前位置标记是否为3，如果为3，则表示该位置为终点，游戏结束，输出恭喜过关，提示是否查看通关路径,从键盘输入2查询通关路径 图7目标完成游戏路径图图四、详细设计1.用结构体构建栈 通过构建的栈实现迷宫求解时寻找路径的数据的存放于取出，其关键代码如下：typedef structSElemType *top; /顶部指针SElemType *base; /底部指针int stacksize; /当前栈的大小SqStack;2.构建类构建一个Hidding类，并有私有成员：x坐标，y坐标，位置标志，初始方向；共有成员：PrintM
13、ap打印地图，GameFunction游戏主循环，Move_up向上移动，Move_down向下移动，Move_left向左移动，Move_right向右移动，IsGameOver判断游戏是否结束，Move_Keys接收移动的指令，InDirection相反方向输出，dir_flage方向标志，Hidding:Start()开始游戏等等类，在通过类的实现来执行相应的功能，具体代码如下：class Hiddingprivate:int point_x; /控制运动的点的x坐标int point_y; /控制运动的点的y坐标int flage; /判断标志int direction; /初始方向public:Hidding();int PrintMap(int mapHH); /打印地图int GameFunction(int mapHH, SqStack &S);/游戏主循环int Move_up(int mapHH,SqStack &S
