数据结构课程设计报告迷宫求解递归与非递归文档格式.docx
- 文档编号:748931
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:12
- 大小:45.31KB
数据结构课程设计报告迷宫求解递归与非递归文档格式.docx
《数据结构课程设计报告迷宫求解递归与非递归文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告迷宫求解递归与非递归文档格式.docx(12页珍藏版)》请在冰点文库上搜索。
=v<
=3)到达的新点(i,j)的坐标:
i=x+move[v].x;
j=y+move[v].y;
当到达了某点而无路可走时需返回前一点,再从前一点开始向下一个方向继续试探。
因此,压入栈中的不仅是顺序到达的各点的坐标,而且还要有从前一点到达本点的方向。
栈中元素是一个由行、列、方向组成。
具体结构定义如下:
#definem3
#definen3
typedefstruct{
intx,y;
}item;
/*路线移动的方向坐标,x为横向,y纵向*/
itemmove[4];
(递归只需定义到这里)
intx,y,d;
}Datatype;
/*路线移动的方向坐标,x为横坐标,y为总坐标*/
Datatypedata[MAXSIZE];
/*存储路线移动的方向坐标*/
inttop;
}SeqStack,*PSeqStack;
4、功能函数设计
迷宫栈的实现函数mazepath()
迷宫递归的实现函数path()
为了防止重复达到某点,以避免发生死循环,每次达到了某点(i,j)后,改变maze[i][j]的值,迷宫栈的实现直接置-1,算法结束前恢复原迷宫;
而迷宫递归是将当前值置为已走的步骤,这样输出时对走过的路更显而易见。
(1)栈的函数设计:
栈的初始化函数Init_SeqStack()
判栈空Empty_SeqStack()
入栈函数Push_SeqStack()
出栈函数Pop_SeqStack()
取栈顶函数GetTop_SeqStack()
销毁栈Destroy_SeqStack()
5、程序代码
迷宫栈:
#include<
stdio.h>
stdlib.h>
#defineMAXSIZE100
#definem3
#definen3/*定义迷宫的行数和列数,可更改*/
/*路线移动的方向坐标*/
/*横纵坐标及方向*/
/*定义栈*/
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)/*入栈*/
top==MAXSIZE-1)
{
top++;
data[S->
top]=x;
}
intPop_SeqStack(PSeqStackS,Datatype*x)/*出栈*/
if(Empty_SeqStack(S))
*x=S->
top];
top--;
voidDestroy_SeqStack(PSeqStack*S)/*毁栈*/
if(*S)
free(*S);
*S=NULL;
return;
intmazepath(intmaze[][n+2],itemmove[4],intx0,inty0)/*迷宫功能实现函数*/
{/*求迷宫路径,入口参数:
迷宫数组,下标移动的增量数组,开始点(x0,y0),0(m,n)是终点,返回值:
1表示求出路径,0表示无路径*/
Datatypetemp;
intx,y,d,i,j;
temp.x=x0;
temp.y=y0;
temp.d=-1;
S=Init_SeqStack();
/*初始化栈*/
if(!
S)
printf("
栈初始化失败"
);
Push_SeqStack(S,temp);
while(!
Empty_SeqStack(S))
Pop_SeqStack(S,&
temp);
x=temp.x;
y=temp.y;
d=temp.d+1;
while(d<
4)/*存在剩余方向可以搜索*/
{
i=x+move[d].x;
j=y+move[d].y;
if(maze[i][j]==0)/*此方向可以走*/
{
temp.x=x;
temp.y=y;
temp.d=d;
maze[x][y]=-1;
Push_SeqStack(S,temp);
/*点(x,y)可以走,用栈保存可以走的路径*/
x=i;
y=j;
if(x==m&
&
y==n)/*迷宫有路*/
{
while(!
{
Pop_SeqStack(S,&
printf("
(%d,%d)<
-"
temp.x,temp.y);
/*打印可以走的路径*/
}
Destroy_SeqStack(&
S);
/*销毁栈*/
return1;
}
elsed=0;
/*方向复位,从第一个方向开始试探*/
}
elsed++;
/*试探下一个方向*/
}/*while(d<
4)*/
}/*while*/
Destroy_SeqStack(&
printf("
迷宫无路径\n"
return0;
/*迷宫无路*/
voidmain()
itemmove[4];
intmaze[m+2][n+2];
inti,j;
for(i=0;
i<
m+2;
i++)/*输入迷宫,四周为1*/
for(j=0;
j<
n+2;
j++)
scanf("
%d"
&
maze[i][j]);
move[0].x=1;
move[0].y=0;
move[1].x=0;
move[1].y=1;
move[2].x=-1;
move[2].y=0;
move[3].x=0;
move[3].y=-1;
/*给方向坐标赋值*/
mazepath(maze,move,1,1);
getch();
迷宫递归:
intpath(intmaze[][n+2],itemmove[],intx,inty,intstep)
迷宫数组,下标移动的增量数组,开始点(x,y),以及开始点对应的步数step,(m,n)是终点,返回值:
inti;
step++;
maze[x][y]=step;
if(x==m&
y==n)
/*起始位置是出口,找到路径,结束*/
4;
i++)
if(maze[x+move[i].x][y+move[i].y]==0)
if(path(maze,move,x+move[i].x,y+move[i].y,step))
return1;
/*下一个是出口,则返回*/
step--;
maze[x][y]=0;
return0;
printf("
\n"
if(path(maze,move,1,1,1))
for(i=0;
for(j=0;
printf("
%d"
maze[i][j]);
printf("
}
}/*输出有路迷宫的路线*/
elseprintf(“迷宫无路径\n”);
getch();
6、运行与测试
迷宫栈(无路径):
有路径:
迷宫递归(无路径):
7、设计心得
迷宫这个问题也是老师经常讲的例子,是加深对栈运用的好程序。
这个程序又加了个递归的算法,相同的程序不同的算法。
我结合老师提过的思想与教材上的例子,很顺利的完成了这个程序。
其实在写完这个程序后,我又想到了马的遍历,这两个程序的设计思想极其相似,所以我很快又写出马的遍历栈与递归的算法,并且运行成功。
至此,三个题目设计都完成了,每次上机都会遇到题目,这次也不例外,经过我的不懈努力,解决了部分,还有的现在不能解决,只能留着日后思考和解决了,例如简化代码,可视化调试。
这次的程序设计也让我意识到,在编写之前,做整体的规划很重要,这才能让我们的编写效率更高。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 迷宫 求解 递归
![提示](https://static.bingdoc.com/images/bang_tan.gif)