迷宫求解数据结构C语言版.doc

《迷宫求解数据结构C语言版.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{intr;intc;}PosType;//通道块坐标typedefstruct{intord;//通道块在路径上的序号PosTypeseat;//通道块的坐标位置intdi;//下一个探索的方向}SelemType;typedefstruct{intr;intc;charadr[10][10

2、];}MazeType;//迷宫行列，内容typedefstruct{SelemType*base;SelemType*top;intstacksize;}SqStack;voidInitStack(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;}voidPush(SqStack&S,SelemType

3、&e){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;}voidPop(SqStack&S,SelemType&e){if(S.top==S.base)re

4、turn;e=*--S.top;}voidInitMaze(MazeType&maze){inti,j;maze.r=8;maze.c=8;for(i=0;i<10;i++){maze.adr[0][i]='#';maze.adr[9][i]='#';}for(i=0;i<10;i++){maze.adr[i][0]='#';maze.adr[i][9]='#';}for(i=1;i<9;i++)for(j=1;j<9;j++)maze.adr[i][j]='1';maze.adr[1][3]='#';maze.ad

5、r[1][7]='#';maze.adr[2][3]='#';maze.adr[2][7]='#';maze.adr[3][5]='#';maze.adr[3][6]='#';maze.adr[4][2]='#';maze.adr[4][3]='#';maze.adr[4][4]='#';maze.adr[5][4]='#';maze.adr[6][2]='#';maze.adr[6][6]='#';maze.adr[7][2]='#';maze.adr[7][3]='#';maze.adr[7][4]='#';ma

6、ze.adr[7][6]='#';maze.adr[7][7]='#';maze.adr[8][1]='#';}intPass(MazeType&maze,PosType&curpos){if(maze.adr[curpos.r][curpos.c]=='1')return1;elsereturn0;}voidFootPrint(MazeType&maze,PosTypecurpos){maze.adr[curpos.r][curpos.c]='*';//已经走过的标记}PosTypeNextPos(PosTypec

7、urpos,inti){PosTypenextpos;nextpos=curpos;switch(i){case1:nextpos.c+=1;break;case2:nextpos.r+=1;break;case3:nextpos.c-=1;break;case4:nextpos.r-=1;break;default:printf("探寻方向错误!");}returnnextpos;}voidMarkPrint(MazeType&maze,PosTypecurpos){maze.adr[curpos.r][curpo

8、s.c]='@';//不通的标识}intStackEmpty(SqStack&S){if(S.base==S.top)return1;elsereturn0;}voidMazePath(MazeType&maze,PosTypestart,PosTypeend){SelemTypee;SqStackS;InitStack(S);PosTypec