一.实验要求
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.定义初始结构体
- 采用栈指针s(不同于栈顶指针top)方式创建和使用顺序栈。
#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 { Box data[MaxSize]; //存放栈中的数据元素 int top; //栈顶伪指针,存放栈顶元素在data数组中的下标 }StType;
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.初始化栈
- 创建一个空栈,由s指向它。
//初始化栈 void InitStack(StType *&s) { s=(StType * )malloc(sizeof(StType)); //分配一个顺序栈空间,首地址存放在s中,即s是一个指向顺序栈首地址得到伪指针 s->top=-1; //栈为空时,栈顶指针设置为-1 }
4.进栈
- 在栈不满的情况下先将栈顶指针增1,然后在该位置上插上元素e,并返回真;否则返回假。
//进栈 bool Push(StType *&s,Box e) { /*元素e进栈*/ if(s->top==MaxSize-1) //栈满,溢出报错 return false; s->top++; //栈顶指针+1 s->data[s->top]=e; //元素e放在栈顶指针处 return true; }
5.出栈
- 在栈不为空的情况下先将栈顶元素赋值给e,然后将栈顶指针减1,并返回真;否则返回假。
//出栈 bool Pop(StType *&s,Box &e) //&表示引用型,如果输出元素作为参数引用则添加该符号 { if (s->top==-1) //栈为空,向下溢出报错 return false; e=s->data[s->top]; //取栈顶元素 s->top--; //栈顶指针-1 return true; }
6.取栈顶元素
- 在栈不为空的情况下,将栈顶元素赋值给e并返回真;否则返回假。
//取栈顶元素 bool GetTop(StType *&s,Box &e) { /*与出栈不同,该算法是读取栈顶元素,用e来存放栈顶元素*/ if (s->top==-1) //栈为空,向下溢出报错 return false; e=s->data[s->top]; //取栈顶元素 return true; }
7.基础操作
- 包括销毁和判断空
//销毁栈 void DestroyStack(StType *&s) { free(s); } //判断空 bool StackEmpty(StType *s) { return (s->top==-1); }
8.*求迷宫路径
- 核心算法
//求迷宫路径 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; StType *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->data[s->top].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 }
四.完整实验代码
#include <stdlib.h> #include <stdio.h> #include <string.h> /*该次实验完成课本93页迷宫问题的实验,实验的迷宫模型采用课本的示意图*/ #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 { Box data[MaxSize]; //存放栈中的数据元素 int top; //栈顶伪指针,存放栈顶元素在data数组中的下标 }StType; /* 解决迷宫问题最重要的就是找到一条出去的路径。在这里求解时,采用穷举法,即从入口出发,按方位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(StType *&s) { s=(StType * )malloc(sizeof(StType)); //分配一个顺序栈空间,首地址存放在s中,即s是一个指向顺序栈首地址得到伪指针 s->top=-1; //栈为空时,栈顶指针设置为-1 } //进栈 bool Push(StType *&s,Box e) { /*元素e进栈*/ if(s->top==MaxSize-1) //栈满,溢出报错 return false; s->top++; //栈顶指针+1 s->data[s->top]=e; //元素e放在栈顶指针处 return true; } //出栈 bool Pop(StType *&s,Box &e) //&表示引用型,如果输出元素作为参数引用则添加该符号 { if (s->top==-1) //栈为空,向下溢出报错 return false; e=s->data[s->top]; //取栈顶元素 s->top--; //栈顶指针-1 return true; } //取栈顶元素 bool GetTop(StType *&s,Box &e) { /*与出栈不同,该算法是读取栈顶元素,用e来存放栈顶元素*/ if (s->top==-1) //栈为空,向下溢出报错 return false; e=s->data[s->top]; //取栈顶元素 return true; } //销毁栈 void DestroyStack(StType *&s) { free(s); } //判断空 bool StackEmpty(StType *s) { return (s->top==-1); } //求迷宫路径 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; StType *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->data[s->top].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; }
五.运行结果
六.实验补充
这一次主要是使用数据结构中栈的相关操作,在此基础上,独立写出求解迷宫路径的算法。
同时数据结构还有线性表等,可以观看我的其他博客了解,同时下一篇博客还会用栈的链式存储结构完成。