栈的迷宫求解(数据结构试验).doc
_ 实验二：迷宫问题 班级： 姓名： 学号： 一、 需求分析（ 1 ） 以二维数据Mazem+2n+2 表示迷宫， 其中： Maze0j 和Mazem+1j（0<=j<=n+1）及Mazei0和Mazein+1(0<=i<=m+1)为添加一圈障碍。数组中以元素值为0 表示通路，1 表示障碍，限定迷宫的大小m,n<=100。（2）用户输入迷宫的规模m,n；并按照此规模输入迷宫的具体数据。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“”表示“死胡同”，即曾途径然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。（6） 测试数据见原题，当入口位置为（1，1），出口位置为（9，8）时，输出数据应为：*#*#*#*#*#*#*#*#*#*#*（7）程序执行的命令为：1）创建迷宫；2）求解迷宫；3）输出迷宫的解。二、 概要设计1. 设定栈的抽象数据类型定义：ADT Stack数据对象：D=ai|aiCharSet,i=1,2,n,n>=0数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack（&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 返回其值。StackTraverse(S,visit()初始条件：栈S 已存在。操作结果：从栈底到栈顶依次对 S 中的每个元素调用函数visit( )。ADT Stack2. 设定迷宫的抽象数据类型为：ADT maze数据对象：D=ai,j|ai,j 、#、*，0im+1,0jn+1,m,n10数据关系：R=ROW，COLROW=<ai-1,j,ai,j>|ai-1,j，ai,jD,i=1,，m+1,j=0,，n+1COL=<ai,j-1,ai,j>|ai,j-1,ai,jD,i=0,，m+1,j=1,，n+1基本操作：InitMaze(&M,a,row,col)初始条件：二维数组arow+2col+2已存在，其中自第1 行至第row+1行、每行中自第1 列至第col+1 列的元素已有值，并且以值0表示通路，以值1 表示障碍。操作结果：构成迷宫的字符型数组，以字符6表示通路，以字符41表示障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M 已被赋值,链栈S已经存在。操作结果：若迷宫M 中存在一条通路，则按如下规定改变迷宫M 的状态：以字符“6”表示路径上的位置，字符“4”表示“死胡同”；否则迷宫的状态不变。PrintMaze(M)初始条件：迷宫M 已存在。操作结果：以字符形式输出迷宫。ADT maze;3. 本程序包含三个模块1） 主程序模块：void main( )初始化；do接受命令；处理命令；while(命令！=“退出”)；2） 栈模块实现栈抽象数据类型3） 迷宫模块实现迷宫抽象数据类型各模块之间的调用关系如下：4. 求解迷宫中一条通路的伪码算法：设定当前位置的初值为入口位置；do若当前位置可通，则将当前位置插入栈顶； /纳入路径若该位置是出口位置，则结束； /求得路径存放在栈中否则切换当前位置的东邻方块为新的当前位置；否则若栈不空且栈位置尚有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置； /后退一步，从路径中删去该通道块，主程序模块迷宫模块栈模块若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；while(栈不空)；栈空说明没有路径存在三、 详细设计1 坐标位置类型typedef structint r,c; /迷宫中行、列的范围PosType;2 迷宫类型typedef structint a, b;char arrMN; /各位置取值6 ,4,1或0MazeType;void initmaze(MazeType &maze,int m,int n)/按照用户输入的m行和n 列的二维数组（元素值为0 或1）/设置迷宫的初值，包括加上边缘一圈的值bool mazepath(MazeType &maze,PosType start,PosType end,SNode *&S)/求解迷宫maze 中，从入口start 到出口end 的一条路径/若存在，则返回TRUE；否则返回FALSEvoid printmaze(mazetype maze)/将迷宫以字符型方阵的形式输出到标准输出文件上3 栈类型typedef structint step; /当前位置在路径上的“序号”PosType position; /当前的坐标位置int dir; /往下一坐标位置的方向ElemType; /栈的元素类型struct SNodeElemType data;SNode *next; /结点类型，指针类型栈的基本操作设置如下：void InitStack(Stack &S)/初始化，设S 为空栈（S.top=NULL）并返回TRUE,否则返回FALSEStatus Push(Stack &S,ElemType e)/若分配空间成功，则在S 的栈顶插入新的栈顶元素e，并返回TRUE；/否则栈不变，并返回FALSEStatus Pop(Stack &S,ElemType &e)/若栈不空，则删除S 的栈顶元素并以e 带回其值，且返回TRUE/否则返回FALSEvoid print(SNode *S) /输出栈的内容其中该程序的C+全部代码如下：#include<iostream>using namespace std;#define n 10#define m 10/迷宫各设置函数void print(char mazenm)for (int i=0;i<n;i+)for(int j=0;j<m;j+)cout<<mazeij<<" "cout<<endl;void add_maze(char mazenm) int a,b,c; for(a=1;a<=(n-2)*(m-2);a+) cout<<"障碍位置为(1<=i<="<<n-1<<""<<"1<=j<="<<m-1<<")(输入0 0完成):" cin>>b>>c; if(b=0&&c=0) cout<<"设置完成"<<endl; break; if(b<=0|c<=0|b>=n|c>=m) cout<<"输入错误"<<endl; break; mazebc=1; void create_maze( char mazenm)int i=0,j=0;/为迷宫加围墙for(j=0;j<m;j+)maze0j=1;mazen-1j=1;for(i=0;i<n;i+)mazei0=1;mazeim-1=1; /设围墙内所有点为通路for(i=1;i<n-1;i+) for(j=1;j<m-1;j+)mazeij=0; print(maze);/输出造好的迷宫 add_maze(maze);/增加迷宫障碍 cout<<endl;print(maze);/再次输出此时造好的迷宫/迷宫栈应用struct Node int i,j;struct StackNode pos;Stack *next;void InitStack(Stack *&S)Stack *p;cout<<"开辟一个新栈"<<endl;p=new Stack;p->next=NULL;S->next=p;cout<<"has created."<<endl;void push(Stack *&S,char mazenm,int a,int b)/入栈及相关操作Stack *p;p=new Stack;p->pos.i=a; p->pos.j=b;p->next=S->next;S->next=p;mazeab='Y'void pop(Stack *&S,char mazenm)/出栈及相关操作if(!S->next) cout<<"the stack is empty!"<<endl; return;else mazeS->next->pos.iS->next->pos.j='N' S->next=S->next->next; void Walking(Stack *&S,char mazenm,int i,int j)if(i=n-2 && j=m-2) return; /表示已经到达终点if(mazeij+1!=1 && mazeij+1!='Y' && mazeij+1!='N')/向东走，if判断包括下一个位置是否是墙（1），是否是已经走过的路（Y）（N）j+;push(S,maze,i,j);Walking(S,maze,i,j);return;if(mazei+1j!=1 && mazei+1j!='Y' && mazei+1j!='N')/向南走i+;push(S,maze,i,j);Walking(S,maze,i,j);return;if(mazeij-1!=1 && mazeij-1!='Y' && mazeij-1!='N')/向西走j-;push(S,maze,i,j);Walking(S,maze,i,j);return;if(mazei-1j!=1 && mazei-1j!='Y' && mazei-1j!='N')/向北走i-;push(S,maze,i,j);Walking(S,maze,i,j);return; pop(S,maze);/四个方向都不通，说明该点无法到达终点，实行出栈i=S->next->pos.i;j=S->next->pos.j;Walking(S,maze,i,j);void games(Stack *&S,char mazenm)int i=1,j=1;push(S,maze,i,j);/先把第一个起始点入栈Walking(S,maze,i,j);/递归算法if(!S->next)cout<<"该迷宫是死胡同"<<endl;else cout<<"该迷宫可走通"<<endl;print(maze);/输出标记通路的迷宫 int main() char mazenm; create_maze(maze);Stack *S;S=new Stack;S->next=NULL; InitStack(S); games(S,maze); /为方便DevC+可以看到最后运行的结果，故设此输入 cout<<"请随便输入一个数以结束程序" int sui; cin>>sui; return 0;四、 调试分析1本次作业比较简单，只有一个核心算法，即求迷宫的路径，所以总的调试比较顺利，只在调试MazePath 算法时，遇到两个问题：其一是，起初输出的迷宫中没有加上4的记号，后发现是因为在MarkPrint 函数中的迷宫参数丢失“变参”的原因；其二是，由于回退时没有将curpos 随之减一，致使栈中路径上的序号有错。2栈的元素中的step 域没有太多用处，可以省略。3StackTraverse 在调试过程中很有用，它可以插入在MazePath 算法中多处，以察看解迷宫过程中走的路径是否正确，但对最后的执行版本没有用。4本题中三个主要算法：InitMaze,MazePath 和PrintMaze 的时间复杂度均为0（a*b），本题的空间复杂度亦为0（a*b）（栈所占最大空间）5经验体会：借助DEBUG 调试器和数据观察窗口，可以加快找到程序中疵点。五、 用户手册1 本程序的运行环境为xp,w7 操作系统，执行文件为：迷宫问题.exe.2 进入演示程序后，即现实文本方式的用户界面：主程序Initialization ReadCommand InterpretInitMaze MazePath PrintMazeInitStack Push Pop StackEmpty StackTraverse FootPrint MarkPrint Pass NextPos 3 进入“产生迷宫（mazeinit）”的命令后，即提示键入迷宫规模，结束符为“回车符”，即提示键入入口位置（行号和列号，中间用空格分开，结束符为“回车符”）和出口位置（行号和列号，中间用空格分开，结束符为“回车符”），之后提示输入迷宫内容，该命令执行之后输出“迷宫图形”。4 进入“求迷宫路径（MazePath）”的命令后， 该命令执行之后根据情况输出更改之后的迷宫图形。接着，若迷宫中存在，输出走迷宫的路径，否则输出“无路可走”。六、 测试结果2组测试数据和输出结果分别如下：1.2.*12_
