迷宫求解原码带详细注释文档格式.docx
《迷宫求解原码带详细注释文档格式.docx》由会员分享，可在线阅读，更多相关《迷宫求解原码带详细注释文档格式.docx（19页珍藏版）》请在冰点文库上搜索。
//走向下一地点的方向
}SEletype,*PSEletype;
typedefstruct//定义堆栈
PSEletypebp,sp;
//栈底指针,栈顶指针
intsize;
//记录现在的容量
intlength;
//记录现在的长度
}Stack;
typedefstruct//定义一个迷宫
PPointp;
//迷宫元素的头指针
inth;
//迷宫的行数
intv;
//迷宫的列数
}Maze;
constintSTACK_INCRIMENT=10;
//定义栈初始容量
constintSTACK_INITLENGTH=10;
//定义栈满时的增加容量
intinitStack（Stack&
stack）;
//初始化堆栈
STATUSpush（Stack&
stack,SEletypeip）;
//将一个元素压入堆栈
STATUSstackEmpty（Stack&
//判断堆栈是否为空
STATUSpop（Stack&
stack,SEletype&
e）;
//从堆栈中弹出一个元素赋值给e
voidviewStack（Stack&
//查看堆栈中所有的元素
voidinputMaze（Maze&
maze）;
//读入迷宫的数据
voidviewMaze（Maze&
//查看一个迷宫
voidgetPoint（Maze&
maze,Point&
start,Point&
end）;
//读入起始位置和结束位置
voiddefaultMaze（Maze&
//使用默认迷宫
voidFootPrintY（Point*curp）;
//留下走过可通过的足迹
voidFootPrintN（Point*curp）;
//留下走过不能通过的足迹
Point*nextPos（Maze&
maze,Point*current,intdirection）;
//返回下点的相邻邻接块
STATUSMazePath（Maze&
end,Stack&
stack）;
//求解迷宫的路径
STATUSpass（Point*p）;
//判断当前位置是否可能通过
STATUSpointEqul（Point*p1,Point*p2）;
//判断两个是否相等
voidCopyPoint（Point&
point,Point*pointc）;
//拷贝一个点
intgetMenuResult（）;
//显示提示菜单,并返回用户选择的功能号
voidMainaction（）;
//主要操作流程
voidshowLeaveMessage（inti）;
//显示系统退出信息
voiddestroyMaze（Maze&
maze）;
//消毁迷宫
voidmain（）//主函数
Mainaction（）;
}
STATUSinitStack（Stack&
stack）//初始化堆栈
if（!
（stack.bp=（PSEletype）malloc（sizeof（SEletype）*STACK_INITLENGTH）））
returnNULL;
stack.sp=stack.bp;
stack.length=0;
stack.size=STACK_INITLENGTH;
returnOK;
stack,SEletypeip）//将一个元素压入堆栈
if（stack.length<
stack.size）//如果堆栈未满,直接赋值
{
（stack.sp）->
di=ip.di;
stack.sp->
ord=ip.ord;
（stack.sp++）->
point=ip.point;
stack.length++;
//printf（"
Input:
%d,%d\n"
ip.di,ip.ord）;
returnOK;
}
else//如果堆栈满,则另外分配空间
if（!
（stack.bp=（PSEletype）realloc（stack.bp,（stack.size+STACK_INCRIMENT）*sizeof（SEletype））））
returnNULL;
Test:
stack.sp=stack.bp+stack.length;
e）//从堆栈中弹出一个元素赋值给e
if（stackEmpty（stack））//若栈空,返回错误信息
returnERROR;
e.di=（--stack.sp）->
di;
//若栈不为空,则读入到e中
e.ord=stack.sp->
ord;
e.point=stack.sp->
point;
//printf（"
Pop:
%d"
stack.sp->
di）;
stack.length--;
stack）//判断堆栈是否为空
returnstack.length==0?
TRUE:
FALSE;
stack）//查看堆栈中所有的元素
PSEletypetemp=stack.bp;
inti=0;
while（temp<
stack.sp）
i++;
printf（"
-->
（%d,%d）"
temp->
point.x,（temp++）->
point.y）;
if（i%6==0）
printf（"
\n"
）;
printf（"
maze）//读入迷宫的数据
inth=0,v=0;
//读入迷宫的行数和列数
inti,j;
输入迷宫的行数:
"
scanf（"
&
h）;
输入迷宫的列数:
v）;
maze.p=（PPoint）malloc（sizeof（Point）*（h+2）*（v+2））;
//分配（h+2）*（v+2）的空间存放迷宫
maze.h=h+2;
maze.v=v+2;
输入迷宫[若此点可走输入Y|y,不可走任意输入,不用空格分隔,每行输入完成后请按回车]:
for（i=0;
i<
maze.h;
i++）//使用循环读入
flushall（）;
//清空每行的缓存
for（j=0;
j<
maze.v;
j++）
{
if（i==0||i==maze.h-1||j==0||j==maze.v-1）
{
（maze.p+（i*maze.v）+j）->
r='
;
//将迷宫四周用'
封闭
}
else
scanf（"
（（maze.p+（i*maze.v）+j）->
r））;
//读入数据到迷宫
if（（（maze.p+（i*maze.v）+j）->
r=='
||（maze.p+（i*maze.v）+j）->
y'
））
（maze.p+（i*maze.v）+j）->
r='
else
（maze.p+（i*maze.v）+j）->
x=i;
y=j;
}
maze）//查看一个迷宫
for（i=0;
i++）
j++）
%c"
（maze.p+（i*maze.v）+j）->
r）;
voidgetPoint（Maze&
maze,Point&
start,Point&
end）//读入起始位置和结束位置
inth,v;
输入起始点的坐标,如（2,3）:
你可输入的范围是（1,1）-（%d,%d）:
maze.h-2,maze.v-2）;
flushall（）;
h,&
while（!
（（h>
=1&
&
h<
=maze.h-2）&
（v>
=1&
v<
=maze.v-2）））
输入错误,请再次输入起始点的坐标,如（2,3）:
scanf（"
start.x=h;
start.y=v;
输入结束点的坐标,如（2,3）:
输入错误,请再次输入结束点的坐标,如（2,3）:
end.x=h;
end.y=v;
读入出境的坐标分别为:
%d,%d,%d,%d"
start.x,start.y,end.x,end.y）;
maze）///使用默认迷宫
chart[8][8]={
{'
'
},{'
},
}};
maze.h=maze.v=10;
maze.p=（PPoint）malloc（sizeof（Point）*（10）*（10））;
if（i==0||i==maze.h-1||j==0||j==maze.v-1）
r=t[i-1][j-1];
//将矩阵的值赋值给迷宫
voidFootPrintY（Point*curp）//留下走过可能通过的足迹
（%d,%d）被标记通过\n"
curp->
x,curp->
y）;
curp->
r=SIT;
voidFootPrintN（Point*curp）//留下走过不通过的足迹
//printf（"
（%d,%d）被标记不能走过\n"
curp->
r=SIN;
maze,Point*current,intdirection）//返回下点的相邻邻接块
Point*p;
if（direction==1）//找出右边的点
p=current+1;
elseif（direction==2）//找出下边的点
p=current+maze.v;
elseif（direction==3）//找出左边的点
p=current-1;
else//找出上边的点
p=current-maze.v;
找到的下一个节点是:
（%d,%d）\n"
p->
x,p->
returnp;
STATUSpass（Point*p）//判断当前位置是否可能通过
returnp->
r=='
?
maze,Point&
stack）//求解迷宫的路径
SEletypese;
initStack（stack）;
PPointpo;
po=maze.p+maze.v*（start.x）+start.y;
//计算出堆栈中的起始点
intcurstep=1;
//记录当前走过的通道块的次数
do{
if（pass（po））//如果该通道块可以通过
//printf（"
（%d,%d,%c）可以通过\n"
po->
x,po->
y,po->
FootPrintY（po）;
//向可以通过的通道块做标记
CopyPoint（se.point,po）;
//把当前点拷贝到se中,用于在栈中保存路径
se.ord=curstep;
//记录当前的通道块数目
se.di=1;
//下一次的方向（1表示向右）
push（stack,se）;
//保存se,记录走过的路径
if（pointEqul（po,&
end））//如果当前的点是通道的出口则返回有路可走
returnTRUE;
po=nextPos（maze,po,1）;
//若当前的点不是通道的出口,寻找该点右边的点
curstep++;
else
（%d,%d,%c）不可以通过\n"
if（!
stackEmpty（stack））//如果当前通道块不能走过,且堆栈不为空
PPointp;
pop（stack,se）;
//向后退一个通道块
p=maze.p+（se.point.x*maze.v）+se.point.y;
//根据堆栈中刚弹出的se求出后一个坐标的位置
//printf（"
（%d,%d,%c）从栈中弹出:
y,p->
while（se.di==4&
!
stackEmpty（stack））//如果新弹出的通道块是上一个方向上最后一个通道块
//在堆栈不为空的前提下,弹出所有的最后通道块,直到找到下一个可走的路径,并对不能通过的点做下标记
{
p=maze.p+（se.point.x*maze.v）+se.point.y;
FootPrintN（p）;
//留下不能通过的标记
pop（stack,se）;
//弹出di为4的路径点
}
if（se.di<
4）//如果di<
4,说明有下一个可走的路径
se.di++;
push（stack,se）;
//将当前点放入堆栈
po=nextPos（maze,p,se.di）;
//计算下一个要走过的点
}while（!
stackEmpty（stack））;
returnFALSE;
STATUSpointEqul（Point*p1,Point*p2）//判断两个是否相等
if（（p1->
x==p2->
x）&
（p1->
y==p2->
y））
returnTRUE;
point,Point*pointc）//拷贝一个点
point.x=pointc->
x;
point.y=pointc->
y;
intgetMenuResult（）//显示提示菜单,并返回用户选择的功能号
\n\t\t\t*---------------------------*"
\n\t\t\t$WALKMaze$"
\n\t\t\t|1.UsedefaultMaze|"
\n\t\t\t|2.CreatecustomerMaze|"
\n\t\t\t|3.LookupMazemessage|"
\n\t\t\t|4.WalkalongtheMaze|"
\n\t\t\t|0.Exitsystem|"
\n\t\t\t-->
Inputyourchoice:
inttemp;
temp）;
returntemp;
voidMainaction（）//主要操作流程
Mazemaze;
maze.p=NULL;
intct=0;
ct=getMenuResult（）;
）
if（ct==1）//如果选择为1,则建立默认迷宫
maze.p=NULL;
defaultMaze（maze）;
FG（i,'
\n\t\t\tDefaultMazehascreated!
FG（j,'
elseif（ct==2）//如果选择为2,则用户输入迷宫
inputMaze（maze）;
\n\t\t\tCustomerMazehascreated!
elseif（ct==3）
if（maze.p==NULL）
printf（"
\t\t\tMazedon'
texit,pleasecreatetheMaze!
\n\t\t\tMazemessage!
viewMaze（maze）;
FG（j,'
elseif（ct==4）
Stackstack;
Pointstart,end;
\n\t\t\tBeforeWalk!
getPoint（maze,start,end）;
MazePath（maze,start,end,stack）;
\n\t\t\tAfterWalk!
if（stack.length==0）
printf（"
\n没有通路可走!
升级会员 