迷宫问题课程设计报告

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、160;              4）、 需求分析 1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。 2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。 3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。 4、本程序中，用户可以读去文件里的迷宫，也可自己

4、重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径 5）、创新（见源程序附录）6）、软件、硬件环境 软件环境：Microsoft Windows Xp Processional2002 ServiceMicrosoft Visual C+6.0 硬件环境：cpu：AMD Athlon（tm）64x DualProcessor 3800+2.01GHz Main memory:960MB2.实验步骤a.认真阅读课本的相关知识章节。b.认真分析课题的需求分析和功能分析。c.根据分析的思路写出伪代码。d.根据伪代码上机编写程序，进行初步调试。e.逐步增加完善系统的功

5、能，实现人工智能化。f.记录上机运行时遇到的错误，进行认真分析。g.最后认真撰写实验报告，写出实验心得总结。3. 实验内容1）、设计概述(a) 开发平台：VC6.0(b) 参考书籍： 1.数据结构C+描述 熊岳山 陈怀义 编著 国防科技大学出版社 2、数据结构与算法黄定  黄煜廉 编著  广东科技出版社  2000年1月第1版3、数据结构辅导与提高徐孝凯  编著 清华大学出版社 2003年12月第1版(c) 开发周期： 10天（构思3天、雏形3天、修改2天、再修改1天、完善1天）2）、处理流程(a)画出功能结构图Main主函数模块输出

6、路径模块printpath（）获取迷宫模块探索路径模块Findpath（）写文件Writefile（）读文件Readfile（）存储探索路径模块stack类Stack类操作模块数据模块盘空函数isempty（）清空函数clear（）取栈顶函数getpop（）进栈与出栈函数push（）Pop（）构造与析构函数stack（）stack（）结点模块Node*top结点数据类型模块datatype类(b)画出主要数据结构的类图class 类名DataType /定义描述迷宫中当前位置的类型数据成员访问控制权限 数据类型 变量名; public:int x; /x代表当前位置的行坐标 int y; /y

7、代表当前位置的列坐标 int pre; /pre表示移动到下一步的方向 class 类名Move /定义下一个位置的方向数据成员访问控制权限 数据类型 变量名; public:int x; int y;class 类名Node /结点数据成员访问控制权限 数据类型 变量名; public: DataType data; Node *next;class 类名stack数据成员访问控制权限 数据类型 变量名; private: Node *top; /指向第一个结点的栈顶指针成员函数访问控制权限 返回值类型 函数名(参数列表) public: stack(); /构造函数，置空栈 stack()

8、; /析构函数 void Push(DataType data);/把元素data压入栈中 DataType Pop(); /使栈顶元素出栈 DataType GetPop(); /取出栈顶元素 void Clear(); /把栈清空 bool IsEmpty(); /判断栈是否为空，如果为空则返回1，否则返回0(c)主要函数的程序流程图开始 1.main函数流程图： 显示系统信息选择获取迷宫的方式chCh= bCh=a自行输入Writefile（）Readfile()文件读取探索迷宫路径是否存在输出迷宫路径是否继续游戏退出开始2.探索路径函数findpath（）Temp1.x=1Temp1.

9、y=1入口进栈p.pushq.push是否非空temp2=q.getpop（）P q栈顶是否相等探索上下左右四个方位是否有路径到达新位置是否到达出口最后一个元素进栈输出路径回复以改变的迷宫结束 开始3.自行输入迷宫函数writefile（）输入长宽m，n动态申请空间二位数组空间i<=m是否保存迷宫J<=ni+ ；j+输入迷宫输入保存迷宫的文件名保存迷宫结束(d)写出数据测试表（输入数据/预期结果） 测试一：从文件中读取迷宫： 0010001000010001010000110000111001000001000010100010100111100111100010111100000

10、00 输出：探索路径： （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，向下）（9，7，向右）（9，8，向右） （9，9）测试二： 自己输入迷宫： 001000100 输出探索路径： （1，1，向下）（2，1，向右）（2，2，向下）（3，2，向右）（3，3）测试三：自己输入迷宫： 111111000 输出探索路径： Sorry！找不到路径！4.实验结果结果为以下三种情形之一：1）编译不通过：

11、给出编译错。Compiling.stack.cppSkipping. (no relevant changes detected)main.cppLinking.stack.obj : error LNK2005: "public: _thiscall stack:stack(void)" (?0stackQAEXZ) already defined in main.objstack.obj : error LNK2005: "public: _thiscall stack:stack(void)" (?1stackQAEXZ) already defi

12、ned 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.

13、objstack.obj : error LNK2005: "public: struct DataType _thiscall stack:GetPop(void)" (?GetPopstackQAE?AUDataTypeXZ) already defined in main.objstack.obj : error LNK2005: "public: void _thiscall stack:Clear(void)" (?ClearstackQAEXXZ) already defined in main.objstack.obj : error LN

14、K2005: "public: bool _thiscall stack:IsEmpty(void)" (?IsEmptystackQAE_NXZ) already defined in main.objDebug/迷宫问题.exe : fatal error LNK1169: one or more multiply defined symbols found执行 link.exe 时出错.迷宫问题.exe - 1 error(s), 0 warning(s)改正： 在main。cpp中原来包含的是stack.cpp把它改为包含stack.h即可错误二： 用string直

