简介面向武汉理工大学数据结构课程综合实验的完整项目资源以“欢乐连连看”游戏为载体将数组、链表、图、深度/广度优先搜索、哈希表、回溯算法与洗牌算法等抽象概念落到实际可玩的程序设计中。压缩包共103个文件核心是C源码cpp/h与Visual Studio工程文件sln/vcxproj同时带有编译生成的exe、obj等目标文件以及界面所需的bmp、ico、wav素材整体大小约190.99MB。目前已有739人学习下载。资源包含可直接运行的欢乐连连看程序、完整项目源码、作者原创的背景图片与音乐覆盖游戏开始、消子、胜负判断、提示、重排、计时、设置等全部核心模块既可作为武汉理工大学在校生完成综合实验/课程设计的直接参考也适合自学数据结构的读者通过真实代码理解搜索、遍历、状态管理与资源优化方法。各功能模块代码结构清晰便于对照游戏操作逐段分析实现思路。1. 武汉理工大学数据结构综合实验的欢乐连连看不是小游戏是一道综合应用题拿到“武汉理工大学数据结构综合实验-欢乐连连看”这个题目时很多人第一反应是连连看不就是个消消乐小游戏随便写写就能交差。等到动手才发现棋盘怎么存、相同图案怎么快速找出来、两个格子之间怎么判断能不能连、无解时怎么重排每一个功能背后都对应着一类数据结构。它本质上不是游戏开发题而是一道把二维数组、队列BFS、哈希分组、查找与随机重排串起来的综合实验题。这篇文章按我实际做这个课设的路径来写从存储选型讲到消子判定再讲到死局检测和验收答辩适合正在写课设、准备数据结构实验报告和期末复习数据结构与算法应用的同学照着复现。2. 棋盘存储选型为什么用二维数组而不用邻接表2.1 连连看棋盘的本质是图的邻接矩阵第一次做这个实验的人最容易在存储结构上犹豫要不要给每个格子建一个链表存上下左右邻居其实不用。连连看的棋盘是规则的 M×N 网格每个位置只和上下左右四个格子相邻这种邻居关系已经隐含在坐标里。你用二维数组按下标访问任意格子是 O(1)而链表要沿着指针走反而把简单问题复杂化。从数据结构与算法的角度看棋盘本身就是一个邻接矩阵把每个格子看成图的顶点格子上有图案时该顶点不可通行格子上是空格时顶点可通行边就是相邻四个方向。消子判定本质是在这张“可通行图”上做路径搜索二维数组天然支持这种操作。常见做法是定义#define MAX_ROW 12 #define MAX_COL 14 #define EMPTY 0 typedef struct { int row, col; // 实际棋盘行列 int board[MAX_ROW 2][MAX_COL 2]; // 外圈留一圈虚拟空格 } Board;这里MAX_ROW 2和MAX_COL 2不是随便写的。经典连连看允许连线绕到棋盘外面的虚拟区域走也就是说最外圈的格子可以通过棋盘外的“空气”连起来。在数组四周额外留一圈值为EMPTY的虚拟格子边界情况就变成了普通情况判定函数不需要为边界单独写分支。实际棋盘从board[1][1]开始board[0][*]、board[row1][*]那一圈都是虚拟空格。2.2 棋盘初始化保证每张牌成双出现的填充与洗牌初始化最大的坑是图案数量不成双。假如棋盘是 8×12一共 96 个格子图案种类是 10 种那么每种图案必须恰好出现 9.6 个——这不可能。所以初始化逻辑要先计算总格子数保证总数是偶数再均匀分配。我一般先把所有格子的图案按顺序放好再用 Fisher-Yates 洗牌打乱。代码是这样的#include stdlib.h #include string.h void InitBoard(Board* b, int row, int col, int typeCount) { b-row row; b-col col; memset(b-board, 0, sizeof(b-board)); int total row * col; if (total % 2 ! 0) { total--; // 保证剩余格子能两两消完 } int* arr (int*)malloc(sizeof(int) * total); for (int i 0; i total; i) { arr[i] (i % typeCount) 1; // 图案编号从1开始0留给空格 } // Fisher-Yates 洗牌 for (int i total - 1; i 0; i--) { int j rand() % (i 1); int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } // 回填到棋盘内部区域 int idx 0; for (int i 1; i row idx total; i) { for (int j 1; j col idx total; j) { b-board[i][j] arr[idx]; } } free(arr); }这段代码的逻辑是先用等差数列生成图案序列(i % typeCount) 1保证每种图案均匀分布再用 Fisher-Yates 洗牌消除“相同图案聚在一起”的初始排列。total是偶数这个条件必须单独检查否则最后一对永远消不干净游戏会卡在死局。图案编号从 1 开始是有意为之EMPTY固定为 0这样判断路径时只看值是否为 0简单可靠。2.3 三个初始化参数怎么调行列、种类与难度初始化函数里有三个参数直接影响游戏难度row、col、typeCount。常见课程实验给的棋盘范围是 8×10 到 12×14图案种类 8 到 12 种。同样面积下种类越多任意两个相同图案之间的距离越远可消除概率越低游戏越难种类太少则满屏都是配对游戏变得无聊。参数推荐值对难度的影响row × col8×10 到 12×14越大搜索空间越大单次判定耗时增加typeCount812越大配对越分散死局概率升高虚拟空格层固定 1 层去掉后外圈格子基本消不掉调试时建议先用小棋盘比如 6×8、4 种图案跑通消子判定再换大棋盘。小棋盘死局概率低方便验证 BFS 逻辑大棋盘能测出性能问题。这里顺带提醒棋盘越大后面死局检测的耗时越明显所以第 3 章的 BFS 实现要尽量高效别在判定函数里做重复扫描。3. 消子判定用BFS限制最多两个拐点的路径搜索3.1 为什么选BFS而不是DFS最少拐点路径与递归爆栈连连看的规则是两个相同图案之间存在一条不超过两个拐点的折线且折线经过的所有格子都是空的。这个“不超过两个拐点”的限制本质上是在图里求一条拐点数量最少的路径。DFS 也能找到路径但 DFS 的递归顺序和回溯方式决定了它找到的第一条路径不一定是拐点最少的你需要把所有路径都搜完才能确认“到底有没有不超过两个拐点的路径”这比 BFS 慢得多。另一个更现实的理由是递归 DFS 会爆栈。棋盘 12×14路径最长可以绕半张棋盘递归深度可能上百层课程设计的运行环境一般是本地 IDE 或在线评测机栈空间有限深递归很容易出现栈溢出。BFS 用队列迭代实现深度不受调用栈限制而且天然按拐点数量逐层扩展——先找 0 拐点的再找 1 拐点的最后找 2 拐点的一旦找到目标点就可以直接返回不需要遍历全部路径。队列这一数据结构在这里的作用非常典型正好对应数据结构课程里“队列用于广度优先遍历”的考点。3.2 带拐点计数的BFS判定函数完整实现下面这个CanConnect函数是整套代码的核心直接抄下来改改棋盘参数就能跑#include stdio.h #define MAX_ROW 12 #define MAX_COL 14 #define EMPTY 0 #define MAX_BEND 2 typedef struct { int x, y; // 格子坐标 int dir; // 上一次移动方向0上 1下 2左 3右-1表示起点 int bends; // 已经拐弯的次数 } Node; typedef struct { int row, col; int board[MAX_ROW 2][MAX_COL 2]; } Board; static int dx[4] {-1, 1, 0, 0}; static int dy[4] {0, 0, -1, 1}; int CanConnect(Board* b, int x1, int y1, int x2, int y2) { if (b-board[x1][y1] ! b-board[x2][y2]) return 0; // 图案不同 if (x1 x2 y1 y2) return 0; // 同一点 if (b-board[x1][y1] EMPTY) return 0; // 空格不能消 int R b-row 2; // 包含虚拟空格的总行数 int C b-col 2; int best[MAX_ROW 2][MAX_COL 2]; // 到达每个点的最少拐点数 for (int i 0; i R; i) for (int j 0; j C; j) best[i][j] MAX_BEND 1; Node queue[MAX_ROW * MAX_COL * 8]; int head 0, tail 0; queue[tail].x x1; queue[tail].y y1; queue[tail].dir -1; queue[tail].bends 0; tail; best[x1][y1] 0; while (head tail) { Node cur queue[head]; if (cur.bends best[cur.x][cur.y]) continue; // 剪枝 for (int d 0; d 4; d) { int nx cur.x dx[d]; int ny cur.y dy[d]; if (nx 0 || nx R || ny 0 || ny C) continue; // 只有目标格子允许“踩”非空格其余经过处必须是空格 if (!(nx x2 ny y2) b-board[nx][ny] ! EMPTY) continue; int nb cur.bends; if (cur.dir ! -1 cur.dir ! d) nb; // 方向变化才算拐弯 if (nb MAX_BEND) continue; if (nb best[nx][ny]) { best[nx][ny] nb; if (nx x2 ny y2) return 1; // 找到可行路径 queue[tail].x nx; queue[tail].y ny; queue[tail].dir d; queue[tail].bends nb; tail; } } } return 0; }3.3 方向数组、拐点上限与best数组的语义这段代码有三个关键设计需要解释清楚。第一个是dir字段。cur.dir -1表示当前节点是起点起点没有“上一次方向”所以从起点出发向四个方向走都不算拐弯。从第二个格子开始只要d ! cur.dir说明行进方向变了拐点计数加一。这个设计把“拐弯”的定义落到每一次状态转移上比事后判断折线形状直观得多。第二个是best数组。它存的是到达某个格子时的最少拐点数而不是简单的“是否访问过”。这个区别很重要BFS 扩展时拐点多的路径可能先到达某个格子如果只用布尔标记后面拐点更少的路径到达时会被直接拦掉造成漏解。用best存最少拐点数只有当nb best[nx][ny]时才更新并入队保证每个格子保留的是最优到达代价。这其实是 Dijkstra 思想在拐点计数上的简化版。第三个是方向扩展方式。这里每次只走一步而不是沿一个方向走到黑。两种写法都能过但逐步扩展的代码更短、更不容易写错边界条件代价是队列里状态多一些对 12×14 的棋盘来说完全无压力。如果你想支持 N 拐点规则把MAX_BEND改成 3 或 4 即可其他逻辑不用动。4. 死局检测、提示与重排让欢乐连连看能玩到最后一对4.1 死局检测按图案分组后穷举同类对别做全棋盘双重循环死局检测要做的事是在整个棋盘中找是否存在任意一对相同图案它们之间可以用不超过两个拐点的路径连接。只要能找到一对游戏就还有解找不到就必须触发洗牌。最简单粗暴的写法是双重循环遍历所有格子对相同图案调用CanConnect但这是 O(N²) 次 BFS棋盘 12×14 时最多要跑 168×168≈28000 次 BFS明显卡顿。更合理的做法是用哈希分组的思路先用一个数组按图案编号收集所有相同图案的位置再对每组内部做两两配对。比如图案 1 出现在 5 个位置只需 C(5,2)10 次判定而不是和所有其他图案都试一遍。代码结构如下#define MAX_TYPE 20 #define MAX_SLOT (MAX_ROW * MAX_COL) typedef struct { int px[MAX_SLOT]; // 同种图案出现的位置 int cnt; } TypeGroup; int HasMove(Board* b) { TypeGroup groups[MAX_TYPE]; memset(groups, 0, sizeof(groups)); for (int i 1; i b-row; i) { for (int j 1; j b-col; j) { int v b-board[i][j]; if (v EMPTY) continue; if (v MAX_TYPE) continue; // 越界保护 groups[v].px[groups[v].cnt] i * (b-col 2) j; } } for (int t 1; t MAX_TYPE; t) { for (int a 0; a groups[t].cnt; a) { for (int b2 a 1; b2 groups[t].cnt; b2) { int x1 groups[t].px[a] / (b-col 2); int y1 groups[t].px[a] % (b-col 2); int x2 groups[t].px[b2] / (b-col 2); int y2 groups[t].px[b2] % (b-col 2); if (CanConnect(b, x1, y1, x2, y2)) return 1; } } } return 0; }这里用x * (col 2) y把二维坐标压成一维整数是为了让TypeGroup数组只存一个整数省内存也方便比较。取出坐标时用整除和取模还原。HasMove返回 1 表示存在可消除对返回 0 表示死局。注意MAX_TYPE要大于初始化时传入的typeCount否则棋盘填进去的图案类型超出数组范围越界写会直接翻车。4.2 提示功能hasMove第一次找到的可消除对就是答案提示功能的实现比想象中简单复用HasMove的遍历逻辑把return 1改成记录坐标后return。第一次找到的那对相同图案就是当前棋盘“最容易消”的一组其实只是遍历顺序上的第一组但效果上完全够用。提示本质上就是一次死局检测只不过死局检测只关心“有没有”提示关心“是哪一对”。很多同学会把提示做成随机猜一对这是没必要的。因为死局检测本来就要遍历所有同类对顺手记录第一对可行解即可没有任何额外开销。提示按钮的冷却次数建议控制为 3 次否则玩家全程靠提示实验的算法部分体现不出来。实现时给HasMove加一个可选输出参数int HasMoveWithHint(Board* b, int* ox1, int* oy1, int* ox2, int* oy2) { // 逻辑与 HasMove 相同找到后把坐标写入这四个指针再 return 1 }4.3 洗牌与重试上限Fisher-Yates回填后还要复检洗牌功能的常见做法是把所有非空格图案收集到一维数组打乱顺序后重新填回棋盘。这个思路没问题但有一个很容易被忽视的坑洗牌之后棋盘仍然可能无解。原因是洗牌只保证图案分布随机不保证“至少存在一对可连接”。所以洗牌后必须再次调用HasMove做复检无解就再洗一次并设置重试上限防止死循环void ShuffleRemain(Board* b) { int total b-row * b-col; int* vals (int*)malloc(sizeof(int) * total); int n 0; for (int i 1; i b-row; i) for (int j 1; j b-col; j) if (b-board[i][j] ! EMPTY) vals[n] b-board[i][j]; int retry 0; do { for (int i n - 1; i 0; i--) { int j rand() % (i 1); int tmp vals[i]; vals[i] vals[j]; vals[j] tmp; } retry; } while (!BoardValidAfterShuffle(b, vals, n) retry 20); // 回填 int idx 0; for (int i 1; i b-row; i) for (int j 1; j b-col; j) if (b-board[i][j] ! EMPTY) b-board[i][j] vals[idx]; free(vals); }BoardValidAfterShuffle做的事是先把vals临时回填到一个副本棋盘再调用HasMove判断是否有解。20 次重试上限是经验值12×12 棋盘、10 种图案时连续洗 20 次仍无解的概率极低基本不会触发万一触发了就再执行一次完整初始化相当于强制重置本局。注意洗牌时不能动已消除的空格位置否则已经消掉的区域又出现图案游戏逻辑就乱了。4.4 交互层的扩展队列做操作回放栈做撤销如果实验要求里有“道具”“计时”“排行榜”这些加分项数据结构还有更多用武之地。撤销上一手操作用栈每次消除前把两个格子的坐标和图案值压栈撤销时弹栈恢复。操作回放用队列把每一步消除记录成一个节点按顺序存进队列回放时依次出队重放动画。排行榜用数组加排序成绩表按分数从高到低插入插入排序在数据量小的时候比快排更直观也能体现“数据结构与算法”课程里排序章节的考点。这些扩展不是必须的但很多武汉理工大学数据结构综合实验的评分标准里都有“功能创新”这一项。我的建议是优先做撤销和提示撤销用栈实现简单、代码量只有三四十行回放骨架复杂度高放到最后有时间再做。稳扎稳打把核心流程跑通比堆功能更重要。5. 避坑指南连连看实验最容易翻车的五个细节5.1 相邻的相同图案消不掉起始方向被错误剪枝现象两个紧挨着的相同图案明明直线相连程序却判定不可消。原因实现 BFS 时在起点位置就检查了“方向”有的人写了if (cur.dir -1) continue之类的剪枝把起点直接拦掉了还有的人把起点四个方向手动入队后没有给它们设置正确的dir值。解决起点入队时dir固定为-1从-1向任意方向扩展都不增加拐点计数。检查方式很简单在CanConnect里打印四个方向的第一次扩展是否都被处理。5.2 visited用布尔数组导致拐点更少的路径被截断现象部分路径明明存在却返回 0特别是需要绕远路的两个拐点场景。原因用visited[nx][ny]标记是否访问过访问过就不再入队。BFS 的扩展顺序按拐点数分层但同一层内部顺序不定拐点多的路径可能先到达某个中间格子拐点少的路径后到结果被visited挡住。解决把布尔数组换成best最少拐点数数组只有新状态的拐点数严格小于历史值时才能更新入队。这也是第 3 章代码里最不能删的一行。5.3 靠边的格子永远连不上忘了棋盘外圈虚拟空格现象最外两行的图案之间明明可以绕外侧连线程序却判定无解。原因BFS 的搜索范围限制在了1..row、1..col棋盘外那一圈被排除在访问范围外连线自然走不出去。解决搜索时把行范围设为0..row1列范围设为0..col1同时保证InitBoard时外圈初始化为EMPTY。注意虚拟空格本身不能被点击消除鼠标点击交互层要过滤坐标但路径搜索层必须放行。5.4 洗牌后还是死局重排无解与死循环现象点击洗牌后很快又提示“无解可消”或者程序卡死。原因洗牌只重新排列了图案没有在洗牌后判断新布局是否有解。剩余图案少、种类多的时候某些排列天然无解比如剩余四个图案两两不同种无论如何都不可能消。解决洗牌后调用HasMove复检无解就重新洗设置最多 20 次重试。我见过有人把while写成while (!HasMove())不带次数上限一旦某种极端排列出现程序就永动机了。这个坑属于那种“表面不报错实际跑挂”的隐蔽问题验收时演示到洗牌功能才暴露。5.5 用DFS递归搜索路径栈溢出和“玄学超时”现象程序跑小棋盘正常一换成 12×14 的大棋盘点击反应明显变慢偶尔直接崩溃。原因用递归 DFS 做路径搜索12×14 棋盘最坏情况要探索几百个状态递归深度过深导致调用栈溢出同时 DFS 必须搜完所有分支才能确认“无解”在死局检测时会被调用上万次性能被放大几十倍。解决统一改用第 3 章的 BFS 队列实现HasMove全量检测的时间也能压到毫秒级。如果有人跟你说“DFS 也能做出连连看”别急着反驳但自己要清楚能跑通和能扛住验收是两回事BFS 在这个场景里从正确性和性能上都更稳。6. 验收与答辩测试用例、复杂度与实验报告怎么写6.1 一份能说服老师的测试用例表验收时最尴尬的事是老师随手点两下棋盘就发现误判。提前准备一张测试用例表按路径类型覆盖所有情况比临时手点靠谱得多。用例编号场景预期结果T01相邻两个相同图案可消除T02同一行中间隔一个空格可消除直线路径T03L 形单拐点路径可消除拐点数为 1T04Z 形双拐点路径可消除拐点数为 2T05需要 3 个拐点才能连接不可消除T06两个图案相同但路径被其他图案挡住不可消除T07棋盘外圈绕行的连接可消除T08洗牌后无解自动重排重排后存在可行对T09连续消除直到棋盘清空正常结束并计分测试时先把MAX_BEND临时改成 1跑 T03 和 T04如果 T04 返回 0 说明单拐点逻辑正确改回 2 再看 T04 是否通过。这种“降级验证”能帮你快速定位拐点计数写没写对。6.2 复杂度和报告里最加分的一段答辩环节老师常问三件事每次判定的时间复杂度是多少、死局检测为什么不会卡、如果棋盘放大到 100×100 会怎样。想清楚这三个问题的答案比背代码有用。单次CanConnect最坏会遍历所有格子复杂度是 O(M×N)由于每个格子最多入队几次实际约为 O(4×M×N)。死局检测调用CanConnect的次数取决于同类图案的配对总数最坏是 O((M×N)²) 次判定所以整体最坏复杂度是 O((M×N)³)。这个数字听起来吓人但 12×14 的棋盘实际只有 168 个格子配合按类型分组后现代机器一毫秒内就能跑完。如果老师追问大规模场景回答“先按曼哈顿距离粗筛距离超过可连范围的对直接跳过能砍掉大部分无用配对”即可。实验报告里我最推荐写的一段是“问题与调试记录”——直接把第 5 章的那五个坑写进去现象、原因、怎么定位、怎么解决。老师看报告最在意的不是你把功能写得天花乱坠而是你有没有真的遇到过问题并自己解决掉。我第一次做这个实验时花了两天才发现自己栽在visited布尔数组上后来把best数组的调试过程写进报告反而成了报告里最厚实的一段。这个实验做完二维数组、队列、哈希分组、排序这几大件基本都过了一遍手比期末复习周背十遍定义都管用。希望这份笔记能帮你少踩几个坑顺利过验收。本文还有配套的精品资源点击获取
