【数据结构】迷宫问题报告+源码C/C++
之前帮别人写的一个报告，是关于栈的迷宫问题。内容不多，代码在最后。分享给大家，喜欢可以点赞+关注。原创无偿分享，勿商用。
迷宫求解
设计目的
仅认识到栈是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解栈的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方法。
问题描述
迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。
图A
函数说明
- 对栈的处理
InitStack(&S)
操作结果：构造一个空栈 S。
StackEmpty(S)
操作结果：若 S 为空栈，则返回 TRUE，否则返回 FALSE。
Push(&S， e)初始条件：栈 S 已存在。
操作结果：在栈 S 的栈顶插入新的栈顶元素 e。
Pop(&S，&e)
操作结果：删除 S 的栈顶元素，并以 e 返回其值。
- 对迷宫的处理
InitMaze(&maze,a,row,col)
操作结果：对迷宫进行初始化。构成迷宫的字符型数组，以空白字符表示通路，以字符 ‘#’表示障碍，并在迷宫四周加上一圈障碍。
PrintMaze(&maze)
操作结果：以字符形式输出迷宫。
MazePath(&maze,start，end)
操作结果：若迷宫 M 中存在一条通路，则按以下规定改变迷宫 M 的状态：以字符’
-’表示路径上的位置，字符‘X’表示“死胡同”，否则迷宫的状态不变。
程序流程图
重要算法说明
从入口位置开始，将其入栈。
判断当前位置是否可达到，可达到则入栈。
对东西南北四个方向进行遍历，判断能否通过，可通过则更改当前位置。
若当前位置为死路，则出栈并做出‘X’标识。
若当前位置为出口，则存下路径长度退出循环。
使用说明
在该界面，用户有4个可选选项。
选择创建迷宫选项后，需给出迷宫的行列，后用0，1分别表示通路和障碍。
选择查看迷宫选项后，可以查看当前的字符迷宫。
选择寻找通路选项后，可以查看当前迷宫的通路。
调试报告
- 用户手动输入的数组，后自动转化为字符迷宫。
2.查询当前的字符迷宫
3.求解路径后输出迷宫的路径
心得体会
本次实验采用的栈的思想对迷宫问题进行了解决。采用了菜单的方式提供4个功能，分别为创建迷宫、查看迷宫、寻找通路以及退出。对于寻找通路功能来说若可以达到终点，则此算法会按东南西北的顺序寻找到终点的通路，无法保证该通路为最短路，但一定可以走到终点。
本次实验中的另一个的核心就是如何建立存储迷宫的数据结构，即如何用链栈来存储迷宫路径中的各位置以及下一步将要走的方向。并且对试探无路可走后回退的位置要做特殊标识，另外还要在迷宫中标识走过的位置，避免在有路可走时还走回头路出现死循环。算法PrintMaze 和 MazePath 的空间复杂度均为 O（m*n），故本次实验的空间复杂度也为 O(m*n)
附录：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int Status;
#define FALSE 0
#define TRUE 1
#define RANGE 20 //RANGE 为实际分配的空间行列数
int N,M,maze[50][50];
typedef struct { //表达迷宫元素位置信息的坐标
int r,c;
} PosType;
typedef struct { //m，n 为待处理的迷宫的行列数，RANGE 为实际分配的空间行列数
int m,n;
char arr[RANGE][RANGE];
} MazeType;
typedef int directiveType;//东南西北方向用 1，2，3，4 整数对应
typedef struct { //路径拟用栈来存储，此处定义栈元素中数据域的信息
int step;//存储到达该点时经历的步数
PosType seat;//该点位置
directiveType op;//从该点位置走向下一位置的方向
} ElemType;
typedef struct NodeType { //路径拟用链栈来存储
ElemType data;
struct NodeType *next;
} NodeType,*LinkType;
typedef struct { //对链栈的头指针和元素个数进行封装
LinkType top;
int size;
} Stack;
//以上是对存储结构逐层进行定义
void InitStack(Stack &S) { //构建空链栈，不带头结点
S.top=NULL;
S.size=0;
}
Status MakeNode(LinkType &p,ElemType e) { //创建一个新结点，以便插入，本函数可作为链式存储创建结点的通用函数，
p=(NodeType *)malloc(sizeof(NodeType));
if(!p)
return FALSE;
p->data=e;
p->next=NULL;
return TRUE;
}
Status Push(Stack &S,ElemType e) { //入栈操作，栈头（链表头）进行插入
LinkType p;
if(MakeNode(p,e)) {
p->next=S.top;
S.top=p;
S.size++;
return TRUE;
}
return FALSE;
}
Status StackEmpty(Stack S) { //判断是否为空栈，这里是通过 top 指针为 NULL 来判断的，也可以通过 size 是否为 0 来判断
if(S.top==NULL)
return TRUE;
return FALSE;
}
Status Pop(Stack &S,ElemType &e) { //出栈操作，删除表头元素
LinkType p;
if(StackEmpty(S))
return FALSE;
else {
p=S.top;
S.top=S.top->next;
e=p->data;
S.size--;
free(p);
return TRUE;
}
}
Status pass(MazeType maze,PosType now_pos) { //判断迷宫 Maze 中，当前位置 now_pos 是否是一个可达位置
if(maze.arr[now_pos.r][now_pos.c]==' ')
return TRUE;
return FALSE;
}
Status Same(PosType now_pos,PosType end) { //判断当前位置 now_pos 是否已达出口
if(now_pos.r==end.r && now_pos.c==end.c)
return TRUE;
return FALSE;
}
void FootPrint(MazeType &maze,PosType now_pos) {
//在迷宫中标识走过的位置，避免在有路可走时还走回头路出现死循环
maze.arr[now_pos.r][now_pos.c]='-';
}
PosType NextPos(PosType now_pos,int op) {
//通过 op 的值，确定下一步的位置，下一步位置实际是当前位置的四个邻居中的一个
switch(op) {
case 1:
now_pos.c++; //向东走
break;
case 2:
now_pos.r++; //向南走
break;
case 3:
now_pos.c--; //向西走
break;
case 4:
now_pos.r--; //向北走
break;
}
return now_pos;
}
void MarkPrint(MazeType &maze,PosType p) {
//对试探无路可走后回退的位置做特殊标识
maze.arr[p.r][p.c]='X';
}
void PrintMaze(MazeType maze) {
//对迷宫输出，实际是对一个二维数组的输出
int i,j;
printf("\n");
for(i=0; i<maze.m; i++) {
printf("\t");
for(j=0; j<maze.n; j++) {
printf("%c ",maze.arr[i][j]);
}
printf("\n");
}
printf("\n");
}
void InitMaze(MazeType &maze,int a[][50],int row,int col) {
//根据二维数组来初始化迷宫，这个二维数组可以设计为由用户从键盘输入，
//控制每行长度的实际就是定义列的数值，所以要明确参数N
int i,j;
maze.m=row;
maze.n=col;
for(i=0; i<row; i++)
for(j=0; j<col; j++) {
if(a[i][j]==0)
maze.arr[i][j]=' ';
else
maze.arr[i][j]='#';
}
}
int MazePath(MazeType &maze,PosType start,PosType end) { //返回值为路径的长度,返回 0 表示无通路
Stack s;
int now_step=1; //统计路径长度
int found=0;
ElemType e; //以栈元素的形式暂存当前位置的相关信息，以便入栈构成路径
PosType now_pos=start; //设当前位置为开始位置
InitStack(s);
do { //栈不空且未到出口则继续循环
if(pass(maze,now_pos)) { //如果 now_pos 位置可达则先入栈
FootPrint(maze,now_pos); //如果可通则标记为 -，后边如果发现是死胡同，则会重新标记为 X
e.step=now_step;
e.seat=now_pos;
e.op=1;
Push(s,e);
if(Same(now_pos,end)) {
found=s.size;
} else {
now_pos=NextPos(now_pos,1); //到新位置时默认先向东走
now_step++;
}
} else if(!StackEmpty(s)) {
Pop(s,e); //如果 now_pos 位置不可达，且栈不空，则把刚入栈的元素弹出做相关判断
while((e.op==4) && !StackEmpty(s)) {
MarkPrint(maze,e.seat); //标识此路不通
Pop(s,e); //回到上一个位置
now_step--; //不减一的话可以用于统计走过的总步数
}
if(e.op<4) { //如果还有方向未走过，则沿新的方向继续试探
e.op++;
Push(s,e); //默认新方向的下一位置可达，将当前位置入栈
now_pos=NextPos(e.seat,e.op); //通过当前位置，以及去下一位置的方向得出新的位置，再循环查看新位置是否可达
}
}
} while(!StackEmpty(s) && !found);
return found;
}
void Print(int maze[][50]) {
int i,j;
printf("表示迷宫的数组\n");
for(i=0; i<M; i++) {
printf("\t");
for(j=0; j<N; j++) {
printf("%d ",maze[i][j]);
}
printf("\n");
}
printf("\n");
}
void showMenu() {
system("cls");
putchar('\n');
printf(" ");
printf("********************************************************************");
putchar('\n');
putchar('\n');
printf(" ");
printf("1--创建一个新的迷宫\n");
putchar('\n');
printf(" ");
printf("2--查看当前迷宫\n");
putchar('\n');
printf(" ");
printf("3--寻找当前迷宫的通路\n");
putchar('\n');
printf(" ");
printf("4--退出\n");
putchar('\n');
printf(" ");
printf("********************************************************************\n");
}
int main() {
int step=0;
int f=0;
MazeType L;
while(1) {
int ch;
PosType start,end;
showMenu();
printf("请选择功能:");
scanf("%d",&ch);
switch(ch) {
case 1:
printf("请输入迷宫矩阵的行与列！\n");
scanf("%d %d",&M,&N); //M为迷宫的行 N为迷宫的列
printf("请使用0，1分别代表通道与障碍输入%d行%d列的迷宫矩阵！(输入时使用空格分隔)\n",M,N);
int i,j;
int op;
scanf("%d",&op);
if(op==1) {
int i,j;
for(i=0; i<M; i++)//随机生成0，1迷宫矩阵
for(j=0; j<N; j++) {
if(rand()%10000>=6666) maze[i][j]=1;
else maze[i][j]=0;
}
f=1;
InitMaze(L,maze,M,N);//调用 InitMaze 函数将二维数组初始化为迷宫
printf("迷宫创建完成！");
system("pause");
break;
case 2:
if(!f) {
printf("当前不存在迷宫，请先创建一个新的迷宫！");
system("pause");
break;
} else {
printf("由数组转化出的迷宫");
PrintMaze(L);//输出已转化的迷宫
system("pause");
break;
}
case 3:
if(!f) {
printf("当前不存在迷宫，请先创建一个新的迷宫！");
system("pause");
break;
} else {
PrintMaze(L);
MazeType L_tp;
InitMaze(L_tp,maze,M,N);//调用 InitMaze 函数将二维数组初始化为迷宫
printf("请输入迷宫的入口坐标！\n");
scanf("%d %d",&start.r,&start.c); //设置迷宫的入口
start.r--;start.c--;
printf("请输入迷宫的出口坐标！\n");
scanf("%d %d",&end.r,&end.c); //设置迷宫的出口
end.r--;end.c--;
if(L_tp.arr[start.r][start.c]=='#'||L_tp.arr[end.r][end.c]=='#'){
printf("输入异常！起点或终点为障碍......");
system("pause");
break;
}
if(step==MazePath(L_tp,start,end))
printf("迷宫的路径，其中S为起点，F为终点，路径用-表示,路径长度为:%d",step);
else
printf("此迷宫没有通路！");
L_tp.arr[start.r][start.c]='S';
L_tp.arr[end.r][end.c]='F';
PrintMaze(L_tp);
system("pause");
break;
}
case 4:
return 0;
}
}
}