15、接定义字符串str时，说没有定义str 原因：#include<string>using namespace std ;没有用标准空间错误三： 拼写错误正确结果输出：接上面：接上面：5. 实验总结分析1)、时间和空间分析该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比，迷宫长为m，宽为n，在最好情况下的时间和空间复杂度均为O（m+n），在最差情况下均为O（m*n），平均情况在它们之间2)、程序的优点a. 进入演示程序后即显示文本方式的用户界面b. 本程序模块划分比较合理，且利用指针存储迷宫，操作方便。c. 能按照玩游戏人的意愿任意输入迷宫大小，并且可以保存新输入的迷宫

16、，方便退出游戏后仍可打开自己定义文件查看迷宫。3)、遇到的问题及如何解决 a.如何知道哪一点被探索过且路径不通？ 答：maze【i】【j】本来时表示通与不通，那么可以当探索该点之后，将其值赋为-1,就可以知道此点已经被访问过 b.如何正确的使用文件读入迷宫？ 答：查看大一学的C+课本，仔细阅读文件那一章。c.我想让用户在每次玩游戏之后都能查看输入的迷宫，我想的是运行程序时随意新建文本文档，开始是直接输入一个.txt结尾的字符串，但编译好多错误,我猜应该是要调用相关函数，但具体是那一个不清楚。 答：去图书馆借阅相关资料，要调用相应的库函数。4)、存在的缺陷、改进设想 每当自行输入迷宫后，生成相应

17、的文件保存，但是我在想：一旦玩游戏的人多了，玩的次数多了，那么生成的保存迷宫文件就会很多，会给人工智能化系统造成文件冗余。我设想：能不能在一段时间之后系统自动调用函数来清除冗余文件。5)、自我评价、经验体会等通过这次课程设计，体会如下：、进一步熟悉掌握了有关栈的基本操作；、对迷宫有了更多的认识3、更进一步掌握有关类的操作4、由于对栈的算法推敲不足，使程序调试时费时不少总之：我认为这次课程设计做的很好。课程设计的成功使我相信一句话：有付出就会有收获，要相信自己。6. 附录（源程序清单，要求含有至少30%的源码附有注释）迷宫程序代码（本程序有个创新点）/* Name: stack.h Author

18、: 罗丹 Description: 用于记录探索路径的栈类头文件 */#include<iostream>#include"fstream"using namespace std;class DataType /定义描述迷宫中当前位置的类型public:int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int pre; /pre表示移动到下一步的方向; class Move /定义下一个位置的方向 public:int x; int y;class Node /链表结点public: DataType data; Node *nex

19、t;/下面定义栈class stackprivate: Node *top; /指向第一个结点的栈顶指针 public: stack(); /构造函数，置空栈 stack(); /析构函数 void Push(DataType data);/把元素data压入栈中 DataType Pop(); /使栈顶元素出栈 DataType GetPop(); /取出栈顶元素 void Clear(); /把栈清空 bool IsEmpty(); /判断栈是否为空，如果为空则返回1，否则返回0;/* Name: stack.cpp Author: 罗丹 Description: 用于记录探索路径的栈类实

20、现文件 */#include"stack.h"stack:stack() /构造函数，置空栈top=NULL;stack:stack() /析构函数void stack:Push(DataType x) /进栈Node *TempNode; TempNode=new Node; TempNode->data=x; TempNode->next=top; top=TempNode;DataType stack:Pop() /栈顶元素出栈 DataType Temp; Node *TempNode=NULL; TempNode=top; top=top->ne

21、xt; Temp=TempNode->data; delete TempNode; return Temp;DataType stack:GetPop() /取出栈顶元素return top->data;void stack:Clear() /把栈清空top=NULL;bool stack:IsEmpty() /判断栈是否为空，如果为空则返回1，否则返回0if(top=NULL) return true; else return false;/* Name: main.cpp Author: 罗丹 Description: 主函数文件 */#include"stack.h

22、"#include<iostream>#include<string>#include<fstream>using namespace std ;/* Description: 外部函数的声明部分*/bool findpath(int *maze,int m,int n); /寻找迷宫路径 void PrintPath(stack p); /输出路径void Restore(int *maze,int m,int n); /恢复迷宫Move move4=0,1,1,0,0,-1,-1,0; /定义当前位置移动的4个方向(上，右，下，左)int* r

23、eadFile (int &m,int &n);int* write &m,int &n);/* Description: main.cpp*/ void main() cout<<endl;/ cout<<""<<endl; cout<<" 2007-2008年度第一学期数据结构课程之课程设计 "<<endl; cout<<endl; cout<<" 迷宫问题 "<<endl; cout<<&q

24、uot; 开发员 : 罗丹"<<endl; cout<<" 专业班级: 计算机061班"<<endl; cout<<""<<endl; cout<<" 欢迎进入迷宫游戏 "<<endl; int m=0,n=0; int *maze; char ch; int flag=0,flag1=0; while(flag1=0) while(flag=0)/标志是否重新选择 cout<<endl; cout<<" 请

