迷宫问题课程设计报告

南华大学计算机科学与技术学院课程设计报告（2022〜2022学年度第1学期）课程名称数据结构C++描述课程设计迷宫问题名称姓名罗丹 学号20224440109专业计算机科学班级计算机01班与技术地点8—209教师刘霞正确结果输出:Jelx国“E:\课程设计、迷宫问蔻\Debug\迷宫HS.exe-Jelx・♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦2007—2008年度第一学期数据结构课程之课程设计一一迷宫问题开发员:罗丹专亚班级:计算机。61班♦♦♦♦*♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦欢迎进入迷宫游戏★请从以下选项中选择获取迷宫的方法!从文件中瘦率一*W直接自行输入★请选择:a★您选装的是直接从文件中读取迷宫？文件中的迷宫如下:001000100001000101e00011000B11100100a00100001B10001010B11110011110001011110000000★★迷宫的阵为说明:括身内的内容分别表示为《行坐标，列坐标，方向〉<2,1,向下〉<3,1.向下〉<4,1，向下〉《5,1,向右〉5.2.向右〉5,3,向下〉6,3,向右〉6.4,向右〉.向上〉《5,5,向右）<5,6,向右）<5,7,向下〉“，乙向下〉《乙乙向下〉向下〉<9,7,向右〉<9.8.向右》<9,9,>★Congratulations?迷宫路径探索成功，★继续玩吗？<“n〉yLD尽我所能接上面:国TE八课程设计、迷宫向蔻\Debug\迷宫同墨exe”俞330::XXe宽容^1^的内是宫宫宫:b的迷迷迷以<a<b常人入入从选选请青煤请清请★★★★★是否保存新迷宫？ y★请输入除存迷宫的文件名（以・txt结束）"estl.txt★★迷宫的阵为说明:括目内的内容分别表示为《行坐标，列坐标,方向）<1,1,向下〉<2-1，向右）<2,2,向下）<3,2,向右〉<3,3,）★Congratulations!迷宫路径探索成功？★继续玩吗？<y/n>y«霸Fw>fi:b的迷迷迷以猥苣入入入从选选俞330条::(一^44见容的内是宫宫宫请您请请请★★★★是否保存新迷宫？<y/n〉：y★请输入保存世宫的文件名<以.八七结束〉"est2.txt★Sorry?路径不存在去|+注《3t、12接上面:5.实验总结分析1)、时间和空间分析该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比，迷宫长为m,宽为n,在最好情况下的时间和空间复杂度均为0(m+n),在最差情况下均为0(m*n),平均情况在它们之间2)、程序的优点a.进入演示程序后即显示文本方式的用户界面b.本程序模块划分比较合理，且利用指针存储迷宫，操作方便。C,能按照玩游戏人的意愿任意输入迷宫大小，并且可以保存新输入的迷宫，方便退出游戏后仍可打开自己定义文件查看迷宫。3)、遇到的问题及如何解决a.如何知道哪一点被探索过且路径不通？答：maze[i][j]本来时表示通与不通，那末可以当探索该点之后，将其值赋为】就可以知道此点已经被访问过b,如何正确的使用文件读入迷宫？答：查看大一学的C++课本，子细阅读文件那一章。c.我想让用户在每次玩游戏之后都能查看输入的迷宫，我想的是运行程序时随意新建文本文档，开始是直接输入一个.txt结尾的字符串，但编译好多错误，我猜应该是要调用相关函数，但具体是那一个不清晰。答：去图书馆借阅相关资料，要调用相应的库函数。4）、存在的缺陷、改进设想每当自行输入迷宫后，生成相应的文件保存，但是我在想：一旦玩游戏的人多了，玩的次数多了，那末生成的保存迷宫文件就会不少，会给人工智能化系统造成文件冗余。我设想：能不能在一段时间之后系统自动调用函数来清除冗余文件。5）、自我评价、经验体味等通过这次课程设计，体味如下：1、进一步熟悉掌握了有关栈的基本操作；2、对迷宫有了更多的认识3、更进一步掌握有关类的操作4、由于对栈的算法推敲不足，使程序调试时费时不少总之：我认为这次课程设计做的很好。课程设计的成功使我相信一句话：有付出就会有收获，要相信自己。6.附录（源程序清单，要求含有至少30%的源码附有注释）迷宫程序代码（本程序有个创新点）//////////////////////////////////////////////////////////////////////*Name: stack,hAuthor:罗丹Description:用于记录探索路径的栈类头文件*/incIude<iostream>incIude"fstream"usingnamespacestd;cIassDataType{pubIic:intx;inty;intpre;1；〃定义描述迷宫中当前位置的类型//x代表当前位置的行坐标//y代表当前位置的列坐标//pre表示挪移到下一步的方向cIassMove{pubIic:intx;inty;1；〃定义下一个位置的方向cIassNode{pubIic:DataTypedata;Node*next;}；〃链表结点〃下面定义栈

