数据结构课程设计报告——可视化走迷宫游戏

1、45 西安建筑科技大学课程设计（论文）西安建筑科技大学课程设计（论文）题 目： 可视化走迷宫游戏 院 （系）： 专业班级： 姓 名： 学 号： 指导教师： 2011年9月15日第39页（共38页）西安建筑科技大学课程设计（论文）任务书专业班级： 计算机901 学生姓名： 指导教师（签名）： 一、课程设计（论文）题目走迷宫游戏：程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。二、本次课程设计（论文）应达到的目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程

2、序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本题目要达到目的：熟练掌握最短路径的算法设计。 三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等） 1、 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2、 迷宫的墙足够结实，老鼠不能穿墙而过；3、 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4、 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；找出走出迷宫的所有路径，以及最短路径。四、应收集的资料及主要参考文献： 由于本课程没有安

3、排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“线性表”的基本操作。 参考文献：1. 本年级使用的教材：数据结构与算法分析（c+版）（第二版）影印版 2005.72. 数据结构与算法，科学出版社，2005.08；赵文静 祁飞等编著3. 数据结构-c+语言描述，西安交通大学出版社，1999.01，赵文静编著4. visual c+编程实例(任意一本此类书籍)五、审核批准意见教研室主任（签字） 摘要本设计是为了实现一个可视化迷宫，以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠不能穿越墙，只能在路径上移动。而且可以根据自己的需要设计迷宫地图。关键词：mf

4、c 目 录一设计目的.1二问题描述.1三需求分析.1四概要设计.2五详细设计.4六测试分析.27七使用说明.36八总结.37九参考文献.38数据结构课程设计二叉树的遍历及树与二叉树的转换一设计目的通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。二问题描述1.地图要求：根据要求构造一个迷宫地图，并且是老鼠清晰可见，可用键盘操纵老鼠上下左右移动；有一个窗口显示部分地图，另一个窗口显示全部题图。2.操作：老鼠不能穿墙而过，当老鼠

5、到达粮仓提示成功。可以自动找到迷宫的所有路径以及画出最短路径。三需求分析 1.利用mfc可以把迷宫地图以及老鼠形象可变的画出来。 2.需要有墙有路，通过把迷宫地图划分成一个一个小方块，通过一个数组的值来判断是墙是路。（1表示墙0表示路） 3通过鼠标事件控制老鼠的移动。 4把每个数组元素对应一个按钮根据点击按钮，改变数组的值从而改变墙和路的转化。四概要设计操作界面迷宫路径的搜索最短路径的显示全图与部分的同步小老鼠键盘操作用户的登陆界面游戏级别的选择编辑迷宫地图游戏音乐的设置地图的绘制开始结束 图1 程序界面图4.1、操作界面利用mfc单文档初始化界面，设置meau选项，以及分割成大小两个窗口。4

6、.2、用户的登陆界面利用对话框设计用户登陆界面，界面包括用户名，选择的迷宫级别。4.3、地图的绘制根据登陆界面的上面的信息，绘制迷宫地图。选择加载全图菜单会显示迷宫总图。4.4、游戏音乐的设置在迷宫加载之后，播放背景音乐，利用多线程异步播放。4.5、小老鼠键盘操作 利用键盘事件，完成小老鼠的操作。4.6、全图与部分的同步 利用cframewnd类实现两个view类的同步操作。4.7、搜索迷宫路径及最短路径的显示 选择路径菜单利用递归搜索出迷宫所有路径并且把最短路径绘制在全图显示中。4.8、编辑迷宫地图利用对话框中每一个按钮对用迷宫的一部分，编辑迷宫地图。4.9、层次序遍历算法按照树的层次从左到

