2022年栈的应用-迷宫问题-数据结构-源代码推荐 .pdf

《2022年栈的应用-迷宫问题-数据结构-源代码推荐 .pdf》由会员分享，可在线阅读，更多相关《2022年栈的应用-迷宫问题-数据结构-源代码推荐 .pdf（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; int i

2、nitStack(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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - if(s-

3、top - s-base = s-size) s-base = (lujing *)realloc(s-base, (s-size+INCREMENT)*sizeof(lujing); if(!s-base) 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-ba

4、se = s-top) return 1; else return 0; int pass( Maze maze,zuobiao dqzb) if (maze.szdqzb.rdqzb.c=1) return 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

5、dqzb, int Dir) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - zuobiao xzb; switch (Dir) case 1: xzb.r=dqzb.r; xzb.c=dqzb.c+1; break; case 2: xzb.r=dqzb.r+1; xzb.c=dqzb.c; break; case 3: xzb.r=dqzb.r; xzb.c=dqzb.c-1; break; case 4: xzb.r=dq

6、zb.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 = 1; / 探索第一步do if (pass(maze,dqzb) / 当前位置可通过，即是未曾走到过的通道块footPrint(maze,dqzb); / 留下足迹

7、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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - -

8、- - - - pop(s,&e); 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 表示可以通过）); print

9、f(n); Maze maze; /声明 maze maze.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

10、;maze.sz21= 1;maze.sz22= 1;maze.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=

11、0;maze.sz44= 0;maze.sz45= 1;maze.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=

12、 0;maze.sz67= 1;maze.sz68= 1;maze.sz69= 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

13、= 0; maze.sz90= 0;maze.sz91= 0;maze.sz92= 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+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - for (j = 0; j 10; j+)

14、 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -