1、 课程设计(论文) 题 目 名 称 迷宫求解 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 、专 业 信息工程系、电气信息类（信息类） 指 导 教 师 2010 年 1 月 3 日 摘 要 设计一个简单迷宫程序，从入口出发找到一条通路到达出口。 编制程序给出一条 通过迷宫的路径或报告一个“无法通过”的信息。 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程 序。用“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则 继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通 路。假如所有可能的通路都探索到而未能到达出口，则所设
2、定的迷宫没有通路。可以 用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n， n）。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有 东、南、西、北四个方向可通。 关键词：迷宫；栈；链表；二维数组 目 录 1 问题描述 . 1 2 需求分析 . 1 3 概要设计 . 1 31 抽象数据类型定义 1 32 模块划分 . 2 4 详细设计 . 2 41 数据类型的定义 2 42 主要模块的算法描述 3 5 测试分析 . 6 6 课程设计总结 7 参考文献 . 7 附录（源程序清单） 8 1 1 问题描述 迷宫是一个M行N列的0-1矩阵，其中0表示无障碍
3、，1表示有障碍。设入口 为(1， 1)出口为(M，N)每次移动只能从一个无障碍的单元移到其周围8个方向上任 一无障碍的单元， 编制程序给出一条通过迷宫的路径或报告一个 “无法通过” 的信息。 2 需求分析 （1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程 序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一 个坐标，d表示走到下一坐标的方向。否则报告一个无法通过的信息。 （2）建立InitStack函数，用于构造一个空栈。 （3）建立DestroyStack函数，用于销毁栈。 （4）建立Pop函数，用于删除栈顶元素，返回栈顶元素的值。 （5）
4、建立Push函数，用于插入新的栈顶元素。 （6）建立NextPos函数，用于定位下一个位置。 3 概要设计 31 抽象数据类型定义 （1）栈的抽象数据类型定义 InitStack( LStack *S ) 操作结果：构造一个空栈S。 DestroyStack( LStack *S ) 操作结果：栈S被销毁。 Pop( LStack *S，ElemType *e ) 操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回0。 Push( LStack *S，ElemType e ) 操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。 （2）迷宫的抽象数据类型定义 NextPos(unsigned *x，unsigned *y，short di) 操作结果：找到下一个位置。 2 32 模块划分 本程序包括三个模块： （1）主程序模块 void main() 初始化； 构造迷宫； 迷宫求
