迷宫问题求解(新增DIY流程图).doc

目录

一、需求分析描述.............................3

二、系统设计.................................3

三、程序流程图...............................8

四、迷宫求解问题源代码.......................9

五、总结....................................13

六、参考文献................................14

一 需求分析
1 以二维数组MazeType表示迷宫，在其周围加一圈围墙；数组中'#'表示障碍，'_'表示通路。
2 程序引导用户初始化迷宫，输入其中的障碍；
3 迷宫的入口和出口可以由用户自己设定。
4 若迷宫有通路，则在其走过的路径上以'.'表示可以通过；
5本程序可以求解多条路径。既在迷宫求解过程中记下所有的走过的位置；
例如：
*
*
*
*
*
*
*
*
*
*
*
_
_
#

#

*
*

_
#

#

*
*
_
_

#

#

*
*
_
#
#
#

*
*
_
#

#

*
*
_
#

*
*
_
#
#
#
#

#

*
*
_
_
_
_
_
_
_
_
*
*
*
*
*
*
*
*
*
*
*
二 系统设计
1 设定栈的抽象数据类型定义
基本操作：
int InitStack(SqStack &S)
操作结果：构造一个空栈S；
int StackEmpty(SqStack S)
初始条件：栈S已存在。
操作结果：若栈为空则返回TRUE，否则返回FALSE；
GETTOP（S，&e）
初始条件：栈S已经存在；
操作结果：若栈不为空，则以e返回栈顶元素。
int Push(SqStack &S,SElemType e)
初始条件：栈已经存在。
操作结果：在栈的顶部插入新的栈顶元素；
int Pop(SqStack &S,SElemType &e)
初始条件：栈已经存在；
操作结果：删除栈顶元素，并以E返回其值。
2 设定迷宫的抽象数据类型为：
基本操作：
1 void CreatMaze(int r,int l)
初始条件：MazeType maze已经存在，其中从第一行到最后一行，每一行的第一个元素和最后一个元素都为'*'，从第一列的到最后一列，每一列的第一个和最后一个元素的值为'*'
操作结果：构成迷宫的int型数组，以'#'表示障碍，'_'表示通路。

2 mazepath(posit start,posit end)
初始条件：迷宫已经初始化；
操作结果：若迷宫中存在一条通路，则在程序运行过程中走过的路径赋值为1；并在入口处赋值为-1。若迷宫中不存在通路则打印 NO PATH。
3print()
初始条件：迷宫存在通路；
操作结果；以数字数组的形式输出迷宫。
4 footprint(posit a)
操作结果：使迷宫的M的A点的值变为足迹。
5 nextpos(posit c,int di)
操作结果：调整迷宫行进的方向，寻找出路。
3 本程序包括三个模块
1）主程序模块
int main(){
PosType start,end;
int r,l;
cout<<"请输入迷宫（外围有墙）的行、列数(不大于100)：";
cin>>r>>l;
CreatMaze(r,l);
cout<<"迷宫的起点坐标：";
cin>>start.row>>start.line;
cout<<"迷宫的终点坐标：";
cin>>end.row>>end.line;
cout<表示外墙，#表示迷宫内障碍物,.为通路）"<向旋转找到栈顶的位置的下一个相邻块；
若栈不空但栈顶的四周均不可通过，
则{删去栈顶位置；
若栈不为空，则重新测试新的栈顶位置；
只至找到一个可通过的块至栈空；
}
1 坐标的位置的类型
typedef struct{
int line;
int row;
}PosType;2 迷宫类型
void CreatMaze(int r,int l)//定义迷宫的墙为*，通路为_，障碍为#
{
int i,j;
for(i=0;ij=1;j>num;
cout<<"请依次输入障碍物的坐标："<>x>>y;
maze[x][y]='#';
}
cout<迷宫的如下："<t;// 设定当前位置为入口位置
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)//到达终点
return TRUE;
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));
return FALSE;
}

