迷宫实验报告

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

2、上一圈不准通过的墙。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） 为防止出现原地踏步的情况需要标志已经通过的位置，采用一个标志数组MARKm+2n+2，初值均为0，在寻找路径的过程中，假设通过了位置i，j，那么将MARKij置为1。（7） 为了

3、记录查找过程中到达位置i，j及首次到达i,j的前一位置i_pre,j_pre，需要记住前一位置i_pre,j_pre在队列中的序号pre，即队列中数据元素应该是一个三元组i,j,pre。（8） 搜索过程简单下：将入口MAZE11作为第一个出发点，依次在八个方向上搜索可通行的位置，将可通行位置i,j,pre入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，.，如此进行下去，直至到达出口MAZEmn或者迷宫所有位置都搜索完毕为止。2、 实验过程及结果1、 需求分析1、用栈的根本操作完成迷宫问题的求解，其中栈的根本操作作为一个独

4、立的模块存在。2、以二维数组Mm+2n+2表示迷宫，Mij 表示迷宫中相应i,j位置的通行状态0:表示可以通行，1：表示有墙，不可通行，完成迷宫的抽象数据类型，包括出口、入口位置等。3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在50以下)，完成对应迷宫的初始化。根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过，如下例所示：如下所示：4、程序完成对迷宫路径的搜索，为了更好地显示出求解结果，如果存在路径，那么以长方形形式将迷宫打印出来，而不是只按步输出坐标，也便于检查路径的正确性，用特定符号标出迷宫的物理状态，

5、其中字符“#表示出口和入口，“<标记出可行的路径；如果程序完成搜索后没有找到通路，那么提示用户“No Path!。如下图：5、 程序执行的命令： 创立初始化迷宫； 搜索迷宫； 输出搜索到的最短路径。2、 概要设计按照题目要求应该用队列实现路径的存储，但操作过程中遇到很多困难未能解决，应选择栈的操作来实现路径的存储1、迷宫的抽象数据类型定义：ADT Maze数据对象：D：=aij,Start,end|-20<=aij<20,Start,end(i,j)|0im+2,0jn+2,m,n0 数据关系：R=length，width length=<ai-1j,aij>|a

6、i-1,aijD i=1,m+2,j=1,n+2 width=<aij-1,aij>|aijaij-1D根本操作: SetMaze(&M) 初始条件：M已经定义，M的下属单元二维数组M.Mazerow+2d+2已存在，M.start,M.end也已作为下属存储单元存在 操作结果：构成数据迷宫，用数值标识迷宫的物理状态，以0表示通路，以1表示障碍，由终端读取迷宫空间大小，各点处的具体物理状态及Start和End点位置，完成迷宫构建 Pass(M, CurPos) 初始条件：目前迷宫状态及当前位置 操作结果：完成相应的搜索任务，如果可行，那么返回1 NextPos(CurPos

7、, directionr) 操作结果：返回CurPOS位置在方向direction上的下一位置 SameSeat(Path,row,col) 操作结果：假设row，col位置是路径Path中的一个点，那么返回TRUE PrintMaze(M) 初始条件：迷宫M已存在 操作结果：输出字符标示的迷宫 MazePath(M,&Path) 初始条件：迷宫M已存在 操作结果：搜索迷宫，用path返回搜索所得路径。如不存在，返回0 PrintPath(M,Path) 初始条件：迷宫M已存在 操作结果：迷宫M存在可行路径那么将迷宫M及相应最短路径一起打印输出ADT MAZE； 本程序模块结构 主函数

8、模块void main()初始化迷宫和栈；创立迷宫；输出迷宫；搜索路径；输出路径； 栈模块实现栈抽象数据类型； 迷宫模块实现迷宫抽象数据类型；各模块之间的调用关系如下：主程序模块 迷宫模块 栈模块3、 详细设计1、根本数据类型操作 栈模块 typedef structint order;Position seat;int direction;SElemType;/步数、方向及位置/栈定义 typedef struct lnodeSElemType *base;SElemType *top;/设两指针便于判断栈是否为空int stacksize;/栈当前可使用的最大容量SqStack; 参数设置

9、：#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_SIZE;return ok;Status StackEmpty(Sqstack &S) / 假设S为空返回TRUE，否那么

