迷宫问题——数据结构课程设计迷宫问题.docVIP

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