7、右访问树的结点，层序遍历用于保存结点的容器是队列。void levelorder(binode root)。4.10、树与二叉树的转换算法转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的有孩子。void exchange()，class tree。4.11、结束界面利用选继续还是结束游戏作为结束画面，点击继续级别将自动加1.五详细设计5.1、各模块流程图 新建登陆logdlg类对象，并且显示出来根据选择的级别初始化对应迷宫数组根据对应的迷宫数组初始化迷宫地图，同时初始化背景音乐，并且把玩家信息显示出来存入文件play.txt中。点击开始按钮 图1 游戏界面显示 开始ny按下键盘按方向键u

8、p方向键down方向键left方向键right判断对应m_maze是否为0判断是否到达粮仓根据对应的操作老鼠进行相应的修改m_x，m_ynn结束yy 图2 小老鼠操作键盘事件利用cframewnd对象在部分图view类创建全图view类对象利用已建立的全图view类对象根据键盘事件部分图中小老鼠的位置变化m_xx，m_yy修改其类中小老鼠的位置m_x，m_y实现全图与部分图的同步图3、全图与部分图的同步 点击路径菜单y搜索迷宫当前位置上下左右对应数组的数值m_mazei-1j=0orm_mazei+1j=0orm_mazeij-1=0orm_mazejj+1=0orm_mazei-1j=0or

9、m_mazei+1j=0orm_mazeij-1=0ormazejj+1=0orm_mazeij=-1,表示已经遍历过的路;把对应的数组i，j，direct添加到结构体中判断是否到达粮仓m_maze818=0）yyn把结构体数组的内容添加到maze.txt中比较得出最短路径，利用drawmaze()画出最短路径 图4、迷宫路径以及最短路径点击编辑迷宫菜单y 图5、后序递归遍历开始申请一个binode 数组 int top=0判断结点是否空输出结点值s+top=root结点的值变为它的左孩子判数组是否空root=stop-root=root-rchild结束判数组或结点是否空nynyn 图6、前

10、序非递归遍历开始申请一个binode 数组 int top=0判断结点是否空s+top=root 结点的值变为它的左孩子判数组是否空输出结点值root=stop-root=root-rchild结束判数组或结点是否空nyynn 图 7、中序非递归遍历开始 申请一个stackelemtype数组用一个临时变量存根的信息 数组标志致零 stop.ptr = p p=p-lchild top+判数组标志致是否为一输出结点的数据数组标位致一p = stop-1.ptr p= p-rchild结束nyynnyyn判数组是否空判数组是否空判树是否空 图8、后序非递归遍历开始申请一个binode数组s申请两

11、个整形变量数组首元赋为根结点s2*i+1 = root-lchild ；s2*i+2 = root-rchild i+root = si max=i输出数组结束n判断树是否空y图9、层次序非递归遍历5.2、源程序我真诚地保证： 我自己独立地完成了整个程序从分析、设计到编码的全过程。 如果在上述过程中，我遇到了困难而求教于人，那么，我将在程序报告中详细地列举我所遇到的问题，以及别人给我的提示。 我的程序里中凡是引用到其他程序或文档之处，例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,我都已经在程序的注释里很清楚地注明了引用的出处。我从未抄袭过别人的程序，也没有盗用别人的程序，无论是修改

12、式地抄袭还是原封不动地抄袭。我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。#includeusing namespace std;#include #include #include /包涵暂停函数的头文件 #define maxisize 100#include tree.h#define len sizeof(struct btree) int maxi=1; typedef struct btree /二叉树节点结构体btree *lchild,*rchild; char data; *binode; typedef struct stackelemtype/栈的结

13、构体binode ptr;int flag;stackelemtype;binode p ;/二叉树的建立binode stree_creat(char *a,int k) binode root; maxi+;if(ak=0|kmaxisize) return null; /判断树是否为空else root=(binode)malloc(len);/动态申请节点root-data=ak; root-lchild=stree_creat(a,2*k+1); /递归调用为左孩子赋值root-rchild=stree_creat(a,2*k+2); /递归调用为右子赋值return root;/返

