迷宫问题课程设计报告

南华大学计算机科学与技术学院试验报告南华大学计算机科学与技术学院试验报告LDLD尽我所能南华大学课程设计报告〔2023 ~ 2023 学年度 第1学期〕课程名称名称

c++描述迷宫问题姓名罗丹学号20234440109专业与技术班级01班地点8—209教师刘霞南华大学计算机科学与技术学院试验报告南华大学计算机科学与技术学院试验报告1010LD尽我所能试验目的及要求、设计目标〔问题描述〕迷宫问题问题描述：迷宫试验是取自心理学的一个古典试验。在该试验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了很多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中查找道路以到达出口。对同一只老鼠重复进展上述试验，始终到老鼠从入口到出口，而不走错一步。老鼠经屡次试验最终得到它学习走迷宫的路线。、功能设计要求编写一个程序求解迷宫问题。迷宫由mn01有障碍。设入口为〔1，1，出口为〔m，n，每次只能从一个无障碍单元移到四周四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。算法输入：代表迷宫入口的坐标算法输出：穿过迷宫的结果。算法要点：创立迷宫，摸索法查找路径，输出解、试验目的1、加深对栈特性理解，以便在解决实际问题中敏捷运用它们2、加深对栈操作实际算法的理解3、进一步生疏把握链表的操作；4、把握指针的应用5、更进一步把握有关类的操作、需求分析1、本程序实现迷宫的探究过程.以用户和计算机对话的方式，即在计算机终端上显示并输出路径。2、本演示程序中，输入形式以“回车符”为完毕标志，且允许消灭重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探究路径，每个结点含三个整形变量。输入的形式以回车完毕。4、本程序中，用户可以读去文件里的迷宫，也可自己重输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探究路径，并输出迷宫的路径、创〔见源程序附录〕、软件、硬件环境软件环境：MicrosoftWindowsXpProcessional2023ServiceMicrosoftVisualC++6.0硬件环境：cpu：AMD Athlon〔tm〕64xDualProcessor3800+2.01GHz Mainmemory:960MB试验步骤认真阅读课本的相关学问章节。认真分析课题的需求分析和功能分析。c.依据分析的思路写出伪代码。d.依据伪代码上机编写程序，进展初步调试。e.逐步增加完善系统的功能，实现人工智能化。f.记录上机运行时遇到的错误，进展认真分析。g.最终认真撰写试验报告，写出试验心得总结。StackStack类数据模块操作模块〔〕〔〕Pop〔〕〔〕〔〕结点数据类型 模 块datatype类、设计概述开发平台：VC6.0参考书籍：C++描述熊岳山陈怀义编著国防科技大学出版社2、《数据构造与算法》黄定黄煜廉编著广东科技出版社2023113《数据构造辅导与提高》徐孝凯编著 清华大学出版社2023年12月第1版开发周期：10天〔33211天〕、处理流程MainMain主函数模块猎取迷宫模块探究路径模块Findpath〔〕输出路径模块printpath〔〕读文件Readfile〔〕写文件Writefile〔〕存储探究路径模块stack类结点模块构进栈与清空函盘空函Node*top析出栈函函 数数数数stackpushgetpopcler〕isemptyclassclassMove//定义下一个位置的方向数 访问掌握权限数据类型变量名;据 public:成 intx;员 inty;classNode//结点数 访问掌握权限数据类型变量名;据 public:成 DataTypedata;员 Node*next;classstack数据成访问掌握权限数据类型变量名;private:Node*top;//指向第一个结点的栈顶指针voidPush(DataTypedata);//dataDataTypePop; //使栈顶元素出栈DataTypeGetPop; //取出栈顶元素voidClear; //把栈清空boolIsEmpty; //推断栈是否为空，假设为空则返回1，否则0classclassDataType//定义描述迷宫中当前位置的类型数据成员访问掌握权限数据类型变量名;public:intx;inty;intpre;//x//y//pre员成员函访问掌握权限public:stack;返回值类型函数名(参数列表)//构造函数，置空栈数~stack;//析构函数开头主要函数的程序流程图1.开头main函数流程图：显示系统信息显示系统信息选择猎取迷宫的方式chCh==’a’Ch==’b’Readfile文件读取自行输入探究迷宫路径是否存在输出迷宫续玩耍退出探究路径函数findpath〔〕 开头Temp1.x=1Temp1.y=1入口进栈p.pushq.push是否非空temp2=q.getpop〔〕Pq栈顶是否相等探究上下左右四个方位是否有路径

