1、 数据结构课程设计数据结构课程设计 迷宫求解迷宫求解 班级：班级： 学号：学号： 姓名：姓名： 指导老师：指导老师： 迷宫求解迷宫求解 1 1、 问题描述问题描述 输入一个任意大小的迷宫数据， 用递归和非递归两种方法求 出一条走出迷宫的路径，并将路径输出。 2 2、 设计思路设计思路 从入口出发，按某一方向向前探索，若能走通并且未走过，即某 处可以到达，则到达新点，否则试探下一个方向；若所有的方向均没 有通路，则沿原路返回前一点，换下一个方向再继续试探，直到找到 一条通路，或无路可走又返回入口点。 在求解过程中，为了保证在到达某一点后不能向前继续行走（无 路）时，能正确返回前一点以便继续从下一
2、个方向向前试探，则需要 用一个栈 （递归不需要递归不需要） 保存所能够到达的每一点的下标及从该点前 进的方向。设迷宫为 m 行 n 列，利用 mazemn来表示一个迷宫， mazeij=0 或 1；其中：0 表示通路，1 表示不通，当从某点向下 试探时，中间点有四个方向可以试探，而四个角点有两个方向，其他 边缘点有三个方向，为使问题简单化，用 mazem+2n+2来表示迷 宫，而迷宫的四周的值全部为 1，这样做使问题简单了，每个点的试 探方向全部为 4，不用再判断当前点的试探方向有几个。 3 3、 数据结构数据结构设计设计 在上述表示迷宫的情况下，每个点有 4 个方向去试探，如当前点 的坐标（
3、x，y） ，与其相邻的 4 个点的坐标都可根据与该点的相邻方 位而得到。因为出口在（m，n） ，因此试探顺序规定为：从当前位置 向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便求 出新点的坐标， 将从正东开始沿顺时针进行的 4 个方向的坐标增量放 在一个结构数组 move4中，在 move 数组中，每个元素有两个域组 成，x 为横坐标增量，y 为纵坐标增量。这样对 move 设计会很方便地 求出从某点（x，y）按某一方向 v(0top=-1; return S; int Empty_SeqStack(PSeqStack S) /*判栈空*/ if(S-top=-1) return 1
4、; else return 0; int Push_SeqStack(PSeqStack S,Datatype x) /*入栈*/ if(S-top=MAXSIZE-1) return 0; else S-top+; S-dataS-top=x; return 1; int Pop_SeqStack(PSeqStack S,Datatype *x) /*出栈*/ if(Empty_SeqStack(S) return 0; else *x=S-dataS-top; S-top-; return 1; void Destroy_SeqStack(PSeqStack *S) /*毁栈*/ if(*
5、S) free(*S); *S=NULL; return; int mazepath(int mazen+2,item move4,int x0,int y0) /*迷宫功 能实现函数*/ /*求迷宫路径，入口参数：迷宫数组，下标移动的增量数组，开始点（x0， y0） ，0（m,n）是终点，返回值：1 表示求出路径，0 表示无路径*/ PSeqStack S; Datatype temp; int x,y,d,i,j; temp.x=x0; temp.y=y0; temp.d=-1; S=Init_SeqStack(); /*初始化栈*/ if(!S) printf(“栈初始化失败“); re
6、turn 0; Push_SeqStack(S,temp); while(!Empty_SeqStack(S) Pop_SeqStack(S, x=temp.x; y=temp.y; d=temp.d+1; while(d4) /*存在剩余方向可以搜索*/ i=x+moved.x; j=y+moved.y; if(mazeij=0) /*此方向可以走*/ temp.x=x; temp.y=y; temp.d=d; mazexy=-1; Push_SeqStack(S,temp); /*点（x，y）可以走，用栈保存可以 走的路径*/ x=i;y=j; if(x=m printf(“(%d,%d)-“,temp.x,temp.y); /*打印可以走 的路径*/ Destroy_SeqStack
