文档介绍：数据结构试验——迷宫问题数据结构试验——迷宫问题(一)基本问题 1. 问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入,让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行, 迷宫唯一的出口处放有一块奶酪,吸引老鼠找到出口。简而言之,迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图 1所示。图 1迷宫示意图迷宫四周设为墙; 无填充处, 为可通处。设每个点有四个可通方向, 分别为东、南、西、北( 为了清晰,以下称“上下左右”) 。左上角为入口。右下角为出口。迷宫有一个入口,一个出口。设计程序求解迷宫的一条通路。 2. 数据结构设计以一个 m×n的数组 mg表示迷宫,每个元素表示一个方块状态,数组元素 0 和1分别表示迷宫中的通路和障碍。迷宫四周为墙,对应的迷宫数组的边界元素均为 1。根据题目中的数据,设置一个数组 mg如下 int mg[M+2][N+2]= {{1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构,将栈定义为 Struct {int i;//当前方块的行号 int j;//当前方块的列号 int di; //di 是下一个相邻的可走的方位号}st[MaxSize];// 定义栈数据结构试验——迷宫问题 int top=-1 //初始化栈 3 设计运算算法要寻找一条通过迷宫的路径,就必须进行试探性搜索,只要有路可走就前进一步,无路可进,换一个方向进行尝试;当所有方向均不可走时,则沿原路退回一步(称为回溯) ,重新选择未走过可走的路,如此继续,直至到达出口或返回入口(没有通路) 。在探索前进路径时,需要将搜索的踪迹记录下来,以便走不通时,可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反,因此可以借用一个栈来记录前进路径。方向:每一个可通点有 4个可尝试的方向,向不同的方向前进时,目的地的坐标不同。预先把 4个方向上的位移存在一个数组中。如把上、右、下、左(即顺时针方向)依次编号为 0、1、2、 move[4] 如图 3所示。 move[4] xy0-1010121030-1 图2数组 move[4] 方位示意图如下: 通路:通路上的每一个点有 3个属性:一个横坐标属性 i、一个列坐标属性 j和一个方向属性 di,表示其下一点的位置。如果约定尝试的顺序为上、右、下、左(即顺时针方向) ,则每尝试一个方向不通时, di值增 1,当 d增至 4 时,表示此位置一定不是通路上的点,从栈中去除。在找到出口时,栈中保存的就是一条迷宫通路。(1 )下面介绍求解迷宫( xi,yj )到终点( xe,ye )的路径的函数:先将入口进栈(其初始位置设置为—1),在栈不空时循环——取栈顶方块(不退栈)①若该方块为出口,输出所有的方块即为路径,其代码和相应解释如下: 数据结构试验——迷宫问题 int mgpath(int xi,int yi,int xe,int ye) // 求 解路径为:(xi,yi)->(xe,ye) {struct {int i;//当前方块的行号 int j;//当前方块的列号 int di;//di 是下一可走方位的方位号}st[MaxSize]; //定义栈 int top=-1; //初始化栈指针 int i,j,k,di,find; top++; //初始方块进栈 st[top].i=xi;st[top].j=yi; st[top].di=-1;mg[1][1]=-1; while (top>-1) //栈不空时循环{i=st[top].i;j=st[top].j;di=st[top].di; //取栈顶方块 if(i==xe &&j==ye) //找到了出口,输出路径{printf(" 迷宫路径如下:\n"); for (k=0;k<=top;k++) {printf("\t(%d,%d)",st[k].i,st[k].j); if((k+1)%5==0) //每输出每 5个方块后换一行 printf("\n"); }printf("\n"); return(1); //找到一条路径后返回 1 }②否则,找下一个可走的相邻方块若不存在这样的路径,说明当前的路径不可能走通,也就是恢复当前方块为 0后退栈。若存在这样的方块,则其方位保存在栈顶元素中,并将这个可走的相邻方块进栈(其初始位置设置为-1) 求迷宫回溯过程如图 4所示数据结构试验——迷宫问题从前一个方块找到相邻可走方块之后, 再从当前