迷宫实验报告

1、.一、实验内容3、迷宫问题。假设迷宫由m 行 n 列构成，有一个出口和一个入口，入口坐标为（1,1），出口坐标为（ m,n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个 “无法通过”的信息。（ 1）用 c 语言实现顺序存储队列上的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。（ 2）设计一个二维数组mazem+2n+2表示迷宫，数组元素为0 表示该位置可以通过，数组元素为1 表示该位置不可以通行。maze11、mazemn分别为迷宫的入口和出口。（ 3）输入迷宫的大小m 行和 n 列，动态生成二维数组；由随机数产生0 或 1，建立迷宫，注意 m*n 的迷宫需要进

2、行扩展，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。（ 4）要求输出模拟迷宫的二维数组；若存在最短路径，则有出口回溯到入口（出队列并利用栈实现） ，再打印从入口到出口的这条路径，例如（1,1）， .，（ i,j ）， .，（ m,n）；若没有路径，则打印“no path”。（ 5）迷宫的任一位置（i,j ）上均有八个可移动的方向，用二维数组direction 存放八个方向的位置偏移量。direction82=0,1， 1,1 ， 0 ， -1 ， -1 ， -1 ，1,-1 ， 1,0 ， -1,0 ， -1,1 ；（ 6）为避免出现原地踏步的情况需要标志已经通过的位置，采用

3、一个标志数组 markm+2n+2 ，初值均为 0，在寻找路径的过程中， 若通过了位置 （i ，j），则将 markij 置为 1。（ 7）为了记录查找过程中到达位置（ i ，j）及首次到达（ i,j ）的前一位置 （i_pre,j_pre ），需要记住前一位置（ i_pre,j_pre）在队列中的序号 pre，即队列中数据元素应该是一个三元组（ i,j,pre ）。（ 8）搜索过程简单下： 将入口 maze11 作为第一个出发点， 依次在八个方向上搜索可通行的位置，将可通行位置（ i,j,pre ）入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行

4、位置，形成第二层新的出发点，.，如此进行下去，直至达到出口mazemn或者迷宫所有位置都搜索完毕为止。二、实验过程及结果一、需求分析1、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。2、以二维数组mm+2n+2 表示迷宫， mij表示迷宫中相应（i,j ）位置的通行状态（ 0:表示可以通行， 1：表示有墙，不可通行） ，完成迷宫的抽象数据类型，包括出口、入口位置等。3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在 50 以下 )，完成对应迷宫的初始化。根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，

5、无方块的地方可通过，如下例所示：如下所示：.4、程序完成对迷宫路径的搜索，为了更好地显示出求解结果，如果存在路径，则以长方形形式将迷宫打印出来， 而不是只按步输出坐标， 也便于检查路径的正确性， 用特定符号标出迷宫的物理状态，其中字符“ #”表示出口和入口， “”标记出可行的路径；如果程序完成搜索后没有找到通路，则提示用户“no path! ”。如图所示：5、 程序执行的命令： 创建初始化迷宫； 搜索迷宫； 输出搜索到的最短路径。.二、概要 （按照 目要求 用 列 路径的存 ， 但操作 程中遇到很多困 未能解决， 故 的操作来 路径的存 ）1、迷 的抽象数据 型定 ：adt maze数据 象：

6、 d：=aij,start,end|-20=aij20,start,end (i,j)|0 i m+2,0 j n+2,m,n 0 数据关系： r=length ， widthlength=|ai-1,aij d i=1, ,m+2,j=1, ,n+2width=|aijaij-1 d基本操作 :setmaze(&m)初始条件：m已 定 ，m的下属 元二 数 m.mazerow+2d+2已存在，m.start,m.end 也已作 下属存 元存在操作 果：构成数据迷 ，用数 迷 的物理状 ，以0 表示通路， 以 1 表示障碍，由 端 取迷 空 大小，各点 的具体物理状 及start 和 end

