[数据结构课程设计]走迷宫游戏

信 息 工 程 学 院

课程设计报告

课程名称 《数据结构》 课题名称 走迷宫游戏 专 业 班 级 学 号 姓 名

联系方式 指导教师

2015 年 12 月 27 日

目 录

1、数据结构课程设计任务书 ............................................................... １

1.1、题目 ........................................................................... １ 1.2、要求 ........................................................................... １ 2、总体设计 ............................................................................. １

2.1、设计思路及总体组成框架 ......................................................... １ 2.2、操作流程图 ..................................................................... ２ 3、详细设计 ............................................................................. ５

3.1、程序中所采用的数据结构及存储结构的说明 ......................................... ５ 3.2、函数功能模块说明 ............................................................... ５ 3.3、各函数的调用关系 ............................................................................................................................... ７ 4、调试与测试： ......................................................................... ７

4.1、调试方法与步骤： ............................................................... ７ 4.2、测试结果的分析与讨论： ......................................................... ８ 4.3、测试过程中遇到的主要问题及采取的解决措施： ................................... １０ 6、源程序清单 ......................................................................... １０ 7、数据结构课程设计总结 ............................................................... １４ 8、参考文献 ........................................................................... １４

1、数据结构课程设计任务书

1.1题目

程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

1.2、要求

1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2) 迷宫的墙足够结实，老鼠不能穿墙而过；

3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5) 找出走出迷宫的所有路径。

利用序列化功能实现迷宫地图文件的存盘和读出等功能 2、总体设计

2.1、设计思路及总体组成框架

1、思路

（1）. 利用mfc 可以把迷宫地图以及老鼠形象可变的导出来。

（2）. 需要有墙有路，通过把迷宫地图划分成一个一个小方块，通过一个数组的值来

判断是墙是路。（1表示墙0表示路）

（3）. 利用栈，来存入当前位置，然后判断下一位置，是否有路，存入栈中或出栈。 （4）. 把每个数组元素对应一个按钮根据点击按钮，改变数组的值从而改变墙和路的

转化。

(5).键盘接受字符，根据字符调用不同的图片，达到老鼠超前走的效果。

2、数据结构

本程序运用的逻辑结构是线性和存储结构为顺序。之所以采用本结构是因为，迷宫主要用到

栈来储存当前位置，和判断下一位置，来入栈。

抽象数据类型线性表的定义如下： ADT Stack{ 数据对象：D={ai | ai ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| ai-1,a i ∈D,i=1,2,3,……，n} 基本操作： Initstack(&s)

操作结果：构造一个空栈s 。 Stackempty （s ）

初始条件：栈s 已经存在。 操作结果：将s 清为空栈。 Push （&s，e ）

初始条件：栈s 已经存在。

操作结果：插入元素e 为新的栈顶元素。 Pop （&s，&e）

初始条件：栈s 已经存在，且非空。

操作结果：删除s 的栈顶元素，并用e 返回其值。 } ADT Stack

3、根据课程设计题目的功能要求，总体概要的组成框图如下：

2.2、操作流程图

1、键盘操作流程：

2、模块流程图：

面向对象而非面向工程的程序设计，事件和判断都具有同时性和并发性。 3、游戏界面显示

3、详细设计

3.1、程序中所采用的数据结构及存储结构的说明 数据类型：结构体，整形数据

输入：按照窗口、菜单提示按鼠标左键

移动老鼠位置，按键盘的上、下、左、右键 输出：可视化迷宫

3.2、函数功能模块说明

（1） 开始游戏

void CMainFrame::OnStart()：开始游戏。

void CLabyrinthView::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags)：小老鼠键盘操。第一个参数表示哪个按键，接受上、下、左、右字符，判断调用哪个小老鼠图片，最后用脚印图片覆盖老鼠图片，达到朝前走，留下脚印的效果。 （2）重新开始

void CMainFrame::OnSysmap()：系统地图。

void CLabyrinthView::OnSelfmap()、void CLabyrinthView::OnLButtonDown(UINT nFlags, CPoint point)：绘制地图函 数。达到墙变路、路变墙的目的。 （3）保存图片

void CMainFrame::OnSave()：保存地图。 （4）载入图片

void CMainFrame::OnOpen()：载入地图。

BOOL CLabyrinthView::OnEraseBkgnd(CDC* pDC)：设置欢迎画面，载入图片。

（5）自绘地图

void CLabyrinthView::OnLButtonDown(UINT nFlags, CPoint point)： 墙变路，路变墙

（6）自动寻路

