1、数据结构课程设计迷宫求解 班级: 学号: 姓名: 指导老师: 迷宫求解1、 问题描述输入一个任意大小的迷宫数据,用递归和非递归两种方法求出一条走出迷宫的路径,并将路径输出。2、 设计思路从入口出发,按某一方向向前探索,若能走通并且未走过,即某处可以到达,则到达新点,否则试探下一个方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向再继续试探,直到找到一条通路,或无路可走又返回入口点。在求解过程中,为了保证在到达某一点后不能向前继续行走(无路)时,能正确返回前一点以便继续从下一个方向向前试探,则需要用一个栈(递归不需要)保存所能够到达的每一点的下标及从该点前进的方向。设迷宫为m行n列,
2、利用mazemn来表示一个迷宫,mazeij=0或1;其中:0表示通路,1表示不通,当从某点向下试探时,中间点有四个方向可以试探,而四个角点有两个方向,其他边缘点有三个方向,为使问题简单化,用mazem+2n+2来表示迷宫,而迷宫的四周的值全部为1,这样做使问题简单了,每个点的试探方向全部为4,不用再判断当前点的试探方向有几个。3、 数据结构设计在上述表示迷宫的情况下,每个点有4个方向去试探,如当前点的坐标(x,y),与其相邻的4个点的坐标都可根据与该点的相邻方位而得到。因为出口在(m,n),因此试探顺序规定为:从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题,方便求出新点的坐标
3、,将从正东开始沿顺时针进行的4个方向的坐标增量放在一个结构数组move4中,在move数组中,每个元素有两个域组成,x为横坐标增量,y为纵坐标增量。这样对move设计会很方便地求出从某点(x,y)按某一方向v(0=v=3)到达的新点(i,j)的坐标:i=x+movev.x;j=y+movev.y;当到达了某点而无路可走时需返回前一点,再从前一点开始向下一个方向继续试探。因此,压入栈中的不仅是顺序到达的各点的坐标,而且还要有从前一点到达本点的方向。栈中元素是一个由行、列、方向组成。具体结构定义如下:#define m 3#define n 3typedef structint x,y; item
4、; /*路线移动的方向坐标,x为横向,y纵向*/item move4;(递归只需定义到这里)typedef structint x,y,d;Datatype; /*路线移动的方向坐标,x为横坐标,y为总坐标*/typedef structDatatype dataMAXSIZE; /*存储路线移动的方向坐标*/int top;SeqStack,*PSeqStack;4、 功能函数设计迷宫栈的实现函数mazepath()迷宫递归的实现函数path()为了防止重复达到某点,以避免发生死循环,每次达到了某点(i,j)后,改变mazeij的值,迷宫栈的实现直接置-1,算法结束前恢复原迷宫;而迷宫递归是
5、将当前值置为已走的步骤,这样输出时对走过的路更显而易见。(1) 栈的函数设计:栈的初始化函数 Init_SeqStack() 判栈空 Empty_SeqStack()入栈函数 Push_SeqStack()出栈函数 Pop_SeqStack()取栈顶函数 GetTop_SeqStack() 销毁栈 Destroy_SeqStack()5、 程序代码迷宫栈:#include#include#define MAXSIZE 100#define m 3 #define n 3 /*定义迷宫的行数和列数,可更改*/typedef structint x,y;item;item move4; /*路线移
6、动的方向坐标*/typedef structint x,y,d;Datatype; /*横纵坐标及方向*/typedef structDatatype dataMAXSIZE;int top;SeqStack,*PSeqStack; /*定义栈*/PSeqStack Init_SeqStack(void) /*初始化栈*/PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);if(S)S-top=-1;return S;int Empty_SeqStack(PSeqStack S) /*判栈空*/if(S-top=-1)return 1;elsere
7、turn 0;int Push_SeqStack(PSeqStack S,Datatype x) /*入栈*/if(S-top=MAXSIZE-1)return 0;elseS-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(*S)free(*S);*S=NULL;return
8、;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(栈初始化失败);return 0;Push_SeqStack(S,temp);while(!Empty_SeqSta
9、ck(S)Pop_SeqStack(S,&temp);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&y=n) /*迷宫有路*/while(!Empty_SeqStack(S)Pop_SeqStack(S,&temp);printf(%d,%d)-,
10、temp.x,temp.y); /*打印可以走的路径*/Destroy_SeqStack(&S); /*销毁栈*/return 1;else d=0; /*方向复位,从第一个方向开始试探*/else d+; /*试探下一个方向*/ /*while(d4)*/ /*while*/Destroy_SeqStack(&S); /*销毁栈*/printf(迷宫无路径n); return 0; /*迷宫无路*/void main()item move4;int mazem+2n+2;int i,j;for(i=0;im+2;i+) /*输入迷宫,四周为1*/for(j=0;jn+2;j+)scanf(%
11、d,&mazeij);move0.x=1;move0.y=0;move1.x=0;move1.y=1;move2.x=-1;move2.y=0;move3.x=0;move3.y=-1; /*给方向坐标赋值*/mazepath(maze,move,1,1);getch();迷宫递归:#include#include#define m 3#define n 3typedef structint x,y;item;item move4;int path(int mazen+2,item move,int x,int y,int step)/*求迷宫路径,入口参数:迷宫数组,下标移动的增量数组,开始
12、点(x,y),以及开始点对应的步数step,(m,n)是终点,返回值:1表示求出路径,0表示无路径*/int i;step+;mazexy=step;if(x=m&y=n)return 1; /*起始位置是出口,找到路径,结束*/for(i=0;i4;i+)if(mazex+movei.xy+movei.y=0)if(path(maze,move,x+movei.x,y+movei.y,step)return 1; /*下一个是出口,则返回*/step-;mazexy=0;return 0;void main()item move4;int mazem+2n+2;int i,j;for(i=0
13、;im+2;i+)for(j=0;jn+2;j+)scanf(%d,&mazeij);printf(n);move0.x=1;move0.y=0;move1.x=0;move1.y=1;move2.x=-1;move2.y=0;move3.x=0;move3.y=-1;if(path(maze,move,1,1,1)for(i=0;im+2;i+)for(j=0;jn+2;j+)printf(%d ,mazeij);printf(n); /*输出有路迷宫的路线*/else printf(“迷宫无路径n”);getch();6、 运行与测试迷宫栈(无路径):有路径:迷宫递归(无路径):有路径:7、 设计心得迷宫这个问题也是老师经常讲的例子,是加深对栈运用的好程序。这个程序又加了个递归的算法,相同的程序不同的算法。我结合老师提过的思想与教材上的例子,很顺利的完成了这个程序。其实在写完这个程序后,我又想到了马的遍历,这两个程序的设计思想极其相似,所以我很快又写出马的遍历栈与递归的算法,并且运行成功。至此,三个题目设计都完成了,每次上机都会遇到题目,这次也不例外,经过我的不懈努力,解决了部分,还有的现在不能解决,只能留着日后思考和解决了,例如简化代码,可视化调试。这次的程序设计也让我意识到,在编写之前,做整体的规划很重要,这才能让我们的编写效率更高。