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

#include #include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef structint r;int c;PosType;/通道块坐标typedef struct int ord;/通道块在路径上的序号PosType seat;/通道块的坐标位置int di;/下一个探索的方向SelemType;typedef struct int r;int c;char adr1010;MazeType;/迷宫行列，内容typedef struct SelemType * base; SelemType * top;int stacksize;SqStack;void InitStack(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;void Push(SqStack &S,SelemType &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;void Pop(SqStack &S,SelemType &e)if(S.top=S.base) return;e=*-S.top;void InitMaze(MazeType &maze)int i,j;maze.r=8;maze.c=8;for(i=0;i10;i+)maze.adr0i=#;maze.adr9i=#;for(i=0;i10;i+)maze.adri0=#;maze.adri9=#;for(i=1;i9;i+)for(j=1;j9;j+)maze.adrij=1;maze.adr13=#;maze.adr17=#;maze.adr23=#;maze.adr27=#; maze.adr35=#;maze.adr36=#;maze.adr42=#;maze.adr43=#;maze.adr44=#;maze.adr54=#;maze.adr62=#;maze.adr66=#;maze.adr72=#;maze.adr73=#;maze.adr74=#;maze.adr76=#;maze.adr77=#;maze.adr81=#;int Pass(MazeType &maze,PosType &curpos)if(maze.adrcurpos.rcurpos.c=1)return 1;elsereturn 0;void FootPrint(MazeType &maze,PosType curpos)maze.adrcurpos.rcurpos.c=*;/已经走过的标记PosType NextPos(PosType curpos,int i)PosType nextpos;nextpos=curpos;switch(i)case 1:nextpos.c+=1;break;case 2:nextpos.r+=1;break;case 3:nextpos.c-=1;break;case 4:nextpos.r-=1;break;default:printf(探寻方向错误!);return nextpos;void MarkPrint(MazeType &maze,PosType curpos)maze.adrcurpos.rcurpos.c=;/不通的标识int StackEmpty(SqStack &S)if(S.base=S.top)return 1;elsereturn 0;void MazePath(MazeType &maze,PosType start,PosType end)SelemType e;SqStack S;InitStack(S);PosType curpos;int curstep;curpos=start;curstep=1;doif(Pass(maze,curpos)FootPrint(maze,curpos);/留下走过足迹*e.ord=curstep;e.seat=curpos;e.di=1;Push(S,e);/压入栈路径if(curpos.r=end.r&curpos.c=end.c) return;curpos=NextPos(curpos,1);/探索下一步curstep+;/ifelse/当前位置不能通过if(!StackEmpty(S) Pop(S,e);/top指针退后一下，指向上一步while(e.di=4&!StackEmpty(S)MarkPrint(maze,e.seat);/如果此步上下左右都探索过了且栈不为空留下不通过且返回一步Pop(S,e);/while,用while是可以连续返回if(e.di4)e.di+;Push(S,e);/换下一个方向探索curpos=NextPos(e.seat,e.di);/探索下一位置块/if/if/elsewhile(!StackEmpty(S);/mazepathvoid PrintMaze(MazeType &maze)int i,j; for(i=0;i10;i+) printf(%4d,i);/输出行 printf(nn); for(i=0;i10;i+) printf(%2d,i);/输出列 for(j=0;j10;j+) printf(%4c,maze.adrij); printf(nn); void main()MazeType m