void CLabyrinthView::OnAuto()：为自动寻路函数。其重要调用Seqstack * CSkfction::init_Seqstack()、int CSkfction::Empty_Seqstack(Seqstack *s)、int CSkfction::Push_Seqstack(Seqstack *s,DataType x)、int CSkfction::Pop_Seqstack(Seqstack *s,DataType *x)函数。 （7）设置时间

int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)：到达在在状态栏中显示时间，调用了系统的函数SetTimer(1,1000,NULL); 第一个参数为对应时器的代号。在一个程序中，可能有多个SetTimer ，在Ontime 响应时，可以根据第一个参数来确定是哪一个记时器所引起的事件。第二个参 数用于设置时间。 第三个参数为一个回调函数的指针，用NULL 的话，系统会把SetTimer 产生的消息加入消息队列中。调用了一下三个函数信息，来显示时间。m_wndStatusBar.CommandToIndex(IDS_LASTTIME); //按规定宽度显示

m_wndStatusBar.SetPaneInfo(0,IDS_LASTTIME,SBPS_POPOUT,150);//剩余时间凸出来m_wndStatusBar.SetPaneText(1,str2);//在窗格中显示文本信息。

void CMainFrame::OnTimer(UINT nIDEvent)：根据时间判断老鼠是否饿死。 void CMainFrame::OnSettime()：设置时间。 （8）音效设置

void CMainFrame::OnMusicOn()：音乐来。 void CMainFrame::OnMusicOff()：音乐关。 （9）游戏退出

void CMainFrame::OnAppExit()：

void CMainFrame::OnClose()：退出游戏，弹出对话框。

（10）框架

BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)：设置窗口信息。

int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)：在状态栏显示时间信息。

3.3、各函数的调用关系

程序界面：

4、调试与测试： 4.1、调试方法与步骤：

内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：

1. 实际完成的情况说明（完成的功能，支持的数据类型等）；

基本功能都已经完成，而且还加了保存图片、载入图片、设置时间、游戏帮助等功能。 2. 上机过程中出现的问题及其解决方案；

(1) 问题：每次走完迷宫，它都会保持现有状态，如果重新开始，要自己按重新开始，

次才能开始，很麻烦。

解决方案：void CMainFrame::OnTimer(UINT nIDEvent)函数中调用void

CMainFrame::OnOpen()，这样在每次游戏结束时就可以调用这个函数，载入图片。

（2）问题：通过键盘来如何控制对象（老鼠）的移动, 我希望达到一种老鼠会动的效果，即

朝左走头往左哦哦，朝右走，头朝右。

解决方案：导入一组老鼠图片，用数组进行控制，没走一步判断调用哪一组老鼠图片。 （3）问题：键盘控制时老是出错。

解决方案：后来通过CSDN 、博客园等IT 技术社区找到了相关文章，如果你按键没有反应是因为它把你的消息转发到了其它的激活窗口的处理程序上，可以试着点击窗口的空白区域，不让任何子控件获得焦点（没有任何一个控件有一个虚线的框）的时候，这个就能激活了。

4.2、测试结果的分析与讨论：

（1）如果不按开始按钮，会弹出一下对话框，如（图一）

（图一）

（2）游戏顺利进行，并成功。如（图二）

（图二）

（3）自动寻路完成，如（图三）

（图三）

（4）自动寻路完成，如（图四）

（图四）

（5）走完全部的路，如（图五）

（图五）

（6）非法输入：

当小老鼠上、下、左、右移动时，如果按下非以上四键，老鼠呆在原地不动。 对游戏和程序没有影响。

4.3、测试过程中遇到的主要问题及采取的解决措施：

6、源程序清单

1. 定义程序中所有用到的数据及其数据结构

结构体，类，栈

typedef struct //顺序栈初始化判栈空以及出入栈

{

int x,y,di;

}DataType;

typedef struct

{

DataType data[MAXSIZE];

int top;

}Seqstack;

typedef struct

{

int x;

int y;

}item;

2．主函数和其他函数的伪码算法；

（1）、BOOL CLabyrinthView::OnEraseBkgnd(CDC* pDC)