14、回根节点指针 void print(binode root) /输出所创建的二叉树 binode hmaxisize=null; double top=0,j=0,m=0; int base=0,n=0,k=0,topint=0; htopint=root; j=log(maxi+1)/log(2)-1; if(pow(2,j+1)-1maxi) j+; coutlchild; h+topint=hbase-rchild; base+; for(topint=0,top=0;hk!=null;topint+)/按层输出 m=pow(2,j)-top;/计算每行输出的空格数 if(top!=0)

15、 m=m-top; for(n=0;nm;n+) cout ; for(base=0;basedata=0) cout;/当为空时输出 else coutdata ; k+; coutn; for(n=0;n(m-1);n+) cout ; for(base=0;basepow(2,top)&hk!=null;base+) cout/| ; coutlchild); postorder(root-rchild); if(root-data=0) ; else coutdatalchild); if(root-data=0) ; else coutdatarchild); /二叉树的前序递归遍历

16、算法void preorder(binode root) if(root=null)return;/递归调用的约束条件 else if(root-data=0) ; else coutdatalchild); preorder(root-rchild); /二叉树的前序遍历非递归算法 void f_preorder(binode root)binode smaxisize;/申请一个binode数组int top=0;/采用顺序栈，并假定不会发生上溢 do while(root!=null)/当结点不为空时 if(root-data=0) ; else coutdatalchild;/根赋值为

17、它的左孩子 if(top0)/当节点为空但栈顶不为零时 root=stop-;/栈顶下移把栈顶元素负给根结点root=root-rchild; /根赋值为它的右子while(root!=null|top0);/中序非递归遍历算法void f_inorder(binode root)binode smaxisize; /申请一个binode数组int top=0; /采用顺序栈，并假定不会发生上溢do while(root!=null) /当结点不为空时 s+top = root; /依次将结点压入栈 root = root-lchild; /根赋值为它的左孩子 if(top0) /当节点为空但

18、栈顶不为零时 root = stop; /把栈顶元素负给根结点if(root-data=0) ; else coutdatarchild; /根赋值为它的右子 while(root!=null|top0); /后序非递归遍历算法void f_postorder(binode root) /申请一个stackelemtype数组 stackelemtype smaxisize;binode p=root; int top = 0;dowhile(p!=null) /当结点不为空时 stop.flag = 0;/标记位负为零 stop.ptr = p;/将树的结点依次压入栈中 p=p-lchild

19、;/树沿左子树下移 top+; while(stop-1.flag = 1)/当栈的最上面元素标记位为一时输出 if( stop-1.ptr-data=0) top-; else coutdata0) /当节点为空但栈顶不为零时stop-1.flag = 1; /栈的最上面元素标记位赋值为一p = stop-1.ptr; /栈的最上面元素树结点赋给pp = p-rchild;/树沿右子树下移while(top0);/层序遍算法void levelorder(binode root) binode smaxisize; /申请一个binode数组 int maxi,i=0; s0= root;/

20、数组首元赋为根结点 while(root!=null)/当结点不空时 s2*i+1 = root-lchild;/左孩子赋给下标为2*i+1的数组员s2*i+2 = root-rchild; /右孩子赋给下标为2*i+1的数组员i+;root = si;/root变为当前数组元素的值maxi = i; for( i=0;idata=0) ; else coutdata;/依次输出 void pause()coutendlendlendl;system(pause);coutendlendlendl; /树转换为二叉树void exchange() tree mytree1;/实例化一个tree

21、 classmytree1.inputtree();/调用inputtree()函数pause();mytree1.showtree();/调用showtree()函数pause();mytree1.show_binarytree();/调用show_binarytree()函数pause();/输入二叉树信息的函数binode creat() binode p=null ;coutn; if(n!=#) bi=n; i+;while(n!=#); p=stree_creat(b,0);/创建树 print(p);/输出树 return p; void welcome()for(int i=0

22、;i3;i+)system(cls); /执行dos下的清屏命令coutnnnnnnnnnntttloading;for(int j=0;j10;j+)sleep(80);cout.;void end() system(cls);coutnnnnendl;coutnttt*endl;coutnttt* *endl;coutnttt* 感谢您的使用! *endl;coutnttt* goodbye! *endl;coutnttt* *endl;coutnttt*nnnnnnntttendl;exit(0);/主函数int main() int k;welcome();dosystem(cls);

