简介武汉理工大学数据结构与算法实验“欢乐连连看”完整项目包面向计算机科学与软件工程专业学生用于理解树、图、哈希表等非线性结构在真实游戏场景中的设计与应用。资源以Visual Studio解决方案形式组织共281个文件7z压缩包约226.97MB涵盖C源文件与头文件.cpp/.h、编译生成的中间文件.obj/.tlog/.ipch、可执行程序与调试文件.exe/.pdb以及界面所需的位图.bmp和项目配置文件.xml/.suo等便于直接加载与二次开发。项目围绕连连看核心玩法集中展示深度优先搜索、广度优先搜索与动态规划在路径查找和匹配策略中的具体实现同时涉及邻接矩阵/邻接表建模、哈希表状态记录等关键技巧可帮助学习者将课堂理论映射为可运行代码。目前已有2570人学习浏览适合课程设计、期末实验或面试算法复习时参考借鉴。1. 数据结构综合实验里的连连看非线性结构不是噱头某高校的《数据结构与算法综合实验》把欢乐连连看作为课程设计主题时很多人第一反应是“这不就是个消消乐游戏”真正打开 LLK.sln 才发现决定游戏能不能跑起来的不是那几百行绘图和事件代码而是棋盘建模、图案索引、连通性判定这一整套非线性结构设计。棋盘本身是二维数组属于线性结构的直觉范畴可一旦要回答“哪些图案还能消”“这两个格子连不连得通”“剩余局面是不是死局”问题立刻就变成图和哈希表的活。这套实验值得拆的地方就在这里把一个看似休闲的游戏拆成图的连通性问题、哈希索引问题和路径搜索问题顺带把 DFS、BFS 这类算法落到一个能编译、能断点调试的 Visual Studio 工程里。适合课程设计需要参考实现、或者想对照成熟工程省掉环境折腾的同学。2. 非线性结构选型棋盘二维数组、空格连通图与图案哈希索引2.1 棋盘是二维数组可连通性却要用图来建连连看棋盘的静态存储用二维数组就够了board[y][x]存图案编号0 表示空格。但路径搜索真正关心的是“空格之间的连通关系”图案编号在搜索阶段完全不参与判断。直接把棋盘当图用会很别扭每个格子的四个邻居里有图案的格子不能用只有值为 0 的空格才允许通过。所以常见做法是维护一张只包含空格的连通图每次消除之后做局部更新。// connect_graph.h #include vector struct Point { int x, y; }; class ConnectGraph { public: ConnectGraph(int rows, int cols) : rows_(rows), cols_(cols), adj_(rows * cols) {} void rebuild(const std::vectorstd::vectorint board) { for (auto list : adj_) list.clear(); for (int y 0; y rows_; y) { for (int x 0; x cols_; x) { if (board[y][x] ! 0) continue; // 只给空格建图 int idx y * cols_ x; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 || nx cols_ || ny 0 || ny rows_) continue; if (board[ny][nx] 0) adj_[idx].push_back(ny * cols_ nx); } } } } private: int rows_, cols_; std::vectorstd::vectorint adj_; // 邻接表空格坐标的一维索引 static constexpr int dx[4] {1, -1, 0, 0}; static constexpr int dy[4] {0, 0, 1, -1}; };逻辑说明board[ny][nx] 0才加边这样 BFS 搜索时不用每次都判断图案值idx y * cols_ x把二维坐标压成一维避免在邻接表里存Point结构体省内存也方便数组索引。方向数组dx/dy是四连通标准写法顺序无所谓只要和后续 BFS 的方向编号保持一致。参数说明rows_/cols_是棋盘行列数adj_长度固定为rows * cols棋盘内每个空格都有一条到四条边。实际工程里不需要每次消除都全量rebuild棋盘 10×14 这种小规模全量重建也就几百次循环但如果棋盘更大可以在消除两个格子后只对这两个格子所在行和列做局部邻接更新性能差异明显。为什么不用邻接矩阵棋盘一般 10×14、14×18空格最多一两百个邻接矩阵要N*N个 bool浪费且遍历邻居时要扫一整行。邻接表只保存实际连通的边BFS 展开邻居时直接拿到可走格子不需要额外过滤。这也是很多课程设计最容易忽略的点二维数组负责“存数据”连通图负责“描述关系”两者职责不同混在一起写会让路径判定代码越来越乱。2.2 图案哈希索引把“有没有可消除对”从全盘扫描变成 O(P)连连看还有个隐藏需求快速知道某个图案还剩哪些位置以及当前局面是否死局。如果每次点击都全盘扫二维数组棋盘 140 格还能忍但“提示”按钮和“死局检测”一旦要做全盘候选扫描每次 O(rows*cols) 就会拖慢响应。用哈希表做图案索引是更自然的选型。#include unordered_map #include vector struct Point { int x, y; }; // key: 图案编号, value: 该图案仍留在棋盘上的坐标集合 std::unordered_mapint, std::vectorPoint patternIndex; void RemoveFromIndex(int type, int x, int y) { auto vec patternIndex[type]; for (auto it vec.begin(); it ! vec.end(); it) { if (it-x x it-y y) { vec.erase(it); return; } } } bool AddToIndex(int type, int x, int y) { patternIndex[type].push_back({x, y}); return true; }逻辑说明消除成功后调用RemoveFromIndex把坐标从对应图案的 vector 里删掉AddToIndex用于初始化局面。哈希表的查询平均 O(1)拿到某个图案编号就能直接枚举它剩余的所有位置不需要再遍历整个棋盘。参数说明type是图案编号从 1 开始0 保留给空格Point可以用std::pairint,int替代但结构体字段名更直观。需要留意 vector 删除是 O(n) 的如果同一图案剩余位置很多可以换成std::unordered_setint存一维索引代价是坐标转换多一步。这个结构的价值在“提示”功能和死局判定上体现得很直接提示按钮遍历patternIndex里每个图案的坐标集合两两配对调用连通判定死局判定则是检查是否所有图案对都不可连通。没有哈希索引时每轮都要重建候选清单有索引后候选数量只和未消除图案数相关。下表是三种数据结构在这个场景里的定位对比方便答辩时讲清楚选型理由数据结构存什么亮点坑二维数组 board棋盘快照读写 O(1)、直观不回答连通性问题邻接表图空格可达关系BFS/DFS 直接展开邻居需要维护一维索引映射unordered_map 图案索引图案剩余坐标候选查找 O(1)vector 删除是 O(n)可换 set这里有个常见误用有人把“图结构”理解为要把每个格子都建成节点包括有图案的格子。实际上连连看的规则决定了路径只能经过空格图案格子是障碍物。所以图里只有空格两个端点要消除的图案在搜索时被当作“临时可通行”处理即可。这个边界如果不划清后面 BFS 会写出大量判断障碍物的分支。3. 路径判定算法零拐直连、一拐枚举与最少转弯 BFS3.1 零拐与一拐边界条件先用几何直判连连看的路径规则是两点之间最多两个拐弯路径只能走棋盘内空格。最朴素的实现是先处理零拐和一拐这两个简单情况再交给 BFS 处理二拐。零拐就是同行或同列且中间全空一拐就是枚举一个拐点让两段都满足零拐。bool IsLineEmpty(const vectorvectorint board, int x1, int y1, int x2, int y2) { if (x1 x2) { int step (y1 y2) ? 1 : -1; for (int y y1 step; y ! y2; y step) if (board[y][x1] ! 0) return false; } else if (y1 y2) { int step (x1 x2) ? 1 : -1; for (int x x1 step; x ! x2; x step) if (board[y1][x] ! 0) return false; } else return false; return true; } bool IsOneCorner(const vectorvectorint board, int x1, int y1, int x2, int y2) { if (board[y1][x1] 0 || board[y2][x2] 0) return false; if (x1 x2 || y1 y2) return IsLineEmpty(board, x1, y1, x2, y2); Point corners[2] { {x1, y2}, {x2, y1} }; for (auto c : corners) { bool canPass (board[c.y][c.x] 0) || (c.x x1 c.y y1) || (c.x x2 c.y y2); if (canPass IsLineEmpty(board, x1, y1, c.x, c.y) IsLineEmpty(board, c.x, c.y, x2, y2)) return true; } return false; }逻辑说明IsLineEmpty是开区间判断不包含两端点所以两点相邻时循环不执行直接返回 true。IsOneCorner里两个候选拐点分别是(x1,y2)和(x2,y1)它们必须为空或者和某个端点重合。参数说明board的 0 语义是空格/已消除board[y][x]习惯要注意后面所有函数都统一y在前x在后避免下标写反。这段代码能提前筛掉大量不需要进 BFS 的简单情况。3.2 BFS 按“转弯次数”搜索dist 最小与转弯最少不是一回事二拐路径是连连看最核心的判定。教科书里的 BFS 通常求最短步数但这里要的最少“转弯次数”步数完全无所谓。如果直接用普通 BFS 记录步数会得到一条绕远但直行的路径也可能是一条转弯三连的短路径后者直接违反游戏规则。我见过不少翻车案例两个图案明明二拐能连上程序却提示不可消除就是因为 visited 数组只记了坐标没记方向。struct Node { int x, y, turn, dir; }; // dir: 0左 1右 2上 3下 bool CanConnectWithBFS(const vectorvectorint board, int x1, int y1, int x2, int y2) { const int maxTurn 2; dequeNode q; int dist[20][20][4]; // 按棋盘上限开或动态分配 memset(dist, 0x3f, sizeof(dist)); for (int d 0; d 4; d) { // 起点四个方向视为 0 转弯 dist[y1][x1][d] 0; q.push_back({x1, y1, 0, d}); } while (!q.empty()) { Node t q.front(); q.pop_front(); if (t.turn dist[t.y][t.x][t.dir]) continue; // 过期状态 for (int d 0; d 4; d) { int nx t.x dx[d], ny t.y dy[d]; if (nx 0 || nx cols || ny 0 || ny rows) continue; if (board[ny][nx] ! 0 !(nx x2 ny y2)) continue; int add (d t.dir) ? 0 : 1; int nt t.turn add; if (nt maxTurn || nt dist[ny][nx][d]) continue; dist[ny][nx][d] nt; if (add 0) q.push_front({nx, ny, nt, d}); else q.push_back({nx, ny, nt, d}); } } for (int d 0; d 4; d) if (dist[y2][x2][d] maxTurn) return true; return false; }逻辑说明状态是“坐标 方向”dist[y][x][d]记录从起点、以方向 d 到达(x,y)的最少转弯次数。同一个格子从不同方向进入后续路径完全不同所以不能用二维 visited 一票否决。这里用 deque 做 01BFS直行代价 0 放队首转弯代价 1 放队尾保证按转弯次数从小到大的顺序扩展。参数说明maxTurn2是连连看规则上限起点四个方向都入队等价于“初始方向自由”如果没有这一步起点朝四个方向直走时会被误判为转向。add (d t.dir) ? 0 : 1是核心方向不变不增加转弯方向改变才加 1。为什么不写成普通 BFS priority_queue因为代价只有 0 和 1deque 插入是 O(1)priority_queue 是 O(log n)。对 10×14 棋盘差距不大但思路更干净。注意终点(x2,y2)本身可以是非空格搜索时要把终点放行否则永远找不到目标。3.3 全盘搜索做“提示”与死局判定别在每次点击时触发单次点击只用跑一次CanConnectWithBFS很快。但“提示”按钮要遍历所有候选对复杂度是 O(P × V × E)P 是剩余图案对数量V 是格子数E 是边数。棋盘小时没事图案种类多、剩余数量大时最高可能到几十万次状态转移集中在一次点击里会卡一下。常见做法是给“提示”和“死局检测”单独控制不在正常消除路径里跑全盘扫描。搜索候选时先按图案索引分组只对同一图案编号的坐标做组合判定数量远小于全棋盘两两配对。DFS 在这里也可以做但纯 DFS 找所有二拐路径容易在环上打转必须维护 visited 状态并且限制转弯深度。实际使用中 BFS 更稳DFS 更适合做“记录一条可行路径并回放”这种带路径动画的需求。如果要做提示排序先对候选对跑一遍 BFS 拿到最小转弯数再按转弯数升序排列优先提示转弯最少的。4. 避坑清单字符集、平台工具集、下标与工作目录4.1 先搞清楚工程里各个目录是干嘛的打开工程包第一件事不是双击 exe而是先看目录结构。LLK.sln 是 Visual Studio 解决方案文件Debug 目录下有编译好的 LLK.exe 和 LLK.pdb。.vs 文件夹是 VS 的本地缓存删了不影响源码.idea 文件夹是 JetBrains 系 IDE比如 CLion的工程配置用 VS 的同学不用管它.git 表示项目用 Git 管理提交代码前应该把 Debug、.vs 加进 .gitignore。路径作用注意事项LLK.slnVS 解决方案入口用 VS 打开别用记事本改Debug/LLK.exe编译输出双击运行可能受工作目录影响Debug/LLK.pdb调试符号断点看变量靠它别删.vs/本地缓存/用户配置可整体删除不影响代码.idea/JetBrains 系配置VS 用户不需要改.git/版本历史提交前把输出目录和缓存加进忽略稳妥运行方式是用 VS 打开 LLK.sln选 Debug x86 或 x64按 CtrlF5 启动。直接双击 Debug 里的 exe 也能跑但下面第 4.4 会说为什么有时候闪退。改过类头文件之后建议菜单里“生成 → 重新生成解决方案”避免旧对象文件残留导致奇奇怪怪的链接错误。4.2 避坑一中文注释乱码或界面方块字现象用新版 VS 打开旧工程源码注释变成乱码窗口标题和按钮文字显示成方块。原因老工程默认用 GBK代码页 936保存源文件新版 VS 默认按 UTF-8 读取编码对不上。解决如果不想转码在项目属性的“C/C → 命令行 → 其他选项”里加/utf-8让编译器按 UTF-8 处理源文件如果源码本来就夹杂 GBK 和 UTF-8更稳妥的办法是用 VS 打开文件后“文件 → 另存为 → 编码保存为 UTF-8 with BOM”逐个源文件统一。注意别用记事本默认保存它会把 UTF-8 BOM 去掉下次打开又乱。这个坑在课程设计里非常普遍因为很多模板工程是从老版本 VS 迁移过来的。判断方法很简单打开源码文件看“文件 → 高级保存选项”里的编码是什么。4.3 避坑二LNK2019 与“平台工具集不存在”现象链接阶段报LNK2019 无法解析的外部符号指向某个成员函数或者直接提示工具集未安装。原因Debug 和 Release 产物混在同一个输出目录旧对象文件带着过期符号定义更常见的是工程用 v142 平台工具集VS2019本机只装了 v143VS2022或者反过来。解决右键项目 → 属性 → 配置属性 → 常规 → 平台工具集改成当前 VS 匹配的版本。改完先“生成 → 清理解决方案”再重新生成。清理这一步不能省混着的 .obj 不删LNK2019 还会继续。PropertyGroup LabelConfiguration PlatformToolsetv143/PlatformToolset /PropertyGroup逻辑说明这段是 vcxproj 里的配置片段PlatformToolset指定编译工具链。参数说明v142 对应 VS2019v143 对应 VS2022两个版本可以互相切换但需要本机安装了对应组件。反之如果 VS Installer 里没装 C 桌面开发组件先去补装再回 VS 打开工程。4.4 避坑三双击 exe 闪退F5 却正常现象从资源管理器里双击 Debug/LLK.exe窗口闪一下就没了在 VS 里按 F5 运行一切正常。原因游戏启动时按相对路径读取关卡数据或资源文件双击 exe 时工作目录是 Debug 本身而数据可能在项目根目录或者 data 子目录。VS 调试运行时会自动把工作目录设为项目目录所以没问题。解决在项目属性 → 调试 → 工作目录里填$(ProjectDir)这样 F5 和双击的行为就一致了如果不想依赖工作目录把所有关卡 txt 拷到 exe 同级目录也是一种临时办法。我一般会在 main 函数开头打印一行当前工作目录路径出现闪退先看路径少猜很多次。4.5 避坑四数组下标习惯与 BFS 状态缺失现象棋盘上两个相同图案明明相邻点击却提示不可消除或者消除一次之后棋盘出现“幽灵格子”再点就卡死。原因board[y][x]写成board[x][y]C 的 vector 越界不一定会崩溃读的是错误坐标里的垃圾数据逻辑错但程序继续跑。BFS 端的原因更隐蔽visited 只记录坐标不记录方向第二次从另一个方向到达同一个格子时被直接丢弃可行路径被剪掉。解决全工程统一y * cols x的一维索引或者所有函数都严格board[y][x]BFS 的 dist 必须开成[y][x][dir]三维不要偷懒降成二维 bool。可以在CanConnectWithBFS里加一句断言assert(x 0 x cols y 0 y rows)一旦越界立刻暴露省得在调试器里翻半天。这个三维状态的设计我在 3.2 已经解释过真正跑起来踩坑时才会体会到它的必要性——第一次改成二维 visited 时看似更省内存结果漏掉了大量合法路径返工大半天。5. 验证与进阶棋盘自检脚本与最少转弯搜索的实战微调5.1 用 Python 脚本做棋盘正则化自检课程设计最怕手写测试棋盘时某个图案出现奇数次玩到最后一对永远消不掉还以为是算法 bug。写个小脚本在生成关卡数据时直接校验能省掉很多无意义调试。这个脚本放在工程 tools 目录下每次新增关卡先跑一遍再进游戏。import random def generate_board(rows, cols, types8): # 每个图案必须成对出现这是连连看能消完的基本前提 cells rows * cols pairs_per_type cells // 2 // types values [] for k in range(types): values [k 1] * (pairs_per_type * 2) while len(values) cells: values.append(0) # 多余格用空格补位 random.shuffle(values) return [values[i * cols:(i 1) * cols] for i in range(rows)] def check_board(rows, cols, grid): counter {} for y in range(rows): for x in range(cols): v grid[y][x] if v: counter[v] counter.get(v, 0) 1 for k, cnt in counter.items(): assert cnt % 2 0, f图案{k}出现{cnt}次不是偶数 print(棋盘校验通过所有图案数量均为偶数)逻辑说明generate_board先按图案种类生成配对数量再用 0 补足不是整对的格子洗牌后输出棋盘。check_board遍历统计每个图案出现次数凡是奇数直接断言失败。参数说明rows/cols是棋盘尺寸types是图案种类数types 0时函数会退化成全空格棋盘实际调用不要传 0。建议再加一个文件读写封装把生成的棋盘按“第一行行数列数后面每行用空格分隔”的格式写入 txtC 端写对应的加载函数解析两边用同一套格式约定。这个脚本的价值不只是生成数据它还是后期改版的地基。比如把棋盘从 10×14 改成 14×18手调数据很容易出错脚本生成后换算一下行列删改格式即可。我习惯把check_board接到 C 的关卡初始化函数里Debug 模式下每次加载棋盘都跑一遍Release 模式关掉兼顾速度和安全性。5.2 把 BFS 换成 A* 与双向 BFS什么时候值得二拐路径搜索的状态空间是rows * cols * 410×14 棋盘最多 560 个状态01BFS 几十微秒就跑完理论上没有换 A* 的必要。但“提示”按钮要批量判定候选对时可以先用 01BFS 算出每个候选对的转弯数然后按转弯数加曼哈顿距离排序优先提示更“近”的体验比随机弹一个好不少。算法状态代价队列结构适用场景朴素 BFS记录步数queue最短路问题不适用于连连看01BFS转弯代价 0/1deque连连看路径判定推荐A*启发式 代价priority_queue候选对排序可给提示功能用实际参数微调里有几个经验maxTurn从 2 改成 1游戏直接变成“仅零拐和一拐可消”难度陡增适合做困难模式图案种类越多死局概率越高10×14 棋盘配 810 种图案比较耐玩12 种以上提示按钮会被频繁触发空格越多路径选择越多棋盘下半局往往比开局简单想控制游戏时长可以按剩余图案数量动态调整图案索引的候选策略。A* 在这里的主要价值是给“提示”排序而不是替代 CanConnect因为启发函数一旦不满足可采纳性找到的“最短路”未必是转弯最少的反而引入额外 bug。这段折腾下来最大的体会是连连看这类小游戏算法正确性比性能重要得多而正确性往往卡在状态定义上。只要把“坐标 方向”这个组合状态想清楚01BFS 写出来很短也不容易翻车。从那以后我每次改连连看棋盘的数据映射或者路径规则都强制先跑一遍脚本里的自检再开 VS 断点验证一条二拐路径血泪经验换来的习惯希望帮到你。本文还有配套的精品资源点击获取
