(完整word版)数据结构栈求解迷宫问题C语言版.doc

(完整word版)数据结构栈求解迷宫问题C语言版
(完整word版)数据结构栈求解迷宫问题C语言版
(完整word版)数据结构栈求解迷宫问题C语言版
数据结构栈求解迷宫问题(C语言版)

/*
数据结构C语言版栈求解迷宫问题
P50-52利用栈求解迷宫问题
编译环境：Dev-C++4.9.9.2
日期：2011年2月12日
*/

/***************头文件**********************/

//迷宫坐标位置类型
typedefstruct
{
intx; //行值
inty; //列值
}PosType;

#defineMAXLENGTH25//设迷宫的最大行列为25

typedefintMazeType[MAXLENGTH][MAXLENGTH];//迷宫数组[行][列]

typedefstruct//栈的元素类型
{
intord;//通道块在路径上的＂序号＂
PosTypeseat;//通道块在迷宫中的＂坐标位置＂
intdi;//从此通道块走向下一通道块的＂方向＂(0～3表示东～北)
}SElemType;

//全局变量
MazeTypem;//迷宫数组

intcurstep=1;//当前足迹,初值为1

#defineSTACK_INIT_SIZE10 //存储空间初始分配量

#defineSTACKINCREMENT2 //存储空间分配增量

//栈的顺序存储表示P46
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;
}

//使迷宫m的a点的序号变为足迹(curstep)，表示经过
voidFootPrint(PosTypea)
{
m[a.x][a.y]=curstep;
}

//根据当前位

置及移动方向，返回下一位置
PosTypeNextPos(PosTypec,intdi)
{
PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{行增量,