《用栈寻找迷宫路径.docx》由会员分享，可在线阅读，更多相关《用栈寻找迷宫路径.docx（5页珍藏版）》请在金锄头文库上搜索。
1、用栈寻找迷宫路径李良益 2013地球信息科学与技术2015 5.121. 需求分析因为迷宫的特点，走的通或走不通，可以用1和0表示，所以在计算机可以用抽象方法表示迷宫，用如图所示的01图表示迷宫。图中1为通道，0为墙，所求通道为简单通道，即所求路径上不能出现同一通道块。迷宫文件以“maze.txt”的文件名读取。文件内容如下：0 0 0 0 0 0 0 0 0 00 1 1 0 1 1 1 0 1 00 1 1 0 1 1 1 0 1 00 1 1 1 1 0 0 1 1 00 1 0 0 0 1 1 1 1 00 1 1 1 0 1 1 1 1 00 1 0 1 1 1 0 1 1 00 1
2、 0 0 0 1 0 0 1 00 0 1 1 1 1 1 1 1 00 0 0 0 0 0 0 0 0 0在计算机中迷宫0以爱心符号表示，1则用空白，再输入两个坐标，表示起点和终点，横纵坐标从0开始。若坐标不在迷宫之内，则要求重新输入。最后输出带有有路径的迷宫。2. 主体设计 先考虑程序主要流程：打开文件“maze.txt”,并读取到二维数组且备份，初始化栈，寻找路径并存入栈中，提取路径，打印备份。程序设计主要有3个要点，即定义位置，栈与栈的元素1）位置的定义typedef structint x;int y;postype;2) 栈的定义typedef structint ord;post
3、ype seat;int di;SElemType;c)栈元素定义typedef structSElemType *base;SElemType *top;int stacksize;SqStack;将它们都定义为全局变量：SqStack S = 0, 0, 0 ;使用的栈SElemType e = 0, 0, 0 , 0 ;当前位置int maze1010;迷宫postype start = 0, 0 , end = 0, 0 ;开始和结束位置子函数包括四个对栈的操作：Status InitStack()；初始化栈Status GetTop()； 得到栈顶元素Status Push()；元素
4、入栈Status Pop()；元素出栈两个寻找相关路径的操作i：int next()；修改当先位置为下一个前进位置或者是要测试的位置Status FindPath()；主函数调用，找到路径存入栈中3. 详细设计假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块的位置”则求迷宫中一条路径的算法的基本思想是：若当前位置可通，则纳入“当前路径”，并继续朝下一位置探索，即切换下一位置为当前位置，如此反复，直到达到出口；若当前位置不可通，则应顺着来向退向前一通道块，然后朝着来向之外的其他方向探索；若该通道块的四周4个方块均不可通，则应从当前路径删除该通道块。所谓下一位置指的是当前位置四周四个方
5、向，假设栈S记录当前路径，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为入栈，“从当前路径上删除前一通道块”的操作即为出栈。求一条路径的算法可简单描述如下：do若当前位置可通，则当前位置插入栈顶；若该位置是出口，则结束；否则，切换当前位置的东临块为新的当前位置；否则，若栈不空且栈顶位置尚有其他位置可以搜索， 则设定新的当前位置为沿顺时针方向找到的栈顶位置的下一临块；若栈不空，但栈顶位置四周均不通，则删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；while（栈不空）；在此，尚需说明的一点是，所谓当前位置可通，指的是未经走到过的通
6、道块，即要求该通道块不仅是通道块，而且既不在当前路径上（否则所求路径不是简单路径），而且不是曾经纳入过的通道块，（否则只能在死胡同里转圈）主要功能函数：Status FindPath()int n=1;doif (mazee.seat.xe.seat.y = 1)Push();mazee.seat.xe.seat.y = 0;if (e.seat.x = end.x&e.seat.y = end.y)return 0;elsee.di = 0;next(e);elseif (S.top != S.base&e.di 4)next(e);if (S.top != S.base&e.di = 4)
7、mazee.seat.xe.seat.y = 0;Pop(); Pop();mazee.seat.xe.seat.y = 1;while(S.base!=S.top);return 0;修改当前一通道块为下一通道块的函数：int next()if (e.di = 0) e.di+; e.seat.y+; return 0; if (e.di = 1) e.di+; e.seat.x+; e.seat.y-; return 0; if (e.di = 2) e.di+; e.seat.y-; e.seat.x-; return 0; if (e.di = 3) e.seat.x-; e.seat
8、.y+; if (mazee.seat.xe.seat.y = 0)e.di+;return 0; 4. 调试分析（1） 出现的错误问题有如下，当程序中路径设计不够完善时，没考虑仔细，有点代码忘记写时，会出现错误，比如每个坐标路径的判断，需要进行一步一步的调试，观察每一个变量的值的变化情况。调试完成，进行实验验证，看是否是最佳路径，不然继续调试。张老师教导当遇到错误时，进行一步一步调试是很有效果的，这样避免更多错误的出现和最后不知道错误在哪里。（2） 算法的时空分析空间复杂度为一个栈的空间，O(n)时间复杂度为遍历所有的路径，O(n)5. 用户使用说明运行程序，等待结果。6. 测试结果正确。7. 附录maze.c maze.txt
