1、 计 算 机 科 学 与 技 术 学 院 课 程 设 计 报 告 （ 2007 2008 学年度 第 1 学期 ） 课程名称 数据结构 c+描述 课程设计 名称 迷宫问题 1.实验目的及要求 1） 、） 、设计目标（设计目标（问题描述）问题描述） 迷宫问题迷宫问题 问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶 大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口， 在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行 上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走 迷宫的路线。
2、 2） 、功能设计要求） 、功能设计要求 编写一个程序求解迷宫问题。迷宫由 m 行 n 列的二维数组设置，0 表示无障碍，1 表示 有障碍。设入口为（1，1） ，出口为（m，n） ，每次只能从一个无障碍单元移到周围四个方 向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得 出没有通路的结论。 算法输入：代表迷宫入口的坐标 算法输出：穿过迷宫的结果。 算法要点：创建迷宫，试探法查找路径，输出解 3） 、） 、实验目的 1、加深对栈特性理解，以便在解决实际问题中灵活运用它们 2、加深对栈操作实际算法的理解 3、进一步熟悉掌握链表的操作； 4、掌握指针的应用 5、更进一步
3、掌握有关类的操作 4） 、） 、 需求分析 1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示 提示信息之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径 并输出路径。 2、本演示程序中，输入形式以回车符为结束标志，且允许出现重复字符。 3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变 量。输入的形式以回车结束。 4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输 入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径 5） 、创新） 、创新（见源程序附录）（见源程序附录） 6） 、软件、硬件
4、环境） 、软件、硬件环境 软件环境：软件环境：Microsoft Windows Xp Processional2002 Service Microsoft Visual C+6.0 硬件环境：硬件环境：cpu：AMD Athlon（tm）64x Dual Processor 3800+2.01GHz Main memory:960MB 2.实验步骤 a.认真阅读课本的相关知识章节。 b.认真分析课题的需求分析和功能分析。 c.根据分析的思路写出伪代码。 d.根据伪代码上机编写程序，进行初步调试。 e.逐步增加完善系统的功能，实现人工智能化。 f.记录上机运行时遇到的错误，进行认真分析。 g.
5、最后认真撰写实验报告，写出实验心得总结。 3. 实验内容 1） 、设计概述） 、设计概述 (a) 开发平台：开发平台：VC6.0 (b) 参考书籍：参考书籍： 1.数据结构数据结构 C+描述描述 熊岳山熊岳山 陈怀陈怀义义 编著编著 国防科技大学出版社国防科技大学出版社 2、 数据结构与算法黄定 黄煜廉 编著 广东科技出版社 2000 年 1 月第 1 版 3、 数据结构辅导与提高徐孝凯 编著 清华大学出版社 2003 年 12 月第 1 版 (c) 开发周期：开发周期： 10 天（构思天（构思 3 天天、雏形、雏形 3 天天、修改、修改 2 天天、再修改、再修改 1 天天、完善、完善 1 天
6、天） 2） 、处理流程） 、处理流程 (a)画出功能结构图画出功能结构图 (b)画出主要数据结构画出主要数据结构的类图的类图 class 类名 DataType /定义描述迷宫中当前位置的类型 Main 主函数模块 获取迷宫模块 探索路径模块 Findpath（） 输出路径模块 printpath（） 读文件 Readfile（） 写文件 Writefile（） 存 储 探 索 路 径模块 stack 类 Stack 类 结 点 数 据 类 型模块 datatype 类 取 栈 顶 函数 getpop （） 进栈与 出栈函 数 push （） Pop（） 清空函 数 clear （） 结点模块 Node*top 操作模块 数据模块 构 造 与 析 构 函 数 stack （） stack （） 盘空函 数 isempty （） 数 据 成 员 访问控制权限 数据类型 变量名; public: int x; /x 代表当前位置的行坐标 int y; /y 代表当前位置
