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

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

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

3、。 因为出口在 （ m，n ），因此试探顺序规定为 ：从当前.专业 .整理 .下载可编辑位置向前试探的方向为从正东沿顺时针方向进行 。 为了简化问题 ，方便求出新点的坐标 ，将从正东开始沿顺时针进行的 4 个方向的坐标增量放在一个结构数组 move4 中，在 move 数组中，每个元素有两个域组成 ，x 为横坐标增量 ，y 为纵坐标增量 。这样对 move 设计会很方便地求出从某点 （x，y）按某一方向 v(0<=v<=3) 到达的新点（ i，j）的坐标：i=x+movev.x;j=y+movev.y;当到达了某点而无路可走时需返回前一点 ，再从前一点开始向下一个方向继续试探。因此

4、，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向 。栈中元素是一个由行 、列、方向组成 。具体结构定义如下 ：#define m 3#define n 3typedef structint x,y;item;/* 路线移动的方向坐标,x 为横向,y 纵向 */item move4; （递归只需定义到这里 ）typedef structint x,y,d;Datatype;/* 路线移动的方向坐标，x 为横坐标，y 为总坐标 */typedef struct.专业 .整理 .下载可编辑Datatype dataMAXSIZE;/* 存储路线移动的方向坐标*/int top

5、;SeqStack,*PSeqStack;4、功能函数设计迷宫栈的实现函数mazepath()迷宫递归的实现函数path()为了防止重复达到某点，以避免发生死循环 ，每次达到了某点 (i,j)后，改变 mazei j的值，迷宫栈的实现直接置 -1 ，算法结束前恢复原迷宫 ；而迷宫递归是将当前值置为已走的步骤，这样输出时对走过的路更显而易见。（1）栈的函数设计 ：栈的初始化函数Init_SeqStack()判栈空Empty_SeqStack()入栈函数Push_SeqStack()出栈函数Pop_SeqStack()取栈顶函数GetTop_SeqStack()销毁栈Destroy_SeqStac

6、k()5、程序代码迷宫栈：#include<stdio.h>#include<stdlib.h>.专业 .整理 .下载可编辑#define MAXSIZE 100#define m 3#define n 3/* 定义迷宫的行数和列数 ，可更改 */typedef structint x,y;item;item move4;/* 路线移动的方向坐标 */typedef structint x,y,d;Datatype;/* 横纵坐标及方向 */typedef structDatatype dataMAXSIZE;int top;SeqStack,*PSeqStack;/*

7、 定义栈 */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;elsereturn 0;int Push_SeqStack(PSeqStack S,Datatype x)/* 入栈 */if(S->top=MAXSIZE-1)return 0;elseS

8、->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;.专业 .整理 .下载可编辑int mazepath(int mazen+2,item mov

9、e4,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_SeqStack(S)Po

10、p_SeqStack(S,&temp);x=temp.x;.专业 .整理 .下载可编辑y=temp.y;d=temp.d+1;while(d<4)/* 存在剩余方向可以搜索 */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_Seq

11、Stack(S,&temp);printf("(%d,%d)<-",temp.x,temp.y);/* 打印可以走的路径 */.专业 .整理 .下载可编辑Destroy_SeqStack(&S);/* 销毁栈 */return 1;else d=0;/* 方向复位 ，从第一个方向开始试探 */else d+;/* 试探下一个方向 */ /*while(d<4)*/*while*/Destroy_SeqStack(&S);/* 销毁栈 */printf(" 迷宫无路径 n");return 0;/* 迷宫无路 */voi

12、d main()item move4;int mazem+2n+2;int i,j;for(i=0;i<m+2;i+)/* 输入迷宫 ，四周为 1*/.专业 .整理 .下载可编辑for(j=0;j<n+2;j+)scanf("%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<stdio.h&g

13、t;#include<stdlib.h>#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).专业 .整理 .下载可编辑/* 求迷宫路径 ，入口参数 ：迷宫数组 ，下标移动的增量数组，开始点 （ x，y），以及开始点对应的步数step ，（ m,n ）是终点，返回值：1 表示求出路径，0 表示无路径 */int i;step+;mazexy=step;if(x=m&&y=n)return 1;/*

14、 起始位置是出口 ，找到路径 ，结束 */for(i=0;i<4;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;i<m+2;i+)for(j=0;j<n+2;j+)scanf("%d",&mazeij);printf(

15、"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;i<m+2;i+)for(j=0;j<n+2;j+)printf("%d ",mazeij);printf("n");/* 输出有路迷宫的路线 */.专业 .整理 .下载可编辑else printf(迷宫无“路径 n ” );getch();6、运行与测试迷宫栈（无路径）：有路径：迷宫递归 （无路径）：.专业 .整理 .下载可编辑有路径：7、设计心得迷宫这个问题也是老师经常讲的例子 ，是加深对栈运用的好程序。这个程序又加了个递归的算法 ，相同的程序不同的算法 。我结合老师提过的