文档介绍：《数据结构》课程设计迷宫求解班级:学号:姓名:指导老师:迷宫求解问题描述输入一个任意大小的迷宫数据,用递归和非递归两种方法求出一条走出迷宫的路径,并将路径输出。设计思路从入口出发,按某一方向向前探索,若能走通并且未走过,即某处可以到达,则到达新点,否则试探下一个方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向再继续试探,直到找到一条通路,或无路可走又返回入口点。在求解过程中,为了保证在到达某一点后不能向前继续行走(无路)时,能正确返回前一点以便继续从下一个方向向前试探,则需要用一个栈(递归不需要)保存所能够到达的每一点的下标及从该点前进的方向。设迷宫为m行n列,利用maze[m][n]来表示一个迷宫,maze[i][j]=0或1;其中:0表示通路,1表示不通,当从某点向下试探时,中间点有四个方向可以试探,而四个角点有两个方向,其他边缘点有三个方向,为使问题简单化,用maze[m+2][n+2]来表示迷宫,而迷宫的四周的值全部为1,这样做使问题简单了,每个点的试探方向全部为4,不用再判断当前点的试探方向有几个。数据结构设计在上述表示迷宫的情况下,每个点有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;功能函数设计迷宫栈的实现函数mazepath()迷宫递归的实现函数path()为了防止重复达到某点,以避免发生死循环,每次达到了某点(i,j)后,改变maze[i][j]的值,迷宫栈的实现直接置-1,算法结束前恢复原迷宫;而迷宫递归是将当前值置为已走的步骤,这样输出时对走过的路更显而易见。栈的函数设计:栈的初始化函数Init_SeqStack() 判栈空Empty_SeqStack()入栈函数Push_SeqStack()出栈函数Pop_SeqStack()取栈顶函数GetTop_SeqStack()销毁栈Destroy_SeqStack()程序代码迷宫栈:#include<>#include<>#defineMAXSIZE100#definem3#definen3/*定义迷宫的行数和列数,可更改*/typedefstruct{ 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; else return0;}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