迷宫问题实验报告.doc

07信管 王丹 学号：222007321022057迷宫问题实验报告题目：编制一个求解迷宫通路的程序一、 问题描述：迷宫是一个矩形区域，有一个入口和出口。在迷宫内部不能穿越墙或障碍。创建一个m行n列的迷宫，输入障碍物坐标，入口坐标和出口坐标，迷宫问题要求寻找一条从入口到出口的路径。二、需求分析1.用户输入迷宫的数据：迷宫的行数和列数，障碍物的坐标，入口坐标，出口坐标2.迷宫的入口位置和出口位置可由用户随时设定3.在本实验中，若设定的迷宫存在通路，则以“#”表示迷宫周围的墙和迷宫中的障碍物，以“*”表示迷宫中的通路，“”表示“死胡同”，即曾途经然而不能到底出口的位置，余者用空格符输出。若设定的迷宫不存在通路，则报告相应信息。4.本程序只求出一条成功的通路。5.程序执行的命令包括：创建迷宫，创建空栈，销毁栈，寻找通路，求解迷宫，输出迷宫的图形等等6.测试数据 当入口坐标为（1，1），出口坐标为（4，5）时，输出迷宫应为下图：三、 概要设计1. 设定栈的抽象数据类型定义：ADT Stack数据对象：D=ai | aiCharSet，i=1,2,n,n=0数据元素：R1= | ai-1 , aiD,i=2,n基本操作:InitStack(&S)操作结果:构造一个空栈S。DestoryStack（&S）初始条件：栈S已存在。操作结果：销毁栈S。ClearStack（&S）初始条件：栈S已存在。操作结果：将栈S清为空栈。StackLength（&S）初始条件：栈S已经存在。操作结果：返回栈S的长度。StackEmpty（&S）初始条件：栈S已经存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop（S，&e）初始条件：栈S已经存在。操作结果：若栈S不为空，则以e返回栈顶元素。Push（&S，e）初始条件：栈S已经存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop（&S，&e）初始条件：栈S已经存在。操作结果：删除S的栈顶元素，并以e返回其值。ADT Stack；2. 设定迷宫的抽象数据类型为：ADT Maze数据对象：D=ai,j| ai,j#,*,0=i=9,0=j=9数据关系：R=r，c r=| ai-1,j, ai,jD,i=1,9,j=0,.9 c=| ai,j-1, ai,jD,i=0,9,j=1,.9基本操作：InitMaze(MazeType &maze)初始条件：二维数组maze.adr已存在，其中自第1行至第r行,每行中自第1列至第c列的元素已有值，并且以字符*表示通路，以字符#表示障碍。操作结果：构成迷宫的字符型数组，以*表示通路，以字符#或空格表示迷宫中障碍墙，并在迷宫四周加上一圈障碍。MathPath（&M）初始条件：迷宫M已经被赋值。操作结果：若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：以数字表示路径的标号，字符表示死胡同，否则迷宫状态不变。PrintMaze（M）初始条件：迷宫M已经存在。操作结果：以字符形式输出迷宫。ADT Maze；3. 求解迷宫中的一条通路的伪码算法：设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的南邻位置为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索； 则设定新的位置为沿顺时针方向旋转找到的栈顶位置的下一邻块； 若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置； 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或栈空； while（栈不空）；四、 详细设计1.坐标位置类型typedef struct int r,c;/迷宫中r行c列的位置PosType;2.迷宫类型 typedef struct int r; int c;char adrMAXLENMAXLEN;MazeType;void InitMaze(MazeType &maze)/按照用户输入的r行和c列的二维数组/设置maze的初值，包括边上的一圈的值int Pass(MazeType maze,PostType curpos)/当前位置可通则返回TRUE，否则返回FALSE；void PrintMaze(MazeType maze)/将迷宫以字符型方阵的形式输出3.栈类型typedef struct int ord; PostType seat; int di; SElemType;typedef struct SElemType* base; SElemType* top; int stackSize; SqStack;栈的基本操作设置如下：int Initstack(Sqstack &s) s.base=(SElemType*)malloc(Stack_Init_size*sizeof(SElemType);if(!s.base) exit(overflow); s.top=s.base;s.stacksize=Stack_Init_size;return OK;/初始化int Stackempty(Sqstack s) if(s.top=s.base) return TRUE;else return FALSE;/判空int Pop(Sqstack &s,SElemType &e) printf(出栈的元素为: );if(s.top=s.base) return ERROR;e=*-s.top; printf(%d,%d,%d,%d)n ,e.seat.x,e.seat.y,e.ord,e.di);return OK;/删除int Push(Sqstack &s,SElemType e) printf(入栈的元素为:);*(s.top)+=e; printf(%d,%d,%d,%d)n ,e.seat.x,e.seat.y,e.ord,e.di);return OK;/插入void Destorystack(Sqstack &s) free(s.base);s.base=NULL;s.top=NULL;s.stacksize=0;/销毁4. 求迷宫路径的算法int MazePath(MazeType &maze,PostType start,PostType end) SqStack S; PostType curpos; int curstep; SElemType e; InitStack(S); curpos=start; curstep=1; do if(Pass(maze,curpos) FootPrint(maze,curpos); e.ord=curstep; e.seat=curpos; e.di=1; Push(S,e); if(curpos.r=end.r& curpos.c=end.c) if(!DestroyStack(S) exit(OVERFLOW); else return TRUE; else curpos=NextPos(curpos,1); curstep+; else if(!StackEmpty(S) Pop(S,e); while(e.di=4& !StackEmpty(S) MarkPrint(maze,e.seat); Pop(S,e); if(e.di 4) e.di+; Push(S,e); curpos=NextPos(e.seat,e.di); while(!StackEmpty(S); if(!DestroyStack(S) exit(OVERFLOW); else return FALSE;5. 主函数中的调用void main()MazeType maze;PostType start, end;char cmd;doprintf(请创建迷宫：n);if(!InitMaze(maze)printf(创建迷宫失败!);exit(OVERFLOW);printf(请输入迷宫入口的坐标：);scanf(%d,%d,&start.r,&start.c);printf(请输入迷宫出口的坐标：