25、从以下选项中选择获取迷宫的方法！"<<endl; cout<<" <a>从文件中读取"<<endl; cout<<" <b>直接自行输入"<<endl; cout<<" 请选择:" cin>>ch; if(ch='a')maze=read);flag=1; else if(ch='b')maze=write);flag=1; else cout<<" Sorry!您

26、输入的选择代码不在范围内!请从新选择"<<endl; if(findpath(maze,m,n) cout<<" Congratulations! 迷宫路径探索成功!"<<endl; /得到路径 else cout<<" Sorry! 路径不存在"<<endl; cout<<endl; cout<<" 继续玩吗？(y/n)" char c; cin>>c; if(c=n) flag1=1; else flag=0; cout<

27、;<" 谢谢,您已经退出迷宫系统 "<<endl; cout<<""<<endl;/* Description: 获取迷宫函数*/int* readFile (int &m,int &n) /读出文件int *maze; int i=0,j=0; cout<<" 您选择的是直接从文件中读取迷宫!"<<endl; cout<<endl; cout<<" 文件中的迷宫如下： "<<endl; char

28、ch; /定义一个字符，读取文件中的内容 ifstream open("maze.txt"); /定义一个文件对象，并打开文件"maze.txt" /读取内容记录行数和列数 （创新点一：从文件中直接读取迷宫） while(open.get(ch) /从读取文件中内容（一旦个字符形式） if(ch='0'|ch='1') j+; /是0或1字符宽就加1 if(ch='n') i+; /如果是换行符，就行加1 n=j; /得列数 j=0; open.close(); /读取文件结束 m=i; maze=new

29、int *m+2; /申请长度等于行数加2的二维指针(为后面的回复迷宫打下基础) for(i= 0;i<m+2;i+) /申请空间 mazei=new intn+2; i=j=1; ifstream open1("maze.txt"); /重新读取文件，以得到内容 while(open1.get(ch) if(ch='1'|ch='0') mazeij=ch-'0' /把数字字符转化为数字，并存到指针里 cout<<mazeij<<" " /在屏幕中显示迷宫 j+; if(ch

30、='n') /遇到换行，指针也相应换行 cout<<endl; i+; j=1; open1.close(); /读取结束 return maze; int* writeFile (int &m,int &n) /将自定义迷宫写入文件int a,b; int i,j;int*maze; cout<<" 您选择的是自行输入迷宫!"<<endl; cout<<" 请输入迷宫的长:"cin>>b; /输入迷宫的长和宽 cout<<" 请输入迷宫的宽

31、:"cin>>a; cout<<" 请输入迷宫内容(0代表可通，1代表不通):n" m=a; n=b; /m,n分别代表迷宫的行数和列数 maze=new int *m+2; for(i= 0;i<m+2;i+) mazei=new intn+2; /创新点二：:随意申请空间 for(i=1;i<=m;i+) /输入迷宫的内容，0代表可通，1代表不通 for(j=1;j<=n;j+) cin>>mazeij; cout<<" 是否保存新迷宫？(y/n): " char choos

32、e; cin>>choose; if(choose='Y'|choose='y') char ch; string str; cout<<" 请输入保存迷宫的文件名(以.txt结束):" cin>>str; ofstream open(str.c_str(); /创新点三：按玩游戏人的意愿创建存储迷宫的文件，也可不建立。 for(i=1;i<=m;i+) for(j=1;j<=n;j+) ch='0'+mazeij; open<<ch; open<<end

33、l; flush(cout); open.close(); for(i=0;i<m+2;i+) mazei0=mazein+1=1; for(i=0;i<n+2;i+) maze0i=mazem+1i=1; return maze; /* Description: 探索路径函数*/bool findpath(int *maze,int m,int n)stack q,p; /创新点四：用栈p、q,分别存探索迷宫的过程和存储路径 DataType Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /将入口位

34、置入栈 p.Push(Temp1); maze11=-1; /创新点五：标志入口位置已到达过 while(!q.IsEmpty() /栈q非空，则反复探索 Temp2=q.GetPop(); if(!(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop<4;loop+) /探索当前位置的4个相邻位置 x=Temp2.x+moveloop.x; y=Temp2.y+moveloop.y; if(mazexy=

35、0) /判断新位置是否可达 Temp1.x=x; Temp1.y=y; mazexy=-1; /标志新位置已到达过 q.Push(Temp1); /新位置入栈 if(x=(m)&&(y=(n) /成功到达出口 Temp1.x=m; Temp1.y=n; Temp1.pre=0; p.Push(Temp1); /把最后一个位置入栈 PrintPath(p); Restore(maze,m,n); /恢复路径（因为迷宫里面的内容已被改变 return 1; /表示成功找到路径 if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y)/如果没有新位置入栈，则返回到上一个位置 p.Pop(); q.Pop(); return 0; /表示查找失败，即迷宫无路经/* Description: 输出路径函数*/void PrintPath(stack p) /输出路径cout<<endl; cout<<" 迷宫的路径为"<&l