7、点位置，完成迷 构建pass(m, curpos)初始条件：已知目前迷 状 及当前位置操作 果：完成相 的搜索任 ，如果可行， 返回1nextpos(curpos, directionr)操作 果：返回curpos 位置在方向direction 上的下一位置sameseat(path,row,col)操作 果：若（row ，col）位置是路径path 中的一个点， 返回trueprintmaze(m)初始条件：迷 m 已存在操作 果： 出字符 示的迷 mazepath(m,&path)初始条件：迷 m 已存在操作 果：搜索迷 ，用path 返回搜索所得路径。如不存在，返回0printpath(

8、m,path)初始条件：迷 m 已存在操作 果：迷 m 存在可行路径 将迷 m 及相 最短路径一起打印 出adt maze； 本程序模 构 主函数模 void main()初始化迷 和 ； 建迷 ； 出迷 ；搜索路径； 出路径； 模 抽象数据 型； 迷 模 迷 抽象数据 型；.各模块之间的调用关系如下：主程序模块迷宫模块栈模块三、详细设计1、基本数据类型操作 栈模块 typedef structint order;position seat;int direction;selemtype;/ 步数、方向及位置/栈定义 typedef struct lnodeselemtype *base;se

9、lemtype *top;/ 设两指针便于判断栈是否为空int stacksize;/ 栈当前可使用的最大容量sqstack; 参数设置：#define stack_init_size 100#define stackincrent 10/- 基本操作的算法描述-status initstack(sqstack &s) / 构造一个空栈 s.base=(selemtype )malloc(stack_init_size*sizeof(selemtype);if(!s.base)exit(overlow);/ 存储分配失败s.top=s.base;s.stacksize=stack_init_s

10、ize;return ok;status stackempty(sqstack &s)/ 若 s 为空返回true ，否则返回falsereturn s.base=s.top;status gettop(sqstack &s,selemtype &e)/ 栈不空，用 e 返回 s 的栈顶元素及 ok ，否则返回 error if(s.top=s.base)return error;e=*(s.top-1); return ok;.status push(sqstack &s,selemtype &e) / 插入元素 e 为新的栈顶元素 if(s.top-s.base=s.stacksize)/

