迷宫实验报告(共19页).doc

《迷宫实验报告(共19页).doc》由会员分享，可在线阅读，更多相关《迷宫实验报告(共19页).doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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） 为避免出现原地踏步的情况需要标志已经通过的位置，采用一个标志数组MARKm+2n+2，初值均为0，在寻找路径的过程中

3、，若通过了位置（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）入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，.，如此进行下去，直至达到出口MAZEmn或者迷宫所有位置都搜索完毕为止。二、 实验过

4、程及结果一、 需求分析1、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。2、以二维数组Mm+2n+2表示迷宫，Mij 表示迷宫中相应（i,j）位置的通行状态（0:表示可以通行，1：表示有墙，不可通行），完成迷宫的抽象数据类型，包括出口、入口位置等。3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在50以下)，完成对应迷宫的初始化。根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过，如下例所示：如下所示：4、程序完成对迷宫路径的搜索，为了更好地显示出求解结果，如果存在路径，则以长方形形式

5、将迷宫打印出来，而不是只按步输出坐标，也便于检查路径的正确性，用特定符号标出迷宫的物理状态，其中字符“#”表示出口和入口，“”标记出可行的路径；如果程序完成搜索后没有找到通路，则提示用户“No Path!”。如图所示：5、 程序执行的命令： 创建初始化迷宫； 搜索迷宫； 输出搜索到的最短路径。二、 概要设计（按照题目要求应该用队列实现路径的存储，但操作过程中遇到很多困难未能解决，故选择栈的操作来实现路径的存储）1、迷宫的抽象数据类型定义：ADT Maze数据对象：D：=aij,Start,end|-20=aij20,Start,end(i,j)|0im+2,0jn+2,m,n0 数据关系：R=

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

7、os, 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； 本程序模块结构 主函数模块v

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

9、efine 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，否则返回FALSEreturn

10、 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.stacksize+STACKICREMENT)Sizeof(Selemtype

11、);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返回其数据return ok; 迷宫模块： 迷宫的数据类型 #define MAXLENGTH

12、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;/ 开始与结束位置与栈的单元类型相同MAZE;/ “迷宫”型数据迷宫模块中的基本操作Status semaze(MA

13、ZE &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=rand()%2;/随机生成迷宫 M-length=length;M-width=width;M-start.row=1;M-start.col=1;M-end.row=M-l

14、ength;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;rowM.length+2;row+)for(col=0;colM.width+2;col+)if(row=1&col=1)|(row=M.length&col=M.width)printf(# );

15、/入口和出口用#表示elseprintf(%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方向上的下一位置Retur

16、nPos.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)if(Path.basenum.seat.row=row&Path.basenum.seat.col=col)/路径某一步所在的位置return TRUE;num+;p+;return FALSE;Status Maz

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

18、at=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(S) M.Mazecurpos.rowcurpos.col= ;/标记不能通过 Pop(S,&e); / 留下不能通过的

19、标记，并退回一步 / 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.seat,e.direction); / 当前位置设为新方向的相邻块 / if / if / elsewhile(!StackEmpty(S);curpos=M.start; / 设定当前位置为入口位置curstep=1; / 探索第一步/如果第一次查找无结果则再进行一次八个方

20、向的查找，检查是否存在第一次查找不到的特殊情况do if(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); / 下一位置是

21、当前位置的东邻 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.direction=4&te.direction=2) Pop(S,&e); e.direction+; Push(S,&e); / 换下

