迷宫游戏数据结构课程设计.doc
《迷宫游戏数据结构课程设计.doc》由会员分享,可在线阅读,更多相关《迷宫游戏数据结构课程设计.doc(23页珍藏版)》请在咨信网上搜索。
1、计算机解迷宫问题通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。迷宫的入口点的下标为(1,1),出口点的下标为(m,n)。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫的任一位置,均可约定有东、南、西、北四个方向可通。有一种简单走出迷宫的方法,把手放在右边的墙上开始前进,始终不要把手从墙上移开。如果迷宫向右拐,你也顺着墙向右拐。只要不把手从墙上移开,最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径,但它
2、可以最终得到结果,换句话说,这种方法走不出迷宫的风险是最小的。本设计是为了实现一个可视化迷宫,以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上,并且限制小老鼠不能穿越墙,只能在路径上移动。而且可以根据自己的需要设计迷宫地图。关键词 迷宫;栈;VC+ 6.0 目录1 课设题目11.1课设题目.11.2基本要求:.11.3 需求分析12 程序总体设计22.1流程图:.22.2概要设计.62.3 运行结果及分析7总结9源程序10参考文献201 课设题目1.1课设题目编写一个程序求解迷宫问题。迷宫由m行n列的二维数组设置,0表示无障碍,1表示有障碍。设入口为(1,1),出口为(m,n),每
3、次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。算法输入:代表迷宫入口的坐标算法输出:穿过迷宫的结果。算法要点:创建迷宫,试探法查找路径,输出解1.2基本要求:1.求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一个坐标的方向。2.输出迷宫示意图1.3 需求分析1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令,然后程序就探索路径并输出路径。 2、本演示程序中,输入形式以“回车符
4、”为结束标志,且允许出现重复字符。3、利用二维指针实现迷宫位置的存储,并用栈存贮探索路径,每个结点含三个整形变量。输入的形式以回车结束。4、本程序中,用户可以读去文件里的迷宫,也可自己重新输入迷宫,而且用户可以输入任意大小的迷宫,然后程序自动探索路径,并输出迷宫的路径。2 程序总体设计2.1流程图:1.功能结构图Main主函数模块输出路径模块printpath()获取迷宫模块探索路径模块Findpath()存储探索路径模块stack类读文件Readfile()写文件Writefile()Stack类数据模块操作模块盘空函数isempty()清空函数clear()取栈顶函数getpop()进栈与
5、出栈函数push()Pop()构造与析构函数stack()stack()结点模块Node*top结点数据类型模块datatype类2.画出主要数据结构的类图class 类名DataType /定义描述迷宫中当前位置的类型数据成员访问控制权限 数据类型 变量名; public:int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int dir; /dir表示移动到下一步的方向 class 类名Move /定义下一个位置的方向数据成员访问控制权限 数据类型 变量名; public:int x; int y;class 类名Node /结点数据成员访问控制权限 数据类型
6、变量名; 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();
7、 /判断栈是否为空,如果为空则返回1,否则返回0开始 3.main函数流程图 显示系统信息选择获取迷宫的方式chCh= bCh=aReadfile()文件读取自行输入Writefile()探索迷宫路径是否存在输出迷宫路径是否继续游戏退出开始2.探索路径函数findpath()Temp1.x=1Temp1.y=1入口进栈p.pushq.push是否非空temp2=q.getpop()P q栈顶是否相等探索上下左右四个方位是否有路径到达新位置是否到达出口最后一个元素进栈输出路径回复以改变的迷宫结束开始3.自行输入迷宫函数writefile()输入长宽m,n动态申请空间二位数组空间i=m是否保存迷宫
8、J=ni+ ;j+输入迷宫输入保存迷宫的文件名保存迷宫结束2.2概要设计1.构建一个二维数组mazeM+2N+2用于存储迷宫矩阵自动或手动生成迷宫,即为二维数组mazeM+2N+2赋值构建一个队列用于存储迷宫路径建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况实现搜索算法屏幕上显示操作菜单 2.本程序包含10个函数: (1)主函数 main()(2)手动生成迷宫函数 shoudong_maze()(3)打印迷宫路径 (若存在路径) result_maze()(4)入队 enqueue()(5)出队 dequeue()(6)判断队列是否为空 is_empty()(7)访问节
9、点 visit()(8)搜索迷宫路径 mgpath()2.3 运行结果及分析 总结通过这段时间的数据结构课程设计,本人对计算机的应用,数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践,没有实践就无法真正理解这些知识以及掌握它们,使其成为自己的财富。在理论学习和上机实践的各个环节中,通过自主学习和认真听老师讲课分析,我收获了不少。当然也遇到不少的问题,也正是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序,从当初拿着程序不只如何下手到现在知道如何分析问题,如何用专业知识解决实际问题的转变,我发现无论是专业知识还
10、是动手能力,自己都有很大程度的提高。在这段时间里,我对for、while等的循环函数用法更加熟悉,逐渐形成了较好的编程习惯。在老师的指导帮助下,同学们课余时间的讨论中,这些问题都一一得到了解决。在程序的调试能力上,无形中得到了许多的提高。例如:头文件的使用,变量和数组的范围问题,定义变量时出现的问题等等。在实际的上机操作过程中,不仅是让我们了解数据结构的理论知识,更重要的是培养解决实际问题的能力,所以相信通过此次实习可以提高我们分析设计能力和编程能力,为后续课程的学习及实践打下良好的基础。时间过得真快,大学生活不知不觉就走过了一学期,这一学期的大学学习和课程实践阶段的提高,使我们本身知识得到提
11、高的同时,也增强了我们对未来工作的信心,我们相信自己未来两年半的学习更使我们有能力胜任将来的工作。源程序#includeusing namespace std; class T/定义描述迷宫中当前位置的结构类型public:int x;/x代表当前位置的行坐标int y;/y代表当前位置的列坐标int dir;/0:无效,1:东,2:南,3:西,4:北; class LinkNode/链表结点friend class Stack;public:T data;LinkNode *next; class Stackprivate:LinkNode *top;/指向第一个结点的栈顶指针public:
12、Stack();/构造函数,置空栈Stack()/析构函数void Push(T e);/元素data入栈中T Pop();/栈顶元素出栈T GetPop();/取出栈顶元素void Clear();/把栈清空bool empty();/判断栈是否为空,如果为空则返回1,否则返回0; Stack:Stack()/构造函数,置空栈top=NULL; void Stack:Push(T e)/元素x入栈中LinkNode *P;P=new LinkNode;P-data=e;P-next=top;top=P; T Stack:Pop()/栈顶元素出栈T Temp;LinkNode *P;P=top
13、;top=top-next;Temp=P-data;delete P;return Temp; T Stack:GetPop()/取出栈顶元素return top-data; void Stack:Clear()/把栈清空top=NULL; bool Stack:empty()/判断栈是否为空,如果为空则返回1,否则返回0if(top=NULL) return 1;else return 0; int move42=0,1,1,0,0,-1,-1,0;/定义当前位置移动的4个方向 void PrintPath(Stack p)/输出路径cout迷宫的路径为n;coutdata=p.Pop();
14、/取栈p的顶点元素,即第一个位置t.Push(temp-data);/第一个位置入栈tdelete temp;/释放空间while(!p.empty()/如果栈p非空,则反复转移temp=new LinkNode;temp-data=p.Pop();/获取下一个位置/得到行走方向a=t.GetPop().x-temp-data.x;/行坐标方向b=t.GetPop().y-temp-data.y;/列坐标方向if(a=1) temp-data.dir=1;/方向向下,用1表示else if(b=1) temp-data.dir=2;/方向向右,用2表示else if(a=-1) temp-da
15、ta.dir=3;/方向向上,用3表示else if(b=-1) temp-data.dir=4;/方向向左,用4表示t.Push(temp-data);/把新位置入栈delete temp;/输出路径,包括行坐标,列坐标,下一个位置方向while(!t.empty()/栈非空,继续输出data=t.Pop();cout(data.x,data.y,data.dir,;/输出行坐标,列坐标switch(data.dir)/输出相应的方向 case 1:cout)n;break;case 2:cout)n;break;case 3:cout)n;break;case 4:cout)n;break
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 迷宫 游戏 数据结构 课程设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。