中南林业科技大学《数据结构课程设计》报告必做题：连连看游戏选做题：姓名：学号：专业班级：软件工程1班学院：计算机与信息工程学院指导老师：签名：2017年1 月10 日目录一、连连看问题 ..................................................... 错误！未定义书签。
1.1需求分析..................................................................................... 错误！未定义书签。
1.1.1程序的功能 ............................................................................. 错误！未定义书签。
1.1.2.输入输出的要求...................................................................... 错误！未定义书签。
1.2系统设计..................................................................................... 错误！未定义书签。
1.2.1 程序流程图 ............................................................................ 错误！未定义书签。
1.2.2 程序组成 ................................................................................ 错误！未定义书签。
1.3调试测试..................................................................................... 错误！未定义书签。
1.3.1测试用例 ................................................................................. 错误！未定义书签。
1.3.2测试结果 ................................................................................. 错误！未定义书签。
1.3.3存在问题 ................................................................................. 错误！未定义书签。
1.3.4改进设想 ................................................................................. 错误！未定义书签。
1.4程序界面..................................................................................... 错误！未定义书签。
1.5核心源程序清单........................................................................ 错误！未定义书签。
一、连连看问题问题描述该游戏对一堆图案中相同的图案进行配对，点击开始按钮后，要求在一定的时间内完成对所有的图片配对，玩家每次选择两个图形，如果两图形相同，且这两个图形之间存在少于2个拐角的连通路径，则可以消除这两个图形。
成功消除一对图片则计分板会增加10分，对应的时间增加3秒。
要求各类类型的图片个数为偶数个，途中若有玩家找不到可以匹配的图片时可以点击提示按钮，由系统提示出一对可以消除的图片，通过玩家的点击可以消除。
当所有的图片消除时，系统提示消息为“恭喜你，通关了”，如果没有在规定时间完成所有图片的配对，则系统提示为“游戏结束”。
基本要求(1)生成游戏初始局面；(2) 每次用户选择两个图形，如果图形能满足一定条件（如果两个图形一样，且这个两个图形直接存在少于2个弯的拐角），则两个图形都能消掉。
给定具有相同图形的任意两个格子，我们需要寻找这两个格子之间在转弯少的情况下，经过格子数目少的路径。
如果这个优路径的转弯数目少于2，则这个两个格子可以消去；(3)判断游戏是否结束。
如果所有图形全部消去，游戏结束；(4) 判断死锁，当游戏玩家不可能消去任意两个图像的时候，游戏进入“死锁”状态。
设计思想判断两个图形可以消除的条件是：两个图形必须相同，它们之间存在着0个拐角，或1个拐角，亦或是2个拐角可以互相连通消除，否则，消除不了。
广度优先搜索的具体实现：如果两个图形可以通过0个拐角连通，则从第一个选中的图片一次向右，向下，向左，向上搜索可以和当前选中图片消除的另一图片，当搜索到与之相同的图片时，则与之消去；图片布局刷新；如果两个图片之间存在1个拐角可以消去，则广度搜索从当前图片出发，向左，右上下一次寻找一个路径节点(没有图片的点)，使得寻找到的路径节点可以与选中的图片一线连通，并且可以与第二次选中的图片一线连通，则可以判断为可消除图片；图片布局重新刷新；如果连个图片之间存在两个拐角可以连通，则分为两种情况：一种是两个图片在矩形区域的最外沿，则通过判断是否存在一条线使得在两待消除的图片周围一个单位，若存在则消去。
二是两图片在矩形区域内部，则在两待消除的图片水平方向和垂直方向上寻找另外两个中间点能使两中间点之间连通，并且其中一个中间点能和待消图片1一线连通，另一中间点能和待消图片2一线连通，如若找到这样的点，则判断两图片能消去，找不到则不能消去。
1.1需求分析1.1.1程序的功能(1) 初始化游戏界面该部分主要由执行窗口创建函数及游戏地图加载函数来实现。
通过数据的初始化及游戏地图资源的加载为用户呈现一个游戏初始的界面。
(2) 图片的选择该功能主要由鼠标来完成。
在OnLButtonDown()事件函数中通过鼠标的点击事件选取所要消除的两个相同图片。
(3) 图形的判断与消除对于第(2)步所选的两个图片，对其连通性进行判断：如果两图片直线连通，则相互消去；如果两图片连接为一个拐点且相通，则相互消去；如果两图片连接为两个拐点且相通，则相互消去；否则，不能消去。
(4) 判断游戏是否死锁或结束如果所有的图片全部消去，则提示“游戏结束！”的信息。
当游戏玩家不可能在消去任意两个图片时，游戏进入死锁状态。
此时提示相关信息。
（5）游戏的提示当玩家找不到两个可以消去的函数时，可以通过点击提示按钮获取系统帮助，继续游戏。
1.1.2输入输出的要求无具体要求，当玩家第一次点击图片时，对应图片响应点击消息，图片变成红色底片，若第二次点击的图片能和第一次的图片连通，则同时消失，否则选中的图片为红色的底。
1.2系统设计1.2.1程序流程图1.2.2程序组成a.主要组成类：图11.3调试测试1.3.1测试用例图31.3.2测试结果图4图51.3.3存在问题（1）在设计时没有要求去设计提示次数，所以在设计时没有设计点击提示次数的限制条件，玩家可以一直点击提示。
（2）还有分数是固定的，玩家完成所有图片的连接消除，所得的分数是一致的。
（3）为了提高算法的执行效率，鼠标点击图片的次序不同，可能导致出现本可以消除的一对图片不能消去，但解决方案很简单，就是颠倒鼠标点击的次序。
（4）待消除的两图片在矩形区域内部并且有两个拐角时，为了提高执行效率，附加了一些判断条件，导致代码量增多。
1.3.4改进设想（1）根据实际玩家需求，对系统提示次数加以限制，比如最多可以提示5次之类的具体方案，或者没使用一次提示，则所得分为5分而不是10分。
（2）找一个良好的分数与时间的函数，使得玩家用时少的时候，所得分数相对要高一些。
1.4程序界面图61.5核心程序清单(1)LLKDLG.cpp中//在重画函数中添加时间信息，关卡信息和路径线条,通过窗口重绘，来画路径和改变时间void CLLKDlg::OnPaint(){CPaintDC dc3(this);CWindowDC dc(this);CPen lPen(PS_SOLID, 2, RGB(222,211,140));//画笔的样式，宽度，颜色//设置字体颜色dc.SelectObject(&lPen);//选择画笔CFont font; //字体类CString str;str.Format(_T("剩余时间: %3d 秒"),m_time);//m_time 中存储剩余时间信息font.CreatePointFont(100,_T("宋体")); //请求的的大小，取其1/10为其字体大小，这个函数提供了一种简单的方法来创建指定字体类型和字体大小//设置字体dc.SelectObject(&font);dc.SetTextColor(RGB(222,211,140));dc.SetBkColor(TRANSPARENT);dc.TextOut(10,40,str); //显示时间//显示分数font.DeleteObject();font.CreatePointFont(100,_T("宋体"));dc.SelectObject(&font);dc.SetBkColor(RGB(201,186,131));/*m_score= m_time-30;*/str.Format(_T("分数：%d"),m_score);dc.SetTextColor(RGB(255,255,255));dc.TextOut(610,35,str);CWindowDC dc2(this);CPen pen(PS_SOLID, 3, RGB(161,23,21));dc2.SelectObject(pen);//画出路径if (LLKButton::ms_firstBtn != NULL && LLKButton::ms_secondBtn != NULL){//设置计时器，0.2秒后擦除路径线条SetTimer(2,100,NULL);pt1.x = LLKButton::ms_firstBtn->m_location.y * 50 + 45;pt1.y = LLKButton::ms_firstBtn->m_location.x * 50 + 70;pt2.x = LLKButton::ms_secondBtn->m_location.y * 50 + 45;pt2.y = LLKButton::ms_secondBtn->m_location.x * 50 + 70;pt3.x = LLKButton::ms_ptCross1.y * 50 + 45;pt3.y = LLKButton::ms_ptCross1.x * 50 + 70;pt4.x = LLKButton::ms_ptCross2.y * 50 + 45;pt4.y = LLKButton::ms_ptCross2.x * 50 + 70;//无拐点if (LLKButton::ms_ptCross1.x == -1){dc2.MoveTo(pt1);dc2.LineTo(pt2);}//一个拐点else if (LLKButton::ms_ptCross2.x == -1){dc2.MoveTo(pt1);dc2.LineTo(pt3);dc2.MoveTo(pt3);dc2.LineTo(pt2);}//两个拐点else{dc2.MoveTo(pt1);dc2.LineTo(pt3);dc2.MoveTo(pt3);dc2.LineTo(pt4);dc2.MoveTo(pt4);dc2.LineTo(pt2);}}}//初始化地图void CLLKDlg::InitMap(int map[][MAXY]){int i,j;int x,y;int type;//随机数种子srand((unsigned int)time(NULL));//srand函数是随机数发生器的初始化函数。