一.实验要求
1.题目
给定一个M*N的迷宫图，求一条从指定入口到出口的迷宫路径。假设一个迷宫的示意图如下（这里M=8,N=8），其中的每个方块用空白表示通道，用阴影表示障碍物。
2.补充
一般情况下，所求迷官路径是简单路径，即在求得的迷宫路径 上不会重复出现同一方块。一个迷官图的迷官路径可能有多条，这些迷宫路径有长有短，这里仅仅考虑用栈求一条从指定入口到出口的迷宫路径。
二.思路分析
1.构建初始环境
为了表示迷宫，设置一个数组mg,其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块是障碍物(不可走)。为了算法方便，一般在迷宫的外围加一条围墙（已在题目图中画出）。
2. 计运算算法
对于速官中的每个方块，有上、下、左、右4个方块相邻，第i行第j列的当前方块的位置记为(i，j)，规定上方方块为方位0。并按顺时针方向递增编号。在试探过程中，假设按从方位0到方位3的方向查找下一个可走的相邻方块。
求迷宫问题就是在一个指定的迷宫中求出从人口到出口的一 条路径。在求解时采用“穷举法”，即从人口出发按方位0到方位3的次序试探相邻的方块，一且找到一个可走的相邻方块就继续走下去,并记下所走的方位；若某个方块没有相邻的可走方块，则沿原路退回到前一个方块,换下一个位再继续试探，直到所有可能的通路都试探完为止。
为了保证在任何位置上都能沿原路退回(称为回溯)，需要保存从人口到当前位置的路径上走过的方块，由于回溯的过程是从当前位置退回到前一个方块，体现出后进先出的特点,所以采用栈来保存走过的方块。i
若一个非出口方块(i,j)是可走的,将它进栈,每个刚刚进栈的方块,其方位di置为-1(表示尚未试探它的周围),然后开始从方位0到方位3试探这个栈顶方块的四周，如果找到某个方位d的相邻方块(i，j)是可走的，则将栈顶方块(i,j)的方位d,置为d，同时将方块(i，j)进栈,再继续从方块(i，j)做相同的操作。若方块(i，j)的四周没有一个方位是可走的，将它退栈，前一个方块(x，y)变成栈顶方块，再从方块(x,y)的下一个方位继续试探。
三.各部分功能实现
1.定义初始结构体
- 链栈中结点类型LinkNode的声明如下：
#define MaxSize 100 //定义方块结构体 typedef struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一个相邻可走方位的方位号 }Box; /*数据结构体的方位号表示某个方块下一步行走的方向，如下： （i-1，j)方位0，上 (i,j+1)方位1，右； （i+1，j）方位2，下；(i,j-1)方位3，左。 类似于时钟旋转，以顺时针方向旋转 */ typedef struct linknode { Box data; //数据域 struct linknode *next; //指针域 }LinkStNode; //链栈节点类型
2.初始设置环境
- 交代迷宫的基础构成与算法思路
/* 与顺序栈不同，链栈的优点是不存在栈满上溢出的情况，规定栈的所有操作都是在单链表的表头进行 */ /* 解决迷宫问题最重要的就是找到一条出去的路径。在这里求解时，采用穷举法，即从入口出发，按方位0到方位3的次序试探相邻的 方块，一旦找到一个可走的相邻方块就继续走下去，并几下所走的方位；若某个方块没有相邻的可走方块，则沿原路返回前一个方 块，换一个方位继续尝试，直到所有的通路都试探完为止。 沿原路返回，相当于进栈后再退出去，此时栈顶指针刚好指向前一个方块，符合后进先出的特点，所以使用链栈来保存。 */ const int m=8,n=8; //这里定义的是8*8的迷宫 int mg[m+2][n+2]= { {1,1,1,1,1,1,1,1,1,1},{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,1},{1,1,1,1,1,1,1,1,1,1} }; /* 这里可以采用读取文件的方式读入数据，但是为了节省空间，这里还是直接输入。 1表示为障碍物，0表示对于方块为通道。 本来是8*8的迷宫，但是为了美观，这里在上下两边定义了一圈围墙，故有m+2和n+2。 */ /* 算法思路：一个方块是（i，j）可走的，将他进栈，每一个刚进栈的方块，其di置为-1表示还没有试探他的周围，然后从0到3探索这个方块的四周。 如果找到某个方位可以走，改变di的值，将可走相邻方块进栈，随后进行相同操作。 问题：如果某个方块已进栈，探索相邻位置时，很可能探索到原来的那个方块，进而来回死循环，为此可以将一个方块进站后其对应的mg数组 元素的值改为-1，当出栈（表示该方块没有相邻方块）将气质回复为0. */
3.初始化栈
- 创建链栈的头结点，并将其next域置为NULL
//初始化栈 void InitStack(LinkStNode *&s) { s=(LinkStNode * )malloc(sizeof(LinkStNode)); //创建一个空链栈，即建立链栈的头结点，并将其next域置为空 s->next=NULL; //栈为空时，头结点指向NULL }
4.销毁栈
- 释放链栈s占用的全部点空间
//销毁栈 void DestroyStack(LinkStNode *&s) { LinkStNode *pre=s,*p=s->next; //定义两个结构体指针，pre指向头结点，p指向首节点 while(p!=NULL) //循环到p为空 { free(pre); //释放怕热结点 pre=p; //pre、p同步后移 p=pre->next; } free(pre); //当p为空时，此时pre指向尾结点，释放其空间 }
5.判断栈空
- 运算判断s->next=NULL是否成立
//判断链栈是否为空 bool StackEmpty(LinkStNode *s) { return (s->next==NULL); }
6.进栈
- 新建一个结点，用于存放元素e（由p指向它），让后将其插入到头结点之后作为新的首节点。
//进栈 void Push(LinkStNode *&s,Box e) { /*新建一个结点，用于存放元素e（即p指向它），然后将其插入到头结点之后作为新的首节点*/ LinkStNode *p; p=(LinkStNode *)malloc(sizeof(LinkStNode)); //新建节点p p->data=e; //存放元素e p->next=s->next; //将p节点插入作为新首节点 s->next=p; }
7.出栈
- 在栈不为空的情况下提取首节点的数据域赋给引用型参数e，然后将其删除
//出栈 bool Pop(LinkStNode *&s,Box &e) { /*在栈不为空的情况下，提取首节点的数据域赋给参数e，然后再蒋钦删除*/ LinkStNode *p; if(s->next==NULL) //栈空的情况下返回假 return false; p=s->next; //p指向首节点 e=p->data; //提取首节点的值 s->next=p->next; //删除首节点 free(p); //释放被删除节点的存储空间 return true; //返回真 }
8.取栈顶元素
- 在栈不为空的情况下提取首节点的数据域赋值给引用型参数e。
//取栈顶元素 bool GetTop(LinkStNode *&s,Box &e) { if(s->next==NULL) //栈空的情况下返回假 return false; e=s->next->data; //提取首节点的值 return true; //返回真 }
9.*求解迷宫路径
- 核心算法
//求迷宫路径 bool mgpath(int x1,int y1,int x2,int y2) //求解路径为(x1,y1)到（x2,y2) { Box path[MaxSize],e; //定义一个方块的集合和个体 int i,j,di,k,il,jl; LinkStNode *s; //定义栈s InitStack(s); //初始化栈 e.i=x1;e.j=y1;e.di=-1; //设置e为入口 Push(s,e); //首先入口e进栈 mg [x1][x2]=-1; //入口e进栈后，将e设置为-1.避免重复走到该方块 while(!StackEmpty(s)) { GetTop(s,e); //取栈顶的方块 i=e.i;j=e.j;di=e.di; if(i==x2 && j==y2) //如果栈顶是出口，输出该路径即可 { printf("一条迷宫路径如下：\n"); k=0; //计数器，计算path数组的长度 while(!StackEmpty(s)) { Pop(s,e); //出栈方块e path[k++]=e; //将e添加到path数组中 } /*一般情况下，k的值即路径长度大于1，这里为了输出美观做一些格式调整*/ while(k>=1) { k--; printf("\t(%d,%d)",path[k].i,path[k].j); if((k+2)%5==0) //输出5个方块后换一行 printf("\n"); } printf("\n"); DestroyStack(s); //输出完路径后为了节省空间，这里将栈销毁 return true; //输出一条迷宫路径后返回true代表这部分完好 } bool find=false; while(di<4 && !find) //恒为真，一直执行 { di++; //di顺时针递增 switch(di) //用switch语句来表示各个方位 { case 0:il=i-1;jl=j;break; case 1:il=i;jl=j+1;break; case 2:il=i+1;jl=j;break; case 3:il=i;jl=j-1;break; } if(mg[il][jl]==0) //找到一个相邻可走方块，设置find为真 find=true; } if(find) //找到相邻可走方块后进栈并进行下一步 { s->next->data.di=di; //修改栈顶(表头首节点）元素di的值，表示要进栈的元素是栈顶元素哪个方位的方块 e.i=il;e.j=jl;e.di=-1; //把找到的相邻可走方块信息赋予一个结构体实例 Push(s,e); //把该实例进栈 mg[il][jl]=-1; //进站后，把(il,jl)迷宫值改为-1，避免重复走到该模块 } else //如果没有相邻可走方块，则退栈 { Pop(s,e); //将栈顶方块退栈 mg[e.i][e.j]=0; //退栈后，将其迷宫的值回复原样 } } DestroyStack(s); //算法完成后，无论找到与否，都销毁栈节省空间 return false; //如果没有执行上面代码表示没有可走路径，返回false }
四.C语言实现
#include <stdlib.h> #include <stdio.h> #include <string.h> #define MaxSize 100 /*该次实验完成课本93页迷宫问题的实验，实验的迷宫模型采用课本的示意图*/ //定义方块结构体 typedef struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一个相邻可走方位的方位号 }Box; /*数据结构体的方位号表示某个方块下一步行走的方向，如下： （i-1，j)方位0，上 (i,j+1)方位1，右； （i+1，j）方位2，下；(i,j-1)方位3，左。 类似于时钟旋转，以顺时针方向旋转 */ typedef struct linknode { Box data; //数据域 struct linknode *next; //指针域 }LinkStNode; //链栈节点类型 /* 与顺序栈不同，链栈的优点是不存在栈满上溢出的情况，规定栈的所有操作都是在单链表的表头进行 */ /* 解决迷宫问题最重要的就是找到一条出去的路径。在这里求解时，采用穷举法，即从入口出发，按方位0到方位3的次序试探相邻的 方块，一旦找到一个可走的相邻方块就继续走下去，并几下所走的方位；若某个方块没有相邻的可走方块，则沿原路返回前一个方 块，换一个方位继续尝试，直到所有的通路都试探完为止。 沿原路返回，相当于进栈后再退出去，此时栈顶指针刚好指向前一个方块，符合后进先出的特点，所以使用链栈来保存。 */ const int m=8,n=8; //这里定义的是8*8的迷宫 int mg[m+2][n+2]= { {1,1,1,1,1,1,1,1,1,1},{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,1},{1,1,1,1,1,1,1,1,1,1} }; /* 这里可以采用读取文件的方式读入数据，但是为了节省空间，这里还是直接输入。 1表示为障碍物，0表示对于方块为通道。 本来是8*8的迷宫，但是为了美观，这里在上下两边定义了一圈围墙，故有m+2和n+2。 */ /* 算法思路：一个方块是（i，j）可走的，将他进栈，每一个刚进栈的方块，其di置为-1表示还没有试探他的周围，然后从0到3探索这个方块的四周。 如果找到某个方位可以走，改变di的值，将可走相邻方块进栈，随后进行相同操作。 问题：如果某个方块已进栈，探索相邻位置时，很可能探索到原来的那个方块，进而来回死循环，为此可以将一个方块进站后其对应的mg数组 元素的值改为-1，当出栈（表示该方块没有相邻方块）将气质回复为0. */ //初始化栈 void InitStack(LinkStNode *&s) { s=(LinkStNode * )malloc(sizeof(LinkStNode)); //创建一个空链栈，即建立链栈的头结点，并将其next域置为空 s->next=NULL; //栈为空时，头结点指向NULL } //销毁栈 void DestroyStack(LinkStNode *&s) { LinkStNode *pre=s,*p=s->next; //定义两个结构体指针，pre指向头结点，p指向首节点 while(p!=NULL) //循环到p为空 { free(pre); //释放怕热结点 pre=p; //pre、p同步后移 p=pre->next; } free(pre); //当p为空时，此时pre指向尾结点，释放其空间 } //判断链栈是否为空 bool StackEmpty(LinkStNode *s) { return (s->next==NULL); } //进栈 void Push(LinkStNode *&s,Box e) { /*新建一个结点，用于存放元素e（即p指向它），然后将其插入到头结点之后作为新的首节点*/ LinkStNode *p; p=(LinkStNode *)malloc(sizeof(LinkStNode)); //新建节点p p->data=e; //存放元素e p->next=s->next; //将p节点插入作为新首节点 s->next=p; } //出栈 bool Pop(LinkStNode *&s,Box &e) { /*在栈不为空的情况下，提取首节点的数据域赋给参数e，然后再蒋钦删除*/ LinkStNode *p; if(s->next==NULL) //栈空的情况下返回假 return false; p=s->next; //p指向首节点 e=p->data; //提取首节点的值 s->next=p->next; //删除首节点 free(p); //释放被删除节点的存储空间 return true; //返回真 } //取栈顶元素 bool GetTop(LinkStNode *&s,Box &e) { if(s->next==NULL) //栈空的情况下返回假 return false; e=s->next->data; //提取首节点的值 return true; //返回真 } //求迷宫路径 bool mgpath(int x1,int y1,int x2,int y2) //求解路径为(x1,y1)到（x2,y2) { Box path[MaxSize],e; //定义一个方块的集合和个体 int i,j,di,k,il,jl; LinkStNode *s; //定义栈s InitStack(s); //初始化栈 e.i=x1;e.j=y1;e.di=-1; //设置e为入口 Push(s,e); //首先入口e进栈 mg [x1][x2]=-1; //入口e进栈后，将e设置为-1.避免重复走到该方块 while(!StackEmpty(s)) { GetTop(s,e); //取栈顶的方块 i=e.i;j=e.j;di=e.di; if(i==x2 && j==y2) //如果栈顶是出口，输出该路径即可 { printf("一条迷宫路径如下：\n"); k=0; //计数器，计算path数组的长度 while(!StackEmpty(s)) { Pop(s,e); //出栈方块e path[k++]=e; //将e添加到path数组中 } /*一般情况下，k的值即路径长度大于1，这里为了输出美观做一些格式调整*/ while(k>=1) { k--; printf("\t(%d,%d)",path[k].i,path[k].j); if((k+2)%5==0) //输出5个方块后换一行 printf("\n"); } printf("\n"); DestroyStack(s); //输出完路径后为了节省空间，这里将栈销毁 return true; //输出一条迷宫路径后返回true代表这部分完好 } bool find=false; while(di<4 && !find) //恒为真，一直执行 { di++; //di顺时针递增 switch(di) //用switch语句来表示各个方位 { case 0:il=i-1;jl=j;break; case 1:il=i;jl=j+1;break; case 2:il=i+1;jl=j;break; case 3:il=i;jl=j-1;break; } if(mg[il][jl]==0) //找到一个相邻可走方块，设置find为真 find=true; } if(find) //找到相邻可走方块后进栈并进行下一步 { s->next->data.di=di; //修改栈顶(表头首节点）元素di的值，表示要进栈的元素是栈顶元素哪个方位的方块 e.i=il;e.j=jl;e.di=-1; //把找到的相邻可走方块信息赋予一个结构体实例 Push(s,e); //把该实例进栈 mg[il][jl]=-1; //进站后，把(il,jl)迷宫值改为-1，避免重复走到该模块 } else //如果没有相邻可走方块，则退栈 { Pop(s,e); //将栈顶方块退栈 mg[e.i][e.j]=0; //退栈后，将其迷宫的值回复原样 } } DestroyStack(s); //算法完成后，无论找到与否，都销毁栈节省空间 return false; //如果没有执行上面代码表示没有可走路径，返回false } //主函数 int main() { if(!mgpath(1,1,m,n)) printf("该迷宫没有解！！！"); return 1; }
五.运行结果
六.补充
这是基于上一篇博客用顺序栈实现迷宫问题求解后，同样的算法思路，只不过现在用链栈完成。
可以与上一篇结合一起对照。
