迷宫求解

在前面的章节中，讲解了线性数据结构最常用的两种形式:顺序表和链式表，本章中介绍的迷宫求解问题，更是巧妙地使用了顺序表的一种特殊形式———顺序栈，展示了C语言在算法领域强大的功能。

栈(Stack)是一种重要的线性结构，是受限的线性表，它是仅能在表的一端进行插入和删除运算的线性表，被广泛地应用到各种系统的程序设计中。

栈的特点是:

(1)通常称插入、删除的这一端为栈顶，另一端为栈底;

(2)当表中没有元素时称为空栈;

(3)栈为后进先出的线性表，简称为LIFO表。

栈的修改是按后进先出的原则进行的。每次删除(退栈)的总是当前栈中“最新”的元素，即最后插入(进栈)的元素，而最先插入的元素被放在栈的底部，要到最后才能删除。如图5-1所示。

图5-1

在实际使用过程中，常用的栈的操作如下:

(1)构造一个空栈S。

(2)判栈空。若S为空栈，则返回1，否则返回0。

(3)判栈满。若S为满栈，则返回1，否则返回0。

(4)进栈。若栈S不满，则将元素x插入S的栈顶。

(5)退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。

(6)取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。

一、需求分析

问题描述:以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。对任意设定的迷宫，求出一条从入口到出口的通路并输出所经过的坐标点，或得出没有通路的结论。

由问题描述可知，我们要实现的是打印从坐标A走到坐标B所经过的结点坐标，即要绕过路障走一条路径出来。简单举例:从左向右走动，中间有障碍物，此时，需要向上再向右，或向下再向右，只有绕过左与右之间的障碍物，才可以顺利从左走至右，以下将仔细地分析问题并实现算法。

二、总体设计

我们将要开发的程序就是设置一个m×n大小的迷宫，并设置入口点和出口点，从入口点走向出口点，将途经的坐标记录到“栈”底，在找到路径时，将弹出栈顶元素，此时，就是所有途经的坐标点。

顺序栈结构体定义如下:

说明:

(1)栈底位置是固定不变的，可设置在向量两端的任意一个端点。

(2)栈顶位置是随着进栈和退栈操作而变化的，用一个整型变量top(通常称top为栈顶指针)来指示当前栈顶位置。

三、功能模块实现

把功能分成栈操作模块、main函数模块、读取迷宫模块、迷宫求解模块和输出路径模块，下面详细讲解。

(1)栈操作模块

栈操作模块主要实现了栈的基本操作，包括创建栈、判断栈是否为空、入栈操作、出栈操作和取栈顶元素操作几部分。

(2)main函数模块

主函数永远是作为驱动出现的，这里的main函数完成了初始化迷宫数据、调用迷宫求解函数和输出路径的功能。

(3)读取迷宫模块

在文件“map．txt”事先写好迷宫数据，使用0表示空位置，使用1表示有障碍位置。程序中还用到了数据2表示经过的位置，数据100表示栈中元素值，也就是路径位置，如图5-2所示。

图5-2　迷宫数据

(4)迷宫求解函数模块

迷宫求解的路径并非是最优的路径，只是使用递归调用的方法，找到了一条从入口到出口的通路，试探前进采取的是右下左上的顺序。

(5)输出路径模块

依次弹出栈顶元素，直至栈空，弹出数据的顺序就是从出口到入口的顺序，反向输出即为正向顺序，同时标记路径点。

四、系统运行

系统设计好了，现在我们就来看看设计的成果。单击【调试】工具栏中的编译按钮、链接按钮和运行按钮即可运行系统。系统运行后在可在屏幕上看到迷宫地图、路径经过的结点位置和路径图示，如图5-3所示。

其中字符ˊ．ˊ表示路径，字符ˊvˊ表示经过但走不通的点。

图5-3

五、小结

本章通过有趣的迷宫求解问题，让读者掌握了顺序栈的用法，对顺序线性结构有了更深的认识，还对程序求解中常用的递归算法灵活地进行了使用。通过这道题目，让我们更加清醒地认识到了算法在程序开发中的重要性。