数据结构课程设计报告迷宫求解递归与非递归.doc

数据结构》课程设计迷宫求解班级：学号：姓名：指导老师：迷宫求解1、问题描述输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出2、设计思路从入口出发，按某一方向向前探索，若能走通并且未走过，即某处可以到达，则到达新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到找到一条通路，或无路可走又返回入口点在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈（递归不需要）保存所能够到达的每一点的下标及从该点前进的方向设迷宫为m行n列,利用maze[m][n]来表示一个迷宫，maze[i][j]=O或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有四个方向可以试探，而四个角点有两个方向，其他边缘点有三个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1，这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个3、数据结构设计在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标（x，y）,与其相邻的4个点的坐标都可根据与该点的相邻方位而得到。

因为出口在（m，n）,因此试探顺序规定为:从当前位置向前试探的方向为从正东沿顺时针方向进行为了简化问题，方便求出新点的坐标，将从正东开始沿顺时针进行的4个方向的坐标增量放在一个结构数组move[4冲，在move数组中，每个元素有两个域组成，x为横坐标增量，y为纵坐标增量这样对move设计会彳艮方便地求出从某点（x,y）按某一方向v（0<=v<=3）到达的新点（i,j）的坐标：i=x+move[v].x;j二y+move[v].y;当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向栈中元素是一个由行、列、方向组成具体结构定义如下：#definem3#definen3typedefstruct{intx,y;}item;/*路线移动的方向坐标,x为横向,y纵向*/itemmove[4];（递归只需定义到这里）typedefstruct{intx,y,d;}Datatype;/*路线移动的方向坐标，x为横坐标，y为总坐标*/typedefstruct{Datatypedata[MAXSIZE];/*存储路线移动的方向坐标*/inttop;}SeqStack,*PSeqStack;4、功能函数设计迷宫栈的实现函数mazepath()迷宫递归的实现函数path()为了防止重复达到某点，以避免发生死循环，每次达到了某点(i,j)后，改变maze[i][j]的值，迷宫栈的实现直接置-1,算法结束前恢复原迷宫；而迷宫递归是将当前值置为已走的步骤，这样输出时对走过的路更显而易见。

1)栈的函数设计：栈的初始化函数Init_SeqStack()判栈空Empty_SeqStack()入栈函数Push_SeqStack()出栈函数Pop_SeqStack()取栈顶函数GetTop_SeqStack()销毁栈Destroy_SeqStack()5、程序代码迷宫栈：/*定义迷宫的行数和列数，可更改*//*路线移动的方向坐标*/#include#include#defineMAXSIZE100#definem3#definen3typedefstruct{intx,y;}item;itemmove[4];typedefstruct{intx,y,d;/*横纵坐标及方向*//*定义栈*/}Datatype;typedefstruct{Datatypedata[MAXSIZE];inttop;}SeqStack,*PSeqStack;PSeqStackInit_SeqStack(void)/*初始化栈*/{PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack));if(S)S->top=-1;returnS;}intEmpty_SeqStack(PSeqStackS)/*判栈空*/{if(S->top==-1)return1;elsereturn0;}intPush_SeqStack(PSeqStackS,Datatypex)/*入栈*/{if(S->top==MAXSIZE-1)return0;else{S->top++;S->data[S->top]=x;return1;}}intPop_SeqStack(PSeqStackS,Datatype*x)/*出栈*/{if(Empty_SeqStack(S))return0;else{*x=S->data[S->top];S->top--;return1;}}voidDestroy_SeqStack(PSeqStack*S)/*毁栈*/{if(*S)free(*S);*S=NULL;return;}intmazepath(intmaze[][n+2],itemmove[4],intx0,inty0)/*迷宫功能实现函数*/{/*求迷宫路径，入口参数：迷宫数组，下标移动的增量数组，开始点(x0，yO),0(m,n)是终点，返回值：1表示求出路径，0表示无路径*/PSeqStackS;Datatypetemp;intx,y,d,i,j;temp.x=x0;temp.y=y0;temp.d=-1;S=Init_SeqStack();if(!S){printf("栈初始化失败");return0;}Push_SeqStack(S,temp);while(!Empty_SeqStack(S)){Pop_SeqStack(S,&temp);x=temp.x;y=temp.y;d=temp.d+1;while(d<4){i=x+move[d].x;j=y+move[d].y;if(maze[i][j]==0)/*初始化栈*//*存在剩余方向可以搜索*//*此方向可以走*/走的路径*/的路径*/探*/temp.x=x;temp.y=y;temp.d=d;maze[x][y]=-1;Push_SeqStack(S,temp);/*点(x,y)可以走，用栈保存可以x=i;y=j;if(x==m&&y==n){/*迷宫有路*/while(!Empty_SeqStack(S)){Pop_SeqStack(S,&temp);printf("(%d,%d)<-",temp.x,temp.y);/*打印可以走}Destroy_SeqStack(&S);return1;}elsed=0;}elsed++;/*while(d<4)*//*while*/}}Destroy_SeqStack(&S);printf("迷宫无路径\n");return0;}销毁/栈**//*方向复位，从第一个方向开始试/*试探下一个方向*//*销毁栈*//*迷宫无路*/voidmain(){itemmove[4];intmaze[m+2][n+2];inti,j;for(i=0;i#include#definem3#definen3typedefstruct{intx,y;}item;itemmove[4];intpath(intmaze[][n+2],itemmove[],intx,inty,intstep){/*求迷宫路径，入口参数：迷宫数组，下标移动的增量数组，开始点(X,y),以及开始点对应的步数step，(m,n)是终点，返回值：1表示求出路径，0表示无路径*/inti;step++;maze[X][y]=step;if(X==m&&y==n)return1;/*起始位置是出口，找到路径，结束*/for(i=0;i<4;i++){if(maze[X+move[i].X][y+move[i].y]==0)if(path(maze,move,X+move[i].X,y+move[i].y,step))return1;/*下一个是出口，则返回*/}step--;maze[X][y]=0;return0;}voidmain(){itemmove[4];intmaze[m+2][n+2];inti,j;for(i=0;i

这个程序又加了个递归的算法，相同的程序不同的算法我结合老师提过的思想与教材上的例子，很顺利的完成了这个程序其实在写完这个程序后，我又想到了马的遍历返两个程序的设计思想极其相似，所以我很快又写出马的遍历栈与递归的算法，并且运行成功至此，三个题目设计都完成了，每次上机都会遇到题目，这次也不例外，经过我的不懈努力，解决了部分，还有的现在不能解决，只能留着日后思考和解决了，例如简化代码，可视化调试这次的程序。