栈的迷宫求解(数据结构试验)

实验二：迷宫问题班级：姓名：学号：一、需求分析（1）以二维数据Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j]（0=j=n+1）及Maze[i][0]和Maze[i][n+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.设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai|ai∈CharSet,i=1,2,…,n,n=0}数据关系：R1={ai-1,ai|ai-1,ai∈D,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()。}ADTStack2.设定迷宫的抽象数据类型为：ADTmaze{数据对象：D={ai,j|ai,j∈{‘’、‘#’、‘@’、‘*’}，0≤i≤m+1,0≤j≤n+1,m,n≤10}数据关系：R={ROW，COL}ROW={ai-1,j,ai,j|ai-1,j，ai,j∈D,i=1,……，m+1,j=0,……，n+1}COL={ai,j-1,ai,j|ai,j-1,ai,j∈D,i=0,……，m+1,j=1,……，n+1}基本操作：InitMaze(&M,a,row,col)初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行、每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，以字符’6’表示通路，以字符‘4’‘1’表示障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M已被赋值,链栈S已经存在。操作结果：若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：以字符“6”表示路径上的位置，字符“4”表示“死胡同”；否则迷宫的状态不变。PrintMaze(M)初始条件：迷宫M已存在。操作结果：以字符形式输出迷宫。}ADTmaze;3.本程序包含三个模块1）主程序模块：voidmain(){初始化；do{接受命令；处理命令；}while(命令！=“退出”)；}2）栈模块——实现栈抽象数据类型3）迷宫模块——实现迷宫抽象数据类型各模块之间的调用关系如下：4.求解迷宫中一条通路的伪码算法：设定当前位置的初值为入口位置；do{若当前位置可通，则{将当前位置插入栈顶；//纳入路径若该位置是出口位置，则结束；//求得路径存放在栈中否则切换当前位置的东邻方块为新的当前位置；}否则{若栈不空且栈位置尚有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；//后退一步，从路径中删去该通道块，主程序模块迷宫模块栈模块若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；}}}while(栈不空)；{栈空说明没有路径存在}三、详细设计1．坐标位置类型typedefstruct{intr,c;//迷宫中行、列的范围}PosType;2．迷宫类型typedefstruct{inta,b;chararr[M][N];//各位置取值‘6’,‘4’,‘1’或‘0’}MazeType;voidinitmaze(MazeType&maze,intm,intn)//按照用户输入的m行和n列的二维数组（元素值为0或1）//设置迷宫的初值，包括加上边缘一圈的值boolmazepath(MazeType&maze,PosTypestart,PosTypeend,SNode*&S)//求解迷宫maze中，从入口start到出口end的一条路径//若存在，则返回TRUE；否则返回FALSEvoidprintmaze(mazetypemaze)//将迷宫以字符型方阵的形式输出到标准输出文件上3．栈类型typedefstruct{intstep;//当前位置在路径上的“序号”PosTypeposition;//当前的坐标位置intdir;//往下一坐标位置的方向}ElemType;//栈的元素类型structSNode{ElemTypedata;SNode*next;};//结点类型，指针类型栈的基本操作设置如下：voidInitStack(Stack&S)//初始化，设S为空栈（S.top=NULL）并返回TRUE,否则返回FALSEStatusPush(Stack&S,ElemTypee)//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE；//否则栈不变，并返回FALSEStatusPop(Stack&S,ElemType&e)//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE//否则返回FALSEvoidprint(SNode*S)//输出栈的内容其中该程序的C++全部代码如下：#includeiostreamusingnamespacestd;#definen10#definem10//迷宫各设置函数voidprint(charmaze[n][m]){for(inti=0;in;i++){for(intj=0;jm;j++){coutmaze[i][j];}coutendl;}}voidadd_maze(charmaze[n][m]){inta,b,c;for(a=1;a=(n-2)*(m-2);a++){cout障碍位置为(1=i=n-1;1=j=m-1)(输入00完成):;cinbc;if(b==0&&c==0){cout设置完成endl;break;}if(b=0||c=0||b=n||c=m){cout输入错误endl;break;}maze[b][c]=1;}}voidcreate_maze(charmaze[n][m]){inti=0,j=0;//为迷宫加围墙for(j=0;jm;j++){maze[0][j]=1;maze[n-1][j]=1;}for(i=0;in;i++){maze[i][0]=1;maze[i][m-1]=1;}//设围墙内所有点为通路for(i=1;in-1;i++){for(j=1;jm-1;j++){maze[i][j]=0;}}print(maze);//输出造好的迷宫add_maze(maze);//增加迷宫障碍coutendl;print(maze);//再次输出此时造好的迷宫}//迷宫栈应用structNode{inti,j;};structStack{Nodepos;Stack*next;};voidInitStack(Stack*&S){Stack*p;cout开辟一个新栈endl;p=newStack;p-next=NULL;S-next=p;couthascreated....endl;}voidpush(Stack*&S,charmaze[n][m],inta,intb){//入栈及相关操作Stack*p;p=newStack;p-pos.i=a;p-pos.j=b;p-next=S-next;S-next=p;maze[a][b]='Y';}voidpop(Stack*&S,charmaze[n][m]){//出栈及相关操作if(!S-next){coutthestackisempty!endl;return;}else{maze[S-next-pos.i][S-next-pos.j]='N';S-next=S-next-next;}}voidWalking(Stack*&S,charmaze[n][m],inti,intj){if(i==n-2&&j==m-2){return;//表示已经到达终点}if(maze[i][j+1]!=1&&maze[i][j+1]!='Y'&&maze[i][j+1]!='N'){//向东走，if判断包括下一个位置是否是墙（1），是否是已经走过的路（Y）（N）j++;push(S,maze,i,j);Walking(S,maze,i,j);return;}if(maze[i+1][j]!=1&&maze[i+1][j]!='Y'&&maze[i+1][j]!='N'){//向南走i++;push(S,maze,i,j);Walking(S,maze,i,j);return;}if(maze[i][j-1]!=1&&maze[i][j-1]!='Y'&&maze[i][j-1]!='N'){//向西走j--;push(S,maze,i,j);Walking(S,maze,i,j);return;}if(maze[i-1][j]!=1&&maze[i-1][j]!='Y'&&maze[i-1][j]!='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);}voidgames(Stack*&S,charmaze[n][m]){inti=1,j=1;push(S,maze,i,j);//先把第一个起始点入栈Walking(S,maze,i,j);//递归算法if(!S-next)cout该迷宫是死胡同endl;elsecout该迷宫可走通endl;print(maze);//输出标记通路的迷宫}intmain(){charmaze[n][m];create_maze(maze);Stack*S;S=newStack;S-next=NULL;InitStack(S);games(S,maze);//为方便DevC++可以看到最后运行的结果，故设此输入cout请随便输入一个数以结束程序;intsui;cinsui;return0;}四、调试分析1．本次作业比较简单，只有一个核心算法，即求迷宫的路径，所以总的调试比较顺利，只在调试MazePath算法时，遇到两个问题：其一是，起初输出的迷宫中没