数据结构迷宫求解算法.doc

《数据结构迷宫求解算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#defineoverflow-1#defineok1#defineerror0#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintStatus;typedefstruct{intx;inty;}PosType;//位置类型typedefstruct{introw,col;inta[50][50];}MazeType;//迷宫类型typedefstruct{intord;//通道块在路径上的序号PosTyp

2、eseat;//通道块在迷宫中的“坐标位置”intdi;//从此通道块走向下一个通道块的方向}SElemType;//栈的元素类型typedefstruct{SElemType*base;SElemType*top;intStacksize;}SqStack;//栈结构StatusInitStack(SqStack&S)//初始化栈{S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(overflow);S.top=S.base;S.St

3、acksize=STACK_INIT_SIZE;returnok;}StatusPush(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(overflow);S.top=S.base+S.Stacksize;S.Stacksize+=STACKINCREMENT;}*S.top++=

4、e;returnok;}StatusPop(SqStack&S,SElemType&e)//出栈{if(S.top==S.base)returnerror;e=*--S.top;returnok;}boolStackEmpty(SqStackS)//判断栈是否为空{if(S.top==S.base)returnok;elsereturnerror;}StatusInitMaze(MazeType&maze)//初始化迷宫{inti,j;for(j=0;j

5、ze.row+1;i++){maze.a[i][0]=1;maze.a[i][maze.col+1]=1;for(intj=1;j

6、os.x][curpos.y]==0;}StatusFootPrint(MazeType&maze,PosTypecurpos)//留下足迹{maze.a[curpos.x][curpos.y]=2;returnok;}SElemTypeCreatElem(intstep,PosTypepos,intdi)//创造一个SElemType型的数据{SElemTypee;e.ord=step;e.seat=pos;e.di=di;returne;}boolIsEnd(PosTypepos1,PosTypepos2)//判断是否结束{retur

7、npos1.x==pos2.x&&pos1.y==pos2.y;}PosTypeNextPos(PosTypecurpos,intdi)//向下一步搜索{PosTypepos=curpos;switch(di){case1:pos.x++;break;//向东case2:pos.y++;break;//向南case3:pos.x--;break;//向西case4:pos.y--;break;//向北}returnpos;}StatusMarkPrint(MazeType&maze,PosTypecurpos)//在死路处留下印迹{maz

8、e.a[curpos.x][curpos.y]='*';returnok;}StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)//寻找路