《迷宫问题课程设计报告》由会员分享，可在线阅读，更多相关《迷宫问题课程设计报告（20页珍藏版）》请在金锄头文库上搜索。
1、南华大学计算机科学与技术学院 实验报告南华大学计算机科学与技术学院课 程 设 计 报 告 （ 2007 2008 学年度 第 1学期 ）课程名称数据结构c+描述课程设计名称迷宫问题姓名 学号 20064440109专业计算机科学与技术班级计算机01班地点8209教师 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）、软件、硬件环境 软件环境：Microsoft Windows Xp P
4、rocessional2002 ServiceMicrosoft Visual C+6.0 硬件环境：cpu：AMD Athlon（tm）64x DualProcessor 3800+2.01GHz Main memory:960MB2.实验步骤a.认真阅读课本的相关知识章节。b.认真分析课题的需求分析和功能分析。c.根据分析的思路写出伪代码。d.根据伪代码上机编写程序，进行初步调试。e.逐步增加完善系统的功能，实现人工智能化。f.记录上机运行时遇到的错误，进行认真分析。g.最后认真撰写实验报告，写出实验心得总结。3. 实验内容1）、设计概述(a) 开发平台：VC6.0(b) 参考书籍： 1.
5、数据结构C+描述 熊岳山 陈怀义 编著 国防科技大学出版社 2、数据结构与算法黄定 黄煜廉编著 广东科技出版社 2000年1月第1版3、数据结构辅导与提高徐孝凯 编著 清华大学出版社2003年12月第1版(c) 开发周期： 10天（构思3天、雏形3天、修改2天、再修改1天、完善1天）2）、处理流程(a)画出功能结构图Main主函数模块输出路径模块printpath（）获取迷宫模块探索路径模块Findpath（）写文件Writefile（）读文件Readfile（）存储探索路径模块stack类Stack类操作模块数据模块盘空函数isempty（）清空函数clear（）取栈顶函数getpop（）进
6、栈与出栈函数push（）Pop（）构造与析构函数stack（）stack（）结点模块Node*top结点数据类型模块datatype类(b)画出主要数据结构的类图class 类名DataType /定义描述迷宫中当前位置的类型数据成员访问控制权限 数据类型 变量名; public:int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int pre; /pre表示移动到下一步的方向 class 类名Move /定义下一个位置的方向数据成员访问控制权限 数据类型 变量名; public:int x; int y;class 类名Node /结点数据成员访问控制权限 数据
7、类型 变量名; public: DataType data; Node *next;class 类名stack数据成员访问控制权限 数据类型 变量名; private: Node *top; /指向第一个结点的栈顶指针成员函数访问控制权限 返回值类型 函数名(参数列表) public: stack(); /构造函数，置空栈 stack(); /析构函数 void Push(DataType data);/把元素data压入栈中 DataType Pop(); /使栈顶元素出栈 DataType GetPop(); /取出栈顶元素 void Clear(); /把栈清空 bool IsEmpty
8、(); /判断栈是否为空，如果为空则返回1，否则返回0(c)主要函数的程序流程图开始 1.main函数流程图： 显示系统信息选择获取迷宫的方式chCh= bCh=a自行输入Writefile（）Readfile()文件读取探索迷宫路径是否存在输出迷宫路径是否继续游戏退出开始2.探索路径函数findpath（）Temp1.x=1Temp1.y=1入口进栈p.pushq.push是否非空temp2=q.getpop（）P q栈顶是否相等探索上下左右四个方位是否有路径到达新位置是否到达出口最后一个元素进栈输出路径回复以改变的迷宫结束 开始3.自行输入迷宫函数writefile（）输入长宽m，n动态申
9、请空间二位数组空间i=m是否保存迷宫J=ni+ ；j+输入迷宫输入保存迷宫的文件名保存迷宫结束(d)写出数据测试表（输入数据/预期结果） 测试一：从文件中读取迷宫： 001000100001000101000011000011100100000100001010001010011110011110001011110000000 输出：探索路径： （1，1，向下） （2，1，向下）（3，1，向下）（4，1，向下）（5，1，向右）（5，2，向右） （5，3，向下）（6，3，向右）（6，4，向右）（6，5，向上）（5，5，向右）（5，6，向右）（5，7，向下）（6，7，向下）（7，7，向下）（8，7
10、，向下）（9，7，向右）（9，8，向右） （9，9）测试二： 自己输入迷宫： 001000100 输出探索路径： （1，1，向下）（2，1，向右）（2，2，向下）（3，2，向右）（3，3）测试三：自己输入迷宫： 111111000 输出探索路径： Sorry！找不到路径！4.实验结果结果为以下三种情形之一：1）编译不通过：给出编译错。Compiling.stack.cppSkipping. (no relevant changes detected)main.cppLinking.stack.obj : error LNK2005: public: _thiscall stack:stack(
11、void) (?0stackQAEXZ) already defined in main.objstack.obj : error LNK2005: public: _thiscall stack:stack(void) (?1stackQAEXZ) already defined in main.objstack.obj : error LNK2005: public: void _thiscall stack:Push(struct DataType) (?PushstackQAEXUDataTypeZ) already defined in main.objstack.obj : error LNK2005: public: struct DataType _thiscall stack:Pop(void) (?PopstackQAE?AUDataTypeXZ) already defined in main.objstack.obj : error LNK2005: public: struct DataType _thiscall stack:GetPop(void) (?GetPopstackQAE?AUDataTypeXZ) alread