23、coutn ; coutn _ ;cout | 欢迎使用树的多种遍历器 |; cout | 树与二叉树的转换 |; cout | |;cout |_| n; coutn ; coutn 1.创建二叉树 ; coutn 2.查看二叉树; coutn 3.前序递归遍历算法 ; coutn 4.中序递归遍历算法 ; coutn 5.后序递归遍历算法 ; coutn 6.前序非递归遍历算法 ; coutn 7.中序非递归遍历算法 ; coutn 8.后序非递归遍历算法 ; coutn 9.层序非递归遍历算法 ; coutn 10. 树与二叉树的转换; coutn 11.退出操作n; coutk; sy

24、stem(cls);coutn ; coutn _ ;cout | 欢迎使用树的多种遍历器 |; cout | 树与二叉树的转换 |; cout | |;cout |_| n; switch(k) case 1: p=creat();/调用creat()创建二叉树pause(); break; case 2: print(p); pause(); break; case 3:print(p); cout二叉树的前序递归遍历 :; preorder(p);/调用preorder(p)前序遍历pause(); break; case 4:print(p); cout二叉树的中序递归遍历 :; in

25、order(p); /调用inorder(p)中序遍历 pause(); break; case 5: print(p); cout二叉树的后序递归遍历 :; postorder(p); /调用postorder(p) 后序遍历 pause(); break; case 6: print(p); cout二叉树前序非递归遍历:; f_preorder(p); /调用f_preorder(p)前序遍历 pause(); break; case 7: print(p); cout二叉树中序非递归遍历:; f_inorder(p); /调用f_inorder(p) 中序遍历 pause(); bre

26、ak; case 8: print(p); cout二叉树后序非递归遍历:; f_postorder(p); pause(); break; case 9: print(p); cout二叉树层序非递归遍历:; levelorder(p); pause(); break; case 10: exchange();/调用exchange() 实现树与二叉树的转换 break; case 11: end() break; default:cout您的输入有误!按任意键继续.;pause(); while(1);六测试分析二叉树遍历中用到的最重要的一个思想就是递归调用，这次作业是我对递归有了更深入的

27、理解，尤其是对退回上一层后应执行的语句和结点位置的思路更加清晰。程序调试比较顺利。用栈同样可以实现二叉树的遍历，这使我认识到解决一个问题可以有多种不同的途径，应随时将以前学过的知识灵活应用起来，解决新的问题。在使用栈结构时，为了方便，我采用了二叉树结构，将其与链式栈结合起来。 因为遍历二叉树的基本操作是访问结点，所以无论哪一种遍历方式，对含有n个结点的二叉树，其时间复杂度为o（n），所需辅助空间最大容量为树的深度，最坏为n，所以空间复杂度为o(n)。因该程序对应不同的遍历定义了不同的结构，使每种结构的通用性降低，可以在递归和非递归中使用同一种结构这一方面作进一步的思考。6.1、测试目的测试该程

28、序是否完成所有功能，以及程序存在的不足。6.2、测试数据12345671 327654 6.3、测试结果图10、开始过度界面图11、开始菜单图12、创建二叉树图13、查看二叉树图14、二叉树的前序递归遍历图15、二叉树的中序递归遍历图16、二叉树的后序递归遍历图17、二叉树的前序非递归遍历图18、二叉树的中序非递归遍历图19、二叉树的后序非递归遍历图20、层序非递归遍历图21、输入要建立树的信息图22、输出树的形状图23、输出转换成的二叉树的形状图24、结束界面七使用说明运行程序，首先出现主界面。主界面有十一个选项。选项一，选择此选项进行二叉树的创建。按层输入树的信息，如果为空输入零。选项二，选择此选项可显示所创建的二叉