数据结构栈和队列迷宫问.docxVIP

数据结构实验报告 实验目的 通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 2 .实验内容 利用栈结构实现迷宫求解问题。迷宫求解问题如下： 心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。 提示： 1、可以使用递归或非递归两种方法实现 2、老鼠能够记住已经走过的路，不会反复走重复的路径 3、可以自己任意设置迷宫的大小和障碍 4、使用“穷举求解”的方法 2. 程序分析 2.1 存储结构 存储结构：顺序栈 data data data A1A2A3A2A1 A1 A2 A3 A2 A1 top top top （1）空栈 (2)A1A2入栈 (3)A3出栈 2.2 关键算法分析 1.试探方向： （1）基本思想 每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move [ 4 ]中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。 (x， (x，y) 与点(x，y)相邻的4个点及坐标 (x，y+1) (x，y-1) (x+1，y) (x-1，y) x y 0 0 1 1 1 0 2 0 -1 3 -1 0 增量move数组 （2）基本代码 struct item { int x ; //行 int y ; //列 } ; item move[4] ; 2.寻找路径 基本思想： 利用栈的结构，走过的路入栈，如果不能走出栈，采用遍历法，因此栈内存储的数据就是寻一条路径。 当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。 代码 栈构造函数： void seqstack::Push(int x,int y,int d) //入栈 { if(top=StackSize-1)throw上溢; top++; data[top].d=d; data[top].x=x; data[top].y=y; } 寻找路径： int seqstack::findpath(int a,int b) { item move[4]={{0,1},{1,0},{0,-1},{-1,0}};//定义移动结构 int x, y, d, i, j ; Push(a,b,-1); //起点坐标入栈 while(top!=-1) { d=data[top].d+1; x=data[top].x; y=data[top].y; Pop(); //出栈 while (d4) //方向是否可以移动 { i=x+move[d].x ; j=y+move[d].y ; //移动后坐标 if(Map[i][j]==0) //是否能移动 { Push(x,y,d); //移动前坐标入栈 x=i; y=j; Map[x][y]= -1 ;