武汉理工大学数据结构与算法综合实验连连看.pdf

《武汉理工大学数据结构与算法综合实验连连看.pdf》由会员分享，可在线阅读，更多相关《武汉理工大学数据结构与算法综合实验连连看.pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.学生学号学生学号Xxx实验课成绩实验课成绩学学 生生 实实 验验 报报 告告 书书实验课程名称实验课程名称开课学院开课学院指导教师姓名指导教师姓名学生姓名学生姓名学生专业班级学生专业班级数据结构与算法综合实验计算机科学与技术学院xxxxxxxx2015-2016学年第2学期.实验课程名称：数据结构与算法综合实验实验项目名称实验者同组者xxx连连看游戏综合实践专业班级xxxxx报告成绩组别完成日期年月日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的目的调研连连看游戏，了解连连看游戏的功能和规则等。掌握集成开发工具。掌握 C+的基础编程。了解 MFC 框架，包括 MFC Dialo

2、g 应用程序和 GDI 编程。了解线性结构，重点掌握数组和栈操作，掌握数组的遍历、消子和胜负判断等算法。了解企业软件开发过程，了解系统需求分析和设计，应用迭代开发思路进行项目开发。养成良好的编程习惯和培养软件工程化思维，综合应用“C+编程、MFC Dialog、算法、线性结构”等知识，开发“连连看游戏”桌面应用程序，达到掌握和应用线性核心知识的目的。2.要求要求待开发的连连看游戏称为“欢乐连连看”，使用二维数组来保存游戏地图的数据，实现连连看的核心功能。欢乐连连看的功能有：主界面、开始游戏、消子、判断胜负、提示、重排、计时、游戏模式。主界面.游戏主界面就是进行各项操作的入口。开始游戏玩家选择开

3、始游戏模式，进入游戏后，选择开始游戏，系统根据设置的主题风格生成图片布局，以供玩家点击消除。游戏地图大小为 640*400，是一个 16 行乘 10 列的矩形，分成 160 个小正方形，存放 160 张图片，每张图片大小为 40*40。消子对玩家选中的两张图片进行判断，判断是否符合消除规则。只有符合以下规则的图片对才能被消除：一条直线连通两条直线连通三条直线连通如果可以消除，从游戏地图中提示连接路线，然后消除这两张图片，并计算相应的积分。如果不能消除，则保持原来的游戏地图。判断胜负当游戏完成后，需要判断游戏胜负。不同模式下判断胜负的规则不同。基本模式时，如果在五分钟内将游戏地图的所有图片都消除

4、，则提示玩家胜利。休闲模式时，如果游戏地图中所有图片都被消除，则提示玩家获胜。提示可以提示界面上能够消除的一对图片。计时设定一定时间来辅助游戏是否结束。.重排根据随机数，重新排列地图上的图片。游戏模式游戏模式有:基本模式、休闲模式和关卡模式三种，可以根据是否定时等规则进行设置。二、分析与设计1.数据结构的设计1)1)顶点存储顶点存储添加 global.h 文件，定义结构体 tagVertex,用于保存游戏地图中一个点的行号、列号、值信息。typedef struct tagVertexint row;/行int col;/列int info;/信息类Vertex;2)2)游戏地图存储结构游戏地

5、图存储结构使用二位数组来保存连连看游戏地图，在给没一种图片一个编号，并将这些编号保存在二位数组中。用户在屏幕上选择两张图片，对应为数组中的两组坐标。分别实现三个消子判断算法：一条直线连通、两条直线连通、三条直线连通，并使用者三个算法进项消子判断。若符合消子规则，就在屏幕上消除一对图片，并把数组对应元素清空。游戏地图中图片种类和重复次数与游戏的级别汉难度有关。图片种类越多，.重复次数越小，游戏难度越大，反之则越容易。只有两张相同的图片才能消除。为保证游戏中的图片能够完全消掉，每种图片出现的次数一定是偶数，即 2 的倍数。地图的大小与图片元素种类之间的关系地图的行数*地图的列数=图片种类数*每种图

