简介一份完整的武汉理工大学数据结构与算法综合实验连连看游戏开发报告面向学习数据结构与算法、C及MFC框架的本科生主要用于课程设计或综合实践参考。压缩包内包含1个docx文档大小约1.37MB内容涵盖实验目的与要求、需求分析、二维数组数据结构设计、三种消子判断算法一条直线、两条直线、三条直线连通的详细流程与C代码实现、胜负判断、提示、重排、计时及游戏模式设计并展示了使用MFC Dialog和GDI编程构建图形界面的思路。报告中对三种连通算法的路径搜索以及用栈保存关键点均有详细讲解并配有可运行代码片段读者可直接对照使用或在此基础上扩展关卡模式。报告还融入了软件工程化思维从系统需求分析到迭代开发均有说明。目前已有227人学习适合需要完成连连看课程设计或想深入理解数组、栈及连通算法应用的读者参考。1. 从“连连看”实验要求看数据结构课设的真实考点“武汉理工大学数据结构与算法综合实验连连看”这个标题看起来只是一门 C 语言课的期末大作业但放在编程能力和面试的语境里它是数据结构和算法综合能力最典型的压力测试。连连看这个选题不是让你做一个娱乐产品而是要你用数据结构和算法把“棋盘建模、图案匹配、连通路径搜索、死局检测、自动求解”这一整条链路打通。很多 5 年以上开发者也未必能在半小时内写出一个无死锁的消除判定。它考察的核心不是界面而是三件事如何抽象棋盘状态如何把“拐弯不超过两次”翻译成搜索算法以及如何控制最坏情况下的复杂度。这篇文章就从这三个维度把这条链路拆开讲清楚。2. 棋盘与消除连连看底层数据结构从二维数组到状态机有人看到“综合实验”四个字上来就画 UML 类图设计了一堆抽象接口最后代码没写几行反而被自己的架构套住。数据结构实验最忌讳过度设计。连连看的棋盘是一个天然的二维网格最直接的数据结构就是二维数组但真正决定代码质量的是你怎么用状态机去管理消除过程。2.1 为什么二维数组依然是成本最低的棋盘模型连连看的棋盘在逻辑上是一个ROWS × COLS的矩阵每个单元格的值表示一种图案空位用 0 表示。二维数组让随机访问的时间复杂度是 O(1)内存连续、缓存利用率高这在路径搜索里非常关键——因为你会在短时间内反复读取相邻格子。有些同学为了展示“高级”数据结构把棋盘设计成邻接表图结构每个格子是一个 Node 对象记录了上下左右四个指针。这个方案在理论课上可以讲但在实际操作里是给自己挖坑你需要额外处理节点生命周期路径搜索时指针跳转的局部性也很差。除非棋盘是稀疏的否则没有理由放弃顺序存储。另一个常见误区是把“格子值”和“格子状态”混在一个变量里。比如用board[r][c] -1表示已消除用0表示空位。听起来没问题但当你写“剩余图案数量”统计时就要小心-1和0的语义冲突。我的做法是棋盘只存图案值0 表示空需要记录“已消除”等额外状态时再开一个同尺寸的bool数组。空间换清晰度很划算。在代码实现上推荐用一维数组配合下标计算来模拟二维。这样做的好处是如果需要把棋盘状态存档或做网络传输可以直接对整个一维数组做 memcpy如果做“棋盘镜像”或“旋转”也只处理一段连续内存。2.2 消除条件的状态机从“两个相同”到“三态校验”很多第一次写连连看的同学把消除判断写成“两个格子图案相同就直接消掉”。这忽略了连连看真正的规则图案相同只是必要条件还必须存在一条拐弯不超过两次、且不经过任何非空格子的路径。所以这里需要一个状态机流程是检查两个坐标是否越界检查两个格子是否都是有效图案非空检查两个格子的图案值是否相等调用路径搜索算法检查二者之间是否存在合法路径如果路径合法把两个格子置空否则返回失败。这个流程里的第 4 步是最耗时的。如果你在 UI 层每点击一次都做一次全盘扫描那会非常卡。正确做法是把路径搜索独立成函数并且加上一层短路判断如果两个格子相邻直接返回 true如果两个格子在同一行或同一列先检查中间是否全部为空。2.3 数据结构的扩展如果要写存档和回放实验报告如果想拿高分通常会加“历史记录”或“回放”功能。这时候数据结构就要开始扩展了。我的建议是不要马上引入链表或树先用一个动态数组保存每一步的棋盘快照struct Step { int board[MAX_ROWS][MAX_COLS]; int r1, c1, r2, c2; }; vectorStep history;这是“时间换空间”的典型设计。每一步保存整个棋盘内存占用是每一步 100 字节 × 总步数一个 200 步的游戏也就 20KB 左右完全可接受。比维护增量补丁要简单得多而且回放时只需要依次恢复快照。如果你还希望支持“撤销”那更简单了把当前状态压栈撤销时从栈里弹出上一份快照。在设计上快照类最好实现serialize和deserialize方法这样存档可以落盘回放也可以从磁盘开始。下表是棋盘几种建模方式的选型对比模型随机访问复杂度内存与缓存局部性回放/序列化难度适用场景二维数组O(1)优低标准课设推荐一维数组下标运算O(1)最优极低性能敏感/嵌入式邻接表图O(邻接点数)差高理论展示不推荐哈希表索引图案位置O(1) 平均中中频繁检索同图案2.4 棋盘初始化与洗牌的代码实现棋盘初始化看起来很简单实际上有一个隐藏要求每种图案的出现次数必须是偶数否则最后一定会有无法消除的“孤子”。所以不能直接随机填充而是先构造一个图案池再打乱顺序。#include stdio.h #include stdlib.h #include time.h #include string.h #define ROWS 10 #define COLS 12 #define TYPES 6 int board[ROWS][COLS]; void init_board(int rows, int cols, int types) { int total rows * cols; // 图案池保证每个图案出现次数为偶数 int *pool (int*)malloc(sizeof(int) * total); for (int i 0; i total; i) { pool[i] (i % types) 1; // 1 到 types0 保留给空位 } // Fisher-Yates 洗牌 srand((unsigned int)time(NULL)); for (int i total - 1; i 0; i--) { int j rand() % (i 1); int tmp pool[i]; pool[i] pool[j]; pool[j] tmp; } // 一维池子转二维棋盘 int idx 0; for (int r 0; r rows; r) { for (int c 0; c cols; c) { board[r][c] pool[idx]; } } free(pool); }这段代码有几个细节需要说明。第一pool[i] (i % types) 1保证了图案按 1 到 6 循环总数 120 个格子每个图案恰好 20 个天然是偶数。第二洗牌用的是 Fisher-Yates它是无偏的每个图案分布都等概率不要用rand() % total反复交换那会引入偏差。第三这里刻意把 0 留空位棋盘上的图案值从 1 开始逻辑层判断时就用board[r][c] ! 0来判定是否为空。3. 连通性判定与路径搜索把“最多拐两次”翻译成算法这一章是连连看真正的核心算法部分。消除判定里最难的不是“图案相同”而是“存在一条符合条件的连通路径”。把两个差不多的格子消掉背后藏着一个经典问题在网格图中求一个拐弯次数受限的路径。3.1 形式化直线、单拐点与双拐点把连连看的路径规则形式化可以分成三种情况。第一种是直线路径。两个格子在同一行且中间所有格子都为空或者两个格子在同一列中间所有格子都为空。这种情况不需要搜索直接检查线段上的每个单元格即可。第二种是单拐点路径。两个格子的连线构成一个直角拐点出现在“以这两个点为对角顶点的矩形”的另外两个角之一。也就是如果起点是(r1, c1)终点是(r2, c2)那么潜在拐点只有两个(r1, c2)和(r2, c1)。检查的方法是确保拐点本身是空位并且起点到拐点、拐点到终点这两条线段都畅通。第三种是双拐点路径。路径形状是一个“Z”字形或者更复杂一点两个拐点分布在两条平行的水平线或垂直线上。如果两个格子既不在同一行也不在同一列双拐点路径可以看作先让一条线段从起点延伸到某个中间行r_k然后水平移动到终点的列再垂直到达终点。枚举所有可能的r_k和c_k即可。有一个细节容易被忽略很多实现允许路径从棋盘的外围边界绕过去也就是把棋盘外圈当作空位。比如起点在左下角终点在右上角路径可以贴着棋盘外圈走。解决方法是把整个棋盘逻辑上扩展一圈空位搜索时索引范围从[-1, ROWS]和[-1, COLS]扩大。在 C 数组里这通常用“坐标值平移”实现actor_r r 1actor_c c 1在逻辑坐标上搜索。3.2 用 BFS 把“拐弯次数”当成路径代价分情况枚举适合标准规则但如果想统一处理“最多拐 N 次”的变体或者想实现一个更优雅的框架BFS 会更好。BFS 状态里不再只记录坐标而是记录“方向”和“拐弯次数”这样可以对拐弯次数做一个最短路搜索。from collections import deque def has_path(board, r1, c1, r2, c2, max_turns2): 判断两点之间是否存在拐弯不超过 max_turns 次的路径 rows, cols len(board), len(board[0]) # 四个方向上、下、左、右 dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] # visited[turns][r][c] visited set() # 队列里存 (行, 列, 方向, 拐弯次数) q deque() # 起点可以向四个方向出发初始不算拐弯 for d in range(4): dr, dc dirs[d] visited.add((r1, c1, d, 0)) q.append((r1, c1, d, 0, [])) while q: r, c, direction, turns, path q.popleft() # 到达终点且拐弯次数不超过限制 if (r, c) (r2, c2): return True for nd in range(4): dr, dc dirs[nd] nr, nc r dr, c dc # 检查边界 if not (0 nr rows and 0 nc cols): continue # 不能走到非空格子除非是终点 if board[nr][nc] ! 0 and (nr, nc) ! (r2, c2): continue # 计算新拐弯次数 new_turns turns if nd direction else turns 1 if new_turns max_turns: continue state (nr, nc, nd, new_turns) if state in visited: continue visited.add(state) q.append((nr, nc, nd, new_turns, path [(nr, nc)])) return False这段 BFS 代码有几点值得注意。第一状态里包含了“方向”和“累计拐弯次数”这是最短路径题里常用的技巧本质上是在一个带有状态维度的图上做 BFS。第二new_turns只有在方向改变时才加一这正好匹配连连看的规则。第三visited 集合里记录了到达某格子的方向和拐弯次数也就是说同一个格子可能被访问多次只要方向和拐弯数不同这是必要的因为方向会影响后续路径。3.3 三个必调的剪枝参数BFS 在 10×12 的棋盘上表现还算可以但到了 30×40 的大棋盘就必须做剪枝和优化。第一个剪枝是“初始方向去重”。起点出队后如果两个方向是直线相对的比如上和下先走哪个都一样可以在入队时只保留一个方向。这个优化对减少队列长度很有效。第二个剪枝是“非法终点预判”。在 BFS 开始前先检查终点四周是否有至少一个空位或起点本身与终点相邻否则路径不可能到达。这是一个很便宜的提前退出条件能省掉大量无效搜索。第三个剪枝是“按候选路径排序”。在分情况枚举双拐点时先枚举较短的候选线段。因为短线段更可能不被障碍物阻挡命中概率更高平均扫描路径数会下降很多。下面这张表对比了常用的搜索思路方案最坏复杂度空间占用优点缺点分情况枚举O(ROWSCOLS)O(1)实现简单速度快规则一变就得重写BFS 最小拐弯O(ROWSCOLS4)O(ROWSCOLS4)通用可支持 N 次拐弯状态多内存略高回溯 DFS指数级O(路径长度)代码直观最坏情况不可控3.4 为什么“回溯 剪枝”也能用如果实验要求展示“剪枝算法”那用回溯法写出“全盘自动求解”是很好的加分点。回溯法的思路是递归扫描所有可消除对逐一尝试消除如果最终能清空棋盘就返回成功。回溯法里最关键的剪枝是“每次递归先找有且仅有一对可消除的棋子”。如果某一轮只有一对棋子能够相互连通那么这条分支是唯一确定的不用尝试其他选择。另一个剪枝是“提前检查剩余棋子是否还有可消除对”如果当前棋盘上根本不存在任何可消除对则直接回退不再扩展子节点。我实际写代码时会先实现find_all_pairs得到候选列表然后对候选列表按“曼哈顿距离”排序优先消除距离近的。这个排序不影响正确性但会显著减少回溯深度尤其是棋盘上一开始就有大量可选消除对的时候。4. 从控制台到可视化连连看界面分层与代码落地技巧很多同学写课设的第一天就打开图形库结果调了一个星期的坐标映射和事件循环核心算法一行没写。正确顺序是先做控制台版用命令输入坐标验证算法再包一层可视化界面。这样逻辑和表现分离出了问题能快速定位到底是算法 bug 还是 UI bug。4.1 控制台版“最小可运行”架构控制台版的逻辑层只暴露三个接口初始化棋盘、尝试消除、判断游戏结束。表现层就是打印棋盘和处理输入。进入游戏后输入r1 c1 r2 c2 示例2 3 2 8 退出-1 -1 -1 -1我用一个 while 循环驱动整个游戏流程代码如下while (1) { print_board(board, ROWS, COLS); int r1, c1, r2, c2; printf( ); scanf(%d %d %d %d, r1, c1, r2, c2); if (r1 -1) break; if (is_legal_remove(board, r1, c1, r2, c2)) { board[r1][c1] 0; board[r2][c2] 0; printf(消除成功\n); } else { printf(无法消除\n); } if (is_game_over(board, ROWS, COLS)) { printf(恭喜通关\n); break; } }这个循环非常容易调试。如果发现消除判定有误直接在控制台里输入坐标甚至可以写一个自动化脚本去模拟一连串输入用来做回归测试。界面层的东西全部不碰这样的分层让核心算法的正确性可以先被验证。4.2 可视化外壳的常见坑坐标映射与状态机当代码迁移到图形界面时最常见的 bug 是坐标映射。假设每个格子大小是 50×50 像素点击点(x, y)对应的格子坐标是(y / 50, x / 50)。这里是一个二维数组第一个下标是行对应绘图坐标的 y 轴第二个下标是列对应 x 轴。另一个坑是点击状态机。必须区分“当前没有选中任何棋子”“已经选中第一个棋子”“正在播放消除动画”三种状态。如果用一个int selected_r -1去记录代码很快就变成一团乱麻。我建议用枚举typedef enum { STATE_IDLE, STATE_SELECTED, STATE_ANIMATING } ClickState;在STATE_SELECTED状态下再次点击同一个格子应该取消选中点击另一个格子则尝试消除。很多初版实现把“取消选中”漏掉导致用户无法改选。下面给出逻辑层和表现层的职责划分这是多层架构的骨架功能点数据层/逻辑层职责表现层职责棋盘状态维护 board 数组读取并绘制图案玩家点击不感知鼠标坐标转换 状态机消除判定检查路径和条件调用后显示结果提示功能返回一对坐标高亮显示洗牌重排非空棋子触发重绘4.3 提示功能与全盘扫描的实现提示功能本质上是一次“找出任意一对可消除棋子”的全盘扫描。在 10×12 的棋盘上直接双重循环找所有同图案的点对再调用路径搜索即可。int find_one_pair(int board[ROWS][COLS], int *r1, int *c1, int *r2, int *c2) { for (int i 0; i ROWS; i) { for (int j 0; j COLS; j) { if (board[i][j] 0) continue; for (int k i; k ROWS; k) { for (int l (k i ? j 1 : 0); l COLS; l) { if (board[k][l] 0) continue; if (board[i][j] ! board[k][l]) continue; if (has_path(board, i, j, k, l)) { *r1 i; *c1 j; *r2 k; *c2 l; return 1; } } } } } return 0; }这段代码的关键在for (int l (k i ? j 1 : 0))。它杜绝了“同一对格子被扫描两次”的问题保证每一对坐标组合最多检查一次。这里的语义是如果第二层循环还在同一行就从j1开始如果到了下一行则可以从l0开始。这个写法能省掉一个重复判断。4.4 自动洗牌与“无解”检测当游戏进行到中后期棋盘上可能会出现没有任何一对可消除的局面。此时需要自动重排剩余棋子。洗牌时不能改变图案数量所以要先把非空格子的图案收集到临时数组里打乱顺序后重新填回非空位置。洗牌完成后还需要再检查一次是否立即存在可消除对。如果依然不存在就再洗。为了防止死循环设定一个最大重试次数比如 20 次。达到上限后可以直接给用户提示“本局已无解”这在很多商业连连看里也被称作“死局”。这里的设计逻辑是洗牌只是“重新排列”不是“重新生成图案”因为图案频率表已经定死重新生成会破坏“每种图案数量偶数”的约束。5. 最后一关死局检测、自动求解与性能优化如果前面的章节只是让你“能玩”这一章决定实验报告是 80 分还是 95 分。5.1 死局检测不能只看剩余棋子数量游戏结束的条件不是“剩余棋子数为 0”而是“不存在任何可消除对”。这个检测用第 4 章里的find_one_pair来实现返回 0 且棋盘上还有非空格子就是死局。死局时可以做两件事自动洗牌或者提示玩家手动洗牌。这里有一个优化点不要每次消除后都扫描全盘而是维护一个计数器当剩余棋子数降到某个阈值比如 20 个再扫描这样能避免每步的无效计算。5.2 自动求解用回溯和剪枝跑通全盘自动求解是“加分项”里最常见的实现。它本质上是对整个消除顺序做一个搜索。因为每一次消除都会改变棋盘所以必须用带撤销的回溯法。def solve(board, steps): pairs find_all_pairs(board) if not pairs and is_empty(board): return steps if not pairs: return None # 剪枝优先消除“唯一配对”的格子 for r1, c1, r2, c2 in sorted(pairs, keymanhattan_distance): v1, v2 board[r1][c1], board[r2][c2] board[r1][c1] board[r2][c2] 0 result solve(board, steps [(r1, c1, r2, c2)]) if result is not None: return result board[r1][c1], board[r2][c2] v1, v2 return None在刚才这段代码里manhattan_distance排序是关键剪枝。距离近的棋子对更容易让棋盘变得“稀疏”从而给后续消除创造空间。每次递归前先调用is_empty判断提前终止也避免了不必要的继续搜索。5.3 棋盘增大时的性能优化策略如果实验要求支持 30×40 的大棋盘暴力 BFS 会开始显示卡顿。这时需要做两件事。第一把“检查两点是否连通”的路径搜索从“每次计算”改为“带缓存记忆化”用一个哈希表记录已经计算过的点对结果。第二为每种图案建立“位置索引表”这样搜索同图案候选点时不需要遍历整个棋盘。实测数据表明10×12 棋盘上的全盘扫描耗时约 5ms而 30×40 棋盘如果加上位置索引和缓存扫描时间可以控制在 25ms 以内。这个指标对“提示”按钮来说足够流畅。5.4 对抗测试用自动化脚本代替手工点击最后一个技巧不要手动点鼠标验证算法。我习惯在逻辑层写一个run_all_tests()函数里面放几组特殊棋盘全空棋盘所有格子为空任何两点都不应有路径两个相同图案相邻必须能直接消除两个相同图案被一个障碍物隔开必须被判定为不可消除两个相同图案位于棋盘外圈对角验证外圈路径是否生效只留下一对可消除棋子验证死局检测能不能正确触发洗牌。把这些用例写成断言每次修改完算法后跑一遍比玩十遍游戏都管用。没有任何一个可靠的连连看实现是完全靠手工点出来的。本文还有配套的精品资源点击获取