迷宫与栈问题

迷宫与栈问题 目录 一、 系统开发的背景 .................................................... 1 二、 系统分析与设计 .................................................... 1 (一) 系统功能要求 ...................................................... 1 (二) 系统模块结构设计 .................................................. 1 三、 系统的设计与实现 .................................................. 2 (一) 栈的基本操作 ...................................................... 2 (二) 迷宫算法:PATH(SEQSTACK *S) ......................................... 4 (三) 迷宫路径输出算法:PRINTPATH(SEQSTACK *S) ............................. 6 (四) 主函数 ............................................................ 7 四、 系统测试 .......................................................... 8 (一) 测试主函数迷宫的输入输出 .......................................... 8 二) 测试迷宫函数和迷宫路径输出函数 .................................... 8 ( .............................................................. 9 五、 总结 六、 附件(代码) ...................................................... 9 迷宫与栈问题 一、 系统开发的背景 迷宫问题是心理学中的一个经典问题，一直以来人们乐都此不彼的研究它。 同样利用栈的思想也可以解决迷宫问题。 二、 系统分析与设计 (一) 系统功能要求 以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出。其中:(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。 (二) 系统模块结构设计 通过对系统功能的分析，系统功能如图1所示。 迷宫与栈问题 栈主 迷迷 的函宫宫 数 基算路 本法 径 操输 作 出 1 图1 迷宫与栈问题系统功能图 通过上图的功能分析，把整个系统划分为4个模块: 1、栈的基本操作:该模块主要包括栈的初始化、栈空判别算法、入栈算法、出栈算法;主要通过函数SeqStack *Init_SeqStack()、Empty_SeqStack(SeqStack *s)、Push_SeqStack(SeqStack *s,DateType x)、pop_SeqStack(SeqStack *s,DateType *x)实现; 2、迷宫算法:该模块主要通过函数path(SeqStack *s)实现， 3、迷宫路径输出算法:该模块主要通过函数 printpath(SeqStack *s) 实现; 4、主函数:该模块主要是迷宫的输入、打印，以及对以上函数的调用。 三、 系统的设计与实现 (一) 栈的基本操作 分析:栈的初始化算法也可理解为置空栈算法:首先建立栈空间，然后初始化栈顶指针。利用if来判断是否申请到足够大的储存空间，然后返回空指针或栈空间地址;栈空判别算法:当栈顶指针指向栈底时，栈为空;入栈算法:入栈时，首先借助if语句判断栈是否满了，栈满时，不能入栈，返回错误代码0，相反，栈顶指针向上移动，将x置于新的栈顶，入栈成功返回成功代码1;出栈算法:出栈时，首先判断栈是否为空，借助于if语句，栈空不能出栈，返回错误代码0，相反，保存栈顶元素值，栈顶指针向下移动 ，栈顶元素存入*x，返回成功代码1;该模块如图2所示: 2 栈的基本操作 栈栈入出 的空栈栈 初判操操 始别作 作 算化 法 图2 栈的基本操作 该模块的具体代码如下所示: //栈的初始化算法 SeqStack *Init_SeqStack(){ SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack)); s->top=0; return s; } //栈空判别算法 int Empty_SeqStack(SeqStack *s){ if(s->top==0) //判断空栈 return 1; else return 0; } //入栈算法 int Push_SeqStack(SeqStack *s,DateType x){ if(s->top==Maxsize-1) //判断栈满 return 0; else{ s->top++; s->data[s->top]=x; return 1; } } //出栈算法 int pop_SeqStack(SeqStack *s,DateType *x){ if(Empty_SeqStack(s)) 3 return 0; else{ *x=s->data[s->top]; s->top--; return 1; } } (二) 迷宫算法:path(SeqStack *s) 分析:从迷宫入口出发，按照一定的顺序(在本程序中顺序依次为右、右下、下、左下、左、左上，上、右上)对周围的墙、路进行判断;若周围的位置都为1(即没有通路)，则沿原路返回前一点，换下一个方向继续试探，直到所有通路都试探到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走时，能正确返回前一点，以便继续从下一个方向向前试探，则需要用一个栈保存所能到达的没一点的下标及从该点前进的方向。栈是由行、列、方向组成的三元组。迷宫求解算法思想如下: (1) 栈初始化。 (2) 将入口坐标及到达该点的方向(设为-1)入栈。 (3) 伪代码入下: while(栈不空){ 栈顶元素>=(x,y,d) 出栈; 求下一个要试探的方向d++; while(还有剩余试探方向){ if(d方向可走){ (x,y,d)入栈; 求新点坐标(i,j); 将新点(i,j)切换为当先点(x,y); If((x,y)==(m,n)) 结束; else 重置d=0; 4 } else d++; }} 该模块的具体代码如下所示: //迷宫算法 int path(SeqStack *s) { DateType temp; int x,y,d,i,j; temp.x=1; temp.y=1; temp.d=-1; //初始化入口坐标及方向 Push_SeqStack(s,temp); while(!Empty_SeqStack(s)) { pop_SeqStack(s,&temp); x=temp.x; y=temp.y; d=temp.d+1; while(d<8) { i=x+move[d].x; j=y+move[d].y; if(maze[i][j]==0) //该点可达 { temp.x=x; temp.y=y; temp.d=d; //坐标及方向 Push_SeqStack(s,temp); // 坐标及方向入栈 x=i; y=j; maze[x][y]=-1; // 到达新点 if(x==m && y==n) return 1; //到出口，迷宫有路，成功返回1 else d=0; //重新初始化方向 } else d++; //改变方向 } } return 0; //迷宫无路，失败返回0 5 } (三) 迷宫路径输出算法:printpath(SeqStack *s) 分析:利用for循环输出栈中保存的路径。该算法的流程图如图3所 示: i=1 N itop Y {[s->data[i].x,s->data [i] s->data[i].d] .]y,s->data[i].d i++ 图3 迷宫路径输出流程图 该模块的具体代码如下所示: void printpath(SeqStack *s) { int i; for(i=1;i<=s->top;i++) {printf("{[%d,%d],%d}",s->data[i].x,s->data[i].y,s->data[i].d); if(i<=s->top) printf("-->"); if(i%3==0) printf("\n"); } printf("\n"); 6 } (四) 主函数 分析:迷宫的输入输出借助于for循环实现，为了迷宫算法查找方 便，用maze[m+2][m+2]来表示迷宫,在四周加上一圈“哨兵”即迷宫四周的 值全部为1。标识迷宫入口和出口即将maze[1][1]、maze[m][n]置为0。 该模块的具体代码如下所示: void main() { SeqStack *s; int i,j,k; printf("~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf(" 迷宫与栈问题 \n"); printf("~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("请按行输入迷宫(%d*%d):\n",m,n); printf("提示:0表示通路，1表示阻碍\n"); for(i=1;i<=m;i++) for(j=1;j<=n;j++) { scanf("%ld",&maze[i][j]); } maze[1][1]=0; maze[m][n]=0; for(i=0;i #include #define m 10 //迷宫的行 #define n 10 //迷宫的列 //顺序栈的类型描述 #define Maxsize 50 9 int maze[m+2][n+2]; //Move数组定义 typedef struct{ int x,y; }item; item move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; //栈中元素的设计 typedef struct{ int x,y,d; }DateType; //横坐标及方向 typedef struct{ DateType data[Maxsize]; int top; }SeqStack; SeqStack *s;//定义一个指向顺序栈的指针变量 //栈的初始化算法 SeqStack *Init_SeqStack(){ SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack)); s->top=0; return s; } //栈空判别算法 int Empty_SeqStack(SeqStack *s){ if(s->top==0) //判断空栈 return 1; else return 0; } //入栈算法 int Push_SeqStack(SeqStack *s,DateType x){ if(s->top==Maxsize-1) //判断栈满 return 0; else{ s->top++; s->data[s->top]=x; return 1; } } //出栈算法 int pop_SeqStack(SeqStack *s,DateType *x){ if(Empty_SeqStack(s)) return 0; else{ 10 *x=s->data[s->top]; s->top--; return 1; } } //迷宫算法 int path(SeqStack *s) { DateType temp; int x,y,d,i,j; temp.x=1; temp.y=1; temp.d=-1; //初始化入口坐标及方向 Push_SeqStack(s,temp); while(!Empty_SeqStack(s)) { pop_SeqStack(s,&temp); x=temp.x; y=temp.y; d=temp.d+1; while(d<8) { i=x+move[d].x; j=y+move[d].y; if(maze[i][j]==0) //该点可达 { temp.x=x; temp.y=y; temp.d=d; //坐标及方向 Push_SeqStack(s,temp); // 坐标及方向入栈 x=i; y=j; maze[x][y]=-1; // 到达新点 if(x==m && y==n) return 1; //到出口，迷宫有路，成功返回1 else d=0; //重新初始化方向 } else d++; //改变方向 } } return 0; //迷宫无路，失败返回0 } 11 //打印迷宫路径函数 void printpath(SeqStack *s) { int i; for(i=1;i<=s->top;i++) { printf("{[%d,%d],%d}",s->data[i].x,s->data[i].y,s->data[i].d); if(i<=s->top) printf("-->"); if(i%3==0) printf("\n"); } printf("\n"); } void main() { SeqStack *s; int i,j,k; printf("~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf(" 迷宫与栈问题 \n"); printf("~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("请按行输入迷宫(%d*%d):\n",m,n); printf("提示:0表示通路，1表示阻碍\n"); for(i=1;i<=m;i++) for(j=1;j<=n;j++) { scanf("%ld",&maze[i][j]); } maze[1][1]=0; maze[m][n]=0; for(i=0;i