{ extern int wall[13][17]；//定义一个控制迷宫的数组

获得客户区句柄；

CBitmap bmp[4];//创建位图

for(int j=0;j

{

for(int k=0;k

{

if(wall[j][k]==0)

{

}

if(wall[j][k]==1)

{

}

if(wall[j][k]==2)

{

}

if(wall[j][k]==3)

{

}

}

}

（2）、void CLabyrinthView::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags) //第一个参数表示哪个按键

{

//用背景涂抹走过的痕迹

char ch[16];

for(int i=0;i

{

for(int j=0;j

{

//老鼠4个方向16张图，循环输出到bitmap 数组

}

}//当选择开始游戏后，才能让老鼠走动

if(m_timestatus==1)

{

if(nChar==VK_DOWN)//nchar 从键盘中接受的变量

{

}

if(nChar==VK_RIGHT)

{

}

if(nChar==VK_UP)

{

}

if(nChar==VK_LEFT)

{

}

}

else//解决游戏结束后还可继续走的bug, 让他结束就变到初始位置

{ y=start_x;

x=start_y;

}//如果走到出口：

if(wall[y][x]==2)

{AfxMessageBox("你很棒！恭喜你赢了！(*^__^*) 嘻嘻……");

}

//贴走动的图:

}

（3）、void CLabyrinthView::OnAuto()

{item move[4]={1,0,0,1,-1,0,0,-1};

//获取操作权

//老鼠4个方向16张图，循环输出到bitmap 数组

CSkfction *csk=new CSkfction();//定义栈

Seqstack *s=csk->init_Seqstack();//初始化

while(!csk->Empty_Seqstack(s)) //不空运行

{

while(d

{ //试探指向下一个位置 0->x+1 y右 1->x y+1下 2->x-1 y左3->x y-1上 if(wall[i][j]==0||wall[i][j]==2)//试探可通

{

//刷白走过的路

temp.x=j;temp.y=i;//将试探给要压栈的temp

//找老鼠行走方向

if(temp.di==0) di=2;if(temp.di==1) di=0;

if(temp.di==2) di=1;if(temp.di==3) di=3;

mdc->SelectObject(bitmap[di][index++]);//选择各方向的图 csk->Push_Seqstack(s,temp);

wall[y][x]=-1;//已经贴图的

//if(wall[y][x]==2)

if(x==16&&y==10)

{成功找到粮仓，开始走全部路线

}

else

d=0;

}

else

d++;

}} }

（4）void CLabyrinthView::OnLButtonDown(UINT nFlags, CPoint point) { if(m_selfmap==1)

{//获取dc 指针

//获取鼠标坐标，转换为墙的xy 坐标，存入数组。

int j=(int)point.x/50;

int k=(int)point.y/50;

//路变墙，墙变路

switch(wall[k][j]){

case 1:

//贴路的图片

case 0:

//贴墙的图片

}

}

}

（5）void CMainFrame::OnTimer(UINT nIDEvent)

{

if(m_lasttime

{

MessageBox("你怎么让老鼠饿死啦！o(>﹏

OnOpen();

}

else if(m_timestatus==1)

{//时间消耗

}

CFrameWnd::OnTimer(nIDEvent);

}

（6）void CMainFrame::OnSave()

{

//用于保存地图

extern int wall[13][17];

char ch[13][17];

for(int i=0;i

for(int j=0;j

ch[i][j]=wall[i][j]+48;

}

}

//保存文件2种方式1：asc2码 2：二进制码

//数组中有2、3所以用asc 码

FILE *pFile=fopen("Gamemap.txt","w");

fwrite(ch,1,222,pFile);

fclose(pFile);

}

（7）void CMainFrame::OnSettime()

{

//设置游戏时间菜单用于创建一个对话框类，并传入输入值,

//并重画状态栏

CSetTime dlg;

if(IDOK==dlg.DoModal()){

m_settime=dlg.m_time;

m_lasttime=m_settime;

CString str1,str2;

str1.Format("剩余时间:%d",m_lasttime);

str2.Format("规定时间:%d",m_settime);

CClientDC dc(this);

m_wndStatusBar.CommandToIndex(IDS_LASTTIME);

m_wndStatusBar.SetPaneInfo(

}

}

0,IDS_LASTTIME,SBPS_NORMAL,150); m_wndStatusBar.SetPaneText(0,str1); m_wndStatusBar.CommandToIndex(IDS_SETTIME); m_wndStatusBar.SetPaneInfo( 1,IDS_SETTIME,SBPS_NORMAL,150); m_wndStatusBar.SetPaneText(1,str2); Invalidate();

}7、数据结构课程设计总结

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

在刚开始的几次调试中曾经出现过不能运行、不能正确输出结果、不能正常显示等等各种问题。经过我的努力及同学的帮助，这些问题最终克服，并且使程序的功能也得到了一定的完善。现在它能人性化的展现小老鼠的迷宫之旅。

在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。

8、参考文献

书籍：

1. 《C 语言程序设计（第三版）》， 出版社：高等教育出版社， 主编：廖雷， 出版日期：2009年6月

2. 《数据结构（c 语言描述）》，出版社：中国水利水电出版社，主编：马秋菊 出版日期：2006年

《大话数据结构》，出版社：清华大学出版社，主编，程杰，出版日期：2011年6月 3. http://student.zjzk.cn/course_ware/data_structure/web/main.htm

数据结构自考网： zhidao.baidu.com 百度知道