cIassstack

{private:

Node*top;〃指向第一个结点的栈顶指针pubIic:stack();"stack();〃构造函数，置空栈〃析构函数voidPush(DataTypeDataTypePop();DataTypeGetPop();voidClear();boolIsEmpty();)；data);〃把元素data压入栈中〃使栈顶元素出栈〃取出栈顶元素〃把栈清空〃判断栈是否为空，如果为空则返回1,否则返回0//////////////////////////////////////////////////////////////////////*Name: stack.cppAuthor:罗丹Description:用于记录探索路径的栈类实现文件*/#incIude"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;deIeteTempNode;returnTemp;)DataTypestack::GetPop(){returntop->data;}voidstack::Clear(){top=NULL;}〃取出栈顶元素〃把栈清空booIstack::IsEmpty()0//判断栈是否为空，如果为空则返回1,否则返回{if(top二二NULL)returntrue;eIsereturnfalse;}//////////////////////////////////////////////////////////////////////*Name: main.cppAuthor:罗丹Description:主函数文件*/#include"stack,h"incIude<iostream>incIude<string>incIude<fstream>usingnamespacestd/*Description:外部函数的声明部份/〃寻觅迷宫路径〃输出路径〃寻觅迷宫路径〃输出路径〃恢复迷宫〃定义当前位置挪移的4个方voidPrintPath(stackp);voidRestore(int**maze,intm,intn);Movemove[4]={{0,1},{1,0},{0,-1},{-1,0}};向(上，右，下，左)int**readFiint**writeFi/*int&n);int&n);int**readFiint**writeFi/*int&n);int&n);Description:main.cpp*/voidmain()(cout«endI;//。。"”♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦量加I;cout«" 2022-2022年度第一学期数据结构课程之课程设计n«endI;cout<<endI;cout«n迷宫问题"«endI;cout«"开辟员：罗丹"<<endl;cout«"专业班级：计算机061班"<<endl;cout«n欢迎进入迷宫游戏 n«endI;intm=0,n=0;int**maze;charch;intflag=0,fIag1=0;whiIe(flag1==0){whiIe(flag=0)//标志是否重新选择[cout«endI;cout«"★请从以下选项中选择获取迷宫的方法！"«endl;cout«H <a>从文件中读取“<<endI;cout«" <b>直接自行输入“<<endl;cout«"★请选择:"；cin»ch;if(ch=二*a'){maze=readFiIe(m,n);fIag=1;}eIseif(ch=='b'){maze=writeFiIe(m,n);flag=1;}eIsecout«"★Sorry!您输入的选择代码不在范围内！请从新选择”<<endl;)if(findpath(maze,m,n))cout«"★Congratulations!迷宫路径探索成功！"<<endI;〃得到路径eIsecout«"ilrSorry!路径不存在★"〈〈endI;cout<<endI;cout«"★继续玩吗？(y/n)“；charc;cin»c;if(c==n)fIag1=1;eIsefIag=0;)谢谢,您已经退出迷宫系统)/*Description:获取迷宫函数*/int**readFiIe(int&m,int&n) 〃读出文件{int**maze;inti=0,j=0;cout«"★您选择的是直接从文件中读取迷宫!"«endI;cout<<endI;"«endI;〃定义一个字符，读取文件中的内容〃定义一个文件对象，并打开文件”maze,txt”"«endI;〃定义一个字符，读取文件中的内容〃定义一个文件对象，并打开文件”maze,txt”（创新点一：从文件中直接读取迷宫）//从读取文件中内容（一旦个字符形式）〃是‘0’或者字符宽就加1〃如果是换行符，就行加1〃得列数charch;ifstreamopen("maze.txt");〃读取内容记录行数和列数while(open,get(ch)){if(ch=,0|||ch='r){j++；}if(ch-'\n'){i++;n=j；户0;]1]1open,cIose();m=i;maze二newint*[m+2];指针(为后面的回复迷宫打下基础)for(i=0;i<m+2;i++){maze[i]=newint[n+2];}i二尸1；ifstreamopenl("maze.txt");while(openl.get(ch))(if(ch='r||ch='O'){maze[i][j]=ch-'O';到指针里cout«maze[i][j]«" ";j++；}if(ch=='\n'){cout«endI;if户；}1openl.cIose();returnmaze;)〃读取文件结束〃申请长度等于行数加2的二维〃申请空间〃重新读取文件，以得到内容〃把数字字符转化为数字，并存〃在屏幕中显示迷宫〃遇到换行，指针也相应换行〃读取结束〃将自定义迷宫写入文件int**writeFiIe(int&m,int&n){inta,b;〃将自定义迷宫写入文件inti,j;int**maze;cout«"★您选择的是自行输入迷宫！"<<endl;cout«" 请输入迷宫的长："；cin»b; 〃输入迷宫的长和宽cout«" 请输入迷宫的宽：n；cin»a;cout«"★请输入迷宫内容(0代表可通，1代表不通)：\rT;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;i4-+) 〃输入迷宫的内容，0代表可通，1代表不通for(j=1;j<=n;j++)cin»maze[i][j];cout«"★是否保存新迷宫？(y/n):";charchoose;cin>>choose;if(choose='Y'||choose='y'){charch;stringstr;cout«n★请输入保存迷宫的文件名(以.txt结束)：cin»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<<endI;fIush(cout);}open,cIose();}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;}〃仓lj新点二：按玩游戏人的意愿创建存

