迷宫问题——数据结构课程设计迷宫问题

《迷宫问题——数据结构课程设计迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、*******************实践教学*******************兰州理工大学计算机与通信学院2012年春季学期算法与数据结构课程设计题目：迷宫问题专业班级：计算机科学与技术一班姓名：程文鑫学号：10240127指导教师：张永成绩：目录摘要3前言4正文5一、采用c++语言定义相关的数据类型5二、各模块的伪码算法6三、函数的调用关系图10四、调试分析11五、测试结果111、开始界面122、自动生成迷宫运行情况123、键盘输入迷宫运行情况14总结16致谢17参考文献18附录19源程序（带注释）19摘要本程序主要是对任意给定的迷宫，求出一条从入口到出口的

2、通路，或得出没有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1、生成迷宫：根据提示输入数据，然后生成一个8行8列的迷宫。2、探索迷宫路径：由输入的入口位置开始，对相邻的（上，下，左，右）四个方向的方块进行探索，若可通则“纳入路径”，否则顺着“来向”退到“前一通道块”，朝着“来向”之外的其它方向继续探索。3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后弹出路径坐标，输出在屏幕上。关键字：栈，栈的存储结构，出栈与入栈前言求迷宫中从入口到出

3、口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。迷宫问题要求，所求路径必须是简单路径，即在求得路径上不能同时重复出现同一通道。在迷宫中用1和0分别表示迷宫中的通路和障碍。首先，输入迷宫数据，在计算机的屏幕上显示一个8行8列的矩阵表示迷宫。矩阵中的每个数据

4、或为通路（以0表示），或为墙（以1表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则“纳入当前路径”，并继续朝“下一个位置”探索，即切换“下一位置”为“当前位置”，如此重复直到到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”，之外的其它方向继续探索，若该通道块的四周四个方块均“不可通”，则应该从“当前路径”上删除该通道块，所谓“下一个位置”指的是“当前位置”四周四个方向（上，

5、下，左，右）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径坐标。最后希望通过对该课题的设计，理解和掌握所学到的各种数据结构，学会把学到的知识应用于解决实际的问题当中，培养自己的动手能力。正文一、采用c++语言定义相关的数据类型1、定义坐标（X，Y）:#include#includeusingnamespacestd;structCoor{

6、introw;intcolumn;intdirection;};2、定义方向：structMove{introw;intcolumn;};3、定义/链表结点：structLinkNode{Coordata;LinkNode*next;};4、定义栈：classstack{private:LinkNode*top;public:stack();~stack();voidPush(Coordata);CoorPop();CoorGetPop();voidClear();boolIsEmpty();};5、定义迷宫定义移动的4个方向：Movemove[4]={{0,1},

7、{1,0},{0,-1},{-1,0}};6、几个函数功能的描述:stack();//构造函数，置空栈~stack();//析构函数voidPush(Coordata);//把元素data压入栈中CoorPop();//使栈顶元素出栈CoorGetPop();//取出栈顶元素voidClear();//把栈清空boolIsEmpty();//判断栈是否为空boolMazepath(int**maze,intm,intn);//寻找迷宫maze中从（0，0）到（m,n）的路径//到则返回true,否则返回falsevoidPrintPath(stackp);//输