数据结构课程设计报告——走迷宫

西安建筑科技大学课程设计（论文）题目：可视化走迷宫游戏院（系）：专业班级：姓名：学号：指导教师：2011年9月15日西安建筑科技大学课程设计（论文）任务书专业班级：计算机901学生姓名：指导教师（签名）：一、课程设计（论文）题目走迷宫游戏：程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。二、本次课程设计（论文）应达到的目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本题目要达到目的：熟练掌握最短路径的算法设计。三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等）1、老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2、迷宫的墙足够结实，老鼠不能穿墙而过；3、正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4、添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；找出走出迷宫的所有路径，以及最短路径。四、应收集的资料及主要参考文献：由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“线性表”的基本操作。参考文献：1.本年级使用的教材：数据结构与算法分析（C++版）（第二版）影印版2005.72.数据结构与算法，科学出版社，2005.08；赵文静祁飞等编著3.数据结构-C++语言描述，西安交通大学出版社，1999.01，赵文静编著4.《VisualC++编程实例》(任意一本此类书籍)五、审核批准意见教研室主任（签字）摘要本设计是为了实现一个可视化迷宫，以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠不能穿越墙，只能在路径上移动。而且可以根据自己的需要设计迷宫地图。关键词：mfc目录一．设计目的........................................................................................1二．问题描述.......................................................................................1三．需求分析.......................................................................................1四．概要设计........................................................................................2五．详细设计.......................................................................................4六．测试分析……………………………………………………....27七．使用说明……………………………………...........................36八．总结............................................................................................37九．参考文献....................................................................................3844西安建筑科技大学课程设计（论文）第1页（共38页）《数据结构》课程设计—二叉树的遍历及树与二叉树的转换一．设计目的通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。二．问题描述1.地图要求：根据要求构造一个迷宫地图，并且是老鼠清晰可见，可用键盘操纵老鼠上下左右移动；有一个窗口显示部分地图，另一个窗口显示全部题图。2.操作：老鼠不能穿墙而过，当老鼠到达粮仓提示成功。可以自动找到迷宫的所有路径以及画出最短路径。三．需求分析1.利用mfc可以把迷宫地图以及老鼠形象可变的画出来。2.需要有墙有路，通过把迷宫地图划分成一个一个小方块，通过一个数组的值来判断是墙是路。（1表示墙0表示路）3．通过鼠标事件控制老鼠的移动。4．把每个数组元素对应一个按钮根据点击按钮，改变数组的值从而改变墙和路的转化。四．概要设计44西安建筑科技大学课程设计（论文）第2页（共38页）图1程序界面图4.1、操作界面利用mfc单文档初始化界面，设置meau选项，以及分割成大小两个窗口。4.2、用户的登陆界面利用对话框设计用户登陆界面，界面包括用户名，选择的迷宫级别。4.3、地图的绘制根据登陆界面的上面的信息，绘制迷宫地图。选择加载全图操作界面迷宫路径的搜索最短路径的显示全图与部分的同步小老鼠键盘操作用户的登陆界面游戏级别的选择编辑迷宫地图游戏音乐的设置地图的绘制开始结束44西安建筑科技大学课程设计（论文）第3页（共38页）菜单会显示迷宫总图。4.4、游戏音乐的设置在迷宫加载之后，播放背景音乐，利用多线程异步播放。4.5、小老鼠键盘操作利用键盘事件，完成小老鼠的操作。4.6、全图与部分的同步利用CFrameWnd类实现两个view类的同步操作。4.7、搜索迷宫路径及最短路径的显示选择‘路径‘菜单利用递归搜索出迷宫所有路径并且把最短路径绘制在全图显示中。4.8、编辑迷宫地图利用对话框中每一个按钮对用迷宫的一部分，编辑迷宫地图。4.9、层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。voidLevelOrder(BiNoderoot)。4.10、树与二叉树的转换算法转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的有孩子。voidexchange()，classTree。4.11、结束界面利用选继续还是结束游戏作为结束画面，点击继续级别将自动加1.五．详细设计5.1、各模块流程图44西安建筑科技大学课程设计（论文）第4页（共38页）图1游戏界面显示新建登陆logdlg类对象，并且显示出来根据选择的级别初始化对应迷宫数组根据对应的迷宫数组初始化迷宫地图，同时初始化背景音乐，并且把玩家信息显示出来存入文件play.txt中。点击开始按钮44西安建筑科技大学课程设计（论文）第5页（共38页）图2小老鼠操作开始NY按下键盘按方向键up方向键down方向键left方向键right判断对应m_maze[][]是否为0判断是否到达粮仓根据对应的操作老鼠进行相应的修改m_x，m_yNN结束YY44西安建筑科技大学课程设计（论文）第6页（共38页）图3、全图与部分图的同步键盘事件利用CFrameWnd对象在部分图view类创建全图view类对象利用已建立的全图view类对象根据键盘事件部分图中小老鼠的位置变化m_xx，m_yy修改其类中小老鼠的位置m_x，m_y实现全图与部分图的同步44西安建筑科技大学课程设计（论文）第7页（共38页）点击路径菜单Y搜索迷宫当前位置上下左右对应数组的数值m_maze[i-1][j]=0orm_maze[i+1][j]=0orm_maze[i][j-1]=0orm_maze[j][j+1]=0orm_maze[i-1][j]=0orm_maze[i+1][j]=0orm_maze[i][j-1]=0ormaze[j][j+1]=0orm_maze[i][j]=-1,表示已经遍历过的路;把对应的数组i，j，direct添加到结构体中判断是否到达粮仓m_maze[8][18]=0————————————————————））YYN把结构体数组的内容添加到maze.txt中比较得出最短路径，利用drawmaze()画出最短路径44西安建筑科技大学课程设计（论文）第8页（共38页）图4、迷宫路径以及最短路径点击编辑迷宫菜单Y44西安建筑科技大学课程设计（论文）第9页（共38页）图5、后序递归遍历44西安建筑科技大学课程设计（论文）第10页（共38页）图6、前序非递归遍历开始申请一个BiNode数组inttop=0判断结点是否空输出结点值s[++top]=root结点的值变为它的左孩子判数组是否空root=s[top--]root=root-rchild结束判数组或结点是否空NYNYN44西安建筑科技大学课程设计（论文）第11页（共38页）图7、中序非递归遍历开始申请一个BiNode数组]inttop=0判断结点是否空s[++top]=root结点的值变为它的左孩子判数组是否空输出结点值root=s[top--]root=root-rchild结束判数组或结点是否空NYYNN44西安建筑科技大学课程设计（论文）第12页（共38页）图8、后序非递归遍历开始申请一个StackElemType数组用一个临时变量存根的信息数组标志致零s[top].ptr=pp=p-lchildtop++判数组标志致是否为一输出结点的数据数组标位致一p=s[top-1].ptrp=p-rchild结束NYYNNYYN判数组是否空判数组是否空判树是否空44西安建筑科技大学课程设计（论文）第13页（共38页）图9、层次序非递归遍历5.2、源程序我真诚地保证：我自己独立地完成了整个程序从分析、设计到编码的全过程。如果在上述过程中，我遇到了困难而求教于人，那么，我将在程序报告中详细地列举我所遇到的问题，以及别人给我的提示。我的程序里中凡是引用到其他程序或文档之处，例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,我都已经在程序的注释里很清楚地注明了引用的出处。我从未抄袭过别人的程序，也没有盗用别人的程序，无论是修改式地抄袭还是原封不动地抄袭。开始申请一个BiNode数组s[]申请两个整形变量数组首元赋为根结点s[2*i+1]=root-lchild；s[2*i+2]=root-rchildi++root=s[i]max=i输出数组结束N判断树是否空Y44西安建筑科技大学课程设计（论文）第14页（共38页）我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。#includeiostreamusingnamespacestd;#includestdlib.h#includemath.h#includewindows.h//包涵暂停函数的头文件#definemaxIsize100#includetree.h#defineLENsizeof(structbtree)intmaxI=1;typedefstructbtree//二叉树节点结构体{btree*lchild,*rchild;chardata;}*BiNode;typedefstructStackElemType//栈的结构体{BiNodeptr;intflag;}StackElemType;BiNodep;//二叉树的建立BiNodestree_creat(char*a,intk){44西安建筑科技大学课程设计（论文）第15页（共38页）BiNoderoot;maxI++;if(a[k]=='\0'||kmaxIsize)returnNULL;//判断树是否为空else{root=(BiNode)malloc(LEN);//动态申请节点root-data=a[k];root-lchild=stree_creat(a,2*k+1);//递归调用为左孩子赋值root-rchild=stree_creat(a,2*k+2);//递归调用为右子赋值ret