版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、利用栈实现迷宫的求解一、要解决的问题:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍,设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。二:算法基本思想描述:用一个字符类型的二维数组表示迷宫,数组中每个元素取值“0”(表示通路)或“1”(表示墙壁)。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”, 表示迷宫的边界;第1行第1列元素和第m行第n列元素置成“0”, 表示迷宫的入口和出口 走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东、南、西、北4个方向顺序试探下一个位置;用二维数组move记录4个方向上行下标增量和列下标
2、增量,则沿第i个方向前进一步,可能到达的新位置坐标可利用move数组确定:Px=x+movei0Py=y+movei1如果某方向可以通过,并且不曾到达,则前进一步,在新位置上继续进行搜索; 如果4个方向都走不通或曾经到达过,则退回一步,在原来的位置上继续试探下一位置。三:设计:1:数据结构的设计:(1)定义三元数组元素的结构typedef struct MazeDirectint Dx; /行标int Dy; /列标int direct; /走到下一个坐标点的方向MazeDirect;(2)定义链表节点的结构组成typedef struct LinkNodeelemtype data; /数据
3、域struct LinkNode *next; /指针域LinkNode;(3)定义链栈的头指针typedef structLinkNode *top; /栈的头指针LinkStack;(4)移动数组结构的定义typedef structint x,y;/x为行标,y为列标Direction_increm;2:算法的设计:【1】迷宫图的设计设迷宫为m行n列,利用mazemn来表示一个迷宫,mazeij=0或1; 其中:0表示通路,1表示不通,当从某点向下试探时,中间点有4个方向可以试探,(见图)而四个角点有2个方向,其它边缘点有3个方向,为使问题简单化我们用mazem+2n+2来表示迷宫,而迷
4、宫的四周的值全部为1。这样做使问题简单了,每个点的试探方向全部为4,不用再判断当前点的试探方向有几个,同时与迷宫周围是墙壁这一实际问题相一致。假设有6行8列的迷宫,如下图为maze810构造的迷宫【2】试探方向的设计:在上述表示迷宫的情况下,每个点有4个方向去试探,如当前点的坐标(x , y),与其相邻的4个点的坐标都可根据与该点的相邻方位而得到,如图2所示。因为出口在(m,n),因此试探顺序规定为:从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题,方便的求出新点的坐标,将从正东开始沿顺时针进行的这4个方向(用0,1,2,3表示东、南、西、北)的坐标增量放在一个结构数组move
5、4 中,在move 数组中,每个元素有两个域组成,x:横坐标增量,y:纵坐标增量。Move数组如图3所示。move数组定义如下:typedef struct int x ; /行 int y ; /列 item ; item move4 ;这样对move的设计会很方便地求出从某点 (x,y) 按某一方向 v (0v3) 到达的新点(i,j)的坐标:i =x + movev.x ,j = y + movev.y 。(x-1,y)x y,y-1) (x(x,y)(x,y+1)1 2 3(x+1,y)图2 与点(x,y)相邻的4个点及坐标图3 增量数组move【3】栈的设计:当到达了某点而无路可走时
6、需返回前一点,再从前一点开始向下一个方向继续试探。因此,压入栈中的不仅是顺序到达的各点的坐标,而且还要有从前一点到达本点的方向,即每走一步栈中记下的内容为(行,列,来的方向)。对于图1所示迷宫,依次入栈为:栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的,对于图3迷宫,走的路线为:(1,1,0)(2,1,1)(2,2,0)(3,2,1)(3,3,0)(3,4,0)(下脚标表示方向),当无路可走,则应回溯,对应的操作是出栈,沿下一个方向即方向继续试探。栈中元素是一个由行、列、方向组成的三元组,栈元素的设计如下: typedef structint x , y , d ;/* 横纵坐标
7、及方向*/ datatype ;栈的定义为: SeqStack s ;top 【4】. 如何防止重复到达某点,以避免发生死循环:一种方法是另外设置一个标志数组markmn,它的所有元素都初始化为0,一旦到达了某一点 ( i , j )之后,使mark i j 置1,下次再试探这个位置时就不能再走了。另一种方法是当到达某点(i , j)后使maze i j 置 -1,以便区别未到达过的点,同样也能起到防止走重复点的目的,此处采用后一方法,算法结束前可恢复原迷宫。四:详细设计;1. 算法的设计思想及流程图(1)主要函数的功能说明void ini_stack(LinkStack *)/*初始化链栈*
8、/int empty_Stack(LinkStack *)/*判断是否为空栈*/void push_Stack(LinkStack *,elemtype)/*入栈*/elemtype pop_Stack(LinkStack *) /*出栈*/int size_stack(LinkStack ) /*栈的规模大小*/(2)算法描述【伪代码描述】迷宫求解算法思想如下:(1) 栈初始化;(2) 将入口点坐标及到达该点的方向(设为-1)入栈(3) while (栈不空) 栈顶元素(x , y , d)出栈 ;求出下一个要试探的方向d+ ;/当遇到死路的时候就出栈,寻找原来点的下一个方向while (还
9、有剩余试探方向时) if (d方向可走)则 (x , y , d)入栈 ;求新点坐标 (i, j ) ;将新点(i , j)切换为当前点(x , y) ;if ( (x ,)= =(,n) ) 结束 ;else 重置 d=0 ;else d+ ;五:源程序清单;#include #include int m,n;typedef struct MazeDirectint Dx;int Dy;int direct;MazeDirect; /*定义三元数组元素的结构*/typedef MazeDirect elemtype;typedef struct LinkNodeelemtype data;s
10、truct LinkNode *next; /*定义链表节点的结构组成*/ LinkNode;typedef structLinkNode *top; /*定义链栈的头指针*/LinkStack;void ini_stack(LinkStack *stack)/*初始化链栈*/stack-top=NULL;int empty_Stack(LinkStack *stack)/*判断是否为空栈*/ if (stack-top!=NULL)return 0;elsereturn 1;void push_Stack(LinkStack *stack,elemtype x)/*入栈*/ LinkNode
11、 *s;s=(LinkNode *)malloc(sizeof(LinkNode);s-data=x;s-next=stack-top;stack-top=s;elemtype pop_Stack(LinkStack *stack) /*出栈*/ elemtype x;LinkNode *p;elemtype tmpNull=0,0,0;if (stack-top=NULL)return tmpNull;/(NULL)elsex=stack-top-data;p=stack-top;stack-top=p-next;free(p);return (x);int size_stack(LinkS
12、tack stack) /*栈的规模大小*/ int i;LinkNode *Numb;i=0;Numb=stack.top;while(Numb!=NULL)Numb=Numb-next;i+;return i;int w,t,maze100100;typedef structint x,y;/x为行标,y为列标Direction_increm;Direction_increm MazeMove4=0,1,1,0,0,-1,-1,0;typedef MazeDirect TmpType;int Maze_path()MazeDirect tmp,path;LinkStack s;int x,
13、y,Px,Py,d,flag=0;ini_stack(&s);tmp.Dx=1;tmp.Dy=1;tmp.direct=-1;push_Stack(&s,tmp);while (!empty_Stack(&s)tmp=pop_Stack(&s);x=tmp.Dx;y=tmp.Dy;d=tmp.direct+1;/遇到死路的时候,回溯(通过出栈完成)while (d4)Px=x+MazeMoved.x;Py=y+MazeMoved.y;if (mazePxPy=0)tmp.Dx=x;tmp.Dy=y;tmp.direct=d;push_Stack(&s,tmp);x=Px;y=Py;mazexy=-1;/*标记,防止重复点*/if(x=m&y=n)flag=1;printf(n到达迷宫出口:%d,%d,x,y);printf(n经过的节点有:%d个,size_stack(s);while(!empty_Stack(&s)path=pop_Stack(&s);printf(n(%d,%d,%d),path.Dx,path.Dy,path.direct); break;else d=0;/结束ifelse d+;/结束内部while/结束
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 大班心理健康课程设计
- 大班大玩家社会课程设计
- 2024秋六年级英语上册 Unit 1 How can I get there Part A 第1课时教案 人教PEP
- 北京市2024-2025学年高中英语 Unit 3 Life in the future Period 4 Listening and speaking教学设计 新人教版必修5
- 浅议幼儿园美工区的活动设计和实现 学前教育专业
- 宝玉挨打教学设计 苏教版
- 1《场景歌》教学设计-2024-2025学年统编版语文二年级上册
- 2025历史步步高大一轮复习讲义板块一 第五单元 第12讲 明至清中叶的经济与文化
- 唐宋散文选读第五单元教学设计 粤教版
- 山西省三区八校2025届高三第三学期半期联考物理试题含解析
- (常用)扣件式钢管脚手架检查表
- 统编版初中语文八年级下册第四单元:超级演说家
- 物业管理居间协议书
- 消防管网维护管理保养方案
- 九一八防空应急疏散
- 凉拌黄瓜课件
- 中华民族共同体概论课件专家版8第八讲 共奉中国与中华民族聚力发展
- 2022年4月自考00534外国文学作品选试题及答案含解析
- 《Photoshop图像处理》课件-任务五:滤镜特效技巧的学习
- 2024家庭教育需求趋势洞察报告-第一财经-2024
- 卡丁车项目策划
评论
0/150
提交评论