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

数据结构实验报告实验名称：实验2——题目3学生姓名：班级：班内序号：学号：日期：2012年11月17日实验要求实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2.实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。提示：1、可以使用递归或非递归两种方法实现2、老鼠能够记住已经走过的路，不会反复走重复的路径3、可以自己任意设置迷宫的大小和障碍4、使用“穷举求解”的方法2.程序分析2.1存储结构存储结构：顺序栈datadatadataA1A2A3A2A1A1A2A3A2A1toptoptop（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)xy00111020-13-10增量move数组（2）基本代码structitem{intx;//行inty;//列};itemmove[4];2.寻找路径基本思想：利用栈的结构，走过的路入栈，如果不能走出栈，采用遍历法，因此栈内存储的数据就是寻一条路径。当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。代码栈构造函数：voidseqstack::Push(intx,inty,intd)//入栈{ if(top>=StackSize-1)throw"上溢"; top++; data[top].d=d; data[top].x=x; data[top].y=y;}寻找路径：intseqstack::findpath(inta,intb){ itemmove[4]={{0,1},{1,0},{0,-1},{-1,0}};//定义移动结构 intx,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(d<4)//方向是否可以移动 {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==m&&y==n)//判断是否为终点坐标 { Push(x,y,-1); return1; }elsed=0; } elsed++; } } return0;}伪代码栈初始化;将入口点坐标及到达该点的方向（设为-1）入栈while(栈不空){栈顶元素＝（x,y,d）出栈;求出下一个要试探的方向d++;while（还有剩余试探方向时）{if（d方向可走）则{（x,y,d）入栈;求新点坐标(i,j);将新点（i,j）切换为当前点（x,y）;if((x,ｙ)==(ｍ,n))结束;else重置d=0;}elsed++;}}时间复杂程度时间复杂程度为O（1）2.3其他在运行时可选择是否自己构造地图，实现函数如下：voidcreatmap()//自创地图函数{ for(inti=1;i<9;i++) { for(intj=1;j<9;j++) Map[i][j]=0; } Map[8][9]=1; printmap(); cout<<"请设置障碍物位置:（x,y）。(0,0)结束"<<endl; intp,q; while(1) {cin>>p>>q; if(p==0&&q==0) { cout<<"设置完成"<<endl; break; } if(p<=0||q<=0||p>=9||q>=9) {cout<<"输入错误！"<<endl; } elseMap[p][q]=1; cout<<"继续输入："<<endl; } cout<<endl; cout<<"请设置终点位置:"<<endl; cin>>q>>p; m=p;n=q; Map[m][n]=0;}3.程序运行结果1.主函数流程开始开始是否自己设计迷宫是否自己设计迷宫设置障碍是设置障碍否打印地图设置终点打印地图设置终点设置起点设置起点是否有路径否是否有路径是打印路径打印路径结束结束测试条件当构造的迷宫符合要求，出入的起点正确则能输出正确路径3.测试结果4.总结最初程序编写时不知道怎么实现适用于任何迷宫，后来采取了适当的方式，可以自定义迷宫；由于编程不熟练，开始不知道怎么用栈实现，经过查资料并与同学探讨，清楚了它的结构原理；另外还有很多标识符使用的小问题，经反复调试后终于得到了解决。编程不是一朝一夕的事，还是熟能生巧，所以一