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