完整word版迷宫问题求解最新版新增DIY流程图.docx
《完整word版迷宫问题求解最新版新增DIY流程图.docx》由会员分享，可在线阅读，更多相关《完整word版迷宫问题求解最新版新增DIY流程图.docx（17页珍藏版）》请在冰点文库上搜索。
完整word版迷宫问题求解最新版新增DIY流程图
一、需求分析描述.............................3
二、系统设计.................................3
三、程序流程图...............................8
四、迷宫求解问题源代码.......................9
五、总结....................................13
六、参考文献................................14
一需求分析
1以二维数组MazeType表示迷宫，在其周围加一圈围墙；数组中'#'表示障碍，'_'表示通路。
2程序引导用户初始化迷宫，输入其中的障碍；
3迷宫的入口和出口可以由用户自己设定。
4若迷宫有通路，则在其走过的路径上以'.'表示可以通过；
5本程序可以求解多条路径。
既在迷宫求解过程中记下所有的走过的位置；
例如：
*
*
*
*
*
*
*
*
*
*
*
_
_
#
#
*
*
_
#
#
*
*
_
_
#
#
*
*
_
#
#
#
*
*
_
#
#
*
*
_
#
*
*
_
#
#
#
#
#
*
*
_
_
_
_
_
_
_
_
*
*
*
*
*
*
*
*
*
*
*
二系统设计
1设定栈的抽象数据类型定义
基本操作：
intInitStack（SqStack&S）
操作结果：
构造一个空栈S；
intStackEmpty（SqStackS）
初始条件：
栈S已存在。
操作结果：
若栈为空则返回TRUE，否则返回FALSE；
GETTOP（S，&e）
初始条件：
栈S已经存在；
操作结果：
若栈不为空，则以e返回栈顶元素。
intPush（SqStack&S,SElemTypee）
初始条件：
栈已经存在。
操作结果：
在栈的顶部插入新的栈顶元素；
intPop（SqStack&S,SElemType&e）
初始条件：
栈已经存在；
操作结果：
删除栈顶元素，并以E返回其值。
2设定迷宫的抽象数据类型为：
基本操作：
1voidCreatMaze（intr,intl）
初始条件：
MazeTypemaze已经存在，其中从第一行到最后一行，每一行的第一个元素和最后一个元素都为'*'，从第一列的到最后一列，每一列的第一个和最后一个元素的值为'*'；
操作结果：
构成迷宫的int型数组，以'#'表示障碍，'_'表示通路。
2mazepath（positstart,positend）
初始条件：
迷宫已经初始化；
操作结果：
若迷宫中存在一条通路，则在程序运行过程中走过的路径赋值为1；并在入口处赋值为-1。
若迷宫中不存在通路则打印NOPATH。
3print（）
初始条件：
迷宫存在通路；
操作结果；以数字数组的形式输出迷宫。
4footprint（posita）
操作结果：
使迷宫的M的A点的值变为足迹。
5nextpos（positc,intdi）
操作结果：
调整迷宫行进的方向，寻找出路。
3本程序包括三个模块
1）主程序模块
intmain（）{
PosTypestart,end;
intr,l;
cout<<"请输入迷宫（外围有墙）的行、列数（不大于100）：
";
cin>>r>>l;
CreatMaze（r,l）;
cout<<"迷宫的起点坐标：
";
cin>>start.row>>start.line;
cout<<"迷宫的终点坐标：
";
cin>>end.row>>end.line;
cout<if（MazePath（start,end））{
cout<<"迷宫的通路：
"<PrintMaze（r,l）;
}
elsecout<<"迷宫没有通路！
"<free（S.base）;
return0;
}
2）栈模块
3）迷宫模块
各模块的调用关系如下：
4）求解迷宫的通路的伪码算法：
设定当前位置的处值为入口位置；
DO
{
若当前的位置可通。
则{将当前的位置插入栈顶；
若该位置为出口位置，则结束；
否则切换当前位置的东邻的为新的当前位置；}
否则{
若栈不为空且栈的顶位置尚有其他的方向没有被探索，
则设定新的当前位置为沿顺时针方向旋转找到栈顶的位置的下一个相邻块；
若栈不空但栈顶的四周均不可通过，
则{删去栈顶位置；
若栈不为空，则重新测试新的栈顶位置；
只至找到一个可通过的块至栈空；
}
1坐标的位置的类型
typedefstruct{
intline;
introw;
}PosType;2迷宫类型
voidCreatMaze（intr,intl）//定义迷宫的墙为*，通路为_，障碍为#
{
inti,j;
for（i=0;imaze[i][0]='*';//左面墙
maze[i][l-1]='*';//右面墙
}
for（j=1;jmaze[0][j]='*';//上面墙
maze[r-1][j]='*';//下面墙
}
for（i=1;ifor（j=1;jmaze[i][j]='_';
cout<<"请输入迷宫内障碍物的个数：
";
intnum;
cin>>num;
cout<<"请依次输入障碍物的坐标：
"<intx,y;
for（i=1;i<=num;i++）{
cin>>x>>y;
maze[x][y]='#';
}
cout<"<PrintMaze（r,l）;
cout<}3栈类型
typedefstruct
{
intord;//通道块在路径上的序号
PosTypeseat;//通道块在迷宫中的坐标位置
intdi;//从此通道块走向下一通道块的方向东1；南2；西3；北4
}SElemType;
4迷宫的路径的算法
intMazePath（PosTypestart,PosTypeend）
{
InitStack（S）;
curpos=start;//设定当前位置为入口位置
curstep=1;//第一步
do{
if（Pass（curpos））{//当前位置可以通过（未曾走过）
FootPrint（curpos）;//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push（S,e）;//加入路径
if（curpos.row==end.row&&curpos.line==end.line）//到达终点
returnTRUE;
curpos=NextPos（curpos,1）;//下一位置是当前位置的东邻
curstep++;//探索下一步
}//if
else{//当前位置不能通过
if（!
StackEmpty（S））{
Pop（S,e）;
while（e.di==4&&!
StackEmpty（S））{
MarkPrint（e.seat）;//留下不能通过的标志
Pop（S,e）;//退回一步
//curstep--;
}//while
if（e.di<4）{
e.di++;//换下一个方向探索
Push（S,e）;
curpos=NextPos（e.seat,e.di）;//设定当前位置是该新方向上的相邻块
}//if
}//if
}//else
}while（!
StackEmpty（S））;
returnFALSE;
}
三程序流程图
四代码
#defineSTACK_INIT_SIZE1000
#defineSTACK_MORE10
#defineOVERFLOW-2
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#include
#include
#include
#include
#include
typedefstruct{
intline;
introw;
}PosType;
typedefstruct{
intord;//通道块在路径上的序号
PosTypeseat;//通道块在迷宫中的坐标位置
intdi;//从此通道块走向下一通道块的方向东1；南2；西3；北4
}SElemType;
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
typedefintMazeType[100][100];
MazeTypemaze;
SqStackS;
PosTypecurpos;
SElemTypee;
intcurstep;
intInitStack（SqStack&S）{
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）
exit（OVERFLOW）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
intStackEmpty（SqStackS）{
if（S.base==S.top）
returnTRUE;
elsereturnFALSE;
}
intPush（SqStack&S,SElemTypee）{
if（!
S.base）
exit（OVERFLOW）;
*S.top++=e;
returnOK;
}
intPop（SqStack&S,SElemType&e）{
if（S.top==S.base）
returnERROR;
e=*--S.top;
returnOK;
}
intPass（PosTypecurpos）{
if（maze[curpos.row][curpos.line]=='_'）
returnOK;
elsereturnERROR;
}
voidFootPrint（PosTypecurpos）{
maze[curpos.row][curpos.line]='.';
}
PosTypeNextPos（PosTypecurpos,intdi）{
if（di==1）
curpos.row++;
elseif（di==2）
curpos.line--;
elseif（di==3）
curpos.row--;
elseif（di==4）
curpos.line++;
returncurpos;
}
voidMarkPrint（PosTypecurpos）{
maze[curpos.row][curpos.line]='^';
}
voidPrintMaze（introw,intline）{
for（inti=0;ifor（intj=0;jcout<<（char）maze[i][j]<<"";
cout<}
}
voidCreatMaze（intr,intl）{//定义迷宫的墙为*，通路为_，障碍为#
inti,j;
for（i=0;imaze[i][0]='*';//左面墙
maze[i][l-1]='*';//右面墙
}
for（j=1;jmaze[0][j]='*';//上面墙
maze[r-1][j]='*';//下面墙
}
for（i=1;ifor（j=1;jmaze[i][j]='_';
cout<<"请输入迷宫内障碍物的个数：
";
intnum;
cin>>num;
cout<<"请依次输入障碍物的坐标：
"<intx,y;
for（i=1;i<=num;i++）{
cin>>x>>y;
maze[x][y]='#';
}
cout<"<PrintMaze（r,l）;
cout<}
intMazePath（PosTypestart,PosTypeend）{
InitStack（S）;
curpos=start;//设定当前位置为入口位置
curstep=1;//第一步
do{
if（Pass（curpos））{//当前位置可以通过（未曾走过）
FootPrint（curpos）;//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push（S,e）;//加入路径
if（curpos.row==end.row&&curpos.line==end.line）//到达终点
returnTRUE;
curpos=NextPos（curpos,1）;//下一位置是当前位置的东邻
curstep++;//探索下一步
}//if
else{//当前位置不能通过
if（!
StackEmpty（S））{
Pop（S,e）;
while（e.di==4&&!
StackEmpty（S））{
MarkPrint（e.seat）;//留下不能通过的标志
Pop（S,e）;//退回一步
//curstep--;
}//while
if（e.di<4）{
e.di++;//换下一个方向探索
Push（S,e）;
curpos=NextPos（e.seat,e.di）;//设定当前位置是该新方向上的相邻块
}//if
}//if
}//else
}while（!
StackEmpty（S））;
returnFALSE;
}
intmain（）{
PosTypestart,end;
intr,l;
cout<<"请输入迷宫（外围有墙）的行、列数（不大于100）：
";
cin>>r>>l;
CreatMaze（r,l）;
cout<<"迷宫的起点坐标：
";
cin>>start.row>>start.line;
cout<<"迷宫的终点坐标：
";
cin>>end.row>>end.line;
cout<if（MazePath（start,end））{
cout<<"迷宫的通路：
"<PrintMaze（r,l）;
}
elsecout<<"迷宫没有通路！
"<free（S.base）;
return0;
}
五总结
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。
它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。
数据结构有逻辑上的数据结构和物理上的数据结构之分。
逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。
数据结构是数据存在的形式。
数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
数据结构课程的主要目的是介绍一些常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对它们实行的各种运算的实现算法。
通过这次数据结构课程设计，让我学到了好多东西。
在实际操作过程中犯了一些错误却让我有了意外的收获，所学数据结构理论知识得到了巩固。
通过实际操作，学会数据结构程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。
现在终于挨到了写收获与体会的时候了，的确令人兴奋，看看自己的劳动成果，好开心。
一个星期前的现在，当听到老师布置给我们的题目时，我们都蒙了，这么难的题目我们怎么会啊，但我们只能尽我们自己最大的努力把程序给写出来，虽然知道这一路肯定是异常的艰苦，但豁出去了。
上网查资料、去图书馆查，查相关的函数，在老师的教导下，经过两三天的努力，把程序完美的做了出来。
六参考文献
[1]严蔚敏、吴伟民主编《数据结构》（C语言版）清华大学出版社2002
[2]殷人昆等著《数据结构》（C++版）清华大学出版社2001
[3]金远平著《数据结构》（C++描述）清华大学出版社2005
[4]许卓群等著《数据结构与算法》高等教育出版社2004
[5]FrankM.Carrano等著《数据结构与Ｃ++高级教程》清华大学出版社2004
[6]严蔚敏、吴伟民《数据结构习题集》（c语言版）清华大学出版社
升级会员 