1、* 实践教学实践教学 * 计算机与通信学院 2012 年春季学期 算法与数据结构算法与数据结构 课程设计课程设计 题 目： 迷宫问题 专业班级：计算机科学与技术一班 姓 名： 学 号： 指导教师： 成 绩： 目目 录录 摘 要 . 3 前 言 . 4 正 文 . 5 一、采用 c+语言定义相关的数据类型 5 二、各模块的伪码算法 . 6 三、函数的调用关系图 . 10 四、调试分析 . 11 五、测试结果 . 12 1、开始界面 . 12 2、自动生成迷宫运行情况 12 3、键盘输入迷宫运行情况 14 总 结 . 16 致 谢 . 17 参考文献 . 18 附 录 . 19 源程序（带注释）
2、19 摘摘 要要 本程序主要是对任意给定的迷宫，求出一条从入口到出口的通路，或得出没 有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟 练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题， 培养我们的动手能力。 1、生成迷宫：根据提示输入数据，然后生成一个 8 行 8 列的迷宫。 2、探索迷宫路径：由输入的入口位置开始，对相邻的（上，下，左，右）四 个方向的方块进行探索，若可通则“纳入路径” ，否则顺着“来向”退到“前一通 道块” ，朝着“来向”之外的其它方向继续探索。 3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后 弹出路径坐标，
3、输出在屏幕上。 关键字关键字：栈，栈的存储结构，出栈与入栈 前前 言言 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机 解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探 索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至 所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需 要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路 的算法中应用“栈”也就是自然而然的事。迷宫问题要求，所求路径必须是简单 路径，即在求得路径上不能同时重复出现同一通道。在迷宫中用 1 和 0 分别表示 迷宫中的通路和障碍。
4、 首先，输入迷宫数据，在计算机的屏幕上显示一个 8 行 8 列的矩阵表示迷宫。 矩阵中的每个数据或为通路（以 0 表示） ，或为墙（以 1 表示） ，所求路径必须是 简单路径，即在求得的路径上不能重复出现同一道块。 其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块 位置” ，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通” ，则“纳 入当前路径” ，并继续朝“下一个位置”探索，即切换“下一位置”为“当前位置” ， 如此重复直到到达出口；若当前位置“不可通” ，则应顺着“来向”退回到“前一 通道块” ，然后朝着除“来向” ，之外的其它方向继续探索，若该通道块的四周四 个
5、方块均“不可通” ，则应该从“当前路径”上删除该通道块，所谓“下一个位置” 指的是“当前位置”四周四个方向（上，下，左，右）上相邻的方块。假设以栈 S 记录“当前路径” ，则栈顶中存放的是“当前路径上最后一个通道块” 。由此， “纳 入路径” 的操作为 “当前位置入栈” ； 从当前路径删除前一通道块的操作为 “出栈” 。 最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径 坐标。最后希望通过对该课题的设计，理解和掌握所学到的各种数据结构，学会 把学到的知识应用于解决实际的问题当中，培养自己的动手能力。 正正 文文 一、采用一、采用 c+c+语言定义相关的数据类型语言定义相关的数
6、据类型 1、定义坐标（X，Y）: #include #include using namespace std; struct Coor int row; int column; int direction; ; 2、定义方向： struct Move int row; int column; ; 3、定义/链表结点： struct LinkNode Coor data; LinkNode *next; ; 4、定义栈： class stack private: LinkNode *top; public: stack(); stack(); void Push(Coor data); Coor Pop(); Coor GetPop();
