资源描述：
《数据结构栈和队列迷宫问.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构实验报告1.实验目的通过选择下面五个题目之一进行实现，掌握如下内容：·进一步掌握指针、模板类、异常处理的使用·掌握栈的操作的实现方法·掌握队列的操作的实现方法·学习使用栈解决实际问题的能力·学习使用队列解决实际问题的能力2.实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。提示：1、可以使用递归或非递归两种方法实现2、老鼠能够记住已经走过的路，不会反复走重复的路径3、可以
2、自己任意设置迷宫的大小和障碍4、使用“穷举求解”的方法2.程序分析2.1存储结构存储结构：顺序栈datadatadataA1A2A3A2A1toptoptop（1）空栈(2)A1A2入栈(3)A3出栈2.2关键算法分析1.试探方向：（1）基本思想每个点有4个方向去试探，如当前点的坐标(x,y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组
3、move[4]中，在move数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。(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.寻找路径（1）基本思想：利用栈的结构，走过的路入栈，如果不能走出栈，采用遍历法，因此栈内存储的数据就是寻一条路径。当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到
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)
5、{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）伪代码a)栈初始化;b)将入口点坐标及到达该点的方向（设为-1）入栈c)wh
6、ile(栈不空){栈顶元素＝（x,y,d）出栈;求出下一个要试探的方向d++;while（还有剩余试探方向时）{if（d方向可走）则{（x,y,d）入栈;求新点坐标(i,j);将新点（i,j）切换为当前点（x,y）;if((x,ｙ)==(ｍ,n))结束;else重置d=0;}elsed++;}}（2）时间复杂程度时间复杂程度为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();
7、cout<<"请设置障碍物位置:（x,y）。(0,0)结束"<>p>>q;if(p==0&&q==0){cout<<"设置完成"<8、
9、q<=0
10、
11、p>=9
12、
13、q>=9){cout<<"输入错误！"<>q>>p;m=p