22、一个方向探索 curpos=NextPos(e.seat,e.direction); / 当前位置设为新方向的相邻块 / if / if / elsewhile(!StackEmpty(S);return FAIL; / MazePathvoid PrintPath(MAZE M, SqStack Path)/ 将迷宫及路径一起打印if(StackEmpty(&Path)printf(No Path!n);/路径栈为空，则提示无路径exit(OVERFLOW);printf(nThe Path:n);for(row=0;rowM.length+2;row+)for(col=0;col );nu

23、m+;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); 函数的调用关系反映了本演示程序的层次结构迷宫处理工作栈设置mainInitStack MazePath PrintPath PrintMaze Pass SetMaze SameSeat NextPos Push GetTop Pop StackEmpty 四、 调试分析1、

24、开始没有将Mnm.start.end设置为MAZE 型数据的下属单元，使得各个迷宫操作的函数参数十分散杂，调试时各参数关系不易把握。2、另行设置PrintPath函数，使得终端输出更加友好，并巧妙地将迷宫以特殊、明朗的字符输出，效果更好。3、开始出栈入栈的条件没有控制好，导致输出时不是完整路径，甚至出错。4、选择方向时有一定策略，开始选择时按照顺时针依次读取方向，发现太耗时且效果不好，容易出现不必要的弯折走法，后来通过控制方向顺序，即第一方向为东南方，然后再东方、南方.，选取越靠近出口的方向为优先方向，因为这样的话搜索路径时自然会本着路径最短的原则向出口处行进，那么找到的路径自然是最短路径（之

25、一）。5、由于八个方向的特殊性，根据方向的顺序，搜索路径时仍会出现多走的情况，比如先往东再往西南，其实是可以直接往南的，因此为了避免这种情况，在入栈时还要先进行这种情况的判断，如是这种情况则出栈将前一位置方向改变再入栈。6、为了便于找到最短路径，起初只使用了靠近出口处的五个方向，但是发现有特殊情况存在时由于不能想远离出口的方向行进而找不到路径，因此在搜索路径时进行了两次搜索，第一次使用五个靠进出口的方向搜索，找到路径时则返回SUCCESS，若未搜索到则再进行一次八个方向的搜索，即为了防止漏掉特殊情况，找到时则返回SUCCESS，由于第一搜索无结果若第二次搜索到路径也只能是特殊情况，故也应该是最

26、短路径（之一）。7、最大的问题是并没有按照题目要求来做，因为题目中要求用队列来存储路径，经过实验发现有很多问题难以解决，故选择了只用栈的方法来实现。五、 用户说明 本程序的运行环境为windows 7（64位）操作系统，执行文件为数据结构迷宫.exe； 进入演示程序后，即显示对话形式的提示操作过程， 1、提出输入迷宫的大小2、按enter键输出随机生成的迷宫3、按enter键开始搜索路径搜索结果：The Path：输出迷宫及路径或者输出No Path! 提示输入迷宫大小后，用户输入所要处理迷宫的长row，宽col； 提示输入迷宫后，用户将迷宫输入，0代表可行，1代表障碍； 按任意键开始后，程序

27、自动进行对所建迷宫的搜索，并将搜索结果； 按任意键退出程序。六、 测试结果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 INFEASIBLE -2#define MAXLENGTH 50#define

28、MAXWIDTH 50#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;/设两指针便于判断栈是否为空int stacksize;/栈当前可使用的最大容量SqSta

29、ck;/迷宫定义typedef int ElemType;typedef struct MAZEElemType MazeMAXLENGTHMAXWIDTH;int length,width;Position start,end;MAZE;/迷宫大小及出入口位置/栈操作函数声明Status InitStack(SqStack *S);/初始化Status StackEmpty(SqStack *S);/判空Status GetTop(SqStack *s,SElemType *e);/取栈顶元素Status Push(SqStack *S,SElemType *e);/入栈Status Pop

30、(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,int col);/找到迷宫中可行路径的各个位置Status MazePath(MAZE M,SqStack *

31、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(Please input the length and width of the MAZE:nlength (0lengt

32、h=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;/随机生成迷宫M-length=length;M-width=width;M-start.row=1;M-start.col=1;M-

33、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+)for(col=0;colM.width+2;col+)if(row=1&col=1)|(row=M.length&col=M.width)p

34、rintf(# );/入口和出口用#表示elseprintf(%c ,M.Mazerowcol);printf(n);Status Pass( MAZE M,Position CurPos) 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

35、,-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(Path.basenum.seat.row=row&Path.basenum.seat.col=col)/路径某一步所在的位置return TRU

36、E;num+;p+;return FALSE;Status MazePath(MAZE M,SqStack *Path) / 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中/ （从栈底到栈顶），并返回SUCCESS；否则返回FAILPosition curpos;int curstep;SElemType e,te;curpos=M.start; / 设定当前位置为入口位置curstep=1; / 探索第一步/第一次查找路径，设置5个方向(不远离!终点的五个方向)，若找到则返回SUCCESSdo if(Pass(M,curpos) / 当前位置可通过，即是未曾走到

37、过的通道块 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) Pop(S,&e); while(e.direc

38、tion=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.seat,e.direction); / 当前位置设为新方向的相邻块 / if / if / elsewhile(!StackEmpty(S);curpos=M.start; / 设定当前位置为入口位置curstep=1; / 探索第一步/如果第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况do if(Pass(M,curpos) / 当前位置可通过，即是未曾走到过的通道块 M