6、片重复的次数。地图数据的存储a.用 int 类型的动态二位数组(int*m_pGameMap)存储地图中元素图片的编号。b.获得某行某列对应的元素编号。2.核心算法设计随机开局算法1)计算游戏中元素个数：行数*列数。2)计算每种花色重复数：行数*列数/花色数。判断（行数*列数%花色数）是否为 0。如果不为 0，则进行异常处理。判断每一种花色的重复数能否被 2 整除，如果不能被二整除，则进行异常处理。3)按从左到右，从上到下，将花色数填入游戏地图。实现代码如下：.int nRepeatNum=nRows*nCols/nPicNums;int count=0;for(int i=0;inPicNu

7、ms;i+)for(int j=0;j col2)int temp=col1;col1=col2;col2=temp;/判断两个顶点间是否有不为空的图片for(int i=col1+1;irow2)int temp=row1;row1=row2;row2=temp;for(int i=row1+1;i=row2;i+)if(i=row2)return true;if(m_Mapicol!=BLANK).break;return false;两条直线消子算法若一条直线无法连通，则判断两条直线的情况。在CGameLogic 类中定义OneCornerLink（）函数判断两点是否能两条直线连通。先判

8、断两个顶点的 X 和 Y 方向的直线相交的两个顶点，是否为空。若能构成两条指向连通，那么相交的顶点必须为空才行。若顶点有一个为空，则判断该顶点与两个顶点，横向与纵向一条直线是否连通，若都连通，则表示两条直线消子成功，否则不能相消。实现代码如下：bool CGameLogic:OneCornerLink(int m_Map1015,Vertex v1,Vertex v2).int row1=v1.row;int col1=v1.col;int row2=v2.row;int col2=v2.col;/判断相交的顶点是否为空if(m_Maprow1col2=BLANK)/判断两个同行的顶点是否一条

9、直线连通.if(LineY(m_Map,row1,row2,col2)&LineX(m_Map,row1,col1,col2)if(m_Maprow2col1=BLANK)/判断两个同列顶点是否一条直线连通Vertex V=row1,col2,BLANK;AddVertex(V);return true;if(LineY(m_Map,row1,row2,col1)&LineX(m_Map,row2,col1,col2)Vertex V=row2,col1,BLANK;return false;三条直线消子算法AddVertex(V);return true;若两条直线无法连通，则判断三条直线的

10、情况。在 CGameLogic 类中定义TwoCornerLink()函数判断两点能否三条直线连通。三条直线消子时，假设选择的两张图片的位置为（nRow1，nCol1）和（nRow2，nCol2），则先寻找与 Y 轴平行的连通线段。.如果 Y 轴没有找到可以连通的三条直线，则寻找以 X 轴平行的连通线段。1)搜索关键路径假设玩家选择的两个顶点为 V0（row0,col0），V3（row3,col3），步骤如下：第一步：从地图的第一行开始扫描，当前扫描到 nRow 行。第二步：设置拐点：V1（nRow，col0）,V2(nRow,col3)。第三步：判断 V1 和 V2 是否水平方向向上连通，如

11、果连通，则 V1 到 V2 的连线即为关键路径。如果不连通则接着扫描下一行，重复第二四步。2)判断三条直线连通采用枚举法判断三条直线连通，假设玩家选择两个顶点为 V0 和 V3，判断三条直线连通的具体实现的具体步骤如下：找到其中一条关键路径 V1，V2。判断 V1 和 V0 是否连通。判断 V2 和 V3 是否连通。如果同时满足 V1 和 V0 连通，V2 和 V3 连通，则 V0 和 V3 满足三条直线连通。否则，在此关键路径下V0 和 V3 不连通，找到下一条关键路径，重复24，直到判断出 V0 和 V3 是否连通。3)保存连通路径使用栈来保存连通路径中的关键点：起始点 V0，拐点 V1，

12、拐点 V2 和终点 V3。保存连通路径的步骤如下：保存其实点 V0。判断是否存在能够满足三条直线消子的关键路径 V1、V2。如果存在，保存顶点 V1、V2、V3，如果不存在，在删除起始点 V0。实现代码如下：.bool CGameLogic:TwoCornerLink(int m_Map1016,Vertex v1,Vertex v2)int row1=v1.row;.int col1=v1.col;int row2=v2.row;int col2=v2.col;for(int col=0;col16;col+)if(m_Maprow1col=BLANK&m_Maprow2col=BLANK)

