简介武汉理工大学数据结构与算法实验的欢乐连连看项目以游戏为载体系统训练非线性结构的综合运用适合计算机专业学生、课程设计参考者及需要动手理解树、图、哈希表的开发者。压缩包共281个文件、约227MB核心由9个cpp源码和13个h头文件组成附带Visual Studio解决方案配置、exe可执行文件、编译中间文件及bmp/ico图像资源Git仓库对象也完整保留可作为版本管理学习素材。目前已有2570人浏览学习。项目完整实现连连看核心玩法包括邻接矩阵/邻接表建模、图案匹配与消除判定、DFS/BFS搜索路径等模块便于对照源码观察非线性结构在真实游戏逻辑中的运行流程。可直接运行exe验证效果也能基于sln重新编译调试对数据结构课程实验和期末设计都有较高参考价值。1. 连连看实验到底在考什么非线性结构不是难点建模才是某高校的数据结构实验里连连看通常是“非线性结构”那一章的大作业标题还带着“欢乐”两个字听起来比写红黑树轻松实际上翻车率并不低。很多人第一反应是找一份现成的连连看源码跑起来结果发现评分里一半分数落在“结构设计说明”上另一半在搜索算法的正确性。这个实验真正的考点不是做一个能玩的游戏而是把“两个图案能否消除”这件事抽象成一张图再在图模型上做路径搜索。棋盘格子之间的连通关系属于拓扑关系不是线性表能直接表达的这正是“非线性结构”四个字想让你动用的东西。如果你是正在做这个实验、或者打算做但还没想清楚数据结构怎么选这篇能给你一条走得通的落地路径。我自己的习惯是先写判定函数再写界面层顺序反了会一直陷在显示层的泥潭里。2. 给连连看建立图模型二维数组存棋盘BFS 解决连通判定2.1 为什么棋盘要用二维数组而不是链表连连看的棋盘是固定行列的网格最常见的做法是直接用vectorvectorint或者二维数组来存。每个格子存一个整数值0 表示空格非 0 表示某种图案的编号。这个选择背后是有理由的连连看的搜索核心是“从一个格子出发判断能否到达另一个格子”这要求对任意坐标的读取是 O(1)二维数组天然满足。链表结构在插入删除上有优势但连连看棋盘在游戏过程中只有“某个格子从图案变成空格”这一种修改数组同样能 O(1) 完成链表反而会让坐标寻址变得别扭。图模型在这里是隐式的把每个非空格子看成一个顶点把相邻的空格子之间的通行关系看成边棋盘就形成了一张网格图。值得注意的是这张图是动态变化的——每消除一对图案就有两个顶点从“不可通行”变成“可通行”。所以在写搜索算法时棋盘数据必须是搜索函数的输入参数而不是全局变量里一份被界面反复改动的副本。常见做法是维护一份board作为唯一数据源判定函数每次接收当前局面的拷贝或引用。2.2 搜索算法选型为什么首选 BFS 而不是 DFS连连看的消除规则是两个相同图案之间能用不超过三段直线段连接也就是路径最多拐两次弯。这里有一个关键误区——大部分人会下意识去找“最短路径”以为路径越短越能消除但规则根本不看路径长度只看拐弯次数。于是问题转化成在网格图上找一条从起点到终点的路径使得方向变化的次数不超过 2。BFS 在这里是天然匹配的。把“拐弯次数”当作路径代价直行代价为 0拐弯代价为 1那么这就是一个边权只有 0 和 1 的最短路问题。普通 BFS 队列能处理边权为 1 的图但处理不了边权为 0 的情况所以这里需要用一点小变体把状态扩展分为“先直行到底再拐弯”的层序处理或者直接用 0-1 BFS双端队列。在棋盘尺寸不大比如 10x10 到 16x14的前提下实现一个带拐弯计数的普通 BFS 也完全可行只需要在状态里多记录当前方向和已经拐了几次。DFS 为什么不推荐因为 DFS 会沿着一条路走到底很容易走进死胡同而且为了找到“拐弯不超过 2”的路径DFS 需要回溯大量分支状态爆炸的概率远高于 BFS。在棋盘搜索这种场景下BFS 的层序扩展能保证第一次遇到终点时的拐弯次数就是最小的DFS 没法保证这一点。实际实验中用 DFS 写的判定函数经常出现“明明能消除却判定不可达”的问题排查起来极其痛苦。2.3 状态设计方向 拐弯次数才是完整的状态初写 BFS 的人最容易犯的错误是只用一个二维visited数组记录格子是否访问过。这在普通最短路里没问题但在拐弯约束下是不够的。同一个格子从左边进入和从上方进入后续可走的路径集合完全不同就算到达同一个格子的拐弯次数相同只要进入方向不同后续能扩展的分支就不同。所以visited必须升级成三维标记vis[x][y][dir]表示在坐标(x,y)处、当前朝向为dir时的最小拐弯次数。我用的是四方向编号0 上、1 下、2 左、3 右。状态结构体里存三个字段坐标、当前方向、已拐弯次数。从起点出发时没有方向可以枚举四个方向作为初始状态每个方向的拐弯次数从 0 开始。转移时如果下一步的方向和当前方向一致拐弯次数不变如果不一致拐弯次数加 1超过上限 2 就剪枝。这个“方向变化才计数”的模型是连连看判定算法的核心也是后面所有坑的源头。3. 消除判定算法的完整实现状态搜索与边界处理3.1 核心 BFS 路径搜索代码先给出判定两个格子能否消除的完整函数实现。这里用双端队列做 0-1 BFS直行优先扩展保证拐弯次数最小时尽早命中终点。#include deque #include vector using namespace std; struct State { int x, y; // 当前格子坐标 int dir; // 当前移动方向0上 1下 2左 3右 int turns; // 已经拐弯的次数 }; // board: 棋盘数据board[x][y] 0 表示空格非0表示图案编号 // 判断 (sx, sy) 与 (ex, ey) 两个格子是否能在拐弯不超过2次内连通 bool canConnect(const vectorvectorint board, int sx, int sy, int ex, int ey) { if (board[sx][sy] 0 || board[ex][ey] 0) return false; if (board[sx][sy] ! board[ex][ey]) return false; if (sx ex sy ey) return false; int rows board.size(); int cols board[0].size(); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; // vis[x][y][dir] 记录到达 (x,y) 且朝向为 dir 时的最小拐弯次数 // 初始化为 -1 表示未访问 vectorvectorvectorint vis( rows, vectorvectorint(cols, vectorint(4, -1))); // 0-1 BFS拐弯少的状态优先从队头出队 dequeState dq; // 起点本身不可作为路径经过点从起点的四个相邻格子开始扩展 for (int d 0; d 4; d) { int nx sx dx[d], ny sy dy[d]; if (nx 0 || nx rows || ny 0 || ny cols) continue; // 相邻格子是终点时方向一致且不需要经过空格 if (nx ex ny ey) return true; // 只有空格可以经过 if (board[nx][ny] ! 0) continue; vis[nx][ny][d] 0; dq.push_back({nx, ny, d, 0}); } while (!dq.empty()) { State cur dq.front(); dq.pop_front(); for (int nd 0; nd 4; nd) { int nx cur.x dx[nd], ny cur.y dy[nd]; if (nx 0 || nx rows || ny 0 || ny cols) continue; // 到达终点终点本身可以是图案格不需要是空格 if (nx ex ny ey) { int nt cur.turns (nd ! cur.dir ? 1 : 0); if (nt 2) return true; continue; } // 路径经过的格子必须是空格 if (board[nx][ny] ! 0) continue; int nt cur.turns (nd ! cur.dir ? 1 : 0); if (nt 2) continue; // 只有更优的拐弯次数才继续扩展 if (vis[nx][ny][nd] -1 || nt vis[nx][ny][nd]) { vis[nx][ny][nd] nt; if (nd ! cur.dir) { dq.push_back({nx, ny, nd, nt}); } else { dq.push_front({nx, ny, nd, nt}); } } } } return false; }这段代码的三个关键设计要说明一下。第一起点的相邻格子如果正好是终点直接返回 true这是“两格紧挨着”的消除场景不需要经过任何空格。第二终点判断放在障碍判断之前因为终点本身是有图案的格子不能被当成障碍拦掉这是很容易写反的地方。第三用双端队列做 0-1 BFS方向不变的状态放入队头优先扩展拐弯的状态放入队尾这样能更快找到拐弯次数少的路径同时也避免普通 BFS 里同层扩展顺序对结果的影响。3.2 边界处理路径能否走出棋盘一个容易被忽略的问题是路径能不能经过棋盘外部的区域多数网络上的连连看实现不允许路径走出棋盘但某些变体规则允许连线绕过棋盘边缘。我的建议是实验里明确写成“不允许出界”因为题目通常只要求在棋盘内部寻找路径而且允许出界的搜索需要额外处理虚拟外圈代码复杂度会明显上升。上面给出的版本是不允许出界的。如果你想让路径允许贴边绕行有一个取巧的办法在原棋盘四周加一圈全 0 的虚拟格子搜索时把边界扩大到rows2、cols2这样路径就能“走出棋盘”了。但要注意终点和起点的坐标也要相应偏移否则坐标映射会乱。我见过有人在答辩时被老师问“边界情况怎么处理”答不出“外圈虚拟空格”方案这就是平时没想过的细节。3.3 参数设计一行代码控制游戏难度搜索算法本身的参数不多真正影响难度的是棋盘尺寸和图案种类数。棋盘越大、图案种类越多可消除的对越少死局概率越高。一个比较稳的参数组合是8 行 10 列配 5 种图案或者 10 行 12 列配 6 种图案。图案种类数的上限要满足rows * cols / 2能整除种类数否则图案数量不平衡必然出现“某一个图案多一个”的生成错误。// 参数配置示例 int rows 10, cols 12; int types 6; // 图案种类数 int board[10][12]; // 实际使用时用 vectorvectorint判定函数是纯内存计算单次搜索在 10x10 的棋盘上耗时不到 1 毫秒。如果实测中发现点击后有明显卡顿优先检查是不是把整份棋盘拷贝传参了传引用能省掉大量复制开销。另一个性能隐患是每次调用canConnect都重新分配三维vis数组这个可以接受但如果你要做“自动提示”功能会频繁调用数百次搜索那就要考虑复用内存或者把vis改成整型时间戳标记。4. 地图生成与可解性保证随机地图不随机洗牌逻辑要闭环4.1 生成合法地图成对填充再洗牌连连看地图生成的核心约束是每个图案必须成对出现。最稳妥的做法是先生成一个包含所有图案对的一维数组随机打乱后再填入棋盘。#include algorithm #include random #include vector using namespace std; // 生成棋盘rows*cols 必须是偶数 vectorvectorint generateBoard(int rows, int cols, int types) { int total rows * cols; if (total % 2 ! 0) return {}; // 格子数必须为偶数才能成对 // 每对图案的编号为 i % types vectorint values; for (int i 0; i total / 2; i) { values.push_back(i % types); } // 复制一份保证每种图案都有成对的另一半 vectorint all values; all.insert(all.end(), values.begin(), values.end()); // 随机打乱 mt19937 rng(random_device{}()); shuffle(all.begin(), all.end(), rng); // 填入二维棋盘 vectorvectorint board(rows, vectorint(cols)); int idx 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { board[i][j] all[idx]; } } return board; }这里有个容易踩的坑如果直接for (int i 0; i total / 2; i) values.push_back(i % types)那么当total / 2大于types时每种图案会出现多对这没问题但你需要保证total / 2能被types整除否则某些图案会比其他图案多一对消除到最后会剩下无法配对的格子。所以实际参数选择时我会先算一下(rows * cols / 2) % types 0不满足就把types调小或者把棋盘调大。4.2 可解性验证与自动重排随机生成的棋盘不能保证一定“有解”这里的“有解”指至少存在一对可消除的图案。一个合格的开局应该保证玩家第一步一定有可消除的对。最直接的做法是生成后跑一遍全棋盘扫描调用canConnect检查是否存在任意一对相同图案可消除。// 检查当前棋盘是否存在至少一对可消除的格子 bool hasValidMove(const vectorvectorint board) { int rows board.size(), cols board[0].size(); for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (board[i][j] 0) continue; for (int ii 0; ii rows; ii) { for (int jj 0; jj cols; jj) { if (i ii j jj) continue; if (board[i][j] ! board[ii][jj]) continue; if (canConnect(board, i, j, ii, jj)) return true; } } } } return false; } // 无解时重新洗牌 void shuffleBoard(vectorvectorint board) { int rows board.size(), cols board[0].size(); vectorint values; for (int i 0; i rows; i) for (int j 0; j cols; j) if (board[i][j] ! 0) values.push_back(board[i][j]); // 随机打乱后填回非空格 mt19937 rng(random_device{}()); shuffle(values.begin(), values.end(), rng); int idx 0; for (int i 0; i rows; i) for (int j 0; j cols; j) if (board[i][j] ! 0) board[i][j] values[idx]; // 重排后仍然无解就继续重排 if (!hasValidMove(board)) shuffleBoard(board); }这里的洗牌逻辑有个很玄学的现象随机重排后有解的概率其实很高普通 10x10 棋盘配 6 种图案无解概率大约只有百分之几所以递归重排基本不会陷入死循环。但如果地图参数设置得很极限比如 6x6 配 3 种图案无解概率会急剧上升递归洗牌的深度可能变得不可控。我通常会在洗牌函数里加一个重试上限比如 20 次超过后就放宽参数重新生成避免极端情况下程序卡死。4.3 消除操作的主流程点击、判定、更新地图生成和判定函数都准备好后游戏主逻辑就非常简单了。点击第一个格子时记录坐标和图案编号点击第二个格子时调用canConnect返回 true 就把两个格子置 0然后检查是否胜负。这里要特别注意每次消除后棋盘发生变化之前“无解”的局面可能变“有解”因为空格变多了路径选择更多。所以必须在每次消除后重新调用hasValidMove不是只在开局检查一次。“死局检测”和“洗牌按钮”是实验报告里的加分项。我在实现时把这两个功能绑定在一起每次消除后如果hasValidMove返回 false就弹出提示让玩家选择洗牌或者判定失败。洗牌时只打乱剩余非空格不打乱已经消除的空格否则棋盘会出现“虚空生成新图案”的 bug。基于时间戳的vis复用技巧在这里能派上用场死局检测需要遍历所有格子对最坏情况要调用 O(n²) 次搜索如果每次都重新分配三维数组UI 线程会有明显卡顿。5. 避坑连连看搜索里最容易翻车的五个细节5.1 终点格子被当成障碍拦截现象两个相邻的相同图案点击后判定不可消除别的格子之间却没这个问题。原因BFS 的转移条件里写了if (board[nx][ny] ! 0) continue;放在终点判断之前导致终点格本身是图案被当成障碍提前剪掉了。解决终点的判断必须放在障碍判断之前。我在前面代码里已经把nx ex ny ey的检查放在board[nx][ny] ! 0之前顺序不能反。这是连连看判定函数里最隐蔽也最常见的 bug排查方法是在canConnect入口打印起点终点的坐标和图案值。5.2 只记录二维 visited导致错误剪枝现象有些明明能消除的格子对搜索返回 false而且换一组格子又恢复正常。原因visited只记录(x,y)坐标同一格子先被某个方向访问后其他方向到达该格子的状态被丢弃。但不同方向进入同一格子的后续路径能力完全不同可能先到的那条路已经用掉了 2 次拐弯另一条路还一次拐弯都没用却被错误的“已访问”标记挡住。解决把visited改成三维vis[x][y][dir]保存每个方向独立的最小拐弯次数。这是整个实验里最重要的数据结构设计点写代码之前先在草稿纸上画一张 3x3 的棋盘模拟一遍状态扩展比直接写代码再调试快得多。5.3 起点和终点相同导致循环判断现象玩家连续点击同一个格子程序进入死循环或者判定为“可消除”。原因起终点坐标相同时BFS 的终点判断会立刻命中但此时并没有任何路径属于无效消除。解决函数入口直接加上if (sx ex sy ey) return false;。这个检查看起来多余但没有它点击第二次同一个格子时会直接消除而且是零步“消除”严重破坏游戏规则。5.4 洗牌时把已消除的空格也打乱了现象点击洗牌后棋盘上原本空着的位置出现了图案而且总数不对。原因洗牌函数遍历整个棋盘把所有格子都收进数组包括值为 0 的空格打乱后空格也被填上了图案。解决洗牌只收集非空格子。我上面的shuffleBoard里只把board[i][j] ! 0的值放进数组重新填充时也跳过空格位置。这一点看起来是“低级错误”但在边界条件没想清楚时很容易犯而且一旦出现对局数据就彻底乱了。5.5 拐弯次数统计的起止偏差现象路径明明拐了三次弯却判定成功或者只拐了一次弯却判定失败。原因起点初始化时把四个方向的turns都设为 0这样第一个格子直走到第二个格子时确实算 0 次拐弯但如果起点出发是斜着走的——虽然棋盘只有四方向斜走并不存在——这里的问题是终点相邻时的拐弯计数从起点到终点如果直接到达没有dir可比较有些实现会强行把这次移动算成一次拐弯导致相邻格子反而消除失败。解决在起点初始化阶段先检查四个相邻格子是否是终点是就直接返回 true把这个场景从 BFS 主流程中摘出去。终点相邻不需要任何拐弯这是规则上的例外单独处理比硬塞进状态转移要干净得多。6. 进阶双向 BFS 加速自动提示用路径回溯做消除动画当你把基础判定函数跑通之后实验成绩的上限取决于两点自动提示功能和消除动画。自动提示的本质是“找到任意一对可消除的格子”如果每次都用双重循环嵌套canConnect10x10 棋盘最坏要跑几百次搜索界面会卡到肉眼可见。我用的是双向 BFS 的思路从起点和终点同时扩展各自维护一套vis状态当两个方向的扩展区域相遇时说明找到一条连通路径。双向 BFS 对“拐弯次数”这类约束同样适用只需要在状态里同时记录方向相遇时合并双方的拐弯次数判断总拐弯是否不超过 2。实现提示功能时有一个比双向 BFS 更实用的技巧把“从某个点能走到的所有格子”预计算缓存下来。在棋盘开局和每次消除后遍历所有非空格子以每个格子为起点跑一次 BFS记录它能到达的所有同图案格子结果存进一个哈希表。后续调用提示时直接查表就能返回一组可消除对速度从 O(n²) 搜索降到 O(1) 查表。代价是每次棋盘变化后需要重建缓存但棋盘规模小重建一次也就几十毫秒完全在可接受范围内。路径回溯则是动画层的事。canConnect只返回布尔值但如果你想做“消除时高亮连线”需要额外的parent数组记录每个状态是从哪个状态转移过来的终点命中后再反向回溯得到完整路径点列表。常见的做法是定义一个Node结构体数组每个扩展状态保存前驱下标找到终点后用栈弹出路径。在做界面输出时把路径中的拐点坐标转成折线绘制指令就能看到一条清晰的三段式连线。我做这个实验时最后一个教训是canConnect函数一定要保证“前后两次调用之间不依赖任何全局状态”。某次我图省事把vis数组声明成全局复用结果上一次搜索残留的标记污染了下一次判定查了大半天才发现是初始化没清干净。后来我强制要求自己每个搜索函数内部自带状态初始化宁可多花几次内存分配也不碰全局复用。这个习惯后来在写更复杂的图搜索时帮了大忙。希望这篇能帮你在实验里少走几步弯路把时间花在理解图结构本身而不是和诡异的 bug 较劲。本文还有配套的精品资源点击获取