到达位置是否到达出最终一个元素进栈输出路径回复以转变的迷宫完毕开头输入长宽m，开头输入长宽m，n动态申请空间二位数组空间i<=m是否保存迷宫J<=ni++；j++输入迷宫输入保存迷宫的文件名保存迷宫完毕写出数据测试表〔输入数据/预期结果〕测试一：从文件中读取迷宫：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，向下〕〔9，7，向右〕〔9，8，向右〕〔9，9〕测试二：自己输入迷宫：001000100输出探究路径：〔1，1，向下〕〔2，1，向右〕〔2，2，向下〕〔3，2，向右〕〔3，3〕测试三：自己输入迷宫：111111000输出探究路径：Sorry！找不到路径！试验结果结果为以下三种情形之一：1〕编译不通过：给出编译错。Compiling...stack.cppSkipping...(norelevantchangesdetected)main.cppLinking...stack.obj:errorLNK2023:“public: thiscallstack::stack(void)“(??0stack@@QAE@XZ)alreadydefinedinmain.objstack.obj : error LNK2023: “public:(??1stack@@QAE@XZ)alreadydefinedinmain.obj

thiscall stack::~stack(void)“stack.obj : error LNK2023: “public: void thiscall stack::Push(struct (?Push@stack@@QAEXUDataType@@@Z)alreadydefinedinmain.objstack.obj : error LNK2023: “public: struct DataType thiscall stack::Pop(void)“(?Pop@stack@@QAE?AUDataType@@XZ)alreadydefinedinmain.objstack.obj:errorLNK2023:“public:structDataType thiscallstack::GetPop(void)“(?GetPop@stack@@QAE?AUDataType@@XZ)alreadydefinedinmain.objstack.obj : error LNK2023: “public: void(?Clear@stack@@QAEXXZ)alreadydefinedinmain.obj

thiscall stack::Clear(void)“stack.obj : error LNK2023: “public: bool thiscall stack::IsEmpty(void)“(?IsEmpty@stack@@QAE_NXZ)alreadydefinedinmain.objDebug/迷宫问题.exe:fatalerrorLNK1169:oneormoremultiplydefinedsymbolsfoundlink.exe时出错.迷宫问题.exe1error(s),0warning(s)改正：main。cpp中原来包含的是stack.cpp把它改为包含stack.h即可错误二：string直接定义字符串str时，说没有定义str缘由：#include<string>usingnamespacestd没有用标准空间错误三：拼写错误正确结果输出：接上面：接上面：试验总结分析、时间和空间分析该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比，迷宫长为m，宽为，在最好状况下的时间和空间简单度均为〔m+，在最差状况下均为平均状况在它们之间、程序的优点进入演示程序后即显示文本方式的用户界面本程序模块划分比较合理，且利用指针存储迷宫，操作便利。玩耍后仍可翻开自己定义文件查看迷宫。、遇到的问题及如何解决如何知道哪一点被探究过且路径不通？答：maze【ij-1,就可以知道此点已经被访问过如何正确的使用文件读入迷宫？答：查看大一学的C++课本，认真阅读文件那一章。我想让用户在每次玩玩耍之后都能查看输入的迷宫，我想的是运行程序时随便建文本文档，开头是直接输入一个.txt结尾的字符串，但编译好多错误,我猜应当是要调用相关函数，但具体是那一个不清楚。答：去图书馆借阅相关资料，要调用相应的库函数。、存在的缺陷、改进设想能不能在一段时间之后系统自动调用函数来去除冗余文件。、自我评价、阅历体会等通过这次课程设计，体会如下：１、进一步生疏把握了有关栈的根本操作；２、对迷宫有了更多的生疏3、更进一步把握有关类的操作4、由于对栈的算法推敲缺乏，使程序调试时费时不少收获，要信任自己。附录〔30%的源码附有注释〕迷宫程序代码〔本程序有个创点〕//////////////////////////////////////////////////////////////////////*Name: stack.hAuthor:罗丹Description:用于记录探究路径的栈类头文件*/#include<iostream>#include“fstream“usingnamespacestd;classDataType //定义描述迷宫中当前位置的类型{public:intx; //xinty; //yintpre; //pre};classMove //定义下一个位置的方向{public:intx;inty;};classNode //链表结点{public:DataTypedata;Node*next;};//下面定义栈classstack{private:Node*top; //指向第一个结点的栈顶指针public:stack; //构造函数，置空栈~stack; //析构函数voidPush(DataTypedata);//把元素data压入栈中DataTypePop; //使栈顶元素出栈DataTypeGetPop; //取出栈顶元素voidClear; //把栈清空boolIsEmpty; //推断栈是否为空，假设为空则返回10};//////////////////////////////////////////////////////////////////////*Name: stack.cppAuthor:罗丹Description:用于记录探究路径的栈类实现文件*/#include“stack.h“stack::stack //构造函数，置空栈{top=NULL;}stack::~stack //析构函数{}voidstack::Push(DataTypex) //进栈{Node*TempNode;TempNode=newNode;TempNode->data=x;TempNode->next=top;top=TempNode;}DataTypestack::Pop //栈顶元素出栈{DataTypeTemp;Node*TempNode=NULL;TempNode=top;top=top->next;Temp=TempNode->data;deleteTempNode;returnTemp;}DataTypestack::GetPop //取出栈顶元素{returntop->data;}voidstack::Clear //把栈清空{top=NULL;}boolstack::IsEmpty //推断栈是否为空，假设为空则返回1，否则返回0{if(top==NULL)returntrue;elsereturnfalse;}//////////////////////////////////////////////////////////////////////*Name: main.cppAuthor:罗丹Description:主函数文件*/#include“stack.h“#include<iostream>#include<string>#include<fstream>usingnamespacestd;/*Description:外部函数的声明局部*/boolfindpath(int**maze,intm,intn); //查找迷宫路径voidPrintPath(stackp); voidRestore(int**maze,intm,intn); Movemove[4]={{0,1},{1,0},{0,-1},{-1,0}}; //4向(上，右，下，左)int**readFile(int&m,int&n);int**writeFile(int&m,int&n);/*Description:main.cpp*/voidmain{cout<<endl;//cout<<“◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆“<<endl;cout<<“ 2023-2023“<<endl;cout<<endl;cout<<“ “<<endl;cout<<“开发员:罗丹“<<endl;cout<<“专业班级:计算机061班“<<endl;cout<<“◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆“<<endl;cout<<“ 欢送进入迷宫玩耍 “<<endl;intm=0,n=0;int**maze;charch;intflag=0,flag1=0;while(flag1==0){while(flag==0)//标志是否重选择{cout<<endl;cout<<“★请从以下选项中选择猎取迷宫的方法！“<<endl;cout<<“ <a>从文件中读取“<<endl;cout<<“ <b>直接自行输入“<<endl;cout<<“★请选择:“;cin>>ch;if(ch==”a”){maze=readFile(m,n);flag=1;}elseif(ch==”b”){maze=writeFile(m,n);flag=1;}elsecout<<“★Sorry!您输入的选择代码不在范围内!请从选择“<<endl;}if(findpath(maze,m,n))cout<<“★Congratulations!迷宫路径探究成功!“<<endl;//得到路径elsecout<<“★Sorry!路径不存在★“<<endl;cout<<endl;cout<<“★连续玩吗？(y/n)“;charc;cin>>c;if(c==n)flag1=1;elseflag=0;}cout<<“◆◆◆◆◆◆◆感谢,您已经退出迷宫系统◆◆◆◆◆◆◆“<<endl;cout<<“◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆“<<endl;}/*Description:猎取迷宫函数*/int**readFile(int&m,int&n) //读出文件{int**maze;inti=0,j=0;cout<<“★您选择的是直接从文件中读取迷宫!“<<endl;cout<<endl;cout<<“ 文件中的迷宫如下： “<<endl;charch; //定义一个字符，读取文件中的内容ifstreamopen(“maze.txt“); //定义一个文件对象，并翻开文件“maze.txt“//读取内容记录行数和列数 〔创点一 ：从文件中直接读取迷宫〕while(open.get(ch)) //从读取文件中内容〔一旦个字符形式〕{if(ch==”0”||ch==”1”){j++;} //是‘0’或‘11if(ch==”\n”){i++; //1n=j; //得列数j=0;}}open.close; //读取文件完毕m=i;maze=newint*[m+2]; //2指针(为后面的回复迷宫打下根底)for(i=0;i<m+2;i++) //申请空间{maze[i]=newint[n+2];}i=j=1;ifstreamopen1(“maze.txt“); //重读取文件，以得到内容while(open1.get(ch)){if(ch==”1”||ch==”0”){maze[i][j]=ch-”0”; //把数字字符转化为数字，并存到指针里cout<<maze[i][j]<<““;//在屏幕中显示迷宫j++;}if(ch==”\n”)//遇到换行，指针也相应换行{cout<<endl;i++;j=1;}}open1.close;//读取完毕returnmaze;}int**writeFile(int&m,int&n) //将自定义迷宫写入文件{inta,b;inti,j;int**maze;cout<<“★您选择的是自行输入迷宫!“<<endl;cout<<“ 请输入迷宫的长:“;cin>>b; //输入迷宫的长和宽cout<<“ 请输入迷宫的宽:“;cin>>a;cout<<“★请输入迷宫内容(01):\n“;m=a;n=b; //m,n分别代表迷宫的行数和列数maze=newint*[m+2];for(i=0;i<m+2;i++){maze[i]=newint[n+2];} //创点二 ：:随便申请空间for(i=1;i<=m;i++) //输入迷宫的内容，01for(j=1;j<=n;j++)cin>>maze[i][j];cout<<“★是否保存迷宫？(y/n):“;charchoose;cin>>choose;if(choose==”Y”||choose==”y”){charch;stringstr;cout<<“★请输入保存迷宫的文件名(以.txtcin>>str;ofstreamopen(str.c_str); //：按玩玩耍人的意愿创立存储迷宫的文件，也可不建立。for(i=1;i<=m;i++){for(j=1;j<=n;j++){ch=”0”+maze[i][j];open<<ch;}open<<endl;flush(cout);}open.close;}for(i=0;i<m+2;i++)maze[i][0]=maze[i][n+1]=1;for(i=0;i<n+2;i++)maze[0][i]=maze[m+1][i]=1;returnmaze;}/*Description:探究路径函数*/boolfindpath(int**maze,intm,intn){stackq,p; //p、q,分别存探究迷宫的过程和存储路径DataTypeTemp1,Temp2;intx,y,loop;Temp1.x=1;Temp1.y=1;q.Push(Temp1); //将入口位置入栈p.Push(Temp1);maze[1][1]=-1; //标志入口位置已到达过while(!q.IsEmpty) //q{Temp2=q.GetPop;if(!(p.GetPop.x==q.GetPop.x&&p.GetPop.y==q.GetPop.y))p.Push(Temp2);//假设有位置入栈，则把上一个探究的位置存入栈pfor(loop=0;loop<4;loop++) //探究当前位置的4个相邻位置{x=Temp2.x+move[loop].x;y=Temp2.y+move[loop].y;if(maze[x][y]==0) //推断位置是否可达{Temp1.x=x;Temp1.y=y;maze[x][y]=-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); //〔由于迷宫里面的内容已被转变return1;}} //表示成功找到路径if(p.GetPop.x==q.GetPop.x&&p.GetPop.y==q.GetPop.y)//假设没有位置入栈，则返回到上一个位置{p.Pop;q.Pop;}}return0; //表示查