13、if(LineY(m_Map,row1,row2,col)if(LineX(m_Map,row1,col1,col)&LineX(m_Map,row2,col2,col)Vertex V1=row1,col,BLANK;Vertex V2=row2,col,BLANK;AddVertex(V1);AddVertex(V2);return true;.for(int row=0;row10;row+)return false;4)胜负判断算法当所有元素被消掉，进行胜负判断，遍历地图中所有元素的值，当所有元素都为空时，表示获胜，游戏结束，否则继续游戏。实现代码如下：.if(m_Maprowcol1

14、=BLANK&m_Maprowcol2=BLANK)if(LineX(m_Map,row,col1,col2)if(LineY(m_Map,row,row1,col1)&LineY(m_Map,row,row2,col2)Vertex V1=row,col1,BLANK;Vertex V2=row,col2,BLANK;AddVertex(V1);AddVertex(V2);return true;.if(m_GameProgress.GetPos()EnableWindow(TRUE);else if(m_GameProgress.GetPos()0&cgc.IsBlank(cgc.m_Ma

15、p)KillTimer(PLAY_TIMER_ID);int result;result=MessageBox(_T(获胜!是否重新开始游戏？),_T(提示);if(result=IDOK)else exit(0);GetDlgItem(IDC_BUTTON_START)-EnableWindow(TRUE);.5）重排当进行游戏的过程中会出现无法再进行消子的情况，点击重排按钮就可以将剩下子进行随机重排以便客户能够正常进行消子操作。首先在 CGameLogic 类中定义一个DisOrderMap（）函数来对剩下的元素进行重排，实现代码如下：void CGameLogic:DisOrderMap

16、(int m_Map1016)srand(int)time(NULL);int nVertexNum=nRows*nCols;for(int i=0;inVertexNum;i+)/随机获得两个坐标int nIndex1=rand()%nVertexNum;int nIndex2=rand()%nVertexNum;int nTemp=m_MapnIndex1/nColsnIndex1%nCols;int nRows=10;int nCols=16;m_MapnIndex1/nColsnIndex1%nCols=m_MapnIndex2/nColsnIndex2%nCols;.m_MapnIn

17、dex2/nColsnIndex2%nCols=nTemp;.然后在 CGameControl 类中定义一个 DisOrder（）函数来调用 DisOrderMap（）函数，最后再 CGameDlg 类的OnBnClickedButtonReset()函数中调用 DisOrder（）函数，实现代码如下：void CGameDlg:OnBnClickedButtonReset()6）帮助在原有的基础上重新插入一个对话框，重新定义一个 CHelpDialog 类，在这个类中将写有相关游戏说明的图片加载进界面中去，加上滚动条。实现代码如下：BOOL CHelpDialog:OnInitDialog(

18、)./TODO:在此添加控件通知处理程序代码m_dcMem.BitBlt(0,0,800,600,&m_dcBG,0,0,SRCCOPY);InvalidateRect(FALSE);m_gameControl.DisOrder();UpDateMap();CDialogEx:OnInitDialog();ASSERT(IDM_ABOUTBOX&0 xFFF0)=IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX LoadIcon(IDR_MAINFRAME);/IDR_ICON 为图标资源名SetIcon(m_hIcon,TRUE);/Set big iconSetIcon(

19、m_hIcon,FALSE);/Set small icon/加载图片资源HANDLE bmp=:LoadImage(NULL,_T(themepictureHelp1.bmp),IMAGE_BITMAP,0,0,LR_LOADFROMFILE);./获得当前对话框的视频内存CClientDC dc(this);/创建与视频内存兼容的内存 DCm_dcHelp.CreateCompatibleDC(&dc);/将位图资源选入 DCm_dcHelp.SelectObject(bmp);/初始化内存 DCm_dcMen.CreateCompatibleDC(&dc);CBitmap bmpMem;

20、bmpMem.CreateCompatibleBitmap(&dc,500,400);m_dcMen.SelectObject(&bmpMem);/绘制背景到内存中m_dcMen.BitBlt(0,0,800,600,&m_dcHelp,0,0,SRCCOPY);/绘制帮助信息显示区域this-GetDlgItem(IDC_BUTTON_HELP)-GetWindowRect(&m_rtHelp);this-ScreenToClient(&m_rtHelp);/绘制帮助信息.UpdateHelp(0);/表示滚动条的初始位置为 0/设置滚动条范围CBitmap bmpHelp;bmpHelp.

21、Attach(bmp);BITMAP bmpInfo;bmpHelp.GetBitmap(&bmpInfo);/设置滚动条范围(CScrollBar*)this-GetDlgItem(IDC_SCROLLBAR)-SetScrollRange(0,bmpInfo,bmpHelp);滚动条设置：void CHelpDialog:OnVScroll(UINT nSBCode,UINT nPos,CScrollBar*pScrollBar).return TRUE;/return TRUE unless you set the focus to a control/异常:OCX 属性页应返回 FAL

22、SE/TODO:在此添加额外的初始化UINT Pos;int nMaxPos,nMinPos;/TODO:在此添加消息处理程序代码和/或调用默认值switch(nSBCode)case SB_LINEUP:.Pos-=-1;break;case SB_LINEDOWN:Pos+=1;break;case SB_PAGEUP:Pos-=10;break;case SB_PAGEDOWN:Pos+=10;break;case SB_TOP:Pos=nMinPos;case SB_BOTTOM:Pos=nMaxPos;case SB_THUMBPOSITION:/点击在滑块上Pos=nPos;def

23、ault:pScrollBar-SetScrollPos(Pos,TRUE);/设置滚动条当前点的值UpdateHelp(Pos);CDialogEx:OnVScroll(nSBCode,nPos,pScrollBar);break;.7）暂停游戏点击暂停游戏按钮，按钮的文字由”暂停游戏“变成”继续游戏“字样，并且用户不能进行游戏，同时进度条停止计时。实现代码如下：void CGameDlg:OnBnClickedBtnGameStop()m_dcMem.BitBlt(m_rtGameRect.left+40,m_rtGameRect.top+40,m_rtGameRectCString bt

24、nPauseName;CString goGame(继续游戏);CString pauGame(暂停游戏);GetDlgItemText(IDC_BTN_GAME_STOP,btnPauseName);if(btnPauseName=pauGame)/计时器停止计时KillTimer(PLAY_TIMER_ID);SetDlgItemText(IDC_BTN_GAME_STOP,goGame);m_bPlaying=FALSE;.Width(),m_rtGameRect.Height(),&m_stopGame,m_rtGameRect.left,m_rtGameRect.top,SRCCOP

25、Y);InvalidateRect(&m_rtGameRect,FALSE);.else/计时器开始计时SetTimer(PLAY_TIMER_ID,1000,NULL);SetDlgItemText(IDC_BTN_GAME_STOP,pauGame);m_bPlaying=TRUE;UpdateMap();InvalidateRect(&m_rtGameRect,FALSE);8)计时先在游戏界面中添加一个进度条控件，在添加一个static text 文本来记录进度条位置，在 CGameDlg 类中编写 OnTimer（）函数来实现。实现代码如下：void CGameDlg:OnTimer

26、(UINT_PTR nIDEvent).if(nIDEvent=PLAY_TIMER_ID&m_bPlaying)int npos=m_GameProgress.GetPos();if(npos=0)m_GameProgress.StepIt();.MessageBox(_T(时间到，失败);m_bPlaying=FALSE;GetDlgItem(IDC_BTN_GAME_START)-EnableWindow(TRUE);m_dcMem.BitBlt(m_rtGameRect.left,m_rtGameRect.top,m_rtGameRect.Width(),m_rtGameRect.He

27、ight(),&m_dcBG,m_rtGameRect.left,m_rtGameRect.top,SRCCOPY);当用户点击游戏按钮时，进度条开始计时。实现代码如下：void CGameDlg:OnClickedButtonStart()/开始游戏按钮 m_gameControl.StartGame();/开始游戏CString m_present;m_present.Format(_T(%4.0f%),(float)npos/(float)3.0);GetDlgItem(IDC_STATIC_TIME)-SetWindowText(m_present);CDialogEx:OnTimer

28、(nIDEvent);InvalidateRect(&m_rtGameRect,FALSE);GetDlgItem(IDC_BTN_GAME_TIPS)-EnableWindow(FALSE);GetDlgItem(IDC_BTN_GAME_STOP)-EnableWindow(FALSE);GetDlgItem(IDC_BTN_GAME_REARRANGE)-EnableWindow(FALSE);GetDlgItem(IDC_BTN_GAME_START)-EnableWindow(TRUE);UpDateMap();/更新地图.InvalidateRect(rect,FALSE);/更新

29、游戏区域 GetDlgItem(IDC_BUTTON_START)-EnableWindow(FALSE);/让开始按钮变为灰色，开始游戏后不能再点击该按钮 GetDlgItem(IDC_BUTTON_PAUSE)-EnableWindow(TRUE);/开始游戏后将暂停游戏按钮设置为可点击状态 IsPlaying=true;/游戏标示设置为 true m_bGamePause=false;/暂停游戏标示设置为 false/启动定时器this-SetTimer(PLAY_TIMER_ID,1000,NULL);3.测试用例设计先从网上下载一张图标图片和几张 BMP 图像。先设计出游戏主界面，并

30、且调整好相应的参数，并且加载游戏图标和游戏主界面背景。插入一个游戏对话框用来进行游戏，并且添加相应是事件，实现相应的功能。自己当一次游戏玩家，自己分别玩这个游戏的三个模式，看是否可以正常运行，运行过程是否正确，观察游戏是否按照想象中的那样运行。三、主要仪器设备及耗材安装了 Windows XP 或 Windows 7 或其它版本的 Windows 操作系统的 PC 机 1 台。PC 机系统上安装了 Microsoft Visual Studio 2010 开发环境。第二部分：实验过程和结果（可加页）.一、实现说明在 Microsoft Visual Studio 2010集成开发环境中新建一个

31、 Win32 控制台应用程序工程 LLK。在 LLK 中新建三组相关文件。第一组是实现绘图相关操作的头文件 GameDlg.h和原程序文件 GameDlg.cpp。第二组是实现消子功能的头文件CGameLogic.h 和源程序文件 CGameLogic.cpp。第三组是实现游戏控制功能的头文件 CGameControl.h 和源文件 CGameControl.cpp。同时新建一个global.h 文件来存放 Vertex 结构体来存放图片的相关信息。二、调试说明（调试手段、过程及结果分析）调试内容为编写程序的语法的正确性与否，程序逻辑的正确性与否。调试的主要手段是，设置断点，然后启动调试。例如

32、在编写 GameDlg.cpp 的时候出现了图片是奇数的情况，但是通过设置断点并且点击调试后终于发现问题，经过修改后，编译成功。再如，在编写 CHelpDialog 类的时候，无法加载出背景图片，在多次都找不出错误的情况下通过设置断点点击调试，终于找出问题所在，最终问题得以解决。三、软件测试（测试效果.界面、综合分析和结论）1测试效果.界面图 1：主界面.图 2：基本模式界面图 3：消子界面.图 4：重排界面.图 5：提示界面.图 6：获胜界面2综合分析和结论通过对位图的存储和对位图进行随机抽取就能够出现如图片所示的界面，并且通过对图片的设置就能达到消子的效果。能实验连连看实验的基本功能，绘制

33、主界面地图，游戏界面地图，生成元素图片，元素图片的消除，连线的显示，计时，重排，提示等功能都能实现。实验的目的基本达到，基本完成了一个连连看的游戏。第三部分：实验小结、收获与体会这是我第一次编写项目开发程序，因为是第一次编写，所以在编写的过程中觉得很吃力，并且在这次实验中，很多函数以类都没有接触过，不知道它们的功能，所以需要花费很多时间去思考、构思，虽然在编写的过程中遇到了很多问题，但是通过不断的调试，以及跟同学一起探讨，很多问题也都被解决了。通过这次实验真的收获很多，同时也在一定程度上提高了我的编程能力，这次.实验经历的时间很长，也耗费了自己很长的时间，不过最后实现了连连看游戏，自己感觉还是很棒的在这途中了解了 MFC 框架，包括 MFC Dialog 应用程序和 GDI 编程，了解线性结构，数组和栈操作，了解了图的数据结构和应用，和存储结构和邻接矩阵这种结构，了解企业软件开发的过程，应用迭代开发思路进行项目开发。虽然最后编写出来的连连看游戏还不是很完善，但是我会继续完善，不断修改。.