三 程序流程图
前行
左转
右转
后转
否
否
否
是
是
是
是
否
输入数据是否合法
输入障碍坐标
输入迷宫障碍个数
初始化
用户输入迷宫大小
右面是否有障碍
左面是否有障碍
前面是否有障碍
用户输入入口与出口
创建并输入迷宫

是
结束
输出迷宫通路
否
是否达到终点

四 代码
#define STACK_INIT_SIZE 1000
#define STACK_MORE 10
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#include
#include
#include
#include
#include

typedef struct{
int line;
int row;
}PosType;

typedef struct{
int ord; //通道块在路径上的序号
PosType seat; //通道块在迷宫中的坐标位置
int di; //从此通道块走向下一通道块的方向 东1；南2；西3；北4
}SElemType;

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

typedef int MazeType[100][100];

MazeType maze;
SqStack S;
PosType curpos;
SElemType e;
int curstep;

int InitStack(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;
return OK;
}

int StackEmpty(SqStack S){
if(S.base==S.top)
return TRUE;
else return FALSE;
}

int Push(SqStack &S,SElemType e){
if(!S.base)
exit (OVERFLOW);
*S.top++=e;
return OK;
}

int Pop(SqStack &S,SElemType &e){
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}

int Pass(PosType curpos){
if(maze[curpos.row][curpos.line]=='_')
return OK;
else return ERROR;
}

void FootPrint(PosType curpos){
maze[curpos.row][curpos.line]='.';
}

PosType NextPos(PosType curpos,int di){
if(di==1)
curpos.row++;
else if(di==2)
curpos.line--;
else if(di==3)
curpos.row--;
else if(di==4)
curpos.line+
return curpos;
}

void MarkPrint(PosType curpos){
maze[curpos.row][curpos.line]='^';
}

void PrintMaze(int row,int line){
for(int i=0;i为#
int i,j;
for(i=0;i>num;
cout<<"请依次输入障碍物的坐标："<ndl;
int x,y;
for(i=1;i<=num;i++){
cin>>x>>y;
maze[x][y]='#';
}
cout<
FootPrint(curpos);//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e);//加入路径
if(curpos.row==end.row&&curpos.line==end.line)//到达终点
return TRUE;
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(!StackEmptyS));
return FALSE;
}

int main(){
PosType start,end;
int r,l;
cout<<"请输入迷宫（外围有墙）的行、列数(不大于100)：";
cin>>r>>l;
CreatMaze(r,l);
cout<<"迷宫的起点坐标：";
cin>>start.row>>start.line;
cout<<"迷宫的终点坐标：";
cin>>end.row>>end.line;
cout<<<"（其中*表示外墙，#表示迷宫内障碍物,.为通路）"<信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。数据结构课程的主要目的是介绍一些常用的数据结构，阐明数据结构内在的逻辑 关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对它们实行的各种 运算的实现算法。 通过这次数据结构课程设计，让我学到了好多东西。在实际操作过程中犯了一些错 误却让我有了意外的收获，所学数据结构理论知识得到了巩固。通过实际操作，学会数据结构程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。现在终于挨到了写收获与体会的时候了，的确令人兴奋，看看自己的劳动成果，好开心。 一个星期前的现在，当听到老师布置给我们的题目时，我们都蒙了，这么难的题目我们怎么会啊，但我们只能尽我们自己最大的努力把程序给写出来，虽然知道这一路肯定是异常的艰苦，但豁出去了。上网查资料、去图书馆查，查相关的函数，在老师的教导下，经过两三天的努力，把程序完美的做了出来。
六 参考文献
[1] 严蔚敏、吴伟民主编 《数据结构》（C 语言版） 清华大学出版社 2002
[2] 殷人昆等著 《数据结构》（C++版） 清华大学出版社 2001
[3] 金远平著 《数据结构》（C++描述） 清华大学出版社 2005
[4] 许卓群等著 《数据结构与算法》 高等教育出版社 2004
[5] Frank M.Carrano 等著 《数据结构与Ｃ++高级教程》清华大学出版社 2004
[6] 严蔚敏、吴伟民 《数据结构习题集》（c语言版）清华大学出版社