简介这是武汉理工大学数据结构综合实验“欢乐连连看”的完整工程包面向正在学习数据结构或准备课程设计的学生以连连看游戏为载体串联数组、图、搜索等知识点。压缩包共103个文件约190.99MB以C源码cpp/h、Visual Studio工程文件sln/vcxproj为核心附带编译生成的可执行文件exe、调试记录pdb/tlog/ilk以及原创背景图片、音乐等资源bmp/wav/ico/rc目录结构完整可直接打开工程查看实现细节。实验覆盖游戏初始化、消子匹配、胜负判断、提示、重排、计时及设置/帮助等完整功能消子逻辑可看到DFS/BFS或哈希加速的运用重排涉及Fisher-Yates洗牌算法为理解数据结构在实际项目中的落地提供具体样例。已有739人浏览学习适合作为课程设计参考、算法巩固或二次开发基础。1. 借一场连连看把数据结构课欠的账还上这个综合实验到底在考什么第一次看到“武汉理工大学数据结构综合实验-欢乐连连看”这个题目时很多人的第一反应是这不就是个游戏嘛把两张一样的图连起来消掉。但真打开实验要求你会发现分数占比最高的从来不是界面好不好看而是那个“两个方块能不能消掉”的判定函数。这个函数背后是二维数组的顺序存储、图的最短路径搜索、队列的状态扩展以及边界条件的兜底处理——一套标准的数据结构与算法组合拳。这篇笔记就顺着这个实验的完整落地路径走一遍棋盘怎么建、判定器怎么写、欢乐版的提示和重排怎么做、哪些地方最容易翻车。适合正在写这份作业但卡在消除判定或死局重排的同学也适合想拿高分、想把实验报告写出区分度的人。2. 棋盘建模与数据结构选型二维数组之外还要多做一层外扩2.1 棋盘为什么只能用二维数组顺序存储的索引公式连连看棋盘天然是一个 M 行 × N 列的矩形格子每个格子只有“有方块”和“没有方块”两种状态方块本身再带一个花色编号。这种形态对应数据结构课本里最经典的顺序存储结构二维数组。我自己一般用 C# 写这个实验因为 WinForms 做界面快而且 C# 的数组和 Queue 类写起来非常顺。核心声明就一句话// 棋盘定义board[row, col] // 0 表示空格1~n 表示不同花色 private int[,] board;如果用 C 或 C声明方式一样只是访问时要自己注意下标。这里要理解一个点二维数组在内存里是按行优先线性排列的访问board[i, j]时编译器帮你做了base (i * cols j) * sizeof(int)的地址换算严蔚敏《数据结构》顺序表那一章讲过同样思路。所以棋盘本质上就是一个一维线形空间只是用二维下标访问更直观。为什么不建议用链表数组或者一维数组加除法换算原因有两个第一连连看的核心操作是随机访问——点一个格子就立刻要知道它的花色和是否为空数组的 O(1) 随机访问正好满足链表要逐个遍历完全没必要。第二二维数组在遍历整张棋盘时双重循环的逻辑和棋盘结构一一对应代码可读性好答辩时老师问起来也好解释。一维数组虽然省内存但每次行列转换都得r * cols c代码里到处都是调试的时候非常痛苦。2.2 外扩一圈空行把边界判断从代码里删掉这是做连连看最容易被忽略但最值得做的一步。不做过外扩你写 BFS 判断连通性的时候每走一步都要先问“这个格子是不是越界了”。越界检查本身不难难的是它散落在搜索代码的每一个方向扩展里稍微漏一处边界上的方块就永远连不通。常见的做法是棋盘声明比实际游戏区大一圈下标 0 和最后一行一列全部留空游戏区从 1 开始。// 实际游戏区rows 行 x cols 列 // 棋盘数组rows 2 行 x cols 2 列外圈全部为 0空格 int rows 10, cols 17; int[,] board new int[rows 2, cols 2]; // 初始化只填充游戏区 for (int r 1; r rows; r) { for (int c 1; c cols; c) { board[r, c] GetRandomColor(); // 随机花色确保成对 } } // 外圈 board[0, *], board[rows1, *], board[*, 0], board[*, cols1] 保持 0这样做的最大好处是BFS 向外扩展时边界上的格子会把外圈的空格当作通路从而把一个“贴边消除”的操作变成普通的路径搜索不需要任何专门针对边界的 if 判断。比如最上面一行两个方块之间隔着一条顶边通路不外扩的写法要单独处理“往上走出边界再绕回来”的情况外扩后这一逻辑自动成立。这里有一个细节要注意显示界面和棋盘数组的下标偏差。用户在界面上点击第 r 行第 c 列从 1 开始数对应的数组下标仍然是board[r, c]因为外圈只在 0 和 rows1 处。但如果你把数组直接按 0 下标渲染就需要先做r - 1变换。我建议渲染循环也从 1 开始整个代码风格统一后面画消除路径时不容易错位。2.3 花色编号即“数据字典”int 比 char 更好扩展方块花色怎么存很多初学者用 char 存比如A、B或者直接存图片路径字符串。但从数据结构的角度我更推荐用整数编号0 代表空格1 代表“桃子”2 代表“星星”以此类推。为什么第一int 比较相等比字符串快得多而连连看每次点击都要做“两个方块花色是否相同”的判断这个操作在全盘 Hint 里会被调用上千次性能差异就出来了。第二整数可以天然对应到图片数组的下标imageList[colorId - 1]直接取到图片省掉一个字典映射。第三存档和读取方便——棋盘就是一个int[,]序列化成文本文件就是每个格子一个数字加载时按行读回来填进去即可实验报告里“文件存储”这一项也有了着落。如果你用的是 C 语言的严蔚敏版教材思路这里提到的“数据字典”本质上就是一个简单的映射关系表用数组下标实现即可不需要引入哈希表。真正需要哈希表的地方是后面 Hint 功能里按花色分组不过那是优化项先用二维数组硬扫也能跑。3. 消除判定的核心算法BFS 找最短转弯路径把三线分类写法扔掉3.1 把“能不能消”建模成转弯次数约束的最短路径问题连连看的消除规则翻译成算法语言是这样从起点方块的中心走到终点方块的中心路径只能沿水平或垂直方向走路径不能穿过任何非空方块除非是终点本身并且整条路径的转弯次数不能超过 2。注意起点和终点本身的两个方块在判断时视为可穿越因为消除动作就是拿走它们。这个建模方式比网上一堆“分三种情况讨论直线、一个拐弯、两个拐弯”的代码要干净得多。分类讨论的版本性能确实好但每一条边界的判断都是手写特判很容易漏——比如两个方块在同一行但中间隔着两个空格然后再隔一个方块这种情况分类讨论代码只要少处理一种中间形态判定就错了。而且它的逻辑和人类直觉绑定太紧规则稍微改一点比如允许 3 次转弯的欢乐模式整段逻辑就要重写。换成图搜索的思路就统一了把棋盘看成一个网格图每个格子的上下左右邻居都是可达的代价是这条边上是否发生了“转弯”。从起点到终点若转弯次数不超过 2则这两个格子可以消除。这本质上是求限制转弯次数的最短路径用广度优先搜索BFS一层层往外扩散同时记录每个状态已经用掉的转弯次数。BFS 天然保证先到达终点的路径转弯次数最优逻辑上无懈可击老师问起来你也能解释得明白。3.2 BFS 判定器参考实现C# 核心方法带注释下面这个方法是整个实验的心脏我建议把它独立成一个公开方法CanConnect其他地方点击处理、Hint、自动测试全部调它/// summary /// 判断起点(sx, sy)和终点(ex, ey)是否能在最多2次转弯内连通 /// /summary public bool CanConnect(int sx, int sy, int ex, int ey) { // 方向数组下、右、上、左顺序无所谓 int[] dx { 1, 0, -1, 0 }; int[] dy { 0, 1, 0, -1 }; int rows board.GetLength(0); int cols board.GetLength(1); // 记录到达每个格子某个方向时的最小转弯数 // 第三维是方向4个方向各记一次初始化为较大值 int[,,] minTurns new int[rows, cols, 4]; for (int r 0; r rows; r) for (int c 0; c cols; c) for (int d 0; d 4; d) minTurns[r, c, d] int.MaxValue; // 队列元素x坐标, y坐标, 当前朝向, 已用转弯次数 Queue(int x, int y, int dir, int turns) queue new(); // 起点四个方向全部入队转弯次数都记为0 // 这样可以统一处理起点的方向选择 for (int d 0; d 4; d) { minTurns[sx, sy, d] 0; queue.Enqueue((sx, sy, d, 0)); } while (queue.Count 0) { var (x, y, dir, turns) queue.Dequeue(); // 到达终点即连通转弯约束在入队时已经保证 if (x ex y ey) return true; // 已经转了2次弯还往前冲就不用继续扩展了 if (turns 2) continue; for (int nd 0; nd 4; nd) { int nx x dx[nd]; int ny y dy[nd]; // 检查数组越界 if (nx 0 || ny 0 || nx rows || ny cols) continue; // 只能走空格但如果这个格子是终点可以走上去 if (board[nx, ny] ! 0 !(nx ex ny ey)) continue; // 方向没变转弯次数不变方向变了转弯次数1 int newTurns (nd dir) ? turns : turns 1; if (newTurns 2) continue; // 只有发现更优的到达方式更少转弯才入队 if (newTurns minTurns[nx, ny, nd]) { minTurns[nx, ny, nd] newTurns; queue.Enqueue((nx, ny, nd, newTurns)); } } } return false; }逻辑说明minTurns三维数组是去重的关键。同一个格子从不同方向到达、消耗的转弯次数不同是截然不同的两个状态不能简单用二维 visited 布尔数组去重。比如一个格子从左边直走过来用了 1 次转弯从右边绕过来用了 2 次转弯后者完全可能是通往终点的唯一路径粗暴剪枝会漏解。newTurns minTurns[nx, ny, nd]保证了每个格子每个方向只保留最优到达记录BFS 队列不会无限膨胀。另一个细节是turns 2时continue而不是在入队时才判断大于 2 就跳过。这样做的原因是当前格子恰好是终点时在上面的if (x ex y ey)已经返回了所以走到turns 2这个分支的格子即使转弯次数用尽也没必要继续向四周扩散直接剪掉能省不少时间。3.3 参数怎么调棋盘规模、可选的最大转弯次数、连通画线路径这个 BFS 方案里有三个可调参数实验报告里可以写成对比分析。第一个是maxTurns也就是最大允许转弯次数。标准连连看是 2 次但如果实验要求里写着“欢乐连连看”有些版本会把上限放宽到 3让游戏更休闲。实现上只需要把代码里两个2改成3或者抽一个字段出来private const int MaxTurns 2;判断处换成if (newTurns MaxTurns) continue;。这个值直接影响游戏难度——2 次转弯时很多角落的配对根本连不上3 次就会多出大量可行消除对。答辩时老师问“难度怎么控制”这就是一个现成的回答点。第二个是棋盘规模。常见配置是 10 行 × 17 列总共 170 个格子每种花色出 4 张的话需要 85 种不同图片通常到不了这么多所以实际是 10 行 × 14 列或者 8 行 × 12 列更常见。棋盘越小死局概率越高因为配对少棋盘越大BFS 搜索空间越大但 170 格的规模对现代机器来说毫无压力。关键是初始化时保证每种花色的数量是偶数不然最后必然剩单张无法消除。第三个是路径回溯。CanConnect只返回布尔值但很多界面想要画出那条消除连线。要拿到路径就得在 BFS 过程中记录父节点队列节点里增加parent信息到达终点后倒着回溯。回溯得到的是一条反向路径正过来用List(int, int)存每一步的坐标即可。这里用双端队列来倒序存入再按序输出也是常见的做法不过实际用 List 反转一下就够了。要注意路径是否包含起点和终点方块本身渲染时通常画到两个方块的边缘不然线会被方块图片盖住。想省事的做法是不画线消除时在两端播放一个闪烁特效视觉效果也不错还能少写一百行代码。4. 提示、重排与点击状态机把“欢乐”功能做成可维护代码4.1 提示功能全盘搜可行消除对的两种实现取舍欢乐版连连看标配三个辅助技能提示HINT、重排SHUFFLE、死局自动重排。先讲提示。提示的本质是遍历棋盘上所有非空格子两两组合只要花色相同且CanConnect返回 true就把这对作为提示结果返回。最简单的实现是二重循环// 全盘搜索第一个可消除对 public (int x1, int y1, int x2, int y2)? FindHint() { for (int r1 1; r1 rows; r1) { for (int c1 1; c1 cols; c1) { if (board[r1, c1] 0) continue; for (int r2 r1; r2 rows; r2) { for (int c2 (r2 r1 ? c1 1 : 1); c2 cols; c2) { if (board[r2, c2] ! board[r1, c1]) continue; if (CanConnect(r1, c1, r2, c2)) return (r1, c1, r2, c2); } } } } return null; }这个写法在 10×14 的棋盘上最多比较 140×139/2 ≈ 9700 对每对调用一次 BFS。实测每次 BFS 的扩展格子数在几十到上百之间总耗时几十毫秒完全够用。但如果你想要更快的版本可以先用字典按花色分组同组内才做两两配对这样把花色不同的无穷组合全部剪掉。花色数量越多这个优化越明显。实现就是把外层二重循环改成Dictionaryint, List(int, int)遍历字典里每个桶内的格子对即可。我一般两层都写小棋盘用双重循环更直观大棋盘换成分组版本注释写清楚原理。4.2 死局检测与洗牌重排怎么避免“洗了还是无解”死局就是棋盘上还存在方块但没有任何一对可以消除。检测方法恰好复用FindHint——如果它返回 null说明死局。触发时机有两种一种是被动玩家点“重排”按钮时强制洗牌另一种是主动每消除一对后自动检查一次进入死局就弹窗并重置。洗牌本身很简单收集所有非零花色打乱顺序填回棋盘。但这里有个坑随机打乱后依然可能死局。原因很简单死局不仅取决于花色分布还取决于空格位置而空格位置每次消除都会变化。解决办法是循环重排洗牌后调用FindHint检查如果还是 null再洗一次。给一个最大尝试次数比如 20 次超过就强制结束游戏并提示“本局无解”避免极端情况下死循环。如果重排后想保留玩家的分数和步数只需要不动那两个统计字段只重置board数组。但注意重置时花色种类和数量必须和原来完全一致不然可能出现某个花色剩 3 张的bug。最安全的做法是先把非零格子收集到Listint洗牌后按列表顺序回填。4.3 点击交互状态机两个状态的切换与防抖点击逻辑看起来简单其实它是一个小型状态机空闲未选中任何方块和已选中选中了第一个方块两个状态。我习惯用一个枚举加上一个坐标字段来表示private enum ClickState { Idle, Selected } private ClickState clickState ClickState.Idle; private int selectedX, selectedY;点击事件的处理流程按状态机的思维写public void OnCellClicked(int r, int c) { if (board[r, c] 0) return; // 点空格无反应 if (clickState ClickState.Idle) { // 第一次点记录选中高亮显示 selectedX r; selectedY c; clickState ClickState.Selected; Highlight(selectedX, selectedY); } else { // 第二次点如果是同一个格子取消选中 if (r selectedX c selectedY) { clickState ClickState.Idle; Unhighlight(selectedX, selectedY); return; } // 花色不同切换选中到新格子体验更好 if (board[r, c] ! board[selectedX, selectedY]) { Unhighlight(selectedX, selectedY); selectedX r; selectedY c; Highlight(selectedX, selectedY); return; } // 花色相同且判定连通消除 if (CanConnect(selectedX, selectedY, r, c)) { board[selectedX, selectedY] 0; board[r, c] 0; score 10; moves; Unhighlight(selectedX, selectedY); RefreshBoard(); CheckDeadlock(); } else { // 花色相同但连不上常见处理是闪红光提示 ShowFailedFeedback(selectedX, selectedY, r, c); } clickState ClickState.Idle; } }这段状态机代码的好处是所有交互路径都收敛在几种明确的状态迁移里初次点选、重选、取消选中、消除成功、消除失败五条分支一目了然。逻辑说明消除失败时状态也要回到 Idle不然玩家下一次点击会落到“已选中”分支里导致逻辑混乱。点空格的 return 可以稍微做点文章——如果当前是已选中状态点空格不改变状态方便玩家连续试探不同的第二个方块。5. 避坑连连看实验里最常见的 5 个翻车现场5.1 边界点永远连不通原因在外扩行没参与初始化现象棋盘最外一圈的方块无论怎么点都提示不能消除即使它们旁边就是空格。原因声明的棋盘是rows 2和cols 2但初始化时只在1..rows、1..cols循环填了花色。看起来没错但 BFS 搜索时会把外圈空格当通路问题出在访问数组用到了下标 0 或rows1而初始化时把外圈全部设为 0 的代码可能忘了执行导致数组默认值不是 0在 C# 里 int[,] 默认就是 0但在 C 里必须手动 memset很多翻车都出在这里。解决初始化时显式把整个棋盘先清零再填游戏区。不要依赖语言的默认值代码里写明白“外圈清零”这一条。5.2 BFS 把空格当成可走通路结果穿越多个空格直接“穿模”消除现象两个方块之间明明还隔着两个空格按规则中间必须无障碍结果判定说可以消除。原因BFS 的实现把“空格”当成可以穿过的路径这本身没错但很多人忘了路径上不能穿过其他方块。在if (board[nx, ny] ! 0 !(nx ex ny ey)) continue;这一行里如果只写了board[nx, ny] ! 0就 continue那空格全部放行正确问题是如果写成board[nx, ny] ! 0 || (nx ex ny ey)就会把终点也当成障碍导致永远走不到终点。反向的错误是把空格判断去掉只留终点判断那所有空格都变成“可以穿越的虚空”两个方块隔多远都能斜着消掉。解决把障碍判断单独写一行并加上注释说明“终点特殊放行”。写完跑三个用例同行相邻消除、同行隔一个空格消除、同行隔一个方块消除后两个结果必须分别是能、不能。这三个用例放在一个测试函数里每次改动后立刻执行。5.3 重排后还是死局随机洗牌和全局可行解搜索是两回事现象玩家点“重排”棋盘刷新了画面但所有方块依然没有一对能消游戏卡死。原因洗牌只打乱了花色顺序没有保证新布局存在可行消除对。死局与否取决于花色分布加空格分布的组合效应而洗牌算法没有感知这个约束。解决洗牌后立刻调FindHint()如果返回 null 就再洗一次。最大尝试次数设 20超过后从牌堆里任意选一对相邻方块强制挖空人为制造一条通路保证本局永远有解同时提示“重排完成”。代码里把强制挖空的逻辑注释清楚答辩时能解释成“程序保证可玩性的兜底策略”。5.4 提示功能每次卡顿半秒忘了按花色分组剪枝现象第一次点提示按钮没反应第二次点就卡一下界面短暂无响应。原因FindHint的双重循环把所有非空格子两两配对而CanConnect内部每次调用都要 new 一个三维minTurns数组并初始化。在 170 格棋盘上9700 次调用会触发 9700 次数组分配GC 压力大卡顿从此而来。解决第一层优化是先用字典按花色分组只有同组格子才做两两配对组合数会缩小一个数量级。第二层优化可以加一个标志位第一次 Hint 执行时把结果缓存起来玩家再点直接返回缓存。注意每次棋盘变化消除、重排时清空缓存不然会返回已经消掉的方块对。这两层做完提示功能在 10×17 棋盘上能做到 50 毫秒以内。5.5 消除成功但画线路径画到了棋盘外现象界面里方块已经消掉了但那条连线的一端或中途出现在了棋盘边缘外面看起来很怪。原因路径回溯得到的坐标用的是棋盘数组下标而渲染时用的是控件像素坐标。如果棋盘数组是rows 2大小而实际显示区只有rows行没做偏移转换的话外圈下标 0 或rows1对应的像素坐标就落在边界外。解决画线时统一经过一个BoardToPixel(r, c)方法传入棋盘下标返回控件坐标。r和c都要减 1 再乘单元格大小再加半个单元格尺寸得到中心点。所有渲染代码只允许调用这个方法不允许裸写坐标运算。把坐标转换收敛到一个函数里以后再调整格子大小只改一处。6. 用自动化测试验证判定器顺便把实验报告写出区分度到了这一步代码基本跑通了但直接交作业风险还是很大。我的习惯是写一个测试方法把判定器容易出错的场景全部固化成用例public void RunRegressionTests() { // 构造一个固定棋盘6行 x 8列外扩后是 8 x 10 InitBoard(6, 8); // 用例1同一行相邻两个同色方块0次转弯应连通 board[1, 1] 5; board[1, 2] 5; Debug.Assert(CanConnect(1, 1, 1, 2)); // 用例2同一行中间隔一个空格0次转弯应连通 board[1, 4] 6; board[1, 6] 6; // 下标5是空格 Debug.Assert(CanConnect(1, 4, 1, 6)); // 用例3需要转1次弯应连通 // (2,1)和(3,2)拐点在(2,2)或(3,1) board[2, 1] 7; board[3, 2] 7; board[2, 2] 0; board[3, 1] 0; Debug.Assert(CanConnect(2, 1, 3, 2)); // 用例4需要转2次弯应连通 // (2,1)到(4,2)路径 (2,1)-(2,2)-(3,2)-(4,2) board[2, 1] 8; board[4, 2] 8; board[2, 2] 0; board[3, 2] 0; Debug.Assert(CanConnect(2, 1, 4, 2)); // 用例5中间被方块挡死应不连通 board[3, 1] 9; board[3, 3] 9; board[3, 2] 9; // 堵住中间 Debug.Assert(!CanConnect(3, 1, 3, 3)); Debug.Assert(FindHint() ! null); // 当前棋盘至少有一对可消 }这些用例的价值不只是验证代码它们还是实验报告里“测试与验证”章节的现成素材。老师最怕看到报告写“程序运行正常”最想看到的是你明确列出了测试输入、预期输出、实际输出、边界情况。把上面 5 个用例整理成一张表格覆盖直线、单拐、双拐、阻挡、死局检测五类场景报告质量立刻和其他人拉开差距。如果还想再进一步可以在主程序里写一个自动模拟随机点选两个同色方块如果CanConnect返回 true 就模拟消除直到棋盘清空或死局统计通关率和平均重排次数。这个数据不是拍脑袋编的跑 1000 局出来的数字写进报告比任何截图都有说服力。这也是我把这个实验做得最有成就感的地方——判定器稳了其他全是细节。整个实验做下来我最深的体会是别急着写界面先把棋盘建模和 BFS 判定器这两个核心部分写对、测熟。界面只是展示层逻辑才是数据结构的重头戏。数据结构这课的成绩往往就藏在你能不能把一个看似“游戏功能”的需求拆成数组、队列、图搜索这些最基本的元素里。希望这篇笔记能帮你把这份实验做得更顺也希望你答辩时能挺直腰板说“这个消除判定器是我自己写的。”本文还有配套的精品资源点击获取