穷举法求迷宫--栈的应用.doc

/穷举算法2012.8.24#include #include #include#define M 15 #define N 15 /*构造几个结构体模型*/构建入口和出口的标志 结构体typedef struct mark int x; int y; Mark; /构建链栈元素的 结构体typedef struct element int x; /行 int y;/列 int d; /d下一步的方向 Element; /构造链栈一般节点 结构体typedef struct lStack Element elem; struct lStack *next; *PLStack, LStack; /链栈栈顶、栈底指针结构体typedef struct s_head PLStack top; PLStack base; *PS_Head,S_Head;/*栈相关函数*/构造空栈 void InitStack(PS_Head PS) PS-top = (PLStack)malloc(sizeof( LStack);/链栈头，无实际用处，主要是便于操作 if(PS-top = NULL) printf(内存分配失败！n); exit(-1); else PS-base = PS-top; PS-base-next = NULL; return ;/判断栈是否为空int StackEmpty(PS_Head PS) if(PS-top = PS-base) return 1; else return 0; /元素入栈void Push(PS_Head PS, Element *E) PLStack p; p = (PLStack)malloc(sizeof(LStack); if(p = NULL) printf(内存分配失败！n); exit(-1); else p-elem = *E; /参见结构体赋值的语法规则 p-next = PS-top; PS-top = p; return; /栈顶元素出栈 void Pop(PS_Head PS, Element *E) PLStack p; if(!StackEmpty(PS) *E = PS-top-elem; p = PS-top; PS-top = PS-top-next; /栈顶下移 free(p); return; else return ; /*求迷宫路径函数*/void MazePath(struct mark start, struct mark end, int mazeMN, int diradd42) int x,y,d;/几个临时变量int a,b; /两个临时变量Element elem,e; /定义两个链栈元素类型变量S_Head S1,S2;/创建一个保存链栈头的变量InitStack(&S1); /用来作为迷宫求解工具InitStack(&S2); /用来保存成功求解后的路径。 /*最开始的一步就是，指定迷宫的某节点为入口，对其进行重新赋值，使其标记为已经走过*/mazestart.xstart.y = 2; /*对链栈元素类型变量赋值，这个值为非零节点的横纵坐标和方向*/elem.x = start.x; elem.y = start.y; elem.d = -1; /最原始状态-1，为什么不直接赋值为0，原因是与工作状态0，1，2，3和结束状态886相区别，逻辑上更清晰 /*变量已经赋好值，因此可以进行原始入栈操作*/ Push(&S1, &elem); while(!StackEmpty(&S1) /栈不为空 有路径可走 Pop(&S1,&elem); x = elem.x; y = elem.y; d = elem.d+1; /启动工作状态，下一个方向 while(d(%d,%d,%d), e.x, e.y, e.d); return; /结束函数 if(mazeab = 0) /找到可以前进的非出口的点 mazeab = 2; /标记走过此点 ，保存到迷宫数组里elem.x = x; /获取被标记点之前那个点的相关信息elem.y = y; elem.d = d; Push(&S1, &elem); /被标记点之前的那个点坐标信息入栈 x = a; /被标记点的坐标信息赋给x和yy = b; d = -1; /最原始状态-1，为什么不直接赋值为0，原因是与工作状态0，1，2，3相区别 d+; /工作状态 printf(没有找到可以走出此迷宫的路径n); /建立迷宫函数/*实际上是建立一个二维数组，并对二维数组赋值为1或0. 这个数组由用户自己自由的赋值 0代表通路，1代表墙*/void initmaze(int mazeMN) /M和N事先已经声明好了 int i,j; /循环计数变量int m,n; /迷宫行,列 printf(请输入迷宫的行数 m=); scanf(%d,&m); printf(请输入迷宫的列数 n=); scanf(%d,&n); printf(n请输入迷宫的各行各列:n用空格隔开,0代表路,1代表墙n,m,n); /建立内部房间for(i=1;i=m;i+) for(j=1;j=n;j+) scanf(%d,&mazeij); printf(你建立的迷宫为(最外圈为墙).n); /加一圈围墙 for(i=0; i=m+1; i+) mazei0 = 1; mazein+1 = 1; for(j=0; j=n+1; j+) maze0j = 1; mazem+1j = 1; /输出迷宫 for(i=0; i=m+1; i+) for(j=0; j=n+1; j+) printf(%d ,mazeij); printf(n); /主函数void main() int stoMN; /储存迷宫状态的二维数组Mark start, end; /start,end入口和出口的坐标变量名int add42=0,1,1,0,0,-1,-1,0;/二维数组，行增量和列增量 方向依次为东西南北 initmaze(sto);/建立迷宫 ，sto在本函数执行后仍然存在printf(输入入口的横坐标,纵坐标逗号隔开n); scanf(%d,%d,&sta