11、 栈满追加存储空间s.base=(selemtype)realloc(s.base,(s.stacksize+stackicrement)sizeof( selemtype);if(!s.base)exit(overflow)/ 存储分配失败s.top=s.base+s.stacksize;/ 确定新的栈顶指针s.stacksize+=stackincrement;/已分配空间增加*s.top+=*e;return ok;status pop(sqstack &s,selemtype &e)/ 若栈不变，则删除栈顶元素，用e 返回其值及ok, 否则 falseif(s.top=o=s.base

12、)return error;*e=*-s.top;/ 顶指针减小，用e 返回其数据return ok; 迷宫模块： 迷宫的数据类型#define maxlength 50/ 迷宫的最大长度#define maxwidth50/ 屏幕宽度，迷宫的最大宽度/元素类型typedef int status;typedef structint row;int col;position;/位置坐标/迷宫定义typedef int elemtype;typedef struct mazeelemtype mazemaxlengthmaxwidth;/ 迷宫的物理状态描述int length,width;/

13、迷宫的大小position start,end;/ 开始与结束位置与栈的单元类型相同maze;/ “迷宫”型数据迷宫模块中的基本操作status semaze(maze &m)printf( “please input the length and width of the maze” );sanf(“ rlength,width ” );for(k=0;kmaze0k=1;for(j=0;jmazej0=1;for(j=0;jmazejwidth+1=1;for(k=0;kmazelength+1k=1;/设置迷宫围墙for(j=1;j=length;j+)for(k=1;kmazejk=r

14、and()%2;/随机生成迷宫m-length=length;m-width=width;m-start.row=1;m-start.col=1;m-end.row=m-length;m-end.col=m-width;m-mazem-start.rowm-start.col=m-mazem-end.rowm-end.col=0;/ 入口和出口设置 */void printmaze(maze m)/ 打印出迷宫，包括边界printf( 迷宫入口 :1,1- 用 #表示 n);printf( 迷宫出口 :%d,%d- 用 #表示 n,m.length,m.width);for(row=0;row

15、m.length+2;row+)for(col=0;colm.width+2;col+)if(row=1&col=1)|(row=m.length&col=m.width)printf(# );/ 入口和出口用 #表示elseprintf(%c ,m.mazerowcol);printf(n);/用字符型打印输出（i,j ）状态status pass( maze m,position curpos) / 判断迷宫中当前位置 curpos 上能否通过/ 如果通过返回 1if (m.mazecurpos.rowcurpos.col=0)return 1;/ 如果当前位置是可以通过，返回1else

16、return 0;/ 其它情况返回0./ 探索第一步.position nextpos(position curpos, int direction) /返回当前位置在direction 方向上的下一位置returnpos.row=curpos.row+directiondirection-10;returnpos.col=curpos.col+directiondirection-11;return returnpos;status sameseat(sqstack path,int row,int col)/位置（ row ， col）在路径中时返回truewhile(ppath.top)

17、if(path.basenum.seat.row=row&path.basenum.seat.col=col)/路 径 某一步所在的位置return true;num+;p+;return false;status mazepath(maze m,sqstack *s)/ 若迷宫 maze 中从入口start 到出口end 的通道，则求得一条存放在栈中/ （从栈底到栈顶） ，并返回 success；否则返回 fail curpos=m.start; / 设定 当前位置 为 入口位置 curstep=1;/ 第一次查找路径，设置5 个方向 (不远离 ! 终点的五个方向 )，若找到则返回succe

18、ssdoif(pass(m,curpos) / 当前位置可通过，即是未曾走到过的通道块 m.mazecurpos.rowcurpos.col= ; / 留下足迹e.direction=1;e.order=curstep;e.seat=curpos;push(s,&e);/ 加入路径if(curpos.row=m.end.row&curpos.col=m.end.col)/ 到达终点（出口）return success;curpos=nextpos(curpos,1);/ 下一位置在当前位置的右下方curstep+;/ 探索下一步else/ 当前位置不能通过if(!stackempty(s)po

19、p(s,&e);while(e.direction=5&!stackempty(s).m.mazecurpos.rowcurpos.col= ; /标记不能通过pop(s,&e);/ 留下不能通过的标记，并退回一步 / whileif(e.direction5)e.direction+;gettop(s,&te);if(e.direction=5&te.direction=2)pop(s,&e);e.direction+;push(s,&e);/ 换下一个方向探索curpos=nextpos(e.seat,e.direction);/当前位置设为新方向的相邻块 / if / if / else

20、while(!stackempty(s);curpos=m.start;/ 设定 当前位置 为 入口位置 curstep=1;/ 探索第一步/ 如果第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况doif(pass(m,curpos) / 当前位置可通过，即是未曾走到过的通道块 m.mazecurpos.rowcurpos.col= ; / 留下足迹e.direction=1;e.order=curstep;e.seat=curpos;push(s,&e);/ 加入路径if(curpos.row=m.end.row&curpos.col=m.end.col)/

21、到达终点（出口）/printpath(maze,s);/输出路径return success;curpos=nextpos(curpos,1);/ 下一位置是当前位置的东邻curstep+;/ 探索下一步else/ 当前位置不能通过if(!stackempty(s)pop(s,&e);while(e.direction=8&!stackempty(s)m.mazecurpos.rowcurpos.col= ; /标记不能通过pop(s,&e);/ 留下不能通过的标记，并退回一步 / while if(e.direction8).e.direction+;gettop(s,&te);if(e.d

22、irection=4&te.direction=2)pop(s,&e);e.direction+;push(s,&e);/ 换下一个方向探索curpos=nextpos(e.seat,e.direction);/当前位置设为新方向的相邻块 / if / if / else while(!stackempty(s);return fail; / mazepathvoid printpath(maze m, sqstack path)/ 将迷宫及路径一起打印 if(stackempty(&path)printf(no path!n);/路径栈为空，则提示无路径exit(overflow);prin

23、tf(nthe path:n);for(row=0;rowm.length+2;row+)for(col=0;col );num+;p+;elseprintf(%c ,m.mazerowcol);printf(n); 主函数算法：void main()maze m;sqstack path;initstack(&path);.setmaze(&m);printmaze(m);mazepath(m,&path);printpath(m,path); 函数的 用关系反映了本演示程序的 次 构main工作 置迷 理initstackmazepathprintpathprintmazepasssetm

24、azesameseatnextpospushgettoppopstackempty四、 分析1、开始没有将 mnm.start.end 置 maze 型数据的下属 元，使得各个迷 操作的函数参数十分散 ， 各参数关系不易把握。2、另行 置 printpath 函数，使得 端 出更加友好，并巧妙地将迷 以特殊、明朗的字符 出，效果更好。3、开始出 入 的条件没有控制好， 致 出 不是完整路径，甚至出 。4、 方向 有一定策略，开始 按照 依次 取方向， 太耗 且效果不好， 容易出 不必要的弯折走法， 后来通 控制方向 序， 即第一方向 南方，然后再 方、南方 .， 取越靠近出口的方向 先方向，因

25、 的 搜索路径 自然会本着路径最短的原 向出口 行 ，那么找到的路径自然是最短路径（之一）。5、由于八个方向的特殊性，根据方向的 序，搜索路径 仍会出 多走的情况，比如先往 再往西南， 其 是可以直接往南的， 因此 了避免 种情况， 在入 要先 行 种情况的判断，如是 种情况 出 将前一位置方向改 再入 。6、 了便于找到最短路径，起初只使用了靠近出口 的五个方向，但是 有特殊情况存在 由于不能想 离出口的方向行 而找不到路径，因此在搜索路径 行了两次搜索，第一次使用五个靠 出口的方向搜索，找到路径 返回success，若未搜索到 再 行一次八个方向的搜索，即 了防止漏掉特殊情况，找到 返回s

26、uccess，由于第一搜索无 果若第二次搜索到路径也只能是特殊情况，故也 是最短路径（之一）。7、最大的 是并没有按照 目要求来做，因 目中要求用 列来存 路径， 有很多 以解决，故 了只用 的方法来 。.五、用户说明 本程序的运行环境为windows 7 （ 64 位）操作系统，执行文件为数据结构迷宫.exe； 进入演示程序后，即显示对话形式的提示操作过程，1、提出输入迷宫的大小2、按 enter 键输出随机生成的迷宫3、按 enter 键开始搜索路径搜索结果：the path：输出迷宫及路径或者输出no path! 提示输入迷宫大小后，用户输入所要处理迷宫的长row ，宽 col ； 提示

27、输入迷宫后，用户将迷宫输入，0 代表可行， 1 代表障碍； 按任意键开始后，程序自动进行对所建迷宫的搜索，并将搜索结果； 按任意键退出程序。六、测试结果1、无路径：.2、找到最短路径：.七、附录（源代码及注释）#include time.h#include stdio.h#include stdlib.h#include conio.h#define null 0#define true 1#define false 0#define success 1#define fail 0#define ok 1#define error 0#define overflow -1#define inf

28、easible -2#define maxlength 50#define maxwidth50#define stack_init_size 100#define stackincrent 10/元素类型typedef int status;typedef structint row;int col;position;/ 位置坐标typedef structint order;position seat;int direction;selemtype;/ 步数、方向及位置/栈定义typedef struct lnodeselemtype *base;selemtype *top;/ 设两指针

29、便于判断栈是否为空int stacksize;/ 栈当前可使用的最大容量sqstack;/迷宫定义typedef int elemtype;typedef struct maze.elemtype mazemaxlengthmaxwidth;int length,width;position start,end;maze;/ 迷宫大小及出入口位置/栈操作函数声明status initstack(sqstack *s);/ 初始化status stackempty(sqstack *s);/ 判空status gettop(sqstack *s,selemtype *e);/ 取栈顶元素stat

30、us push(sqstack *s,selemtype *e);/ 入栈status pop(sqstack *s,selemtype *e);/ 出栈/迷宫操作函数说明void setmaze(maze *m);/* 设置迷宫，随机生成*/void printmaze(maze m);/* 输出迷宫 */status pass(maze m, position curpos);/ 判断当前位置是否可通 position nextpos(position curpos, int directionr);/ 下一位置status sameseat(sqstack path,int row,in

31、t col);/ 找到迷宫中可行路径的各个位置 status mazepath(maze m,sqstack *path);/ 搜索迷宫路径void printpath(maze m, sqstack path);/若迷宫 m 存在可行路径则将该路径在迷宫中输出/主函数void main()maze m;sqstack path;initstack(&path);setmaze(&m);printmaze(m);mazepath(m,&path);printpath(m,path);/迷宫操作void setmaze(maze *m)int length,width,j,k;printf(pl

32、ease input the length and width of the maze:nlength (0length=50):);scanf(%d,&length);printf(width (0width=50):);scanf(%d,&width);srand(unsigned)time(null);for(k=0;kmaze0k=1;for(j=0;jmazej0=1;.for(j=0;jmazejwidth+1=1;for(k=0;kmazelength+1k=1;/设置迷宫围墙for(j=1;j=length;j+)for(k=1;kmazejk=rand()%2;/ 随机生成迷

33、宫m-length=length;m-width=width;m-start.row=1;m-start.col=1;m-end.row=m-length;m-end.col=m-width;m-mazem-start.rowm-start.col=m-mazem-end.rowm-end.col=0;/ 入口和出口设置 */void printmaze(maze m)int row,col;printf( 迷宫入口 :1,1- 用 #表示 n);printf( 迷宫出口 :%d,%d- 用 #表示 n,m.length,m.width);for(row=0;rowm.length+2;row

34、+)for(col=0;colm.width+2;col+)if(row=1&col=1)|(row=m.length&col=m.width)printf(# );/ 入口和出口用 #表示elseprintf(%c ,m.mazerowcol);printf(n);status pass( maze m,position curpos) if (m.mazecurpos.rowcurpos.col=0)return 1;/ 如果当前位置是可以通过，返回1else return 0;/ 其它情况返回0position nextpos(position curpos, int direction

35、) position returnpos;int direction82=1,1,0,1,1,0,-1,1,1,-1,0,-1,-1,0,-1,-1;/按一定次序依次设置八个方向returnpos.row=curpos.row+directiondirection-10;returnpos.col=curpos.col+directiondirection-11;return returnpos;.status sameseat(sqstack path,int row,int col)selemtype *p=path.base;int num=0;while(ppath.top)if(pa

36、th.basenum.seat.row=row&path.basenum.seat.col=col)/路径某一步所在的位置return true;num+;p+;return false;status mazepath(maze m,sqstack *path)/ 若迷宫 maze 中从入口start 到出口end 的通道，则求得一条存放在栈中/ （从栈底到栈顶） ，并返回 success；否则返回 fail position curpos;int curstep; selemtype e,te;curpos=m.start; / 设定 当前位置 为 入口位置 curstep=1;/ 探索第一

37、步/第一次查找路径，设置 5 个方向 (不远离 !终点的五个方向 )，若找到则返回 success doif(pass(m,curpos) / 当前位置可通过，即是未曾走到过的通道块 m.mazecurpos.rowcurpos.col= ; / 留下足迹e.direction=1;e.order=curstep;e.seat=curpos;push(s,&e);/ 加入路径if(curpos.row=m.end.row&curpos.col=m.end.col)/ 到达终点（出口）return success;curpos=nextpos(curpos,1);/ 下一位置在当前位置的右下方c

38、urstep+;/ 探索下一步else/ 当前位置不能通过if(!stackempty(s)pop(s,&e);while(e.direction=5&!stackempty(s)m.mazecurpos.rowcurpos.col= ; /标记不能通过pop(s,&e);/ 留下不能通过的标记，并退回一步 / while if(e.direction5).e.direction+;gettop(s,&te);if(e.direction=5&te.direction=2)pop(s,&e);e.direction+;push(s,&e);/ 换下一个方向探索curpos=nextpos(e.

39、seat,e.direction); /当前位置设为新方向的相邻块 / if / if / else while(!stackempty(s);curpos=m.start; / 设定 当前位置 为 入口位置 curstep=1;/ 探索第一步/如果第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况doif(pass(m,curpos) / 当前位置可通过，即是未曾走到过的通道块 m.mazecurpos.rowcurpos.col= ; / 留下足迹e.direction=1;e.order=curstep;e.seat=curpos;push(s,&e);/ 加入路径if(curpos.row=m.end.row&curpos.col=m.end.col)/ 到达终点（出口）/printpath(maze,s);/输出路径return success;curpos=nextpos(curpos,1);/ 下一位置是当前位置的东邻curstep+;/ 探索下一步else/ 当前位置不能通过if(!stackempty(s)p