还剩43页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
西安建筑科技大学课程设计(论文)题目可视化走迷宫游戏院(系)专业班级姓名学号指导教师2011年9月15日西安建筑科技大学课程设计(论文)任务书专业班级计算机901学生姓名指导教师(签名)
一、课程设计(论文)题目走迷宫游戏程序开始运行时显示一个迷宫地图,迷宫__有____,迷宫的右__有一个粮仓游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处
二、本次课程设计(论文)应达到的目的数据结构是实践性很强的课程课程设计是加强学生实践能力的一个强有力手段课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告严格实施课程设计这一环节,对于学生基本程序设计素养的培养和软件工__工作作风的训练,将起到显著的促进作用本题目要达到目的熟练掌握最短路径的算法设计
三、本次课程设计(论文)任务的主要内容和要求(包括原始数据、技术参数、设计要求等)老鼠形象可辨认,可用键盘操纵老鼠上下左右__;迷宫的墙足够结实,老鼠不能穿墙而过;正确检测结果,若老鼠在规定时间内走到粮仓处,提示成功,否则提示失败;添加编辑迷宫功能,可修改当前迷宫,修改内容墙变路、路变墙;找出走出迷宫的所有路径,以及最短路径
四、应收集的资料及主要____由于本课程没有安排“课内上机”学时,因此,在课程设计之前必须自己已经上机练习了“线性表”的基本操作____
1.本年级使用的教材数据结构与算法分析(C++版)(第二版)影印版
2005.
72.数据结构与算法,科学出版社,
2005.08;赵文静祁飞等编著
3.数据结构-C++语言描述,西安交通大学出版社,
1999.01,赵文静编著
4.《VisualC++编程实例》任意一本此类书籍
1.地图要求根据要求构造一个迷宫地图,并且是老鼠清晰可见,可用键盘操纵老鼠上下左右__;有一个窗口显示部分地图,另一个窗口显示全部题图
2.操作老鼠不能穿墙而过,当老鼠到达粮仓提示成功可以自动找到迷宫的所有路径以及画出最短路径三.需求分析
1.利用mfc可以把迷宫地图以及老鼠形象可变的画出来
2.需要有墙有路,通过把迷宫地图划分成一个一个小方块,通过一个数组的值来判断是墙是路(1表示墙0表示路)3.通过鼠标__控制老鼠的__4.把每个数组元素对应一个按钮根据__按钮,改变数组的值从而改变墙和路的转化四.概要设计图1程序界面图
4.
1、操作界面利用mfc单文档初始化界面,设置meau选项,以及分割成大小两个窗口
4.
2、用户的登陆界面利用对话框设计用户登陆界面,界面包括用户名,选择的迷宫级别
4.
3、地图的绘制根据登陆界面的上面的信息,绘制迷宫地图选择加载全图菜单会显示迷宫总图
4.
4、游戏音乐的设置在迷宫加载之后,播放背景音乐,利用多线程异步播放
4.
5、小老鼠键盘操作利用键盘__,完成小老鼠的操作
4.
6、全图与部分的同步利用CFrameWnd类实现两个view类的同步操作
4.
7、搜索迷宫路径及最短路径的显示选择‘路径‘菜单利用递归搜索出迷宫所有路径并且把最短路径绘制在全图显示中
4.
8、编辑迷宫地图利用对话框中每一个按钮对用迷宫的一部分,编辑迷宫地图
4.
9、层次序遍历算法按照树的层次从左到右访问树的结点,层序遍历用于保存结点的容器是队列voidLevelOrderBiNoderoot
4.
10、树与二叉树的转换算法转换时结点的第一个孩子变为它的左孩子,兄弟节点变为他的有孩子voidexchange,classTree
4.
11、结束界面利用选继续还是结束游戏作为结束画面,__继续级别将自动加
1.五.详细设计
5.
1、各模块流程图图1游戏界面显示图2小老鼠操作图
3、全图与部分图的同步图
4、迷宫路径以及最短路径图
5、后序递归遍历图
6、前序非递归遍历图
7、中序非递归遍历图
8、后序非递归遍历图
9、层次序非递归遍历
5.
2、源程序我真诚地保证我自己__地完成了整个程序从分析、设计到编码的全过程如果在上述过程中,我遇到了困难而求教于人,那么,我将在程序报告中详细地列举我所遇到的问题,以及别人给我的提示我的程序里中凡是引用到其他程序或文档之处,例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段我都已经在程序的注释里很清楚地注明了引用的出处我从未抄袭过别人的程序,也没有盗用别人的程序,无论是修改式地抄袭还是原封不动地抄袭我编写这个程序,从来没有想过要去破坏或妨碍其他计算机系统的正常运转#includeiostreamusingnamespa__std;#includestdlib.h#include__th.h#includewindows.h//包涵暂停函数的头文件#define__xIsize100#includetree.h#defineLENsizeofstructbtreeint__xI=1;typedefstructbtree//二叉树节点结构体{btree*lchild*rchild;chardata;}*BiNode;typedefstructStackElemType//栈的结构体{BiNodeptr;intflag;}StackElemType;BiNodep;//二叉树的建立BiNodestree_creatchar*aintk{BiNoderoot;__xI++;ifa[k]==\0||k__xIsizereturnNULL;//判断树是否为空else{root=BiNode__llocLEN;//动态申请节点root-data=a[k];root-lchild=stree_creata2*k+1;//递归调用为左孩子赋值root-rchild=stree_creata2*k+2;//递归调用为右子赋值returnroot;//返回根节点指针}}voidprintBiNoderoot//输出所创建的二叉树{BiNodeh[__xIsize]={NULL};doubletop=0j=0m=0;intbase=0n=0k=0topInt=0;h[topInt]=root;j=log__xI+1/log2-1;ifpow2j+1-1__xIj++;cout你刚输入的是:\n;whileh[base]!=NULL//把二叉树的值依次存入数组{h[++topInt]=h[base]-lchild;h[++topInt]=h[base]-rchild;base++;}fortopInt=0top=0;h[k]!=NULL;topInt++//按层输出{m=pow2j-top;//计算每行输出的空格数iftop!=0m=m-top;forn=0;nm;n++cout;forbase=0;basepow2toph[k]!=NULL;base++//控制每层输出的个数{ifh[k]-data==0cout[];//当为空时输出[]elsecouth[k]-data;k++;}cout\n;forn=0;nm-1;n++cout;forbase=0;basepow2toph[k]!=NULL;base++cout/|;cout\n;top+=1;}}//二叉树的后序遍历递归算法voidPostOrderBiNoderoot{ifroot==NULLreturn;//递归调用的约束条件else{PostOrderroot-lchild;PostOrderroot-rchild;ifroot-data==0;elsecout[root-data];}}//二叉树的中序遍历递归算法voidInOrderBiNoderoot{ifroot==NULLreturn;//递归调用的约束条件else{InOrderroot-lchild;ifroot-data==0;elsecout[root-data];InOrderroot-rchild;}}//二叉树的前序递归遍历算法voidPreOrderBiNoderoot{ifroot==NULLreturn;//递归调用的约束条件else{ifroot-data==0;elsecout[root-data];PreOrderroot-lchild;PreOrderroot-rchild;}}//二叉树的前序遍历非递归算法voidF_PreOrderBiNoderoot{BiNodes[__xIsize];//申请一个BiNode数组inttop=0;//采用顺序栈,并假定不会发生上溢do{whileroot!=NULL//当结点不为空时{ifroot-data==0;elsecout[root-data];s[++top]=root;//依次将结点压入栈root=root-lchild;//根赋值为它的左孩子}iftop0//当节点为空但栈顶不为零时{root=s[top--];//栈顶下移把栈顶元素负给根结点root=root-rchild;//根赋值为它的右子}}whileroot!=NULL||top0;}//中序非递归遍历算法voidF_inOrderBiNoderoot{BiNodes[__xIsize];//申请一个BiNode数组inttop=0;//采用顺序栈,并假定不会发生上溢do{whileroot!=NULL//当结点不为空时{s[++top]=root;//依次将结点压入栈root=root-lchild;//根赋值为它的左孩子}iftop0//当节点为空但栈顶不为零时{root=s[top];//把栈顶元素负给根结点ifroot-data==0;elsecout[root-data];//输出根结点root=s[top--];//栈顶下移把栈顶元素负给根结点root=root-rchild;//根赋值为它的右子}}whileroot!=NULL||top0;}//后序非递归遍历算法voidF_PostOrderBiNoderoot{//申请一个StackElemType数组StackElemTypes[__xIsize];BiNodep=root;inttop=0;do{whilep!=NULL//当结点不为空时{s[top].flag=0;//标记位负为零s[top].ptr=p;//将树的结点依次压入栈中p=p-lchild;//树沿左子树下移top++;}whiles[top-1].flag==1//当栈的最上面元素标记位为一时输出{ifs[top-1].ptr-data==0top--;elsecout[s[--top].ptr-data];}iftop0//当节点为空但栈顶不为零时{s[top-1].flag=1;//栈的最上面元素标记位赋值为一p=s[top-1].ptr;//栈的最上面元素树结点赋给pp=p-rchild;//树沿右子树下移}}whiletop0;}//层序遍算法voidLevelOrderBiNoderoot{BiNodes[__xIsize];//申请一个BiNode数组int__xIi=0;s
[0]=root;//数组首元赋为根结点whileroot!=NULL//当结点不空时{s[2*i+1]=root-lchild;//左孩子赋给下标为2*i+1的数组员s[2*i+2]=root-rchild;//右孩子赋给下标为2*i+1的数组员i++;root=s[i];//root变为当前数组元素的值__xI=i;}fori=0;i__xI;i++{ifs[i]-data==0;elsecout[s[i]-data];//依次输出}}voidPause{coutendlendlendl;systempause;coutendlendlendl;}//树转换为二叉树voidexchange{TreecharmyTree1;//实例化一个TreeclassmyTree
1.InputTree;//调用InputTree函数Pause;myTree
1.ShowTree;//调用ShowTree函数Pause;myTree
1.Show_BinaryTree;//调用Show_BinaryTree函数Pause;}//输入二叉树信息的函数BiNodecreat{BiNodep=NULL;cout请输入你的二叉树请按层次由上往下从左到右依次输入并按#结束,如果节点为空请输入0本遍历器仅支持单字符输入为:\n;inti=0j=0;charb[__xIsize]={#}n;//当输入不为#时给数组赋值do{cinn;ifn!=#b[i]=n;i++;}whilen!=#;p=stree_creatb0;//创建树printp;//输出树returnp;}voidwelcome{forinti=0;i3;i++{systemcls;//执行DOS下的清屏命令cout\n\n\n\n\n\n\n\n\n\n\t\t\tloading;forintj=0;j10;j++{Sleep80;cout.;}}}voidend{systemcls;cout\n\n\n\nendl;cout\n\t\t\t********************endl;cout\n\t\t\t**endl;cout\n\t\t\t*感谢您的使用!*endl;cout\n\t\t\t*Goodbye!*endl;cout\n\t\t\t**endl;cout\n\t\t\t********************\n\n\n\n\n\n\n\t\t\tendl;exit0;}//主函数int__in{intk;welcome;do{systemcls;cout\n;cout\n____________________________________________________________________________;cout|欢迎使用树的多种遍历器|;cout|树与二叉树的转换|;cout||;cout|____________________________________________________________________________|\n;cout\n;cout\n
1.创建二叉树;cout\n
2.查看二叉树;cout\n
3.前序递归遍历算法;cout\n
4.中序递归遍历算法;cout\n
5.后序递归遍历算法;cout\n
6.前序非递归遍历算法;cout\n
7.中序非递归遍历算法;cout\n
8.后序非递归遍历算法;cout\n
9.层序非递归遍历算法;cout\n
10.树与二叉树的转换;cout\n
11.退出操作\n;cout请选择你要进行的操作数字键;cink;systemcls;cout\n;cout\n____________________________________________________________________________;cout|欢迎使用树的多种遍历器|;cout|树与二叉树的转换|;cout||;cout|____________________________________________________________________________|\n;switchk{case1:{p=creat;//调用creat创建二叉树Pause;}break;case2:{printp;Pause;}break;case3:{printp;cout二叉树的前序递归遍历:;PreOrderp;//调用PreOrderp前序遍历Pause;}break;case4:{printp;cout二叉树的中序递归遍历:;InOrderp;//调用InOrderp中序遍历Pause;}break;case5:{printp;cout二叉树的后序递归遍历:;PostOrderp;//调用PostOrderp后序遍历Pause;}break;case6:{printp;cout二叉树前序非递归遍历:;F_PreOrderp;//调用F_PreOrderp前序遍历Pause;}break;case7:{printp;cout二叉树中序非递归遍历:;F_inOrderp;//调用F_inOrderp中序遍历Pause;}break;case8:{printp;cout二叉树后序非递归遍历:;F_PostOrderp;Pause;}break;case9:{printp;cout二叉树层序非递归遍历:;LevelOrderp;Pause;}break;case10:{exchange;//调用exchange实现树与二叉树的转换}break;case11:{end}break;default:cout您的输入有误!按任意键继续......;Pause;}}while1;}六.测试分析二叉树遍历中用到的最重要的一个思想就是递归调用,这次作业是我对递归有了更深入的理解,尤其是对退回上一层后应执行的语句和结点位置的思路更加清晰程序调试比较顺利用栈同样可以实现二叉树的遍历,这使我认识到解决一个问题可以有多种不同的途径,应随时将以前学过的知识灵活应用起来,解决新的问题在使用栈结构时,为了方便,我采用了二叉树结构,将其与链式栈结合起来因为遍历二叉树的基本操作是访问结点,所以无论哪一种遍历方式,对含有n个结点的二叉树,其时间复杂度为O(n),所需辅助空间最大容量为树的深度,最坏为n,所以空间复杂度为On因该程序对应不同的遍历定义了不同的结构,使每种结构的通用性降低,可以在递归和非递归中使用同一种结构这一方面作进一步的思考
6.
1、测试目的测试该程序是否完成所有功能,以及程序存在的不足
6.
2、测试数据
12345676.
3、测试结果图
10、开始过度界面图
11、开始菜单图
12、创建二叉树图
13、查看二叉树图
14、二叉树的前序递归遍历图
15、二叉树的中序递归遍历图
16、二叉树的后序递归遍历图
17、二叉树的前序非递归遍历图
18、二叉树的中序非递归遍历图
19、二叉树的后序非递归遍历图
20、层序非递归遍历图
21、输入要建立树的信息图
22、输出树的形状图
23、输出转换成的二叉树的形状图
24、结束界面七.使用说明运行程序,首先出现主界面主界面有十一个选项选项一,选择此选项进行二叉树的创建按层输入树的信息,如果为空输入零选项二,选择此选项可显示所创建的二叉树选项三,选此选项可对所创建的二叉树采用递归算法进行前序遍历选项四,选此选项可对所创建的二叉树采用递归算法进行中序遍历选项五,选此选项可对所创建的二叉树采用递归算法进行后序遍历选项六,选此选项可对所创建的二叉树采用非递归算法进行前序遍历选项七,选此选项可对所创建的二叉树采用非递归算法进行中序遍历选项八,选此选项可对所创建的二叉树采用非递归算法进行后序遍历选项九,选此选项可对所创建的二叉树采用非递归算法进行层序遍历选项十,选此选项可以根据提示进行树的创建并可以按树状输出树,还可以把树转换成二叉树并按树状输出选项十一,选此选项,退出程序八.总结虽然都说“程序=数据结构+算法”,但我在学习运用数据结构编程之前,并没能深刻体会到这一点,直到这次课设实践我__最深的一点是以前用C编程,只是注重如何编写函数能够完成所需要的功能,似乎没有明确的战术,只是凭单纯的意识和简单的语句来堆砌出一段程序感觉有点像张飞打仗,有勇无谋,只要能完成任务就行但现在编程感觉完全不同了在编写一个程序之前,自己能够综合考虑各种因素,首先选取自己需要的数据结构,是树还是图或是别的什么?然后选定一种或几种存储结构来具体的决定后面的函数的主要风格最后在编写每一个函数之前,可以仔细斟酌比对,挑选出最适合当前状况的算法这样,即使在完整的程序还没有写出来之前,自己心中已经有了明确的原图了这样无形中就提高了自己编写的程序的质量另外,我还体会到深刻理解数据结构的重要性只有真正理解这样定义数据类型的好处,才能用好这样一种数据结构了解典型数据结构的性质是非常有用的,它往往是编写程序的关键经过几周的的奋斗,这次数据结构的课程设计终于做完了通过这次课程设计,我发现了以往学习中的很多不足,弄懂了很多疑难问题并学到了很多知识在此我要感谢同学们及几位老师在此次课程设计中对我的指导和帮助九.____
1.本年级使用的教材数据结构与算法分析(C++版)(第二版)影印版
2005.
72.数据结构与算法,科学出版社,
2005.08;赵文静祁飞等编著
3.《数据结构(C语言)》清华出版社,严蔚敏
4.数据结构-C++语言描述,西安交通大学出版社,
1999.01,赵文静编著操作界面迷宫路径的搜索最短路径的显示全图与部分的同步小老鼠键盘操作用户的登陆界面游戏级别的选择编辑迷宫地图游戏音乐的设置地图的绘制开始结束新建登陆logdlg类对象,并且显示出来根据选择的级别初始化对应迷宫数组根据对应的迷宫数组初始化迷宫地图,同时初始化背景音乐,并且把玩家信息显示出来存入文件play.___中__开始按钮开始NY按下键盘按方向键up方向键down方向键left方向键right判断对应m___ze[][]是否为0判断是否到达粮仓根据对应的操作老鼠进行相应的修改m_x,m_yNN结束YY键盘__利用CFrameWnd对象在部分图view类创建全图view类对象利用已建立的全图view类对象根据键盘__部分图中小老鼠的位置变化m_xx,m_yy修改其类中小老鼠的位置m_x,m_y实现全图与部分图的同步__路径菜单Y搜索迷宫当前位置上下左右对应数组的数值m___ze[i-1][j]=0orm___ze[i+1][j]=0orm___ze[i][j-1]=0orm___ze[j][j+1]=0orm___ze[i-1][j]=0orm___ze[i+1][j]=0orm___ze[i][j-1]=0or__ze[j][j+1]=0orm___ze[i][j]=-1表示已经遍历过的路;把对应的数组i,j,direct添加到结构体中判断是否到达粮仓m___ze
[8]
[18]=0————————————————————))YYN把结构体数组的内容添加到__ze.___中比较得出最短路径,利用draw__ze画出最短路径__编辑迷宫菜单Y开始申请一个BiNode数组inttop=0判断结点是否空输出结点值s[++top]=root结点的值变为它的左孩子判数组是否空root=s[top--]root=root-rchild结束判数组或结点是否空NYNYN开始申请一个BiNode数组]inttop=0判断结点是否空s[++top]=root结点的值变为它的左孩子判数组是否空输出结点值root=s[top--]root=root-rchild结束判数组或结点是否空NYYNN开始申请一个StackElemType数组用一个临时变量存根的信息数组标志致零s[top].ptr=pp=p-lchildtop++判数组标志致是否为一输出结点的数据数组标位致一p=s[top-1].ptrp=p-rchild结束NYYNNYYN判数组是否空判数组是否空判树是否空开始申请一个BiNode数组s[]申请两个整形变量数组首元赋为根结点s[2*i+1]=root-lchild;s[2*i+2]=root-rchildi++root=s[i]__x=i输出数组结束N判断树是否空Y1327654。