还剩15页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
南华大学计算机科学与技术学院课程设计报告(2022〜2022学年度第1学期)课程名称数据结构描述C++课程设计迷宫问题名称姓名罗丹学号20224440109专业计算机科学班级计算机班与技术01地点教师刘霞8—209正确结果输出:国“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.89,9,★迷宫路径探索成功,Congratulations★继续玩吗?〉“n y尽我所能LD接上面:国T E八课程设计、迷宫向蔻\Debug\迷宫同墨exe”以常人入入从选★是否保存新迷宫?y选★请输入除存迷宫的文件名(以・txt结俞请青煤请束)estl.txt宽容的清请内是宫宫宫★★迷宫的阵为的迷迷迷说明:括目内的内容分别表示为《行坐标,列坐标,方向)向下〉1,1,,向右)2-1向下)2,2,向右〉3,2,3,3,)★迷宫路径探索成功?Congratulations!★继续玩吗?y/ny★是否保存新迷宫?〉y/n y★请输入保存世宫的文件名以.八七结束〉est
2.txt请您霸★路径不存在去俞条Sorry请请一见容|+注《3t、12接上面:请的内是宫宫宫
5.实验总结分析的迷迷迷以猥苣入入入从选选
1、时间和空间分析该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比,迷宫长为m,宽为n,在最好情况下的时间和空间复杂度均为0m+n,在最差情况下均为0m*n,平均情况在它们之间
2、程序的优点a.进入演示程序后即显示文本方式的用户界面b.本程序模块划分比较合理,且利用指针存储迷宫,操作方便C,能按照玩游戏人的意愿任意输入迷宫大小,并且可以保存新输入的迷宫,方便退出游戏后仍可打开自己定义文件查看迷宫
3、遇到的问题及如何解决a.如何知道哪一点被探索过且路径不通?答maze[i][j]本来时表示通与不通,那末可以当探索该点之后,将其值赋为】就可以知道此点已经被访问过b,如何正确的使用文件读入迷宫?答查看大一学的C++课本,子细阅读文件那一章ba★★★★★★★b:ifwF«eb:033^44^1^::XX::033c.我想让用户在每次玩游戏之后都能查看输入的迷宫,我想的是运行程序时随意新建文本文档,开始是直接输入一个.txt结尾的字符串,但编译好多错误,我猜应该是要调用相关函数,但具体是那一个不清晰答去图书馆借阅相关资料,要调用相应的库函数4)、存在的缺陷、改进设想每当自行输入迷宫后,生成相应的文件保存,但是我在想一旦玩游戏的人多了,玩的次数多了,那末生成的保存迷宫文件就会不少,会给人工智能化系统造成文件冗余我设想能不能在一段时间之后系统自动调用函数来清除冗余文件5)、自我评价、经验体味等通过这次课程设计,体味如下
1、进一步熟悉掌握了有关栈的基本操作;
2、对迷宫有了更多的认识
3、更进一步掌握有关类的操作
4、由于对栈的算法推敲不足,使程序调试时费时不少总之我认为这次课程设计做的很好课程设计的成功使我相信一句话有付出就会有收获,要相信自己
6.附录(源程序清单,要求含有至少30%的源码附有注释)迷宫程序代码(本程序有个创新点)//////////////////////////////////////////////////////////////////////*Name:stack,hAuthor:罗丹Descr ipt ion:用于记录探索路径的栈类头文件*/#i ncIudei ostream#i ncIudefstreamus ingnamespace std;cI assDataType〃定义描述迷宫中当前位置的类型{pub Iic:int x;//x代表当前位置的行坐标int y;int pre;//y代表当前位置的列坐标1;//pre表示挪移到下一步的方向cI assMove〃定义下一个位置的方向{pub Iic:int x;int y;1;cI assNode〃链表结点{pubI ic:DataType data;Node*next;};〃下面定义栈cI assstack{pr ivate:Node*top;〃指向第一个结点的栈顶指针pub Iisct:ack;〃构造函数,置空栈〃析构函数stack;vo id PushDataType data;〃把元素data压入栈中DataType Pop;〃使栈顶元素出栈DataType GetPop;〃取出栈顶元素void Clear;〃把栈清空bool I sEmpty;〃判断栈是否为空,如果为空则返回1,否则返回0;//////////////////////////////////////////////////////////////////////*Name:stack.cppAuthor:罗丹Description:用于记录探索路径的栈类实现文件*/#incIudestack,hstack::stack〃构造函数,置空栈{top=NULL;}stack::〜stack〃析构函数void stack::Push DataTypex〃进栈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-next;Temp=TempNode-data;deIete TempNode;return Temp;DataType stack::GetPop{return top-data;}〃取出栈顶元素void stack::Clear{top=NULL;}〃把栈清空boo Istack::IsEmpty0//判断栈是否为空,如果为空则返回1,否则返回{iftop二二NULL returntrue;eIse returnfalse;}//////////////////////////////////////////////////////////////////////*Name:ma i n.cppAuthor:罗丹Descr ipt ion:主函数文件*/#includestack,h#i ncIudei ostream#i ncIudestr i ng#i ncIudefstreamusi ngnamespace std/*Description:外部函数的声明部份#/bool findpathint**maze,i nt m,i nt n;〃寻觅迷宫路径vo id Pr i ntPathstack p;〃输出路径void Restoreint**maze,int m,int n;〃恢复迷宫Move move
[4]={{0,1},{1,0},{0,-1},{-1,0}};〃定义当前位置挪移的4个方i ntn;i nt**wr iteFii ntn;/*向上,右,下,左i Dnets*c*rirpetadiFoin:main.cpp*/vo id maincout end I;//«”量加I;♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦cout2022-2022年度第一学期数据结构课程之课程设计«n end I;«coutendI;cout n迷宫问题«end I;«cout开辟员罗丹endl;«cout专业班级计算机061班endl;«cout n欢迎进入迷宫游戏n end I;««i ntm=0,n=0;i nt**maze;char ch;int flag=0,fIag1=0;whi Ieflag1==0{whi Iefl ag=0//标志是否重新选择[cout endI;«cout★请从以下选项中选择获取迷宫的方法!endl;««cout Ha从文件中读取“endI;«coutb直接自行输入“endl;«cout★请选择:;«c in ch;»i fch=二*a{maze=readF iIem,n;fIag=1;}eIse if ch==b{maze=wr iteFiIem,n;flag=1;}e Isecout★Sorry!您输入的选择代码不在范围内!请从新选择”endl;«i ff indpath maze,m,ncout★Congratulations!迷宫路径探索成功!endI;〃得到路径e Ise«coutilrSorry!路径不存在★〈〈endI;«coutendI;cout★继续玩吗?y/n“;«char c;cin c;»i fc==n fIag1=1;eIse fIag=0;谢谢,您已经退出迷宫系统/*Descr ipt ion:获取迷宫函数*/int**readFi Ie int m,int n〃读出文件{i nt**maze;int i=0,j=0;cout★您选择的是直接从文件中读取迷宫!endI;««coutendI;cout文件中的迷宫如下:endI;««char ch;〃定义一个字符,读取文件中的内容ifstream openmaze.txt;〃定义一个文件对象,并打开文件”maze,txt”〃读取内容记录行数和列数(创新点一从文件中直接读取迷宫)whileopen,get ch//从读取文件中内容(一旦个字符形式){ifch=,0|||ch=r{j++;}ifch-\n{〃是‘0’或者字符宽就加1i++;n=j;户0;〃如果是换行符,就行加1〃得列数]1〃读取文件结束open,c Iose;m=i;〃申请长度等于行数加2的二维maze二new i nt*[m+2];指针为后面的回复迷宫打下基础〃申请空间for i=0;im+2;i++{maze[i]=new i nt[n+2];}i二尸1;〃重新读取文件,以得到内容ifstream openlmaze.txt;whileopenl.get ch〃把数字字符转化为数字,并存ifch=r||ch=O{maze[i][j]=ch-O;〃在屏幕中显示迷宫到指针里cout maze[i][j];««〃遇到换行,指针也相应换行j++;}ifch==\n{cout endI;«if户;}〃读取结束1int**wr iteFiIei ntm,i ntn{int a,b;〃将自定义迷宫写入文件int i,j;i nt**maze;cout★您选择的是自行输入迷宫!endl;«cout请输入迷宫的长;ci nb;〃输入迷宫的长和宽«»cout请输入迷宫的宽n;ci na;«»cout★请输入迷宫内容0代表可通,1代表不通\rT;«m=a;n=b;//m,n分别代表迷宫的行数和列数maze=new i nt*[m+2];for i=0;im+2;i++{maze[i]=new i nt[n+2];〃创新点二随意申请空间fori=1i=m;i4-+〃输入迷宫的内容,0代表可通,1代表不通for j=1;j=n;j++cin maze[i][j];cout★是否保存新迷宫?y/n:;»«char choose;c inchoose;ifchoose=Y||choose=y{char ch;string str;cout n★请输入保存迷宫的文件名以.txt结束«ciin fstr!;p.GetPop.x二二q.GetPop.xp.GetPop.»〃仓新点二ljy p.Push Temp2;按玩游戏人的意愿创建存ofstream openstr.c_str;〃如果有新位置入栈,则把上一个探索的位置存入栈P储迷宫的文件,也可不建立fori=1;i=m;i++〃判断新位置是否可达{for j=1;j=n;j++{ch=0+maze[i][j];open ch;}〃标志新位置已到达过«openendI;〃新位置入栈fIush cout;}〃成功到达出口open,c Iose;}fori=0;im+2;i++maze[i]
[0]=maze[i][n+1]=1;for i=0;in+2;i++〃把最后一个位置入栈maze
[0][i]=maze[m+1][i]=1;return maze;}/*Description:探索路径函数*/nboo If indpathi nt**maze,intm,int〃创新点四用栈p、q,分别存探索迷宫的过{stack q,p;forloop=0;Ioop4;loop++程和存储路径DataType Tempi,Temp2;int x,y,loop;Tempi.x=1;Tempi.y=1;q.PushTempi;〃将入口位置入栈p.PushTempi;〃仓新点五:{x=Temp
2.lj标志入口位置已到达过maze
[1]
[1]=-1;x+move[Iwhi le!q.IsEmpty〃栈q非空,则反复探索oop].x;{Temp2=q.GetPop;y=Temp
2.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;p.Push Tempi;q.GetPop.y〃探索当前位置的4个相邻位置Pri ntPath p;Restore maze,m,n;//恢复路径因为迷宫里面的内容已被改变return1;}}〃表示成功找到路径if p.GetPop.x==q.GetPop.xp.GetPop.y==q.GetPop.y〃如果没有新位置入栈,则返回到上一个位置{p.Pop;q.Pop;}}return0;〃表示查找失败,即迷宫无路经/*Description:输出路径函数*/void PrintPathstackp〃输出路径{cout endI;«cout★★迷宫的路径为“endl;«cout说明:括号内的内容分别表示为行坐标,列坐标,方向\n“;«stack t;〃定义一个栈,按从入口到出口存取路径introw,co Iumn;DataType data;〃申请空间Node*temp;temp=new Node;〃第一个位置入栈temp-data=p.Pop;t.Pushtemp-data;〃栈P非空,则转移de Ietetemp;wh iI e!p.I sEmpty〃获取下一个位置{temp=new Node;temp-data=p.Pop;〃行坐标方向〃列坐〃得到行走方向标方向〃向下,用1表row=t.GetPop.x-temp-data.x;示//向右,用2表示〃co Iumn=t.GetPop.y-temp-data.y;向上,用3表不〃向左,i f row二二1temp一data.pre=1;用4表示〃把新位置入eIse if coIumn==1temp-data.pre=2;栈eIse ifrow==-1temp-data.pre=3;eIse if coIumn==-1temp-data.pre=4;t.Pushtemp-data;〃栈非空,继续输出de Ietetemp;wh iI e!t.I sEmpty{data=t.Pop;cout n*data.x*,*data.y,;««««««switch data,pre〃输出相应的方向{case0:cout\n;break;«case1::cout n向下\n;break;«case2:cout“向右\n”;break;case3: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)、软件、硬件环境软件环境Microsoft WindowsXp Processional2002ServiceMicrosoft VisualC++
6.0硬件环境cpu AMDAthlon(tm)64x DualProcessor3800+
2.01GHz Mainmemory:960MB
1.实验步骤a.认真阅读课本的相关知识章节b.认真分析课题的需求分析和功能分析c.根据分析的思路写出伪代码d.根据伪代码上机编写程序,进行初步调试e.逐步增加完善系统的功能,实现人工智能化f.记录上机运行时遇到的错误,进行认真分析g.最后认真撰写实睑报告,写出实验心得总结/*Descr iption:恢复路径函数*/void Restoreint**maze,intm,intn〃恢复迷宫{int i,j;fori=0;im+2;i++〃遍历指针forj=0;jn+2;j++〃恢复探索过位置,即把7恢复为0{if maze[i]Ej]==-1maze[i][j]=0;}}
2.实验内容
1、设计概述a开辟平台VC
6.0b参考书籍
1.数据结构C++描述熊岳山陈怀义编著国防科技大学出版社
2、《数据结构与算法》黄定黄煜廉编著广东科技出版社2000年1月第1版
3、《数据结构辅导与提高》徐孝凯编著清华大学出版社2003年12月第1版c开辟周期10天构思3天、雏形3天、修改2天、再修改1天、完善1天
2、处理流程a画出功能结构图b画出主要数据结构的类图Class类名DataType//定义描述迷宫中当前位置的类型数据访问控制权限数据类型变量名;成员pub Iic:int x;//x代表当前位置的行坐标int y;//y代表当前位置的列坐标int pre;//pre表小挪移到下步的方向clasq类名Move〃定义下一个位置的方向数「访问控制权限数据类型变量名;据pub Iic:成int x;员int y;Class类名Node__________________〃结点数访问控制权限数据类型变量名;据pub Iic:成DataType data;员Node*next;class类名stack成访问控制权限返回值类型函数名参数列表数访问控制权限数据类型变量名;DataType Pop;pub Iic:据pr ivate:DataType GetPop;成stack0;〃指向第一个结点的栈顶指针〃构造函数,置空栈Node*top;void Clear;员stack;〃析构函数void PushboolIsEmpty;DataTypedata;〃把元素data压入栈中返回0〃使栈顶元素出栈〃取出栈顶元素〃把栈清空〃判断栈是否为空,如果为空则返回1,否则()C主要函数的程序流程图
1.main函数流程图▼自行输入Readfile文件读取▼Writefile
2.探索路径函数findpath Tempi.x=1Tempi.y=1入口进栈p.pushq.pushd写出数据测试表输入数据/预期结果测试一从文件中读取迷宫001000100001000101000011000011100100000100001010001010011110011110001011110000000输出测试二探索路径:自己输入迷宫:
一、向下下向下右右船向输出探索路径:右右向下上右测试三右下右下右向自己输入迷宫向下下向向下右向111向右111向000向输出探索路径向Sorry!找不到路径!向.实验结果4向结果为以下三种情形之一向1编译不通过给出编译错向Compiling...向stack.cpp向Skipping...no relevantchanges detectedmain.cppLinking...stack.obj:error LNK2005:public:_thiscall stack::stackvoid Ostack@@QAE@XZ alreadydefined in main.objstack,obj error LNK2005:public:_thiscall stack::~stack void1stack@@QAE@XZ alreadydefined inmain.objstack.obj:error LNK2005:public:void_thiscall stack::Pushstruct DataTypePush@stack@@QAEXUDataType@@@Z alreadydefined inmain.objstack.obj:error LNK2005:public:struct DataType_thiscall stack::Popvoid”Pop@stack@@QAEAUDataType@@XZ alreadydefined inmain.objstack.obj:errorLNK2005:public:struct DataType_thiscall stack::GetPopvoidGetPop@stack@@QAEAUDataType@®XZ alreadydefined inmain.objstack,obj errorLNK2005:public:void_thiscall stack::Clear voidClear@stack@@QAEXXZ alreadydefined inmain.objstack,obj errorLNK2005:public:bool_thiscall stack::IsEmptyvoidlsEmpty@stack@@QAE_NXZ alreadydefinedinmain.objDebug/迷宫问题.exe:fatal errorLNK1169:one ormore multiplydefined symbolsfound执行link.exe时出错.迷宫问题.exe-1errors,0wamings在main cpp中原来包含的是stack.cpp把它改为包含stack.h即可o错误二用string直接定义字符串str时,说没有定义str原因#includestringusing namespacestd;没实用标准空间错误三拼写错误5543\/\/\/\/999876555666xz\/XI/\l/z\/\/\/\/\/\/\/\l/z52191817777765543/\,,,,,,,,,,,3221,,,,2211\/\/\/\/TI/71X\77\\77\\/71\\/7\\//\\7\/\/X7\/\/\7\71\7\7\OOOO1O1OS3。