数据结构迷宫问题实验报告Word文件下载.doc
《数据结构迷宫问题实验报告Word文件下载.doc》由会员分享，可在线阅读，更多相关《数据结构迷宫问题实验报告Word文件下载.doc（15页珍藏版）》请在冰点文库上搜索。
若栈为空，返回1，否则返回0
Destroy（&
销毁栈s
}ADTStack
（2）设定迷宫的抽象数据类型定义
ADTyanshu{
D={ai,j|ai,j属于{‘’、‘*’、‘@’、‘#’},0<
=i<
=M,0<
=j<
=N}
R={ROW,COL}
ROW={<
ai-1,j,ai,j>
|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N}
COL={<
ai,j-1,ai,j>
|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
maze,inta[][COL],introw,intcol）\
//设置迷宫的初值，包括边缘一圈的值
BoolMazePath（MazeType&
maze,PosTypestart,PosTypeend）
//求解迷宫maze中，从入口start到出口end的一条路径
//若存在，则返回true，否则返回false
VoidPrintMaze（MazeTypemaze）
//将迷宫打印出来
（3）
栈类型：
int
step;
//当前位置在路径上的"
序号"
PosType
seat;
//当前的坐标位置
DirectiveType
di;
//往下一个坐标位置的方向
}SElemType;
//栈的元素类型
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
栈的基本操作设置如下：
VoidInitStack（SqStack&
S）
//初始化，设S为空栈（S.top=NUL）
VoidDestroyStack（Stack&
//销毁栈S，并释放空间
VoidClearStack（SqStack&
//将栈S清空
IntStackLength（SqStack&
//返回栈S的长度
StatusStackEmpty（SqStack&
？
、若S为空栈（S.top==NULL），则返回TRUE，否则返回FALSE
StatueGetTop（SqStack&
S，SElemTypee）
//r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSE
StatuePop（SqStack&
//若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE
//否则栈不变，并返回FALSE
StatuePush（SqStack&
S，SElemType&
//若分配空间程控，则删除栈顶并以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
}//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<
stdio.h>
stdlib.h>
string.h>
malloc.h>
//迷宫坐标位置类型
typedefstruct
intx;
//行值
inty;
//列值
#defineMAXLENGTH25//设迷宫的最大行列为25
typedefintMazeType[MAXLENGTH][MAXLENGTH];
//迷宫数组[行][列]
typedefstruct//栈的元素类型
intord;
//通道块在路径上的＂序号＂
PosTypeseat;
//通道块在迷宫中的＂坐标位置＂
intdi;
//从此通道块走向下一通道块的＂方向＂（0～3表示东～北）
//全局变量
MazeTypem;
//迷宫数组
intcurstep=1;
//当前足迹,初值为1
#defineSTACK_INIT_SIZE10 //存储空间初始分配量
#defineSTACKINCREMENT2 //存储空间分配增量
//栈的顺序存储表示
typedefstructSqStack
SElemType*base;
//在栈构造之前和销毁之后，base的值为NULL
SElemType*top;
//栈顶指针
intstacksize;
//当前已分配的存储空间，以元素为单位
//顺序栈
// 构造一个空栈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（!
exit（0）;
（*S）.top=（*S）.base+（*S）.stacksize;
（*S）.stacksize+=STACKINCREMENT;
}
*（（*S）.top）++=e;
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；
否则返回0。
intPop（SqStack*S,SElemType*e）
if（（*S）.top==（*S）.base）
*e=*--（*S）.top;
//这个等式的++*优先级相同，但是它们的运算方式，是自右向左
//定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹
//当迷宫m的b点的序号为1（可通过路径），return1;
否则，return0。
intPass（PosTypeb）
{
if（m[b.x][b.y]==1）
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（&
e）;
//退栈到前一位置
curstep--;
while（e.di==3&
!
StackEmpty（S））//前一位置处于最后一个方向（北）
{
MarkPrint（e.seat）;
//留下不能通过的标记（-1）
Pop（&
//退回一步
curstep--;
}
if（e.di<
3）//没到最后一个方向（北）
e.di++;
//换下一个方向探索
Push（&
curstep++;
//设定当前位置是该新方向上的相邻块
curpos=NextPos（e.seat,e.di）;
}
}while（!
StackEmpty（S））;
return0;
//输出迷宫的结构
voidPrint（intx,inty）
inti,j;
for（i=0;
i<
x;
i++）
for（j=0;
j<
y;
j++）
printf（"
%3d"
m[i][j]）;
printf（"
\n"
）;
}
PosTypebegin,end;
inti,j,x,y,x1,y1,n,k;
do{
system（"
cls"
//清屏函数
printf（"
**************************物联网1班-15180118-刘沛航*************************\n\n\n"
1请输入迷宫的行数,列数\n"
2请输入迷宫内墙单元数\n"
3迷宫结构如下\n"
4输入迷宫的起点和终点\n"
5输出结果\n"
0退出\n"
\n\n请选择"
scanf（"
%d"
&
n）;
switch（n）
case1:
{
printf（"
请输入迷宫的行数,列数（包括外墙）：
（空格隔开）"
scanf（"
%d%d"
&
x,&
y）;
for（i=0;
i++）//定义周边值为0（同墙）
{
m[0][i]=0;
//迷宫上面行的周边即上边墙
m[x-1][i]=0;
//迷宫下面行的周边即下边墙
for（j=1;
y-1;
{
m[j][0]=0;
//迷宫左边列的周边即左边墙
m[j][y-1]=0;
//迷宫右边列的周边即右边墙
}
for（i=1;
x-1;
for（j=1;
m[i][j]=1;
//定义通道初值为1
}break;
case2:
{printf（"
请输入迷宫内墙单元数：
"
scanf（"
j）;
printf（"
请依次输入迷宫内墙每个单元的行数,列数：
（空格隔开）\n"
for（i=1;
=j;
{
scanf（"
x1,&
y1）;
m[x1][y1]=0;
}
}break;
case3:
{ Print（x,y）;
刘沛航建立的迷宫，定义墙元素值为0,可通过路径为1，输入0退出"
scanf（"
k）;
}break;
case4:
{printf（"
请输入起点的行数,列数：
scanf（"
begin.x,&
begin.y）;
printf（"
请输入终点的行数,列数：
end.x,&
end.y）;
case5:
if（MazePath（begin,end））//求得一条通路
此迷宫从入口到出口的一条路径如下，谢谢使用刘沛航的程序:
Print（x,y）;
//输出此通路
此迷宫没有从入口到出口的路径，谢谢使用刘沛航的程序\n"
printf（"
输入0退出"
}break;
}while（n!
=0）;
升级会员 