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

#include #include #define overflow -1#define ok 1#define error 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef struct int x;int y;PosType;/位置类型typedef structint row,col;int a5050;MazeType;/迷宫类型typedef structint ord;/通道块在路径上的序号PosType seat;/通道块在迷宫中的“坐标位置”int di;/从此通道块走向下一个通道块的方向SElemType;/栈的元素类型typedef structSElemType *base;SElemType *top;int Stacksize;SqStack;/栈结构Status InitStack(SqStack &S)/初始化栈S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit (overflow);S.top=S.base;S.Stacksize=STACK_INIT_SIZE;return ok;Status 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 (overflow);S.top=S.base+S.Stacksize;S.Stacksize+=STACKINCREMENT;*S.top+=e;return ok;Status Pop(SqStack &S,SElemType &e)/出栈if(S.top=S.base) return error;e=*-S.top;return ok;bool StackEmpty(SqStack S)/判断栈是否为空if(S.top=S.base)return ok;else return error;Status InitMaze(MazeType &maze)/初始化迷宫 int i,j; for( j=0;jmaze.col+2;j+)maze.a0j=1;for( i=1;imaze.row+1;i+)maze.ai0=1;maze.aimaze.col+1=1; for(int j=1;jmaze.col+1;j+) scanf(%d,&maze.aij); for(j=0;jmaze.col+2;j+)maze.amaze.row+1j=1; return ok;/为了避免检查边界，把迷宫的外围都设成障碍，迷宫的内核是row行，col列的数组bool Pass(MazeType maze,PosType curpos)/判断是否可以通过return maze.acurpos.xcurpos.y=0;Status FootPrint(MazeType &maze,PosType curpos)/留下足迹 maze.acurpos.xcurpos.y=2; return ok;SElemType CreatElem(int step,PosType pos,int di)/创造一个SElemType型的数据SElemType e;e.ord=step;e.seat=pos;e.di=di;return e;bool IsEnd(PosType pos1,PosType pos2)/判断是否结束return pos1.x=pos2.x&pos1.y=pos2.y;PosType NextPos(PosType curpos,int di)/向下一步搜索 PosType pos=curpos; switch(di) case 1:pos.x+;break;/向东case 2:pos.y+;break;/向南case 3:pos.x-;break;/向西case 4:pos.y-;break;/向北 return pos;Status MarkPrint(MazeType &maze,PosType curpos)/在死路处留下印迹 maze.acurpos.xcurpos.y=*; return ok;Status MazePath(MazeType &maze,PosType start,PosType end)/寻找路径/若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），/并返回ture；否则返回falseSqStack S;SElemType e;InitStack(S);PosType curpos=start;/设定当前位置为入口位置int curstep=1;/探索第一步doif(Pass(maze,curpos)FootPrint(maze,curpos);/留下足迹e=CreatElem(curstep,curpos,1);Push(S,e);/加入路径if(IsEnd(curpos,end)return ok;/达到终点curpos=NextPos(curpos,1);/下一步是当期位置的东邻curstep+;/探索下一步else/当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(maze,e.seat);/留下不能通过的标记，并退一步Pop(S,e);if(e.di4)e.di+;/换下一个方向Push(S,e);curpos=NextPos(e.seat,e.di);/设定当前位置是新方向上的相邻块while(!StackEmpty(S);return error;Status PrintMaze(MazeType maze)/输出迷宫 int i,j; for(i=0;imaze.row+2;i+) for(j=0;jmaze.col+2;j+) printf(%d ,maze.aij); printf(n); return ok; void main() MazeType maze;printf(请输入迷宫的行数row和列数col：);scanf(%d %d,&maze.row,&maze.col);printf(请输入迷宫数据，0表示通道，1表示障碍：n);InitMaze(maze);PosType star