储迷宫的文件，也可不建立。/*Description:探索路径函数*/booIfindpath(int**maze,intm,intn){stackq,p;〃创新点四：用栈p、q,分别存探索迷宫的过

程和存储路径DataTypeTempi,Temp2;intx,y,loop;Tempi.x=1;Tempi.y=1;q.Push(Tempi);p.Push(Tempi);〃将入口位置入栈maze[1][1]=-1;while(!q.IsEmpty())

{Temp2=q.GetPop();〃仓lj新点五:标志入口位置已到达过〃栈q非空，则反复探索ifif(!(p.GetPop().x二二q.GetPop().x&&p.GetPop().yp.Push(Temp2);〃如果有新位置入栈，则把上一个探索的位置存入栈Pfor(loop=0;Ioop<4;loop++)

{x=Temp2.x+move[Ioop].x;

y=Temp2.y+move[Ioop].y;if(maze[x][y]==0){Tempi.x=x;Tempi.y=y;maze[x][y]二-1;q.Push(Tempi); }if((x=(m))&&(y==(n))){Tempi.x=m;Tempi.y=n;Tempi.pre=0;Push(Tempi);GetPop().y))〃探索当前位置的4个相邻位置〃判断新位置是否可达〃标志新位置已到达过〃新位置入栈〃成功到达出口〃把最后一个位置入栈〃申请空间〃第一个位置入栈〃申请空间〃第一个位置入栈〃栈P非空，则转移〃获取下一个位置〃行坐标方向〃列坐标方向〃向下，用1表示//向右，用2表示〃向上，用3表不〃向左，用4表示〃把新位置入栈〃栈非空，继续输出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; 〃表示查找失败，即迷宫无路经/*Description:输出路径函数*/voidPrintPath(stackp) 〃输出路径{cout«endI;cout«"★★迷宫的路径为“<<endl;cout«" 说明:括号内的内容分别表示为(行坐标，列坐标,方向)\n“；stackt; 〃定义一个栈，按从入口到出口存取路径introw,coIumn;DataTypedata;Node*temp;temp=newNode;temp->data=p.Pop();t.Push(temp->data);deIetetemp;whiIe(!p.IsEmpty()){temp=newNode;temp->data=p.Pop();〃得到行走方向row=t.GetPop().x-temp->data.x;coIumn=t.GetPop().y-temp->data.y;if(row二二1)temp一)data.pre=1;eIseif(coIumn==1)temp->data.pre=2;eIseif(row==-1)temp->data.pre=3;eIseif(coIumn==-1)temp->data.pre=4;t.Push(temp->data);deIetetemp;whiIe(!t.IsEmpty()){data=t.Pop();cout«n "«'(*«data.x«*,*«data.y«",";switch(data,pre) 〃输出相应的方向{case0:cout«")\n";break;:cout«n向下)\n";break;cout<<“向右)\n”；break;cout«"|°]Jl)\n";break;case4:cout<<“向左)\n”；break;}}}1.实验目的及要求1）、设计目标（问题描述）迷宫问题问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成为了多处阻挡。盒子仅有一个出口,在出口处放置一块奶酪，吸引老鼠在迷宫中寻觅道路以到达出口。对同一只老鼠重复进行上述实验，向来到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。2）、功能设计要求编写一个程序求解迷宫问题。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1,1）,出口为（m,n）,每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或者得出没有通路的结论。算法输入：代表迷宫入口的坐标算法输出：穿过迷宫的结果。算法要点：创建迷宫，试探法查找路径，输出解3）、实验目的1、加深对栈特性理解，以便在解决实际问题中灵便运用它们2、加深对栈操作实际算法的理解3、进一步熟悉掌握链表的操作；4、掌握指针的应用5、更进一步掌握有关类的操作4）、需求分析1、本程序实现迷宫的探索过程.以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。2、本演示程序中，输入形式以“回车符”为结束标志，且允许浮现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每一个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径5）、创新（见源程序附录）6）、软件、硬件环境软件环境：MicrosoftWindowsXpProcessional2002ServiceMicrosoftVisualC++6.0硬件环境：cpu：AMDAthlon（tm）64xDualProcessor3800+2.01GHzMainmemory:960MB.实验步骤a.认真阅读课本的相关知识章节。b.认真分析课题的需求分析和功能分析。c.根据分析的思路写出伪代码。d.根据伪代码上机编写程序，进行初步调试。e.逐步增加完善系统的功能，实现人工智能化。f.记录上机运行时遇到的错误，进行认真分析。g.最后认真撰写实睑报告，写出实验心得总结。/*Description:恢复路径函数*/voidRestore(int**maze,intm,intn) 〃恢复迷宫{inti,j;for(i=0;i<m+2;i++)for(j=0;j<n+2;j++){if(maze[i]Ej]==-1)〃遍历指针〃恢复探索过位置，即把7恢复为0maze[i][j]=0;}}.实验内容1)、设计概述(a)开辟平台：VC6.0(b)参考书籍：1.数据结构C++描述熊岳山陈怀义编著国防科技大学出版社2、《数据结构与算法》黄定黄煜廉编著广东科技出版社2000年1月第1版3、《数据结构辅导与提高》徐孝凯编著清华大学出版社2003年12月第1版(c)开辟周期：10天(构思3天、雏形3天、修改2天、再修改1天、完善1天)2)、处理流程(a)画出功能结构图(b)画出主要数据结构的类图Class类名DataType //定义描述迷宫中当前位置的类型数据成员访问控制权限数据类型变量名；pubIic:intx; //x代表当前位置的行坐标inty; //y代表当前位置的列坐标intpre; //pre表小挪移到下步的方向clasq类名Move 〃定义下一个位置的方向数「访问控制权限数据类型变量名；据pubIic:成 intx;员 inty;Class类名Node 〃结点数访问控制权限数据类型变量名;据pubIic:成DataTypedata;员Node*next;class类名stack数

据

成

员访问控制权限数据类型变量名;private:Node*top;〃指向第一个结点的栈顶指针成访问控制权限返回值类型函数名(参数列表)pubIic:stack0； 〃构造函数，置空栈"stack(); 〃析构函数voidPush(DataTypedata);〃把元素data压入栈中DataTypePop();DataTypePop();DataTypeGetPop();voidClear();boolIsEmpty();返回0〃取出栈顶元素〃把栈清空〃判断栈是否为空，如果为空则返回1,否则（C）主要函数的程序流程图1.main函数流程图：▼▼自行输入Writefile()Readfile()

文件读取2.探索路径函数findpath()Tempi.x=1Tempi.y=1入口进栈p.pushq.push(d)写出数据测试表(输入数据/预期结果)测试一：从文件中读取迷宫：001000100001000101000011000011100100000100001010001010011110011110001011110000000\)/\7\17\7\7\17一、\)/\7X)/\)/\7\)/\)/\)/\7\7X)/IT下下下右右船右右上右右下下下下右右向向向向向向向向向向向向向向向1112,,,,,,,,,,,\)/3455677777893455/(\/(\/(\/(\(5666555678999z/l\/(\/(\/(\/(\/(\/(\/(\z/l\/IX/(\z(x输出：

探索路径:11OS3OOOO1OC测试二：自己输入迷宫:输出探索路径:\7\7\17\7下右下右向向向向1122,,,,1223/(\/(\/(\/(\\)/3测试三：自己输入迷宫：111111000输出探索路径：Sorry!找不到路径!4.实验结果结果为以下三种情形之一：1)编译不通过：给出编译错。Compiling...stack.cppSkipping...(norelevantchangesdetected)main.cppL