穷举法求迷宫--栈的应用

《穷举法求迷宫--栈的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//穷举算法2012.8.24#include#include#include#defineM15#defineN15/************************构造几个结构体模型*************************///构建入口和出口的标志结构体typedefstructmark{intx;inty;}Mark;//构建链栈元素的结构体typedefstructelement{intx;//行inty;//列intd;//d下一步的方向}Element;//构造链栈一般节点结构体typedefstruct

2、lStack{Elementelem;structlStack*next;}*PLStack,LStack;//链栈栈顶、栈底指针结构体typedefstructs_head{PLStacktop;PLStackbase;}*PS_Head,S_Head;/*******************************栈相关函数********************************///构造空栈voidInitStack(PS_HeadPS){PS->top=(PLStack)malloc(sizeof(LStack));//链栈头，无实际用处，主要是便于操作if(PS->

3、top==NULL){printf("内存分配失败！");exit(-1);}else{PS->base=PS->top;PS->base->next=NULL;}return;}//判断栈是否为空intStackEmpty(PS_HeadPS){if(PS->top==PS->base)return1;elsereturn0;}//元素入栈voidPush(PS_HeadPS,Element*E){PLStackp;p=(PLStack)malloc(sizeof(LStack));if(p==NULL){printf("内存分配失败！");exit(-1);}else{p

4、->elem=*E;//参见结构体赋值的语法规则p->next=PS->top;PS->top=p;}return;}//栈顶元素出栈voidPop(PS_HeadPS,Element*E){PLStackp;if(!StackEmpty(PS)){*E=PS->top->elem;p=PS->top;PS->top=PS->top->next;//栈顶下移free(p);return;}elsereturn;}/***************************求迷宫路径函数*********************************/voidMazePath(struc

5、tmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2]){intx,y,d;//几个临时变量inta,b;//两个临时变量Elementelem,e;//定义两个链栈元素类型变量S_HeadS1,S2;//创建一个保存链栈头的变量InitStack(&S1);//用来作为迷宫求解工具InitStack(&S2);//用来保存成功求解后的路径。/*最开始的一步就是，指定迷宫的某节点为入口，对其进行重新赋值，使其标记为已经走过*/maze[start.x][start.y]=2;/*对链栈元素类型变量赋值，这个值为非零节点的横纵坐标和

6、方向*/elem.x=start.x;elem.y=start.y;elem.d=-1;//最原始状态-1，为什么不直接赋值为0，原因是与工作状态0，1，2，3和结束状态886相区别，逻辑上更清晰/*变量已经赋好值，因此可以进行原始入栈操作*/Push(&S1,&elem);while(!StackEmpty(&S1))//栈不为空有路径可走{Pop(&S1,&elem);x=elem.x;y=elem.y;d=elem.d+1;//启动工作状态，下一个方向while(d<4)//试探东南西北各个方向，顺时针方向{a=x+diradd[d][0];b=y+diradd[d][1];i

7、f(a==end.x&&b==end.y)//以指定的坐标为出口{elem.x=x;elem.y=y;elem.d=d;Push(&S1,&elem);elem.x=a;elem.y=b;elem.d=886;//d为886表示结束（为拜拜了的谐音），为-1表示原始状态，0，1，2，3表示工作状态Push(&S1,&elem);printf("0=东1=南2=西3=北886为则走出迷宫通路为:(行坐标,列坐标,方向)");/*逆置序列并输出