迷宫问题求解(新增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<<endl;
if(MazePath(start,end)){
cout<<"迷宫的通路："<<endl<<"（其中*表示外墙，#表示迷宫内障碍物,.为通路）"<<endl<<endl;
PrintMaze(r,l);
}
else cout<<"迷宫没有通路！"<<endl;
free(S.base);
return 0;
}
2）栈模块
3）迷宫模块
各模块的调用关系如下：
4）求解迷宫的通路的伪码算法：
设定当前位置的处值为入口位置；
DO
{
若当前的位置可通。
则{将当前的位置插入栈顶；
若该位置为出口位置，则结束；
否则切换当前位置的东邻的为新的当前位置；}
否则{
若栈不为空且栈的顶位置尚有其他的方向没有被探索，
则设定新的当前位置为沿顺时针方向旋转找到栈顶的位置的下一个相邻块；
若栈不空但栈顶的四周均不可通过，
则{删去栈顶位置；
若栈不为空，则重新测试新的栈顶位置；
只至找到一个可通过的块至栈空；
}
1 坐标的位置的类型
typedef struct{
int line;
int row;
}PosType;2 迷宫类型
void CreatMaze(int r,int l)//定义迷宫的墙为*，通路为_，障碍为#
{
int i,j;
for(i=0;i<r;i++){
maze[i][0]='*';//左面墙
maze[i][l-1]='*';//右面墙
}
for(j=1;j<l-1;j++){
maze[0][j]='*';//上面墙
maze[r-1][j]='*';//下面墙
}
for(i=1;i<r-1;i++)
for(j=1;j<l-1;j++)
maze[i][j]='_';
cout<<"请输入迷宫内障碍物的个数：";
int num;
cin>>num;
cout<<"请依次输入障碍物的坐标："<<endl;
int x,y;
for(i=1;i<=num;i++){
cin>>x>>y;
maze[x][y]='#';
}
cout<<endl<<"创建的迷宫的如下："<<endl<<endl;
PrintMaze(r,l);
cout<<endl;
}3 栈类型
typedef struct
{
int ord; //通道块在路径上的序号
PosType seat; //通道块在迷宫中的坐标位置
int di; //从此通道块走向下一通道块的方向 东1；南2；西3；北4
}SElemType;
4 迷宫的路径的算法
int MazePath(PosType start,PosType end)
{
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)//到达终点
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 <string.h>
#include <malloc.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream.h>

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<row;i++){
for(int j=0;j<line;j++)
cout<<(char)maze[i][j]<<" ";
cout<<endl<<endl;
}
}

void CreatMaze(int r,int l){//定义迷宫的墙为*，通路为_，障碍为#
int i,j;
for(i=0;i<r;i++){
maze[i][0]='*';//左面墙
maze[i][l-1]='*';//右面墙
}
for(j=1;j<l-1;j++){
maze[0][j]='*';//上面墙
maze[r-1][j]='*';//下面墙
}
for(i=1;i<r-1;i++)
for(j=1;j<l-1;j++)
maze[i][j]='_';
cout<<"请输入迷宫内障碍物的个数：";
int num;
cin>>num;
cout<<"请依次输入障碍物的坐标："<<endl;
int x,y;
for(i=1;i<=num;i++){
cin>>x>>y;
maze[x][y]='#';
}
cout<<endl<<"创建的迷宫的如下："<<endl<<endl;
PrintMaze(r,l);
cout<<endl;
}

int MazePath(PosType start,PosType end){
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)//到达终点
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;
}

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