数据结构 迷宫问题栈C分解.docx
《数据结构 迷宫问题栈C分解.docx》由会员分享,可在线阅读,更多相关《数据结构 迷宫问题栈C分解.docx(15页珍藏版)》请在冰点文库上搜索。
![数据结构 迷宫问题栈C分解.docx](https://file1.bingdoc.com/fileroot1/2023-4/29/fe2c8b83-c046-4efb-90a1-96a50a8b95a1/fe2c8b83-c046-4efb-90a1-96a50a8b95a11.gif)
数据结构迷宫问题栈C分解
合肥学院
计算机科学与技术系
课程设计报告
2012~2013学年第二学期
课程
数据结构与算法
课程设计名称
迷宫问题(栈)
学生姓名
陈强
学号
1104014026
指导教师
李红
专业班级
计算机科学与技术11级
2013年3月
题目:
迷宫问题(栈):
以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。
设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
要求:
首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。
求得的通路以三元组(i,j,d)的形式输出,其中:
(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。
一、问题分析和任务定义
此程序可以用二维数组存储迷宫数据,设定入口点的下标为(1,1),出口点的下标为(m,n)。
为处理方便起见,在迷宫的四周加一圈障碍。
对于迷宫中任一位置,均可约定有东、南、西、北四个方向可通,并默认以东、南、西、北的顺序进行搜索路线。
将走过的路线放入链栈中,当走出迷宫时,栈中及走出迷宫的路线;当走不出时,栈为空。
实现本程序需要解决以下几个问题:
1.如何通过二维数组建立并存储迷宫。
2.如何进行路径搜索。
3.按一个方向搜索不到出路时怎么办?
4.将符合条件的路线存储。
5.搜索到出路时按顺序输出路线。
首先,可以用二维数组存储迷宫,0和1分别表示迷宫中的通路和障碍,为处理方便起见,建立迷宫时在迷宫四周加一圈障碍。
例如一个5*5的迷宫用二维数组可表示为:
intmaze[7][7]={1,1,1,1,1,1,1,
1,0,0,0,0,0,1,
1,1,1,1,1,0,1,
1,0,0,0,0,0,1,
1,0,1,1,1,1,1,
1,0,0,0,0,0,1,
1,1,1,1,1,1,1};
路径搜索时,需要知道出口和入口的坐标,本程序默认为(1,1)、(m,n)。
定义一个移动坐标(xc,yc),用以记录搜索路线时当前位置的坐标。
搜索时默认按照东、南、西、北的优先顺序进行查找,其中,向东搜索用“1”表示,向南、向西、向北分别用“2”、“3”、“4”表示,“0”表示方向未知。
当向东无路时,再向西查找……当某位置为通路时(maze[i][j]==0),则将这一步的信息放入栈中。
同时,将此步设置为障碍,防止下一步搜索时出现“回头”的现象。
若为障碍时,此时,将栈中元素出去,即沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。
将栈中的元素输出,即寻找到的出迷宫的路线。
假如所有可能的通路都探索到而未能到达出口,则所设的迷宫没有通路。
如上面的例子中,最后输出的路线为:
(1,1,1)、(1,2,1)、(1,3,1)、(1,4,1)、(1,5,2)、(2,5,2)、(3,5,3)、(3,4,3)、(3,3,3)、(3,2,3)、(3,1,2)、(4,1,2)、(5,1,1)、(5,2,1)、(5,3,1)、(5,4,1)、(5,5,0)。
二、数据结构的选择和概要设计
迷宫数据用二维数组intmaze[SIZE+2][SIZE+2]来存储即可(迷宫四周加障碍,所以行列数加2),在定义了迷宫的行列数后,利用两个for循环即可用键盘录入迷宫信息,并在迷宫周围加围墙。
存储搜索路线按题目要求采用链栈的数据结构,用非递归的方法求解路线。
图
(1)为程序的流程图。
三、详细设计和编码
首先建立迷宫。
用户自定义迷宫的行列数m、n,利用嵌套循环将迷宫信息存储于数组maze[m+2][n+2]中:
for(i=0;i{
for(j=0;j{
if(i==0||i==m+1||j==0||j==n+1)//在迷宫周围加障碍
maze[i][j]=1;
else
scanf("%d",&maze[i][j]);
}
}
在对迷宫探索时,每一步都有四个方向可以搜索,为实现这一操作,可建立一个移动数组move[8]。
向东搜索时坐标变化为横坐标不变,纵坐标加一,向南搜索时坐标变化为横坐标加一,纵坐标不变,向西搜索时坐标变化为横坐标不变,纵坐标减一,向北搜索时坐标变化为横坐标减一,纵坐标不变。
这样就完成了向四个方向的搜索操作。
建立链栈用于存储路线信息。
链栈的数据域为包含了i,j,d的结构体,这样就能将路线的每一步信息存储下来。
再建立一个移动坐标,以记录搜索过程中变化方向时坐标的变化。
路线搜索:
1.先将入口信息入栈,当栈不为空时,转2,否则转7;
2.将当前位置信息(item->x、item->y、item->d)赋给动态变量(x、y、d);
3.此位置是否有方向可搜索,是则移动到下一方向,并判断是否为通路,若为通路,转4,若不为通路,换个方向继续搜索,否则转6;
4.则将此位置信息入栈,同时将此位置设置为障碍,避免下一步搜索时返回原路,并判断此位置是否为出口,是则转8,不是转5;
5.初始化搜索方向,转3;
6.执行出栈,判断栈是否为空,是则转,不是则取栈顶元素并转3;
7.迷宫无出路;
8.逆置栈中元素,输出迷宫路线。
如对上面提到的迷宫maze[7][7]进行路线搜索时,入口maze[1][1]的信息为x=1、y=1、d=0(暂时不知道下一步的移动方向,故d的值为0),将其入栈。
此时栈不为空,按照东、南、西、北的优先搜索顺序进行路径查找。
Maze[1][1]向东有方向可搜索,移动坐标变化i=x+move[1].xc、j=y+move[1].yc并且maze[i][j]==0,即此位置可到达。
将此位置信息入栈。
以此类推,当到maze[1][5]时,向东不可再搜索时,开始向南搜索。
移动坐标变化i=x+move[2].xc、j=y+move[2].yc并且maze[i][j]==0,此位置可到达,将此位置信息入栈,同时要初始化搜索方向……最终,将搜索到出口maze[5][5],输出出迷宫路线,程序结束。
四、上机调试过程
1.语法错误及修改
由于本程序运用了链栈的数据结构,并要求用非递归算法求解,所以在设计过程中遇到了不少语法错误。
在建立链栈的过程中无错误,但关于链栈类型的子函数的返回值问题是有一些问题。
在链栈的逆置时,由于不可使用递归算法,产生了一些麻烦,同时增加了时间和空间的复杂度。
在遇到语法错误时,经过反复的调试分析后,所有的语法错误均得到了很好的解决。
2.逻辑错误
在编写本程序之前,本人阅读了一些参考材料,充分的了解了迷宫问题的核心思想,同时也想到了图的深度优先搜索遍历与此题的思想极为相似,所以在编写程序的过程中,未遇到逻辑错误,大多问题都是语法错误。
是
否
是
否
是
是
否是
否
是
图
(1)流程图
五、调试结果及其分析
图
(2)调试结果
上面三张图是程序的运行结果,分别在有出路和无出路的情况下进行了调试。
由于在建立迷宫的过程中,程序会自动加一圈障碍,所以用户只需输入迷宫布局即可。
六、用户使用说明
1.本程序设计源代码重要的语句均有相应的注释,用户可根据注释加以阅读和理解;
2.本程序设计源代码要求迷宫行列数不大于10,用户可根据需要加以修改行列数的最大值SIZE。
3.用户使用程序时,需要先输入行列数(注意范围),再建立与之对应的迷宫数据(0和1分别表示迷宫中的通路和障碍),回车后,即可看到搜索结果。
七、参考文献
[1]王昆仑、李红《数据结构与算法》北京:
中国铁道出版社2006年5月
[2]严蔚敏、吴伟民《数据结构》北京:
北京大学出版社,2007年5月
八、附录
程序源代码:
#include
#include
#defineSIZE10
typedefstruct{//位置信息,x、y为坐标,d为下一步的移动方向
intx,y,d;
}elemtype;
typedefstructnode{//链栈结点类型
elemtypedata;
structnode*next;
}Linkstack;
typedefstruct{
intxc,yc;
}Change;
intmaze[SIZE+2][SIZE+2];//二维数组,存储迷宫信息
voidCreatemove(Changemove[8])//移动数组
{
move[1].xc=0;move[1].yc=1;
move[2].xc=1;move[2].yc=0;
move[3].xc=0;move[3].yc=-1;
move[4].xc=-1;move[4].yc=0;
}
Linkstack*Initstack()//初始化栈
{
Linkstack*L;
L=(Linkstack*)malloc(sizeof(Linkstack));
L->next=NULL;
returnL;
}
Linkstack*Push(Linkstack*L,elemtype*item)//入栈
{
Linkstack*temp=L;
L=(Linkstack*)malloc(sizeof(Linkstack));
L->data=*item;L->next=temp;
returnL;
}
voidGrainPop(Linkstack*L,elemtype*item)//取栈顶元素
{
*item=L->data;
}
Linkstack*DeletePop(Linkstack*L)//出栈
{
if(L==NULL)
{
printf("栈已清空!
\n");
returnNULL;
}
else
{
Linkstack*temp=L;
L=L->next;
free(temp);//释放内存
returnL;
}
}
voidCreatemaze(intm,intn)//建立迷宫
{
inti,j;
printf("建立迷宫:
\n");
for(i=0;i{
for(j=0;j{
if(i==0||i==m+1||j==0||j==n+1)//迷宫周围加障碍
maze[i][j]=1;
else
scanf("%d",&maze[i][j]);
}
}
printf("迷宫打印为:
\n");
for(i=0;i{
for(j=0;jprintf("%3d",maze[i][j]);
printf("\n");
}
}
intStackempty(Linkstack*L)//判断栈是否为空
{
if(L==NULL)
return0;
else
return1;
}
intSearchpath(Linkstack*L,intmaze[SIZE+2][SIZE+2],Changemove[8],intm,intn,Linkstack**p)//路线搜索
{
intx,y,d,i,j;
elemtype*item;
item=(elemtype*)malloc(sizeof(elemtype));
item->x=1;//入口信息入栈,0表示方向未知
item->y=1;
item->d=0;
maze[1][1]=1;//标记
L=Push(L,item);
while(Stackempty(L))
{
x=item->x;
y=item->y;
d=item->d+1;
while(d<5)//1东2南3西4北
{
i=x+move[d].xc;
j=y+move[d].yc;
if(maze[i][j]==0)//此位置为通路
{
L->data.d=d;
item->x=i;
item->y=j;
L=Push(L,item);
maze[x][y]=1;
x=i;
y=j;
if(x==m&&y==n)//判断是否到达出口
{
*p=L;
return1;
}
else
d=1;//初始化搜索方向
}
else
d++;//变化搜索方向
}
L=DeletePop(L);//将不存在出路的结点删除
if(!
L)
GrainPop(L,item);//取栈顶
else
return0;
}
*p=L;
return0;
}
voidPrintpath(Linkstack*L){//路线输出
Linkstack*p,stack[100];
inti=-1;
p=L;
while(p!
=NULL){//栈逆置
stack[i++].data=p->data;
p=p->next;
}
while(i>-1){//输出三元组
i--;
printf("(%2d,%2d,%2d)\n",stack[i].data.x,stack[i].data.y,stack[i].data.d);
}
}
/*voidPrintpath(Linkstack*s)//递归算法输出
{
if(s)
{
Printpath(s->next);
printf("(%2d,%2d,%2d)\n",s->data.x,s->data.y,s->data.d);
}
}*/
voidmain()
{
intm,n;
Changemove[8];
Linkstack*L=NULL;
Linkstack**pL=&L;;
printf("请输入迷宫的行列数(不大于10):
");
scanf("%d%d",&m,&n);
Createmove(move);
Createmaze(m,n);
if(maze[1][1]==0&&maze[m][n]==0&&Searchpath(L,maze,move,m,n,pL))
{
printf("出迷宫的路线为:
\n");
Printpath(L);
}
else
printf("迷宫无出路!
\n");
getchar();
getchar();
}