10、返回FALSEreturn S.base=S.top;Status GetTop(SqStack &S,Selemtype &e) / 栈不空，用e返回s的栈顶元素及OK，否那么返回ERRORif(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)/ 栈满追加存储空间S.base=(SelemType)realloc(S.base,(S.stacks

11、ize+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)return ERROR;*e=*-S.top; / 顶指针减小，用e返回其

12、数据return ok; 迷宫模块： 迷宫的数据类型 #define MAXLENGTH 50/ 迷宫的最大长度#define MAXWIDTH 50/ 屏幕宽度，迷宫的最大宽度/元素类型typedef int Status;typedef structint row;int col;Position;/位置坐标/迷宫定义typedef int ElemType;typedef struct MAZEElemType MazeMAXLENGTHMAXWIDTH;/ 迷宫的物理状态描述int length,width;/ 迷宫的大小Position start,end;/ 开始与结束位置与栈的单

13、元类型相同MAZE;/ “迷宫型数据迷宫模块中的根本操作Status semaze(MAZE &M)Printf(“Please input the length and width of the MAZE);sanf(“rlength,width);for(k=0;k<width+2;k+)M->Maze0k=1;for(j=0;j<length+2;j+)M->Mazej0=1;for(j=0;j<length+2;j+)M->Mazejwidth+1=1;for(k=0;k<width+2;k+)M->Mazelength+1k=1

14、;/设置迷宫围墙for(j=1;j<=length;j+)for(k=1;k<=width;k+)M->Mazejk=rand()%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;/入口和出口设置

15、*/void PrintMaze(MAZE M) / 打印出迷宫，包括边界printf("迷宫入口:1,1-用#表示n");printf("迷宫出口:%d,%d-用#表示n",M.length,M.width);for(row=0;row<M.length+2;row+)for(col=0;col<M.width+2;col+)if(row=1&&col=1)|(row=M.length&&col=M.width)printf("# ");/入口和出口用#表示elseprintf("

16、;%c ",M.Mazerowcol);printf("n");/ 用字符型打印输出i,j状态Status Pass( MAZE M,Position CurPos) / 判断迷宫中当前位置CurPos上能否通过/ 如果通过返回1 if (M.MazeCurPos.rowCurPos.col=0) return 1; / 如果当前位置是可以通过，返回1 else return 0; / 其它情况返回0Position NextPos(Position CurPos, int direction) /返回当前位置在direction方向上的下一位置ReturnPos

17、.row=CurPos.row+Directiondirection-10;ReturnPos.col=CurPos.col+Directiondirection-11; return ReturnPos;Status SameSeat(SqStack Path,int row,int col)/位置row，col在路径中时返回TRUEwhile(p<Path.top)if(Path.basenum.seat.row=row&&Path.basenum.seat.col=col)/路径某一步所在的位置return TRUE;num+;p+;return FALSE;Sta

18、tus MazePath(MAZE M,SqStack *S) / 假设迷宫maze中从入口 start到出口 end的通道，那么求得一条存放在栈中/ 从栈底到栈顶，并返回SUCCESS；否那么返回FAILcurpos=M.start; / 设定"当前位置"为"入口位置"curstep=1; / 探索第一步/第一次查找路径，设置5个方向(不远离!终点的五个方向)，假设找到那么返回SUCCESSdo if(Pass(M,curpos) / 当前位置可通过，即是未曾走到过的通道块 M.Mazecurpos.rowcurpos.col=' '

19、/ 留下足迹 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) Pop(S,&e); while(e.direction=5&&!Stac

20、kEmpty(S) M.Mazecurpos.rowcurpos.col=' '/标记不能通过 Pop(S,&e); / 留下不能通过的标记，并退回一步 / while if(e.direction<5) 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); / 当前位置设为新方向的相邻块

21、 / if / if / elsewhile(!StackEmpty(S);curpos=M.start; / 设定"当前位置"为"入口位置"curstep=1; / 探索第一步/如果第一次查找无结果那么再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况do if(Pass(M,curpos) / 当前位置可通过，即是未曾走到过的通道块 M.Mazecurpos.rowcurpos.col=' ' / 留下足迹 e.direction=1; e.order=curstep; e.seat=curpos; Push(S,&

22、;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) Pop(S,&e); while(e.direction=8&&!StackEmpty(S) M.Mazecurpos.rowcurpos.col='

23、; '/标记不能通过 Pop(S,&e); / 留下不能通过的标记，并退回一步 / while if(e.direction<8) e.direction+; GetTop(S,&te); if(e.direction=4&&te.direction=2) Pop(S,&e); e.direction+; Push(S,&e); / 换下一个方向探索 curpos=NextPos(e.seat,e.direction); / 当前位置设为新方向的相邻块 / if / if / elsewhile(!StackEmpty(S);ret

24、urn FAIL; / MazePathvoid PrintPath(MAZE M, SqStack Path)/ 将迷宫及路径一起打印if(StackEmpty(&Path)printf("No Path!n");/路径栈为空，那么提示无路径exit(OVERFLOW);printf("nThe Path:n");for(row=0;row<M.length+2;row+)for(col=0;col<M.width+2;col+)if(SameSeat(Path,row,col)if(row=1&&col=1)|(r

25、ow=M.length&&col=M.width)printf("# ");elseprintf("> ");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); 函数的调用关系反映了本演示程

26、序的层次结构迷宫处理工作栈设置mainInitStack MazePath PrintPath PrintMaze Pass SetMaze SameSeat NextPos Push GetTop Pop StackEmpty 4、 调试分析1、开始没有将Mnm.start.end设置为MAZE 型数据的下属单元，使得各个迷宫操作的函数参数十分散杂，调试时各参数关系不易把握。2、另行设置PrintPath函数，使得终端输出更加友好，并巧妙地将迷宫以特殊、明朗的字符输出，效果更好。3、开始出栈入栈的条件没有控制好，导致输出时不是完整路径，甚至出错。4、选择方向时有一定策略，开始选择时按照顺时针

27、依次读取方向，发现太耗时且效果不好，容易出现不必要的弯折走法，后来通过控制方向顺序，即第一方向为东南方，然后再东方、南方.，选取越靠近出口的方向为优先方向，因为这样的话搜索路径时自然会本着路径最短的原那么向出口处行进，那么找到的路径自然是最短路径之一。5、由于八个方向的特殊性，根据方向的顺序，搜索路径时仍会出现多走的情况，比方先往东再往西南，其实是可以直接往南的，因此为了防止这种情况，在入栈时还要先进行这种情况的判断，如是这种情况那么出栈将前一位置方向改变再入栈。6、为了便于找到最短路径，起初只使用了靠近出口处的五个方向，但是发现有特殊情况存在时由于不能想远离出口的方向行进而找不到路径，因此在

28、搜索路径时进行了两次搜索，第一次使用五个靠进出口的方向搜索，找到路径时那么返回SUCCESS，假设未搜索到那么再进行一次八个方向的搜索，即为了防止漏掉特殊情况，找到时那么返回SUCCESS，由于第一搜索无结果假设第二次搜索到路径也只能是特殊情况，故也应该是最短路径之一。7、最大的问题是并没有按照题目要求来做，因为题目中要求用队列来存储路径，经过实验发现有很多问题难以解决，应选择了只用栈的方法来实现。5、 用户说明 本程序的运行环境为windows 764位操作系统，执行文件为数据结构迷宫.exe； 进入演示程序后，即显示对话形式的提示操作过程， 1、提出输入迷宫的大小2、按enter键输出随机

29、生成的迷宫3、按enter键开始搜索路径搜索结果：The Path：输出迷宫及路径或者输出No Path! 提示输入迷宫大小后，用户输入所要处理迷宫的长row，宽col； 提示输入迷宫后，用户将迷宫输入，0代表可行，1代表障碍； 按任意键开始后，程序自动进行对所建迷宫的搜索，并将搜索结果； 按任意键退出程序。6、 测试结果1、 无路径：2、 找到最短路径：7、 附录源代码及注释#include "time.h"#include "stdio.h"#include "stdlib.h"#include "conio.h&quo

30、t;#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 INFEASIBLE -2#define MAXLENGTH 50#define MAXWIDTH 50#define STACK_INIT_SIZE 100#define STACKINCRENT 10/元素类型typedef int Status;typedef structint row;int col;Position;/位置坐标

31、typedef structint order;Position seat;int direction;SElemType;/步数、方向及位置/栈定义typedef struct lnodeSElemType *base;SElemType *top;/设两指针便于判断栈是否为空int stacksize;/栈当前可使用的最大容量SqStack;/迷宫定义typedef int ElemType;typedef struct MAZEElemType MazeMAXLENGTHMAXWIDTH;int length,width;Position start,end;MAZE;/迷宫大小及出入口

32、位置/栈操作函数声明Status InitStack(SqStack *S);/初始化Status StackEmpty(SqStack *S);/判空Status GetTop(SqStack *s,SElemType *e);/取栈顶元素Status Push(SqStack *S,SElemType *e);/入栈Status Pop(SqStack *s,SElemType *e);/出栈/迷宫操作函数说明void SetMaze(MAZE *M);/*设置迷宫，随机生成*/void PrintMaze(MAZE M);/*输出迷宫*/Status Pass(MAZE M, Posit

33、ion CurPos);/判断当前位置是否可通Position NextPos(Position CurPos, int directionr);/下一位置Status SameSeat(SqStack Path,int row,int col);/找到迷宫中可行路径的各个位置Status MazePath(MAZE M,SqStack *Path);/搜索迷宫路径void PrintPath(MAZE M, SqStack Path);/假设迷宫M存在可行路径那么将该路径在迷宫中输出/主函数void main()MAZE M;SqStack path;InitStack(&path)

34、;SetMaze(&M);PrintMaze(M);MazePath(M,&path);PrintPath(M,path);/迷宫操作void SetMaze(MAZE *M)int length,width,j,k;printf("Please input the length and width of the MAZE:nlength (0<length<=50):");scanf("%d",&length);printf("width (0<width<=50):");scanf(

35、"%d",&width);srand(unsigned)time(NULL);for(k=0;k<width+2;k+)M->Maze0k=1;for(j=0;j<length+2;j+)M->Mazej0=1;for(j=0;j<length+2;j+)M->Mazejwidth+1=1;for(k=0;k<width+2;k+)M->Mazelength+1k=1;/设置迷宫围墙for(j=1;j<=length;j+)for(k=1;k<=width;k+)M->Mazejk=rand()%2;

36、/随机生成迷宫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(

37、"迷宫出口:%d,%d-用#表示n",M.length,M.width);for(row=0;row<M.length+2;row+)for(col=0;col<M.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 Cur

38、Pos) if (M.MazeCurPos.rowCurPos.col=0) return 1; / 如果当前位置是可以通过，返回1 else return 0; / 其它情况返回0Position NextPos(Position CurPos, int direction) 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+D

39、irectiondirection-11; return ReturnPos;Status SameSeat(SqStack Path,int row,int col)SElemType *p=Path.base;int num=0;while(p<Path.top)if(Path.basenum.seat.row=row&&Path.basenum.seat.col=col)/路径某一步所在的位置return TRUE;num+;p+;return FALSE;Status MazePath(MAZE M,SqStack *Path) / 假设迷宫maze中从入口 st

40、art到出口 end的通道，那么求得一条存放在栈中/ 从栈底到栈顶，并返回SUCCESS；否那么返回FAILPosition curpos;int curstep;SElemType e,te;curpos=M.start; / 设定"当前位置"为"入口位置"curstep=1; / 探索第一步/第一次查找路径，设置5个方向(不远离!终点的五个方向)，假设找到那么返回SUCCESSdo if(Pass(M,curpos) / 当前位置可通过，即是未曾走到过的通道块 M.Mazecurpos.rowcurpos.col=' ' / 留下足迹

41、 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) Pop(S,&e); while(e.direction=5&&!StackEmpty

42、(S) M.Mazecurpos.rowcurpos.col=' '/标记不能通过 Pop(S,&e); / 留下不能通过的标记，并退回一步 / while if(e.direction<5) 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

43、/ if / elsewhile(!StackEmpty(S);curpos=M.start; / 设定"当前位置"为"入口位置"curstep=1; / 探索第一步/如果第一次查找无结果那么再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况do if(Pass(M,curpos) / 当前位置可通过，即是未曾走到过的通道块 M.Mazecurpos.rowcurpos.col=' ' / 留下足迹 e.direction=1; e.order=curstep; e.seat=curpos; Push(S,&e); /

44、 参加路径 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) Pop(S,&e); while(e.direction=8&&!StackEmpty(S) M.Mazecurpos.rowcurpos.col=' '/标记不能通过 Pop(S,&e); / 留下不能通过的标记，并退回一步 / while if(e.direction<8) e.direction+; GetTop(S,&te); if(e.directi