迷宫与栈问题

1、目录目录一、一、 系统开发的背景系统开发的背景.1 1二、二、 系统分析与设计系统分析与设计.1 1( (一一) )系统功能要求系统功能要求.1( (二二) )系统模块结构设计系统模块结构设计.1三、三、 系统的设计与实现系统的设计与实现.2 2( (一一) )栈的基本操作栈的基本操作.2( (二二) )迷宫算法：迷宫算法：PATHPATH(S(SEQEQS STACKTACK * *S S) ) .4( (三三) )迷宫路径输出算法：迷宫路径输出算法：PRINTPATHPRINTPATH(S(SEQEQS STACKTACK * *S S) ) .6( (四四) )主函数主函数.7四、四、

2、系统测试系统测试.8 8( (一一) )测试主函数迷宫的输入输出测试主函数迷宫的输入输出.8( (二二) )测试迷宫函数和迷宫路径输出函数测试迷宫函数和迷宫路径输出函数.8五、五、 总结总结.9 9六、六、 附件（代码）附件（代码）.9 91迷宫与栈问题迷宫与栈问题一、一、 系统开发的系统开发的背景背景迷宫问题是心理学中的一个经典问题，一直以来人们乐都此不彼的研究它。 同样利用栈的思想也可以解决迷宫问题。二、二、 系统分析与设计系统分析与设计( (一一) )系统功能要求系统功能要求以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出

3、口的通路，或得出没有通路的结论。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。( (二二) )系统模块结构设计系统模块结构设计通过对系统功能的分析，系统功能如图 1 所示。迷宫与栈问题迷宫与栈问题栈栈的的基基本本操操作作 迷迷宫宫算算法法主主 函函数数迷迷宫宫路路径径输输出出2图 1 迷宫与栈问题系统功能图通过上图的功能分析，把整个系统划分为 4 个模块：1、栈的基本操作：该模块主要包括栈的初始化、栈空判别算法、入栈算法、出栈算法；主要通过函数 SeqStack

4、 *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、主函数：该模块主要是迷宫的输入、打印，以及对以上函数的调用。三、三、 系统的设计系统的设计与实现与实现( (一一) )栈的基本操作栈的基本操作分析：栈的初始化算法也可理解为置空栈算法

5、：首先建立栈空间，然后初始化栈顶指针。利用 if 来判断是否申请到足够大的储存空间，然后返回空指针或栈空间地址；栈空判别算法：当栈顶指针指向栈底时，栈为空；入栈算法：入栈时，首先借助 if 语句判断栈是否满了，栈满时，不能入栈，返回错误代码 0，相反，栈顶指针向上移动，将 x 置于新的栈顶，入栈成功返回成功代码 1；出栈算法：出栈时，首先判断栈是否为空，借助于 if 语句，栈空不能出栈，返回错误代码 0，相反，保存栈顶元素值，栈顶指针向下移动 ，栈顶元素存入*x，返回成功代码 1；该模块如图 2 所示：3 图 2 栈的基本操作 该模块的具体代码如下所示：/栈的初始化算法SeqStack *In

6、it_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;elses-top+;s-datas-top=x;return 1;/出栈算法int pop_SeqStack(SeqSta

7、ck *s,DateType *x)if(Empty_SeqStack(s)栈的基本操作栈的基本操作栈栈的的初初始始化化栈栈空空判判别别算算法法入入栈栈操操作作出出栈栈操操作作4return 0;else*x=s-datas-top;s-top-;return 1;( (二二) )迷宫算法：迷宫算法：path(SeqStackpath(SeqStack *s)*s)分析：从迷宫入口出发，按照一定的顺序（在本程序中顺序依次为右、右下、下、左下、左、左上，上、右上）对周围的墙、路进行判断；若周围的位置都为 1（即没有通路） ，则沿原路返回前一点，换下一个方向继续试探，直到所有通路都试探到，或找到一

8、条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走时，能正确返回前一点，以便继续从下一个方向向前试探，则需要用一个栈保存所能到达的没一点的下标及从该点前进的方向。栈是由行、列、方向组成的三元组。迷宫求解算法思想如下：（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)） 结束； e

