栈的应用-迷宫问题-数据结构(C语言版)-源代码(直接运行).doc

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#defineSTACK_INIT_SIZE100
#defineINCREMENT10

typedefstruct
{
intr;
intc;
}zuobiao;

typedefstruct
{
intord;//在当前坐标上的“标号”
zuobiaoseat;//坐标
intdi;//走向下一通道的方向
}lujing;

typedefstruct
{
intsz[10][10];
}Maze;

typedefstructSqStack
{
lujing*base;
lujing*top;
intsize;
}SqStack;

intinitStack(SqStack*s)
{
s->base=(lujing*)malloc(STACK_INIT_SIZE*sizeof(lujing));
if(!s->base)
return-1;
s->top=s->base;
s->size=STACK_INIT_SIZE;
return0;
}

intpush(SqStack*s,lujinge)
{
if(s->top-s->base>=s->size)
{
s->base=(lujing*)realloc(s->base,(s->size+INCREMENT)*sizeof(lujing));
if(!s->base)
return-1;
s->top=s->base+s->size;
s->size+=INCREMENT;
}

*s->top++=e;
return0;
}

intpop(SqStack*s,lujing*e)
{
if(s->top==s->base)
return-1;
*e=*(--s->top);
return0;
}

intisEmpty(SqStack*s)
{
if(s->base==s->top)
return1;
else
return0;
}

intpass(Mazemaze,zuobiaodqzb){
if(maze.sz[dqzb.r][dqzb.c]==1)
return1;//如果当前位置是可以通过，返回1
elsereturn0;//否则返回0
}

voidfootPrint(Maze&maze,zuobiaodqzb){
maze.sz[dqzb.r][dqzb.c]=9;
}

voidmarkPrint(Maze&maze,zuobiaodqzb){
maze.sz[dqzb.r][dqzb.c]=4;
}

zuobiaonextPos(zuobiaodqzb,intDir){
zuobiaoxzb;
switch(Dir){
case1:
xzb.r=dqzb.r;
xzb.c=dqzb.c+1;
break;
case2:
xzb.r=dqzb.r+1;
xzb.c=dqzb.c;
break;
case3:
xzb.r=dqzb.r;
xzb.c=dqzb.c-1;
break;
case4:
xzb.r=dqzb.r-1;
xzb.c=dqzb.c;
break;
}
returnxzb;
}

intmazePath(Maze&maze,zuobiaostart,zuobiaoend)
{
SqStack*s=(SqStack*)malloc(sizeof(SqStack));
initStack(s);
zuobiaodqzb=start;//设定"当前位置"为"入口位置"
lujinge;
intcurstep=1;//探索第一步
do{
if(pass(maze,dqzb)){//当前位置可通过，即是未曾走到过的通道块
footPrint(maze,dqzb);//留下足迹
e.di=1;
e.ord=curstep;
e.seat=dqzb;
push(s,e);//加入路径
if(dqzb.r==end.r&&dqzb.c==end.c)
return0;//到达终点（出口）
dqzb=nextPos(dqzb,1);//下一位置是当前位置的东邻
curstep++;//探索下一步
}else{//当前位置不能通过
if(!isEmpty(s)){
pop(s,&e);
while(e.di==4&&!isEmpty(s)){
markPrint(maze,e.seat);
pop(s,&e);//留下不能通过的标记，并退回一步
}
if(e.di<4){
e.di++;//换下一个方向探索
push(s,e);
dqzb=nextPos(e.seat,e.di);//当前位置设为新方向的相邻块
}
}
}
}