迷宫问题.docx
《迷宫问题.docx》由会员分享，可在线阅读，更多相关《迷宫问题.docx（30页珍藏版）》请在冰点文库上搜索。
迷宫问题
*******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2011年春季学期
数据结构课程设计
题目：
专业班级：
姓名：
学号：
指导教师：
成绩：
_____________________
摘要
迷宫问题的求解是一个很好的在栈或者队列等方面的应用问题，本次设计是以栈去实现的。
问题的求解主要是给定一个入口坐标和出口坐标时求出一条从入口到出口的路径，如果不存在或存在要做出相应的判断，存在时打印其路径，并做动态演示。
关键字：
栈，栈的存储结构，出栈与入栈
前言
由于计算机解迷宫时，通常用的是群举的方法，即从入口出发，顺某一方向搜索。
若能走通，则继续往前走；否则沿原路退回，换一个方向再继续搜索，直至所有可能的通路都搜索完为止。
为了保证在任何位置上都能沿原路返回，这就需要一个后进先出的结构来存储起位置，所以用到了栈的概念。
在问题的求解过程中，用到了对栈的定义、栈的初始化、栈的空间的申情、栈的销毁等有关栈的知识。
通过这次课程设计可让我们更深一步的了解栈的概念。
在解决问题的过程中初步懂的如何去选择合适的方法去处理问题，提高解决问题的效率。
正文
1．采用类C语言定义相关的数据类型
（1）定义坐标（X，Y）与搜索方向dir:
typedefstruct
{
intx;//行值
inty;//列值
}PosType;
typedefstruct//栈的元素类型
{
intord;//通道块在路径上的＂序号＂
PosTypeseat;//通道块在迷宫中的＂坐标位置＂
intdi;//从此通道块走向下一通道块的＂方向＂（0～3表示东～北）
}SElemType;
（2）定义栈存放路径：
typedefstructSqStack
{
SElemType*base;//在栈构造之前和销毁之后，base的值为NULL
SElemType*top;//栈顶指针
intstacksize;//当前已分配的存储空间，以元素为单位
}SqStack;//顺序栈
2、各模块的伪码算法
（1）
//使迷宫m的a点的序号变为足迹（curstep），表示经过
voidFootPrint（PosTypea）
{
m[a.x][a.y]=curstep;
}
//根据当前位置及移动方向，返回下一位置
PosTypeNextPos（PosTypec,intdi）
{
PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{行增量,列增量}
//移动方向,依次为东南西北
c.x+=direc[di].x;
c.y+=direc[di].y;
returnc;
}
（2）
voidMarkPrint（PosTypeb）
{
m[b.x][b.y]=-1;
}
//若迷宫maze中存在从入口start到出口end的通道，则求得一条
//存放在栈中（从栈底到栈顶），并返回1；否则返回0
intMazePath（PosTypestart,PosTypeend）
{
SqStackS;
PosTypecurpos;
SElemTypee;
InitStack（&S）;
curpos=start;
do
{
if（Pass（curpos））
{
//当前位置可以通过，即是未曾走到过的通道块
FootPrint（curpos）;//留下足迹
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
e.di=0;
Push（&S,e）;//入栈当前位置及状态
curstep++;//足迹加1
if（curpos.x==end.x&&curpos.y==end.y）//到达终点（出口）
return1;
curpos=NextPos（curpos,e.di）;
}
else
{
//当前位置不能通过
if（!
StackEmpty（S））
{
Pop（&S,&e）;//退栈到前一位置
curstep--;
//前一位置处于最后一个方向（北）
while（e.di==3&&!
StackEmpty（S））
{
MarkPrint（e.seat）;//留下不能通过的标记（-1）
Pop（&S,&e）;//退回一步
curstep--;
}
if（e.di<3）//没到最后一个方向（北）
{
e.di++;//换下一个方向探索
Push（&S,e）;
curstep++;
//设定当前位置是该新方向上的相邻块
curpos=NextPos（e.seat,e.di）;
}
}
}
}while（!
StackEmpty（S））;
return0;
}
（3）
//输出迷宫的结构
voidPrint（intx,inty）
{
inti,j;
for（i=0;i{
for（j=0;jprintf（"%3d",m[i][j]）;
printf（"\n"）;
}
}
intmain（）
{
PosTypebegin,end;
inti,j,x,y,x1,y1;
printf（"请输入迷宫的行数,列数（包括外墙）：
（空格隔开）"）;
scanf（"%d%d",&x,&y）;
for（i=0;i{
m[0][i]=0;//迷宫上面行的周边即上边墙
m[x-1][i]=0;//迷宫下面行的周边即下边墙
}
for（j=1;j{
m[j][0]=0;//迷宫左边列的周边即左边墙
m[j][y-1]=0;//迷宫右边列的周边即右边墙
}
for（i=1;ifor（j=1;jm[i][j]=1;//定义通道初值为1
printf（"请输入迷宫内墙单元数：
"）;
scanf（"%d",&j）;
printf（"请依次输入迷宫内墙每个单元的行数,列数：
（空格隔开）\n"）;
for（i=1;i<=j;i++）
{
scanf（"%d%d",&x1,&y1）;
m[x1][y1]=0;//定义墙的值为0
}
printf（"迷宫结构如下:
\n"）;
Print（x,y）;
printf（"请输入起点的行数,列数：
（空格隔开）"）;
scanf（"%d%d",&begin.x,&begin.y）;
printf（"请输入终点的行数,列数：
（空格隔开）"）;
scanf（"%d%d",&end.x,&end.y）;
if（MazePath（begin,end））//求得一条通路
{
printf（"此迷宫从入口到出口的一条路径如下:
\n"）;
Print（x,y）;//输出此通路
}
else
printf（"此迷宫没有从入口到出口的路径\n"）;
printf（"pause"）;
return0;
}
3、函数关系调用图
4、调试分析
A、调试中遇到的问题既对问题的解决方案
（1）在输入迷宫的大小n时，若n太大，例如n=30，屏幕无法显示第25行以及其后的方块。
解决方法：
EXEC:
printf（“Pleaseinputthesizeofmaze（n*n）:
”）;
scanf（“%d”,&n）;
添加语句：
if（n>24）
{printf（“\nThenumberissolarge!
Tryitagain!
\n”）;
gotoEXEC;}
（2）在输入迷宫的起点与终点坐标时，若输入坐标超过迷宫的表示范围则程序立即结束并不返回任何值，若输入的坐标在迷宫的“围墙”上时，搜索依然进行，并返回路径。
解决方法：
up:
printf（“Pleaseinputthestartpath（c,d）:
”）;
scanf（“%d%d”,&d,&c）;
printf（“Pleaseinputtheendpath（a,b）:
”）;
scanf（“%d%d”,&b,&a）;
添加语句：
if（c>n-2||d>n-2||a>n-2||b>n-2||c==0||d==0||a==0||b==0）
{printf（“Thenumberextendtheboundar
array!
Tryitagain!
\n”）;
gotoup;}
5.测试结果
/*
输出效果：
请输入迷宫的行数,列数（包括外墙）：
（空格隔开）55
请输入迷宫内墙单元数：
2
请依次输入迷宫内墙每个单元的行数,列数：
（空格隔开）
12
32
迷宫结构如下:
00000
01010
01110
01010
00000
请输入起点的行数,列数：
（空格隔开）11
请输入终点的行数,列数：
（空格隔开）33
此迷宫从入口到出口的一条路径如下:
00000
01010
02340
01050
00000
请按任意键继续...
6.源程序
/***************头文件**********************/
//迷宫坐标位置类型
#include
#include
typedefstruct
{
intx;//行值
inty;//列值
}PosType;
#defineMAXLENGTH81//设迷宫的最大行列为81
typedefintMazeType[MAXLENGTH][MAXLENGTH];//迷宫数组[行][列]
typedefstruct//栈的元素类型
{
intord;//通道块在路径上的＂序号＂
PosTypeseat;//通道块在迷宫中的＂坐标位置＂
intdi;//从此通道块走向下一通道块的＂方向＂（0～3表示东～北）
}SElemType;
//全局变量
MazeTypem;//迷宫数组
intcurstep=1;//当前足迹,初值为1
#defineSTACK_INIT_SIZE10//存储空间初始分配量
#defineSTACKINCREMENT2//存储空间分配增量
//栈的顺序存储表示P46
typedefstructSqStack
{
SElemType*base;//在栈构造之前和销毁之后，base的值为NULL
SElemType*top;//栈顶指针
intstacksize;//当前已分配的存储空间，以元素为单位
}SqStack;//顺序栈
/****************实现************************/
//构造一个空栈S
intInitStack（SqStack*S）
{
//为栈底分配一个指定大小的存储空间
（*S）.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
（*S）.base）
return（0）;
（*S）.top=（*S）.base;//栈底与栈顶相同表示一个空栈
（*S）.stacksize=STACK_INIT_SIZE;
return1;
}
//若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。
intStackEmpty（SqStackS）
{
if（S.top==S.base）
return1;
else
return0;
}
//插入元素e为新的栈顶元素。
intPush（SqStack*S,SElemTypee）
{
if（（*S）.top-（*S）.base>=（*S）.stacksize）//栈满，追加存储空间
{
（*S）.base=（SElemType*）realloc（（*S）.base,
（（*S）.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
（*S）.base）
return（0）;
（*S）.top=（*S）.base+（*S）.stacksize;
（*S）.stacksize+=STACKINCREMENT;
}
*（（*S）.top）++=e;
//这个等式的++*优先级相同，但是它们的运算方式，是自右向左
return1;
}
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。
intPop（SqStack*S,SElemType*e）
{
if（（*S）.top==（*S）.base）
return0;
*e=*--（*S）.top;
//这个等式的++*优先级相同，但是它们的运算方式，是自右向左
return1;
}
//定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹
//当迷宫m的b点的序号为1（可通过路径），return1;否则，return0。
intPass（PosTypeb）
{
if（m[b.x][b.y]==1）
return1;
else
return0;
}
//使迷宫m的a点的序号变为足迹（curstep），表示经过
voidFootPrint（PosTypea）
{
m[a.x][a.y]=curstep;
}
//根据当前位置及移动方向，返回下一位置
PosTypeNextPos（PosTypec,intdi）
{
PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{行增量,列增量}
//移动方向,依次为东南西北
c.x+=direc[di].x;
c.y+=direc[di].y;
returnc;
}
//使迷宫m的b点的序号变为-1（不能通过的路径）
voidMarkPrint（PosTypeb）
{
m[b.x][b.y]=-1;
}
//算法3.3P51
//若迷宫maze中存在从入口start到出口end的通道，则求得一条
//存放在栈中（从栈底到栈顶），并返回1；否则返回0
intMazePath（PosTypestart,PosTypeend）
{
SqStackS;
PosTypecurpos;
SElemTypee;
InitStack（&S）;
curpos=start;
do
{
if（Pass（curpos））
{
//当前位置可以通过，即是未曾走到过的通道块
FootPrint（curpos）;//留下足迹
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
e.di=0;
Push（&S,e）;//入栈当前位置及状态
curstep++;//足迹加1
if（curpos.x==end.x&&curpos.y==end.y）//到达终点（出口）
return1;
curpos=NextPos（curpos,e.di）;
}
else
{
//当前位置不能通过
if（!
StackEmpty（S））
{
Pop（&S,&e）;//退栈到前一位置
curstep--;
//前一位置处于最后一个方向（北）
while（e.di==3&&!
StackEmpty（S））
{
MarkPrint（e.seat）;//留下不能通过的标记（-1）
Pop（&S,&e）;//退回一步
curstep--;
}
if（e.di<3）//没到最后一个方向（北）
{
e.di++;//换下一个方向探索
Push（&S,e）;
curstep++;
//设定当前位置是该新方向上的相邻块
curpos=NextPos（e.seat,e.di）;
}
}
}
}while（!
StackEmpty（S））;
return0;
}
//输出迷宫的结构
voidPrint（intx,inty）
{
inti,j;
for（i=0;i{
for（j=0;jprintf（"%3d",m[i][j]）;
printf（"\n"）;
}
}
intmain（）
{
PosTypebegin,end;
inti,j,x,y,x1,y1;
printf（"请输入迷宫的行数,列数（包括外墙）：
（空格隔开）"）;
scanf（"%d%d",&x,&y）;
for（i=0;i{
m[0][i]=0;//迷宫上面行的周边即上边墙
m[x-1][i]=0;//迷宫下面行的周边即下边墙
}
for（j=1;j{
m[j][0]=0;//迷宫左边列的周边即左边墙
m[j][y-1]=0;//迷宫右边列的周边即右边墙
}
for（i=1;ifor（j=1;jm[i][j]=1;//定义通道初值为1
printf（"请输入迷宫内墙单元数：
"）;
scanf（"%d",&j）;
printf（"请依次输入迷宫内墙每个单元的行数,列数：
（空格隔开）\n"）;
for（i=1;i<=j;i++）
{
scanf（"%d%d",&x1,&y1）;
m[x1][y1]=0;//定义墙的值为0
}
printf（"迷宫结构如下:
\n"）;
Print（x,y）;
printf（"请输入起点的行数,列数：
（空格隔开）"）;
scanf（"%d%d",&begin.x,&begin.y）;
printf（"请输入终点的行数,列数：
（空格隔开）"）;
scanf（"%d%d",&end.x,&end.y）;
if（MazePath（begin,end））//求得一条通路
{
printf（"此迷宫从入口到出口的一条路径如下:
\n"）;
Print（x,y）;//输出此通路
}
else
printf（"此迷宫没有从入口到出口的路径\n"）;
printf（"pause"）;
return0;
}
总结
在这三周的数据结构课程设计中,我的题目是:
迷宫问题,这三周课程设计中,通过该题目的设计过程,我加深了对队栈算法的理解,对队栈算法上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。
一个人要完成所有的工作是非常困难和耗时的。
在以后的学习中我会更加注意各个方面的能力的协调发展。
在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。
三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很大，学到很多。
参考文献
1.严蔚敏，吴伟民，《数据结构（C语言版）》，清华大学出版社。
2.严蔚敏，吴伟民，《数据结构题集（C语言版）》，清华大学出版社。
3.《DATASTRUCTUREWITHC++》，WilliamFord，WilliamTcpp，清华大学出版社（影印版）。
4.谭浩强，《C语言程序设计》，清华大学出版社。
致谢
首先感谢我的指导老师卢鹏丽卢老师，她在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术。
感谢我的数据结构老师老师和C语言老师在以往的基础课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。
我的同学在设计完成后对程序的测试，没有他们，也许就难以发现一些潜在的错误，在此一并表示感谢。
附件Ⅰ部分源程序代码
#include
#include
typedefstruct
{
intx;
inty;
}PosType;
#defineMAXLENGTH81
typedefintMazeType[MAXLENGTH][MAXLENGTH];
typedefstruct{
intord;
PosTypeseat;
intdi;
}SElemType;
MazeTypem;
intcurstep=1;
#defineSTACK_INIT_SIZE10
#defineSTACKINCREMENT2
typ
升级会员 