数据结构迷宫算法求解

【文件属性】：
文件名称：数据结构迷宫算法求解
文件大小：36KB
文件格式：DOC
更新时间：2014-04-01 11:02:12
数据结构 /* ****迷宫算法求解************* */ /**计目标：教学演示**************/ #include #define rows 10 #define cols 10 typedef struct {int row; int col; }PosType;/* //坐标点结构 */ typedef struct {int ord;/*//通道块在路径上的“序号” */ PosType seat;/*//通道块在迷宫中的“坐标位置”*/ int di;/*//从此通道快走向下一通道块的“方向” */ }SElemType;/*//栈的元素类型 */ typedef struct {SElemType *base; SElemType *top; int stacksize; }SqStack;/*//堆栈结构 */ void InitStack(SqStack &s)/*//初始化堆栈 */ { s.base=(SElemType *)malloc(100*sizeof(SElemType)); if(!s.base) return NULL; s.top=s.base; s.stacksize=100; } int StackEmpty(SqStack s)/* //栈空判别*/ {return(s.top==s.base); } void Pop(SqStack &s ,SelemType &e)/*//弹栈 */ {e=*--s.top); } void Push(SqStack &s,SElemType e)/*//将元素压入堆栈*/ { *s.top++=e; } /*static int maze[rows][cols]= {{0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,1,0,1,0}, {0,1,1,0,1,0,1,0,1,0}, {0,1,1,0,1,0,0,1,1,0}, {0,1,1,0,0,1,1,1,1,0}, {0,1,1,1,0,1,1,1,1,0}, {0,1,0,1,1,1,0,1,1,0}, {0,1,0,0,0,1,0,0,1,0}, {0,0,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0}, }; */ /* //初始迷宫数据（1－通，0－不通）*/ static int maze[rows][cols]= {{0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,1,0,1,0}, {0,1,1,0,1,0,1,1,1,0}, {0,1,1,1,0,0,0,0,1,0}, {0,1,0,0,0,1,1,1,1,0}, {0,1,0,1,0,1,0,0,0,0}, {0,1,0,1,1,1,0,1,1,0}, {0,1,0,1,0,0,0,0,1,0}, {0,0,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0}, }; /* //初始迷宫数据（1－通，0－不通）*/ static int foot[10][10]={0};/*//标记某点是否走过（1－走过，0－未走过）*/ void printpath(SqStack &s)/*//打印迷宫通路*/ {int i,j; SElemType e; while(!StackEmpty(s)) { Pop(s,e); foot[e.seat.row][e.seat.col]=1; } for(i=0;i<10;i++) {printf("\n"); for(j=0;j<10;j++) if(foot[i][j]) printf(" # "); else printf(" . "); } } int Pass(PosType pos)/*//判断当前的通道块是否可通*/ { return(maze[pos.row][pos.col]); }; void FootPrint(PosType pos) { maze[pos.row][pos.col]=0; } PosType NextPos(PosType curpos,int dir)/*//取当前通道块的下一个通道块*/ { switch(dir) {case 1: curpos.row++; break; case 2: curpos.col++; break; case 3: curpos.row--; break; case 4: curpos.col--; } return curpos;/*//将下一个通道块变为当前通道块*/ } int END(PosType curpos,PosType end) {return(curpos.row==end.row && curpos.col==end.col); } void MazePath(SqStack &s,PosType start,PosType end) {PosType curpos,nextpos; int curstep; SElemType e; SqStack *s; s=InitStack(); curpos=start; curstep=1; do{ if(Pass(curpos)) {FootPrint(curpos); e.ord=curstep;e.seat=curpos;e.di=1; Push(s,e); if(END(curpos,end)) return s; curpos=NextPos(curpos,1); curstep++; }/* end of if */ else { if(!StackEmpty(s)) { e=Pop(s); while(e.di==4 && !StackEmpty(s)) {FootPrint(e.seat);/* The same fuction as MarkPrint ? */ e=Pop(s); }/* end of while */ if(e.di<4) {e.di++;Push(s,e); curpos=NextPos(e.seat,e.di); } /* end of if */ } /* end of if */ } /* end of else */ }while(!StackEmpty(s)); curstep=0; return NULL; } void main() {SqStack *s; static PosType start={1,1},end={8,8}; s=MazePath(start,end); if(s) printpath(s); else printf("\n NO find the path!"); }