简介面向高校数据结构课程学习者与课程设计参赛者这份武汉理工大学数据结构综合实验“欢乐连连看”完整项目包以经典消除游戏为载体演示了数组、链表、图等基本结构以及DFS/BFS搜索、哈希表加速、回溯推理、洗牌算法等知识在真实项目中的落地方式。压缩包内共103个文件约190.99MB其中13个h头文件与10个cpp源文件构成完整的游戏工程便于阅读核心逻辑bmp、ico、wav等多媒体素材为作者原创负责界面与背景音乐exe可直接运行查看效果obj、tlog、pdb等为编译中间产物与构建记录适合对照工程整体结构。已有739人学习浏览。通过本项目可掌握游戏棋盘建模、匹配消除判断、胜负判定、提示与重排等模块的设计思路同时了解多媒体资源管理、界面交互与计时设置等软件工程细节是一份可运行、可修改、可复用的实验参考。1. 数据结构综合实验“欢乐连连看”算法课大作业里最扣细节的一类武汉理工大学数据结构综合实验里的“欢乐连连看”看起来是个小游戏实际是一道把二维数组、路径搜索、状态管理全串起来的综合题。每年都有人选它但多数人把时间花在界面上最后却卡在最朴素的环节两个被其他棋子隔开的图案到底能不能通过不超过两次转折的路径连在一起。这个判定逻辑连同棋盘建模、洗牌、胜负判断才是这份实验真正要交的东西。对基础中等、想拿一份结构清楚源码包照着复现的同学来说它比单纯刷题更能帮你把数据结构课里的知识落实到可以运行的代码上。2. 棋盘与数据模型二维数组之外边界处理才是真正的考点2.1 逻辑棋盘与虚拟边界为什么最后要多出一圈先说选型。连连看整个游戏的“世界”就是一张棋盘所有操作都是随机访问某个格子的内容所以最自然的数据结构是二维数组确定的行数和列数board[r][c]一次定位读写都是 O(1)内存连续、遍历方便。有人一开始想用链表说“消除棋子就是删节点链表更方便”。这是在给自己挖坑。连连看的核心操作不是删除而是“判断两个格子能不能连通”这个操作每一轮都要执行很多次链表随机访问一个中间节点要 O(n)路径扫描时还要反复横跳复杂度完全失控。二维数组加上“先置 0 再统一重绘”的删除方式才是这个场景下的正解。真正的考点在边界。经典连连看规则里两个棋子可以从棋盘外圈绕过去相连也就是路径可以走到棋盘外面再折回来。如果只开ROW * COL的数组路径扫描每走一步都要判断“是不是出界了”代码里全是if (r 1 || r ROW || c 1 || c COL)烦且容易漏。我惯用的做法是在逻辑区域外面多包一圈虚拟边界数组开成(ROW 2) * (COL 2)边界格子全部初始化为 0。这样扫描路径时“走到棋盘外面”等价于“经过一个值为 0 的格子”完全不用特判。多占的十几个int内存可以忽略不计换来的是连通判定代码简洁一大截。数据模型优点代价二维数组 虚拟边界随机访问 O(1)路径扫描统一处理出界多一圈内存删除要置 0结构体 链表删除棋子直接摘节点随机访问 O(n)路径扫描复杂一维数组手动映射下标省内存边界判断要写成表达式可读性差2.2 图案映射与洗牌回填从“有规律”到“可玩”棋盘上的图案用整数表示0 代表空位1 到TYPE_N代表不同图案。初始化时不能用随机数直接填因为随机数不保证每种图案出现偶数次——连连看必须两两配对才能全部消完奇数个图案意味着玩到最后必然剩单只。常见做法是先用一个公式按坐标生成编号保证每种图案数量相同再洗牌打乱分布。洗牌时尤其要注意只能洗内圈非空区域边界 0 不能参与否则空位会被洗进“待发牌堆”盘面出现诡异的空位错乱。#define ROW 10 // 逻辑棋盘行数 #define COL 12 // 逻辑棋盘列数 #define TYPE_N 6 // 图案种类数10*12/620每种 20 个 #define MAX_R (ROW 2) // 含虚拟边界的数组行数 #define MAX_C (COL 2) int board[MAX_R][MAX_C]; // 所有格子清零1..ROW / 1..COL 之外的边界格子保持 0 void board_init(void) { for (int i 0; i MAX_R; i) for (int j 0; j MAX_C; j) board[i][j] 0; } // 按行列位置生成序号再映射成 1..TYPE_N保证每种图案两两成对 void board_fill(void) { for (int i 1; i ROW; i) for (int j 1; j COL; j) board[i][j] (i * (COL 1) j) % TYPE_N 1; } // Fisher-Yates 洗牌只洗非空区域不碰边界 0 void board_shuffle(void) { int tiles[ROW * COL]; int n 0; for (int i 1; i ROW; i) for (int j 1; j COL; j) tiles[n] board[i][j]; for (int i n - 1; i 0; i--) { int j rand() % (i 1); int t tiles[i]; tiles[i] tiles[j]; tiles[j] t; } n 0; for (int i 1; i ROW; i) for (int j 1; j COL; j) board[i][j] tiles[n]; }board_fill里的公式(i * (COL 1) j) % TYPE_N 1是我喜欢用的生成方式COL 1和TYPE_N互质生成的图案分布相对均匀而且每种图案数量恰好相等。洗牌逻辑说明一点先把内圈所有非零值按行优先收集进一个临时数组用 Fisher-Yates 原地随机交换再按同样的行列顺序回填。这样洗完后棋盘依然是合法的“每种图案偶数个”状态空位只在游戏过程中产生不会混进初始牌堆。参数上 10 行 12 列配 6 种图案比较常规玩一局大约三到五分钟TYPE_N调到 8 会明显变难调到 4 则太简单交实验时建议保留一个可配置的宏。3. 连通判定与消去逻辑把“三线连通”写成可运行的代码3.1 两个前置条件与 0 折直连先扫出最干净的一类情况连连看“可消”的定义要讲清楚两个格子非空、图案相同、并且能通过一条最多两个转折的路径连接路径经过的格子必须全部为空。为什么限定两次转折因为三折以上的路径在视觉上已经看不懂了这是产品规则也是算法边界。can_erase函数开头必须先做三个前置判断顺序不能乱。第一两次点击的是同一个格子直接返回不可消第二任何一个格子是 0直接返回不可消第三两个格子图案不同直接返回不可消。这个顺序一旦调换比如先比较图案两个空位都是 0反而会“相等”返回一个可消的假结果后面的路径扫描全白做了。0 折直连是最简单的一类两个点在同一行且中间全空或者同一列且中间全空。实现时扫描的是开区间不包含端点自身。这一步建议封装成line_clear_h和line_clear_v两个静态函数后面单拐点和双拐点判定要反复调用它们。方向处理上别假设参数永远是小坐标在前用step (a b) ? 1 : -1统一方向否则调用处传参顺序一换扫描方向反了坑得很隐蔽。3.2 一个拐点与两个拐点枚举策略的取舍单拐点的数学性质很明确两点(r1,c1)和(r2,c2)拐点只可能出现在(r1,c2)或(r2,c1)这两个位置不需要遍历全棋盘。先检查候选拐点本身是不是空位再分别检查拐点与两端之间是否直线畅通。双拐点分两种形态。H 型路径是“水平段 垂直段 水平段”关键在垂直段所在的列 cV 型路径是“垂直段 水平段 垂直段”关键在水平段所在的行 r。所以双拐点判定不需要 BFS枚举列或行就行每轮最多枚举ROW COL个位置每个位置做三次直线检查对 10×12 的棋盘开销几乎可以忽略。static int line_clear_h(int row, int c1, int c2) { int step (c1 c2) ? 1 : -1; for (int c c1 step; c ! c2; c step) if (board[row][c] ! 0) return 0; return 1; } static int line_clear_v(int col, int r1, int r2) { int step (r1 r2) ? 1 : -1; for (int r r1 step; r ! r2; r step) if (board[r][col] ! 0) return 0; return 1; } int can_erase(int r1, int c1, int r2, int c2) { if (r1 r2 c1 c2) return 0; if (board[r1][c1] 0 || board[r2][c2] 0) return 0; if (board[r1][c1] ! board[r2][c2]) return 0; // 0 折同行或同列直接穿透 if (r1 r2 line_clear_h(r1, c1, c2)) return 1; if (c1 c2 line_clear_v(c1, r1, r2)) return 1; // 1 折拐点只可能在这两个位置 if (board[r1][c2] 0 line_clear_h(r1, c1, c2) line_clear_v(c2, r1, r2)) return 1; if (board[r2][c1] 0 line_clear_v(c1, r1, r2) line_clear_h(r2, c1, c2)) return 1; // 2 折H 型枚举垂直段所在列 c for (int c 0; c MAX_C; c) { if (board[r1][c] ! 0) continue; if (line_clear_h(r1, c1, c) line_clear_v(c, r1, r2) line_clear_h(r2, c2, c)) return 1; } // 2 折V 型枚举水平段所在行 r for (int r 0; r MAX_R; r) { if (board[r][c1] ! 0) continue; if (line_clear_v(c1, r1, r) line_clear_h(r, c1, c2) line_clear_v(c2, r, r2)) return 1; } return 0; }逻辑上分四步走0 折、1 折、2 折的 H 型、2 折的 V 型顺序从简到繁。H 型循环里的c代表垂直段所在的列先从(r1,c1)水平走到(r1,c)再沿第 c 列垂直到(r2,c)最后水平到(r2,c2)。V 型循环对称r代表水平段所在的行。两个循环的枚举范围都从 0 开始到MAX_C-1/MAX_R-1这是刻意的虚拟边界格子本身是 0可以成为路径的一部分于是“绕棋盘外圈相连”这种规则自然就支持了。如果老师明确不允许绕外圈把两个循环改成for (int c 1; c COL; c)和for (int r 1; r ROW; r)即可其余逻辑不用动。参数上的一个优化点H 型循环里可以先判断board[r1][c] 0 board[r2][c] 0再扫两段水平线V 型同理能少做无效的line_clear调用。实验报告里分析复杂度时最坏情况是 O((ROW COL) * MAX_R)对固定棋盘是常数级开销比通用 BFS 好解释得多。4. 从数据结构到可玩原型状态机、输入响应与胜负判断4.1 用枚举状态机稳住主循环游戏不再“一跑就乱”很多同学写大作业的习惯是while(1)里堆if读一个键处理一个键功能能跑但一旦要加“提示”“重排”“计时器”代码就变成一坨乱麻。我一般会先定义一个状态机PLAYING表示等待第一次点击PICKED表示已经选中一个格子、等待第二次点击GAME_OVER表示游戏结束。状态转移只有三条PLAYING - PICKED第一次点击有效格子、PICKED - PLAYING第二次点击结束判定或取消选中、任意状态 -GAME_OVER棋子全部消完。状态机的价值在于“输入、判定、重绘”三件事分离。输入只负责把像素坐标换算成棋盘下标不直接改棋盘棋盘修改统一发生在状态转移时重绘永远根据当前状态画高亮。这样“第一击选中高亮”“第二击判定失败清空选中”这些逻辑就不再散落在各个分支里而是落在明确的状态迁移点上。typedef enum { PLAYING, // 等待第一次点击 PICKED, // 已选中一个格子等待第二次点击 GAME_OVER // 所有格子消完 } GameState; typedef struct { int r[2], c[2]; // 选中的两个坐标 } PickInfo; void game_loop(void) { GameState state PLAYING; PickInfo pick {{0, 0}, {0, 0}}; while (state ! GAME_OVER) { int r input_row(); // 输入系统换算好的棋盘行号 int c input_col(); // 棋盘列号0 表示无效输入 if (state PLAYING) { if (r 1 r ROW c 1 c COL board[r][c] ! 0) { pick.r[0] r; pick.c[0] c; state PICKED; } } else if (state PICKED) { if (r pick.r[0] c pick.c[0]) { state PLAYING; // 再点同一个取消选中 } else if (r 1 r ROW c 1 c COL) { pick.r[1] r; pick.c[1] c; if (can_erase(pick.r[0], pick.c[0], pick.r[1], pick.c[1])) { board[pick.r[0]][pick.c[0]] 0; board[pick.r[1]][pick.c[1]] 0; } state PLAYING; // 无论成功失败都回到等待态 } } if (remaining_count() 0) state GAME_OVER; render_board(state, pick); } }主循环的逻辑说明PLAYING状态下只接受非空格子的点击选中的格子坐标存入pick状态切到PICKED。PICKED状态下先判断是不是点了同一个格子是则取消选中回到PLAYING否则用can_erase做判定判定通过就把两个格子置 0判定失败不做任何修改最后都回到PLAYING等下一次操作。remaining_count()每次循环扫描一次棋盘累加非零格子个数为零时进入GAME_OVER。参数上的扩展点如果想加计时器就在GameState外维护一个累计秒数渲染时显示即可如果想加“重排”按钮把重排处理成一个独立输入分支执行洗牌函数后必须把pick清零、state拉回PLAYING。状态机的好处就是这些扩展都不碰can_erase只加状态和转移。4.2 两次点击与消去联动把判定接到交互上从图形库拿到的原始数据通常是像素坐标第一件事是换算成棋盘下标这一步写不好后面全崩。公式不复杂row (py - offset_y) / cell_h 1col (px - offset_x) / cell_w 1。注意必须先把棋盘左上角在窗口里的偏移量减掉再除以格子尺寸顺序反了就会出现“隔一个格子才能点中”的错位。换算后还要验证row、col是否落在1..ROW、1..COL内落在边界外直接返回一个无效值主循环里用r 0之类的方式丢弃。胜负判断也要留意每次消除后减少一个全局计数是常见做法但重排函数不能改变这个计数因为重排只是打乱非空格子棋子总数不变。我习惯在board_shuffle结束后重新统计一遍总数和计数变量比对不一致立即报错。这种“数据一致性自查”看起来繁琐实则能挡住很多莫名其妙的后期 bug。5. 高频踩坑与排查四个必翻车的雷区5.1 边缘棋子的越界访问点一下就崩的真相现象是图形界面下点边缘棋子程序直接崩溃或者点了没反应。原因基本都在坐标换算像素坐标减偏移量的顺序搞反或者没有对换算结果做范围检查board[r][c]直接访问了负下标或超界下标C 语言不报错但可能踩坏相邻内存表现成随机崩溃。解决方法是统一封装一个convert_to_board(px, py, r, c)函数所有输入路径都走它函数内部先减偏移再整除最后做r 1 r ROW c 1 c COL的范围校验不合法就返回 0。不要在任何其他地方散落像素换算代码这是唯一的入口。提示就算用控制台版本getch读方向键做输入也要把按键映射统一收口到一个函数里别在主循环里到处写switch。5.2 空位被判定成可消选中状态与入参校验的漏现象是第二击点到已经消掉的空位上程序竟然提示“可以消除”或者卡在选中状态不放。原因多半是can_erase的前置判断顺序写错了。最容易翻车的写法是上来就比图案相等两个刚被消掉的空位值都是 00 和 0“相等”不先判空的话会直接返回可消。反过来如果只有一个空位0 和正整数不相等又会返回不可消结果就是行为完全看运气。解决方法是把三个前置判断的顺序固化成一条纪律先判断r1 r2 c1 c2再判断任一个为 0最后判断图案相等。这个顺序不是风格问题是正确性问题。我后来把这三个判断抽成一个check_precondition辅助函数所有入口统一调用再没在这个位置出过事。5.3 死局重排后棋盘数据不同步洗牌算法的隐藏坑现象是游戏玩到后半段提示死局点重排后界面确实变了但玩到最后总有某种图案剩下一个永远消不完。原因基本可以锁定在重排函数的实现上直接把整个board数组的所有元素收集起来洗牌回填把边界 0 和游戏过程中的空位也当成“牌”洗了一遍导致某些图案的配对数被破坏变成奇数。这类 bug 在开局不容易暴露偏偏在死局重排后才显现很难复现。解决方法是重排时只收集1..ROW、1..COL范围内非零的格子洗牌后在同样范围内回填边界格子不动。我习惯在重排函数尾部加一个校验循环统计每个图案号出现的次数任何一个不是偶数就立刻打印错误信息。这个校验函数在开局初始化后也跑一遍相当于给棋盘数据上了一道保险。5.4 双拐点绕外圈判定漏判边界范围写窄了现象是玩家肉眼能看出两个棋子可以绕棋盘外圈连上程序却判定不可消。原因在can_erase的双拐点枚举范围如果写的是for (int c 1; c COL; c)路径就被限制在逻辑棋盘内部外圈路径经过的边界格子根本不在枚举范围内。解决方法是把 H 型和 V 型循环的枚举范围改成0..MAX_C-1和0..MAX_R-1并且确认board_init已经把边界格子清零。这里要提醒一句如果实验要求不允许绕外圈才保留内圈枚举两种规则对应两种范围改完一定要回头跑一遍第 6 章的最小用例确认和需求一致。6. 把实验做成“优秀”健壮性验证与三个低成本扩展6.1 用“最小用例”验证连通判定随机玩十局验证连通性是低效的很多路径形态根本触发不到。我更信任手写棋盘的最小用例测试固定一个已知棋盘对每种路径形状做断言。用例布局期望结果同行直连两个 1 号棋子中间全空可消同行被堵两个 1 号棋子中间放一个 2 号不可消L 形单拐点两个 1 号棋子拐点位置为空可消H 型双拐点两个 1 号棋子被一列 2 号隔开绕下方连通可消外圈绕行两个 1 号棋子分别靠左右边缘从外圈连通可消void test_direct(void) { board_init(); board[3][4] 1; board[3][7] 1; // 中间 3[5]、3[6] 为空 assert(can_erase(3, 4, 3, 7) 1); board[3][5] 2; // 堵上中间一个 assert(can_erase(3, 4, 3, 7) 0); }这个测试函数的价值在于每次改动can_erase或棋盘初始化逻辑后跑一遍就知道有没有破坏已有功能不用靠手感去试。我做完实验后习惯把测试文件也保留在源码包里老师查重时看到有单测印象分会好很多。6.2 三个低成本扩展计时、提示与撤销想让实验报告有亮点不必做花哨的动画三个小扩展就够计时器在状态机外维护一个elapsed计数每秒加一界面渲染一行用时。数据结构上用到一个简单计数变量但和状态机结合得很自然。提示功能遍历棋盘任意两格调用can_erase找到第一对可消的格子并高亮闪烁。本质是对can_erase的穷举调用时间复杂度 O(n²)但对 10×12 棋盘完全可忽略。这个扩展能把“判定算法”变成“搜索算法”正好回扣数据结构课上的查找主题。撤销用一个栈记录每次消除的两个坐标和原图案值回退时恢复棋盘。体验上很见功力技术上用的是教材里最经典的“栈”结构。做完这个实验后我养成了一个习惯任何和棋盘状态相关的函数改动第一件事先跑最小用例第二件事验证图案数量为偶数。那次死局重排翻车让我彻底明白了“先验后合”的价值——看起来是随机分布问题实际是数据一致性没守住。希望这些记录能帮到你少走这段弯路。本文还有配套的精品资源点击获取