数据结构迷宫问题实验报告.docx
《数据结构迷宫问题实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构迷宫问题实验报告.docx（20页珍藏版）》请在冰点文库上搜索。
数据结构迷宫问题实验报告
《数据结构与算法设计》
迷宫问题实验报告
——实验二
专业:
物联网工程
班级:
物联网1班
学号:
姓名:
刘沛航
一、实验目的
本程序就是利用非递归的方法求出一条走出迷宫的路径,并将路径输出。
首先由用户输入一组二维数组来组成迷宫,确认后程序自动运行,当迷宫有完整路径可以通过时,以0与1所组成的迷宫形式输出,标记所走过的路径结束程序;当迷宫无路径时,提示输入错误结束程序。
二、实验内容
用一个m*m长方阵表示迷宫,0与1分别表示迷宫中的通路与障碍。
设计一个程序对于任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
三、程序设计
1、概要设计
（1） 设定栈的抽象数据类型定义
ADTStack{
数据对象:
D={ai|ai属于CharSet,i=1、2…n,n>=0}
数据关系:
R={|ai-1,ai属于D,i=2,3,…n}
基本操作:
InitStack（&S）
操作结果:
构造一个空栈
Push（&S,e）
初始条件:
栈已经存在
操作结果:
将e所指向的数据加入到栈s中
Pop（&S,&e）
初始条件:
栈已经存在
操作结果:
若栈不为空,用e返回栈顶元素,并删除栈顶元素
Getpop（&S,&e）
初始条件:
栈已经存在
操作结果:
若栈不为空,用e返回栈顶元
StackEmpty（&S）
初始条件:
栈已经存在
操作结果:
判断栈就是否为空。
若栈为空,返回1,否则返回0
Destroy（&S）
初始条件:
栈已经存在
操作结果:
销毁栈s
}ADTStack
（2）设定迷宫的抽象数据类型定义
ADTyanshu{
数据对象:
D={ai,j|ai,j属于{‘’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N}
数据关系:
R={ROW,COL}
ROW={|ai-1,j,ai,j属于D,i=1,2,…M,j=0,1,…N}
COL={|ai,j-1,ai,j属于D,i=0,1,…M,j=1,2,…N}
基本操作:
InitMaze（MazeType&maze,inta[][COL],introw,intcol）{
初始条件:
二维数组inta[][COL],已经存在,其中第1至第m-1行,每行自第1到第n-1列的元素已经值,并以值0表示障碍,值1表示通路。
操作结果:
构造迷宫的整形数组,以空白表示通路,字符‘0’表示障碍
在迷宫四周加上一圈障碍
MazePath（&maze）{
初始条件:
迷宫maze已被赋值
操作结果:
若迷宫maze中存在一条通路,则按如下规定改变maze的状态;以字符‘*’表示路径上的位置。
字符‘@’表示‘死胡同’;否则迷宫的状态不变
}
PrintMaze（M）{
初始条件:
迷宫M已存在
操作结果:
以字符形式输出迷宫
}
}ADTmaze
（3）本程序包括三个模块
a、 主程序模块
voidmain（）
{
初始化;
构造迷宫;
迷宫求解;
迷宫输出;
}
b、 栈模块——实现栈的抽象数据类型
c、 迷宫模块——实现迷宫的抽象数据类型
2、详细设计
（1）坐标位置类型:
typedefstruct{
introw; //迷宫中的行
intcol; //、、、、、、的列
}PosType;//坐标
（2） 迷宫类型:
typedefstruct{
intm,n;
intarr[RANGE][RANGE];
}MazeType; //迷宫类型
void InitMaze（MazeType&maze,inta[][COL],introw,intcol）\
//设置迷宫的初值,包括边缘一圈的值
BoolMazePath（MazeType&maze,PosTypestart,PosTypeend）
//求解迷宫maze中,从入口start到出口end的一条路径
//若存在,则返回true,否则返回false
VoidPrintMaze（MazeTypemaze）
//将迷宫打印出来
（3） 栈类型:
typedefstruct{
int step; //当前位置在路径上的"序号"
PosType seat; //当前的坐标位置
DirectiveType di; //往下一个坐标位置的方向
}SElemType;//栈的元素类型
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
栈的基本操作设置如下:
VoidInitStack（SqStack&S）
//初始化,设S为空栈（S、top=NUL）
VoidDestroyStack（Stack&S）
//销毁栈S,并释放空间
VoidClearStack（SqStack&S）
//将栈S清空
IntStackLength（SqStack&S）
//返回栈S的长度
StatusStackEmpty（SqStack&S）
？
、若S为空栈（S、top==NULL）,则返回TRUE,否则返回FALSE
StatueGetTop（SqStack&S,SElemTypee）
//r若栈S不空,则以e待会栈顶元素并返回TRUE,否则返回FALSE
StatuePop（SqStack&S,SElemTypee）
//若分配空间成功,则在S的栈顶插入新的栈顶元素s并返回TRUE
//否则栈不变,并返回FALSE
StatuePush（SqStack&S,SElemType&e）
//若分配空间程控,则删除栈顶并以e带回其值,则返回TRUE
//否则返回FALSE
VoidStackTraverse（SqStack&S,Status）（*Visit）（SElemTypee））
//从栈顶依次对S中的每个节点调用函数Visit
4求迷宫路径的伪码算法:
StatusMazePath（MazeType&maze,PosTypestart,PosTypeend）{//求解迷宫maze中,从入口start到出口end的一条路径
InitStack（s）;
PosTypecurpos=start;
intcurstep=1; //探索第一部
do{
if（Pass（maze,curpos））{ //如果当前位置可以通过,即就是未曾走到的通道块
FootPrint（maze,curpos）; //留下足迹
e=CreateSElem（curstep,curpos,1）; //创建元素
Push（s,e）;
if（PosEquare（curpos,end）） returnTRUE;
curpos=NextPos（curpos,1）; //获得下一节点:
当前位置的东邻
curstep++; //探索下一步
}else{ //当前位置不能通过
if（!
StackEmpty（s））{
Pop（s,e）;
while（e、di==4&&!
StackEmpty（s））{
MarkPrint（maze,e、seat）;Pop（s,e）; //留下不能通过的标记,并退回步
}
if（e、di<4）{
e、di++;Push（s,e）; //换一个方向探索
curpos=NextPos（e、seat,e、di）; //设定当前位置就是该方向上的相块
}//if
}//if
}//else
}while（!
StackEmpty（s））;
returnFALSE;
}
//MazePath
四、程序调试分析
1、首先呢,想自己读入数据的,回来发现那样,很麻烦,所以还就是事先定义一个迷宫。
2、栈的元素类型一开始有点迷惑,后来就解决了
3、本题中三个主要算法;InitMaze,MazePath与PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也就是O（m*n）
五、用户使用说明
1.本程序运行在windows系列的操作系统下,执行文件为:
Maze_Test、exe。
六、程序运行结果
1、建立迷宫:
2.通过1功能建立8*8的迷宫后,通过2功能继续建立迷宫内部:
通过建立自己设定单元数目建立迷宫内墙。
3.通过3功能观察已建立的迷宫结构:
4.通过4功能确立迷宫起点与终点:
（此处像我们随机选择4,4与2,7分别为起点终点）
5.执行5功能,判断就是否有路径走出迷宫:
这种情况无法走出迷宫。
我们再次观察图像设4,4与1,6分别为起点终点,再运行5功能。
观察到可以成功解开迷宫步数从1依次开始。
七、程序清单
#include
#include
#include
#include
//迷宫坐标位置类型
typedefstruct
{
intx;//行值
inty;//列值
}PosType;
#defineMAXLENGTH25//设迷宫的最大行列为25
typedefintMazeType[MAXLENGTH][MAXLENGTH];//迷宫数组[行][列]
typedefstruct//栈的元素类型
{
intord;//通道块在路径上的＂序号＂
PosTypeseat;//通道块在迷宫中的＂坐标位置＂
intdi;//从此通道块走向下一通道块的＂方向＂（0～3表示东～北）
}SElemType;
//全局变量
MazeTypem;//迷宫数组
intcurstep=1;//当前足迹,初值为1
#defineSTACK_INIT_SIZE10//存储空间初始分配量
#defineSTACKINCREMENT2//存储空间分配增量
//栈的顺序存储表示
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）
exit（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）
exit（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;
}
voidFootPrint（PosTypea）//使迷宫m的a点的序号变为足迹（curstep）,表示经过
{
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;
}
//若迷宫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"）;
}
}
voidmain（）
{
PosTypebegin,end;
inti,j,x,y,x1,y1,n,k;
do{
system（"cls"）;//清屏函数
printf（"**************************物联网1班-15180118-刘沛航*************************\n\n\n"）;
printf（"1请输入迷宫的行数,列数\n"）;
printf（"2请输入迷宫内墙单元数\n"）;
printf（"3迷宫结构如下\n"）;
printf（"4输入迷宫的起点与终点\n"）;
printf（"5输出结果\n"）;
printf（"0退出\n"）;
printf（"\n\n请选择"）;
scanf（"%d",&n）;
switch（n）
{
case1:
{
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
}break;
case2:
{printf（"请输入迷宫内墙单元数:
"）;
scanf（"%d",&j）;
printf（"请依次输入迷宫内墙每个单元的行数,列数:
（空格隔开）\n"）;
for（i=1;i<=j;i++）
{
scanf（"%d%d",&x1,&y1）;
m[x1][y1]=0;
}
}break;
case3:
{Print（x,y）;printf（"刘沛航建立的迷宫,定义墙元素值为0,可通过路径为1,输入0退出"）;scanf（"%d",&k）;}break;
case4:
{printf（"请输入起点的行数,列数:
（空格隔开）"）;
scanf（"%d%d",&begin、x,&begin、y）;
printf（"请输入终点的行数,列数:
（空格隔开）"）;
scanf（"%d%d",&end、x,&end、y）;}break;
case5:
{
if（MazePath（begin,end））//求得一条通路
{
printf（"此迷宫从入口到出口的一条路径如下,谢谢使用刘沛航的程序:
\n"）;
Print（x,y）;//输出此通路
}
else
printf（"此迷宫没有从入口到出口的路径,谢谢使用刘沛航的程序\n"）;
printf（"输入0退出"）;scanf（"%d",&k）;
}break;
}
}while（n!
=0）;}
升级会员 