(完整word版)数据结构栈求解迷宫问题C语言版(完整word版)数据结构栈求解迷宫问题C语言版(完整word版)数据结构栈求解迷宫问题C语言版数据结构栈求解迷宫问题(C语言版)/*数据结构C语言版栈求解迷宫问题P50-52利用栈求解迷宫问题编译环境：Dev-C++4.9.9.2日期：2011年2月12日*//***************头文件**********************///迷宫坐标位置类型typedefstruct{intx;//行值inty;//列值}PosType;#defineMAXLENGTH25//设迷宫的最大行列为25typedefintMazeType[MAXLENGTH][MAXLENGTH];//迷宫数组[行][列]typedefstruct//栈的元素类型{intord;//通道块在路径上的＂序号＂PosTypeseat;//通道块在迷宫中的＂坐标位置＂intdi;//从此通道块走向下一通道块的＂方向＂(0～3表示东～北)}SElemType;//全局变量MazeTypem;//迷宫数组intcurstep=1;//当前足迹,初值为1#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量//栈的顺序存储表示P46typedefstructSqStack{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//顺序栈/****************实现************************///构造一个空栈SintInitStack(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;elsereturn0;}//插入元素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;elsereturn0;}//使迷宫m的a点的序号变为足迹(curstep)，表示经过voidFootPrint(PosTypea){m[a.x][a.y]=curstep;}//根据当前位置及移动方向，返回下一位置PosTypeNextPos(PosTypec,intdi){PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{行增量,