资源描述:
《栈的应用-迷宫问题-数据结构(c语言版)-源代码(直接运行)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、#include#include#include#defineSTACK_INIT_SIZE100#defineINCREMENT10typedefstruct{intr;intc;}zuobiao;typedefstruct{intord;//在当前坐标上的“标号”zuobiaoseat;//坐标intdi;//走向下一通道的方向}lujing;typedefstruct{intsz[10][10];}Maze;typedefstructSqStack{lujing*base;lu
2、jing*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+I
3、NCREMENT)*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;elsereturn0;}intpass(Mazemaze,zuob
4、iaodqzb){if(maze.sz[dqzb.r][dqzb.c]==1)return1;//如果当前位置是可以通过,返回1elsereturn0;//否则返回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){cas
5、e1: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);
6、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);//下一位置是当前位置的东邻curst
7、ep++;//探索下一步}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);//当前位置设为新方向的相邻块}}}}while(!isEmpty(s));return-1;}voidmain(){printf("*----Δ迷宫求
8、解Δ----*");printf("---迷宫如下所示:(说明:0表示墙;1表示可以通过)");printf("");Mazemaze;//声明mazemaze.sz