数据结构编程迷宫(用栈的方法解决).doc

#include #define M 4/定义行数为4#define N 4/定义列数为4#define MaxSize 100 /定义栈最多元素个数int mgM+2N+2= /迷宫的四周要加上均为1的外框 1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,0,0,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1;struct int i; /当前方块的行号int j; /当前方块的列号int di; /di是下一个可走相邻方位的方位号 StackMaxSize,PathMaxSize;/定义栈和存放最短路径的数组int top=-1;/初始化栈顶int count=1;/路径数计数int min=MaxSize;/最短路径长度计数void mgpath()/求解路径为:(1,1)-(M,N)int i,j,k,di,find;top+;/初始方块进入栈口Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;while (top-1)/栈不空时循环i=Stacktop.i;j=Stacktop.j;di=Stacktop.di; /取栈顶方块if (i=M & j=N)/找到了出口,输出路径 printf(%4d:,count+);for (k=0;k=top;k+)printf(%d,%d),Stackk.i,Stackk.j);if (k+1)%5=0) printf(n);/每输出5个方块后换一行printf(n);if (top+1min) /找最短路径for (k=0;k=top;k+)Pathk=Stackk;min=top+1;mgStacktop.iStacktop.j=0;/让该位置变为其他路径可走方块top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;find=0;while (di4 & find=0)/找(i,j)方块下一个可走方块di+;switch(di)case 0:i=Stacktop.i-1;j=Stacktop.j;break;case 1:i=Stacktop.i;j=Stacktop.j+1;break;case 2:i=Stacktop.i+1;j=Stacktop.j;break;case 3:i=Stacktop.i,j=Stacktop.j-1;break;if (mgij=0) find=1;if (find=1) /找到了一个可走的相邻方块Stacktop.di=di;/修改原栈顶元素的di值top+; /将可走相邻方块进栈Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;mgij=-1;/避免重复走到该方块，将其置为-1else /没有相邻方块可走,则退栈mgStacktop.iStacktop.j=0; /让该位置变为其他路径可走方块top-;printf(最短路径如下:n);printf(长度:%dn,min);printf(路径:);for (k=0;kmin;k+)printf(%d,%d),Pathk.i,Pathk.j);if (k+1)%5=0)