迷宫求解数据结构C语言版(共6页)

1、精选优质文档-倾情为你奉上#include <stdio.h>#include <stdlib.h>#include <malloc.h>#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 adr101

2、0;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

3、)>=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)in

4、t i,j;maze.r=8;maze.c=8;for(i=0;i<10;i+)maze.adr0i='#'maze.adr9i='#'for(i=0;i<10;i+)maze.adri0='#'maze.adri9='#'for(i=1;i<9;i+)for(j=1;j<9;j+)maze.adrij='1'maze.adr13='#'maze.adr17='#'maze.adr23='#'maze.adr27='#' maz

5、e.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='#

6、'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.

7、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;vo

8、id 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;curp

9、os=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.di<4)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;i<10;i+) printf("%4d",i);/输出行 printf("nn"); for(i=0;i<10;i+) printf("%2d",i);/输出列 for(j=0;j<10;j+) printf("%4c",maze.adrij); printf("nn"); void