栈的应用-迷宫问题-数据结构(C语言版)-源代码(直接运行).doc

《栈的应用-迷宫问题-数据结构(C语言版)-源代码(直接运行).doc》由会员分享，可在线阅读，更多相关《栈的应用-迷宫问题-数据结构(C语言版)-源代码(直接运行).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include #include #include #define STACK_INIT_SIZE 100 #define INCREMENT 10 typedef struct int r; int c; zuobiao; typedef struct int ord; /在当前坐标上的“标号” zuobiao seat; /坐标 int di; /走向下一通道的方向 lujing; typedef struct int sz1010; Maze; typedef struct SqStack lujing *base; lujing *top; int size; SqStack; in

2、t initStack(SqStack *s) s-base = (lujing *)malloc(STACK_INIT_SIZE*sizeof(lujing) ); if(!s-base) return -1; s-top = s-base; s-size = STACK_INIT_SIZE; return 0; int push(SqStack *s, lujing e) if(s-top - s-base = s-size) s-base = (lujing *)realloc(s-base, (s-size+INCREMENT)*sizeof(lujing); if(!s-base)

3、return -1; s-top = s-base+s-size; s-size += INCREMENT; *s-top+ = e; return 0; int pop(SqStack *s,lujing *e) if(s-top = s-base) return -1; *e = *(-s-top); return 0; int isEmpty(SqStack *s) if(s-base = s-top) return 1; else return 0; int pass( Maze maze,zuobiao dqzb) if (maze.szdqzb.rdqzb.c=1) return

4、1; / 如果当前位置是可以通过，返回1 else return 0; / 否则返回0 void footPrint(Maze &maze,zuobiao dqzb) maze.szdqzb.rdqzb.c=9; void markPrint(Maze &maze,zuobiao dqzb) maze.szdqzb.rdqzb.c=4; zuobiao nextPos(zuobiao dqzb, int Dir) zuobiao xzb; switch (Dir) case 1: xzb.r=dqzb.r; xzb.c=dqzb.c+1; break; case 2: xzb.r=dqzb.r

5、+1; xzb.c=dqzb.c; break; case 3: xzb.r=dqzb.r; xzb.c=dqzb.c-1; break; case 4: xzb.r=dqzb.r-1; xzb.c=dqzb.c; break; return xzb; int mazePath(Maze &maze, zuobiao start, zuobiao end) SqStack *s = (SqStack *)malloc(sizeof(SqStack); initStack(s); zuobiao dqzb = start; / 设定当前位置为入口位置 lujing e; int curstep

6、= 1; / 探索第一步 do if (pass(maze,dqzb) / 当前位置可通过，即是未曾走到过的通道块 footPrint(maze,dqzb); / 留下足迹 e.di =1; e.ord = curstep; e.seat= dqzb; push(s,e); / 加入路径 if (dqzb.r = end.r & dqzb.c=end.c) return 0; / 到达终点（出口） dqzb = nextPos(dqzb, 1); / 下一位置是当前位置的东邻 curstep+; / 探索下一步 else / 当前位置不能通过 if (!isEmpty(s) pop(s,&e)

7、; while (e.di=4 & !isEmpty(s) markPrint(maze,e.seat); pop(s,&e); / 留下不能通过的标记，并退回一步 if (e.di4) e.di+; / 换下一个方向探索 push(s, e); dqzb = nextPos(e.seat, e.di); / 当前位置设为新方向的相邻块 while (!isEmpty(s) ); return -1; void main() printf( *-迷宫求解-*nn);printf(-迷宫如下所示:（说明：0表示墙；1表示可以通过）);printf(n);Maze maze; /声明mazemaz

8、e.sz00= 0;maze.sz01= 0;maze.sz02= 0;maze.sz03= 0;maze.sz04= 0;maze.sz05= 0;maze.sz06= 0;maze.sz07= 0;maze.sz08= 0;maze.sz09= 0;maze.sz10= 0;maze.sz11= 1;maze.sz12= 1;maze.sz13= 0;maze.sz14= 1;maze.sz15= 1;maze.sz16= 1;maze.sz17= 0;maze.sz18= 1;maze.sz19= 0;maze.sz20= 0;maze.sz21= 1;maze.sz22= 1;maze

9、.sz23= 0;maze.sz24= 1;maze.sz25= 1;maze.sz26= 1;maze.sz27= 0;maze.sz28= 1;maze.sz29= 0;maze.sz30= 0;maze.sz31= 1;maze.sz32= 1;maze.sz33= 1;maze.sz34= 1;maze.sz35= 0;maze.sz36= 0;maze.sz37= 1;maze.sz38= 1;maze.sz39= 0;maze.sz40= 0;maze.sz41= 1;maze.sz42= 0;maze.sz43= 0;maze.sz44= 0;maze.sz45= 1;maze.

10、sz46= 1;maze.sz47= 1;maze.sz48= 1;maze.sz49= 0;maze.sz50= 0;maze.sz51= 1;maze.sz52= 1;maze.sz53= 1;maze.sz54= 0;maze.sz55= 1;maze.sz56= 1;maze.sz57= 0;maze.sz58= 1;maze.sz59= 0;maze.sz60= 0;maze.sz61= 1;maze.sz62= 0;maze.sz63= 1;maze.sz64= 1;maze.sz65= 1;maze.sz66= 0;maze.sz67= 1;maze.sz68= 1;maze.s

11、z69= 0;maze.sz70= 0;maze.sz71= 1;maze.sz72= 0;maze.sz73= 0;maze.sz74= 0;maze.sz75= 1;maze.sz76= 0;maze.sz77= 0;maze.sz78= 1;maze.sz79= 0;maze.sz80= 0;maze.sz81= 0;maze.sz82= 1;maze.sz83= 1;maze.sz84= 1;maze.sz85= 1;maze.sz86= 1;maze.sz87= 1;maze.sz88= 1;maze.sz89= 0;maze.sz90= 0;maze.sz91= 0;maze.sz

12、92= 0;maze.sz93= 0;maze.sz94= 0;maze.sz95= 0;maze.sz96= 0;maze.sz97= 0;maze.sz98= 0;maze.sz99= 0;int i,j,sum;for (i = 0; i 10; i+) for (j = 0; j 10; j+)printf(%4d,maze.szij);sum+;if(sum%10=0)printf(n);printf(n);printf(-请输入1求解路径图:);int a;scanf(%d,&a);if(a=1)zuobiao rukou,chukou;rukou.r=1;rukou.c=1;chukou.r=8;chukou.c=8;mazePath(maze,rukou,chukou);printf(n);printf(-图解如下所示:（说明：0表示墙；1表示可以通过；4表示走不通；9表示所走的路径）n);for (i = 0; i 10; i+) for (j = 0; j 10; j+)printf(%4d,maze.szij);sum+;if(sum%10=0)printf(n);