9、lse 重置 d=0；5else 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(d8)i=x+moved.x;j=y+moved.y;if(mazeij=0) /该点可达temp.x=x; temp.y=y; t

10、emp.d=d; /坐标及方向Push_SeqStack(s,temp); / 坐标及方向入栈x=i;y=j;mazexy=-1; / 到达新点if(x=m & y=n)return 1; /到出口，迷宫有路，成功返回 1elsed=0; /重新初始化方向elsed+; /改变方向return 0; /迷宫无路，失败返回 06( (三三) )迷宫路径输出算法：迷宫路径输出算法：printpath(SeqStackprintpath(SeqStack *s)*s)分析：利用 for 循环输出栈中保存的路径。该算法的流程图如图 3 所示：图 3 迷宫路径输出流程图该模块的具体代码如下所示：

11、void printpath(SeqStack *s)int i;for(i=1;itop;i+)printf(%d,%d,%d,s-datai.x,s-datai.y,s-datai.d);if(itop)printf(-);if(i%3=0)printf(n);printf(n);itopi=1s-datai.x,s-datai s-datai.d.y,s-datai.di+NY7( (四四) )主函数主函数 分析：迷宫的输入输出借助于 for 循环实现，为了迷宫算法查找方便，用 mazem+2m+2来表示迷宫,在四周加上一圈“哨兵”即迷宫四周的值全部为 1。标识迷宫入口和出口即将 maz

12、e11、mazemn置为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,&mazeij);maze11=0; mazemn=0;for(i=0;im+2;i+)mazei0=1;mazein+1=1; for(j=0;jn+2;j+) maze0j=1; mazem+1j=

13、1; printf(n 输入的迷宫如图所示n); for(i=0;im+2;i+) for(j=0;jn+2;j+) printf(%2d,mazeij);8 printf(n); s=Init_SeqStack(); k=path(s); if(k=1) printf(n 输出路径如下：n); printpath(s); else printf(失败！nn); getchar();四、四、 系统测试系统测试( (一一) )测试主函数迷宫的输入输出测试主函数迷宫的输入输出图 4 迷宫的输入及打印( (二二) )测试迷宫函数和迷宫路径输出函数测试迷宫函数和迷宫路径输出函数9图 5 迷宫路径的输出

14、五、五、 总结总结系统完成了迷宫的输入输出及查找路径并输出了路径的功能。系统不能输出迷宫所有的路径。统过这段时间的课程设计，我对计算机的应用，数据结构的作用以及 C 语言的使用都有了更深的了解。尤其是 C 语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们。在设计此程序时，刚开始感到比较迷茫，然后一步步分析，试着写出基本的算法，思路渐渐清晰，最后完成程序。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。这次课程设计让我更加深入了解很多方面的知识，如顺序结构的栈类型及其基本操作，数组的运用等等。在实际的上机操作过程中，不仅是让我们了解数

15、据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次课程设计可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。六、六、 附件（代码）附件（代码）#include#include#define m 10 /迷宫的行#define n 10 /迷宫的列/顺序栈的类型描述#define Maxsize 5010int mazem+2n+2;/Move 数组定义typedef structint x,y;item;item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;/栈中元素的设计typedef structint

16、x,y,d;DateType; /横坐标及方向typedef structDateType dataMaxsize;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_SeqSta

17、ck(SeqStack *s,DateType x)if(s-top=Maxsize-1) /判断栈满return 0;elses-top+;s-datas-top=x;return 1;/出栈算法int pop_SeqStack(SeqStack *s,DateType *x)if(Empty_SeqStack(s)return 0;else11*x=s-datas-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; /初始化入口坐标及方向

18、Push_SeqStack(s,temp);while(!Empty_SeqStack(s)pop_SeqStack(s,&temp);x=temp.x;y=temp.y;d=temp.d+1;while(d8)i=x+moved.x;j=y+moved.y;if(mazeij=0) /该点可达temp.x=x; temp.y=y; temp.d=d; /坐标及方向Push_SeqStack(s,temp); / 坐标及方向入栈x=i;y=j;mazexy=-1; / 到达新点if(x=m & y=n)return 1; /到出口，迷宫有路，成功返回 1elsed=0; /重新初始化方向elsed+; /改变方向return 0; /迷宫无路，失败返回 012/打印迷宫路径函数void