数据结构实验2栈和队列迷宫问题求解.docx

数据结构实验报告实验名称：实验2——题目3学生姓名：班级：班内序号：学号：日期： 2012年11月17日实验要求实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2 .实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。提示：1、可以使用递归或非递归两种方法实现 2、老鼠能够记住已经走过的路，不会反复走重复的路径 3、可以自己任意设置迷宫的大小和障碍 4、使用“穷举求解”的方法2. 程序分析2.1 存储结构存储结构：顺序栈data data dataA1A2A3A2A1 top toptop（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：纵坐标增量。x13-10增量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 ; if(x==my==n) //判断是否为终点坐标 { Push(x,y,-1); return 1 ; } else d=0 ; } else d++ ;}}return 0;}伪代码栈初始化;将入口点坐标及到达该点的方向（设为-1）入栈while (栈不空){栈顶元素＝（x , y , d）出栈 ;求出下一个要试探的方向d++ ;while （还有剩余试探方向时） {if （d方向可走）则 { （x ,