数据结构实验报告
实验名称： 实验二——题目3. 迷宫问题
学生姓名：
班 级：
班内序号：
学 号：
日 期： 20##年11月25日
1．实验要求
利用栈结构实现迷宫求解问题。迷宫求解问题如下：
心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。
提示：
1、可以使用递归或非递归两种方法实现
2、老鼠能够记住已经走过的路，不会反复走重复的路径
3、可以自己任意设置迷宫的大小和障碍
4、使用“穷举求解”的方法
2. 程序分析
2.1 存储结构
使用栈存储迷宫坐标
2.2 关键算法分析
2.2.1关键算法
寻找迷宫路径：
每走一步：
1、如果当前位置=出口，结束
2、否则：
假设当前位置为路径；
如果东面未走过：向东走一步
如果南面未走过：向南走一步
如果西面未走过：向西走一步
如果北面未走过：向北走一步
设置当前位置走不通，回溯
2.2.2代码详细分析
#include
using namespace std;
struct Point //定义结构类型Point存储迷宫坐标
{
int x,y;
};
template
class Stack //定义模板类Stack实现顺序栈
{
public:
Stack(){top=-1;} //构造函数
void Push(T n){top++;data[top]=n;} //进栈
T Pop(){top--;return data[top+1];} //出栈
private:
T data[100]; //定义数组data存储进栈数据
int top; //栈顶指针top
};
void MasePath(int arr[][10],Point start,Point end) //函数MasePath寻找迷宫路径
{
Stack PointStack; //栈PointStack
Point P=start; //P记录当前迷宫坐标，首先记录入口坐标
arr[P.x][P.y] = 2; //-1——墙；0——路；1——错误路径；2——正确路径
do{ /只要P的坐标不是出口坐标，进行此循环
PointStack.Push(P); //将P记录的坐标存入存入栈
if(arr[P.x][P.y+1]==0) arr[P.x][++P.y]=2; //如果P记录坐标的右左上下有路，P记录的坐标改为路的坐标，并假定是正确路径（记为2）
else if(arr[P.x][P.y-1]==0) arr[P.x][--P.y]=2;
else if(arr[P.x+1][P.y]==0) arr[++P.x][P.y]=2;
else if(arr[P.x-1][P.y]==0) arr[--P.x][P.y]=2;
else //如果P周围没有路了，将P所存坐标退出栈，该坐标记为1，P记录该坐标上一个坐标
{
P=PointStack.Pop();
arr[P.x][P.y]=1;
P=PointStack.Pop();
}
}while ((P.x!=end.x) || (P.y!=end.y));
}
void PrintPath(int arr[][10]) //打印迷宫，墙为■，错误路径或未走路径为□，正确路径为*
{
for (int i=0;i＜10;i++)
{
for (int j=0;j＜10;j++)
{
if (arr[i][j]==-1) cout＜＜"■";
else if (arr[i][j]==2) cout＜＜" *";
else cout＜＜"□";
}
cout＜
}
cout＜
}
void main()
{
int arr[10][10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, //二维数组arr记录迷宫，-1表示墙，0表示路
-1,0,0,-1,0,0,0,-1,0,-1,
-1,0,0,-1,0,0,0,-1,0,-1,
-1,0,0,0,0,-1,-1,0,0,-1,
-1,0,-1,-1,-1,0,0,0,0,-1,
-1,0,0,0,-1,0,0,0,0,-1,
-1,0,-1,0,0,0,-1,0,0,-1,
-1,0,-1,-1,-1,0,-1,-1,0,-1,
-1,-1,0,0,0,0,0,0,0,0,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
Point start,end; //start和end分别记录迷宫入口和出口坐标
start.x=1;
start.y=1;
end.x=8;
end.y=9;
MasePath(arr,start,end); //寻找迷宫路径
PrintPath(arr); //打印迷宫
}
2.2.3时间复杂度
O(1)
3. 程序运行结果
运行结果：
测试的迷宫为10*10，有至少一条正确路径；
4. 总结
开始对题没有理解透，不知道怎么把解题方法用栈编写出来，于是开始一步一步确认：迷宫有横纵坐标，有“墙”有“路”，对应到编程语言就是用0,1等数字表示“墙”和“路”，用二维数组存储，刚好数组的下标可以表示迷宫坐标；由于计算机只能从一个点开始，朝四个方向挨个判断下一步是否走得通，走得通的点需要记录下其坐标，或许还可能走着走着突然发现路走不通了，需要再退回并删除已记录的部分坐标，于是自然想到用栈存储其坐标；而坐标有2个值，要存入顺序结构的栈需要先定义一个结构类型，表示坐标……到此为止，迷宫问题如何用程序语言编写已经清晰。
个人觉得一开始不知道怎么用栈是因为对栈和栈的运用不熟悉，同时也因为缺少编程的实战经验而缺少编程思想。今后需要认真理解所学知识，多看程序应用案例，同时自己也要多上手。