C语言课件 第21 22章

1、第21章 迷宫求解 p 问题描述 p 问题分析及实现 p 开发过程常见问题及解决 第21章 迷宫求解 问题描述 p 问题分析及实现 p 开发过程常见问题及解决 第21章 迷宫求解 问题描述 问题分析及实现 p 开发过程常见问题及解决 第21章 迷宫求解 问题描述 问题分析及实现 开发过程常见问题及解决 迷宫求解 c语言的功能是强大的，可以实现很多有意 义的问题的求解。比如算法领域的经典问 题迷宫求解。在一个mn的迷宫中， 给定一个入口，一个出口，如何从入口走到 出口？本章就实现了这一算法。 21.1 问题描述 以一个mn的长方阵表示迷宫，0和1分别 表示迷宫中的通路和障碍。对任意设定的迷 宫，

2、求出一条从入口到出口的通路并输出所 经过的坐标点，或得出没有通路的结论。 21.2 问题分析及实现 21.2.1 问题分析 21.2.2 问题实现 21.2.3 程序运行 21.2 问题分析及实现 由问题描述可知，我们要实现的是打印从坐 标a，走到坐标b，要绕过路障走一条路径 出来。简单举例：从左向右走动，中间有障 碍物，此时，需要向上再向右，或向下再向 右，只有绕过左与右之间的障碍物，才可以 顺利从左走至右，以下将仔细地分析问题并 实现算法。 21.2.1 问题分析 我们的将要开发的程序，就是设置一个 迷宫（mn）,并设置入口点，出口点， 从出口点走向入口点，将途经的坐标记 录到“栈”底，在

3、找到路径时，将弹出 栈顶元素，此时，就是所有途经的坐标 点。 21.2.2 问题实现 本小节就来通过编程求解迷宫问题，实现的 代码如下。 1. 采用结构体保存过程数据 通过定义两个结构体类型，分别记录栈中的 走过的坐标及走过的方向，采用结构体实现 栈的存储。那么，根据这个思路，代码如下 （代码21-1.txt）。 n nn 21.2.2 问题实现 2. 输出结果 将结果输出至屏幕，以循环打印的方式，调 用标准输入输出函数printf,将结果回显。代 码如下（代码21-2.txt）。 21.2.2 问题实现 01 /*输出路径*/ 02 void outputpath(pseqstack st)

4、 03 04 datatype element; 05 printf(nn出迷宫的路径是:n); 06 while(!isemptystack_seq(st) 07 08 element = top_seq(st); 09 pop_seq(st); 10 printf(n路过的节点坐标是: 第%d行 第%d列, element.x, element.y);/* 打印路径上的每一点*/ 11 12 21.2.2 问题实现 3. 求解经过的坐标点及方向 从入口点开始，依次试探四个方向，只要某 个方向没有障碍，则继续这个方向，并将这 个方向不是障碍物的点做为下一个当前点， 循环直到到达入口点。代码如下（代码21- 3.txt） 21.2.3 程序运行 单击【调试】工具栏中的按钮，即可输出以 下运行结果。 21.3 开发过程常见问题及解决 开发过程常见问题及解决办法如下，仅供参考。 在程序中，如何表示一个坐标点呢？方法很简单： 只需要用一对变量即可保存。即：一个变量保存横坐标， 另外一个变量保存纵