数据结构课程设计报告-迷宫求解(递归与非递归)

《数据结构课程设计报告-迷宫求解(递归与非递归)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计迷宫求解班级：学号：姓名：指导老师：迷宫求解1、问题描述输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。2、设计思路从入口出发，按某一方向向前探索，若能走通并且未走过，即某处可以到达，则到达新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到找到一条通路，或无路可走又返回入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈（递归不需要）保存所能够到达的每一点的下标及从该点前进的方向。设

2、迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1；其中：0表示通路，1表示不通，当从某点向下试探时，中间点有四个方向可以试探，而四个角点有两个方向，其他边缘点有三个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1，这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个。3、数据结构设计在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标（x，y），与其相邻的4个点的坐标都可根据与该点的相邻方位而得到。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探

3、的方向为从正东沿顺时针方向进行。为了简化问题，方便求出新点的坐标，将从正东开始沿顺时针进行的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;当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。栈中元素是一个由行、列、方向组成。具体结构定

4、义如下：#definem3#definen3typedefstruct{intx,y;}item;/*路线移动的方向坐标,x为横向,y纵向*/itemmove[4];（递归只需定义到这里）typedefstruct{intx,y,d;}Datatype;/*路线移动的方向坐标，x为横坐标，y为总坐标*/typedefstruct{Datatypedata[MAXSIZE];/*存储路线移动的方向坐标*/inttop;}SeqStack,*PSeqStack;1、功能函数设计迷宫栈的实现函数mazepath()迷宫递归的实现函数path()为了防止重复达到某点，以避免发

5、生死循环，每次达到了某点(i,j)后，改变maze[i][j]的值，迷宫栈的实现直接置-1，算法结束前恢复原迷宫；而迷宫递归是将当前值置为已走的步骤，这样输出时对走过的路更显而易见。（1）栈的函数设计：栈的初始化函数Init_SeqStack()判栈空Empty_SeqStack()入栈函数Push_SeqStack()出栈函数Pop_SeqStack()取栈顶函数GetTop_SeqStack()销毁栈Destroy_SeqStack()2、程序代码迷宫栈：#include#include#defineMAXSIZE100#de

6、finem3#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));i

7、f(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))r