简介武汉理工大学数据结构与算法综合实验连连看报告以“欢乐连连看”游戏开发为载体完整展示从需求分析、数据结构设计到核心算法实现与MFC界面搭建的实践过程。报告使用int类型动态二维数组保存16行×10列的游戏地图并重点讲解一条直线、两条直线、三条直线三种消子连通判断算法同时覆盖胜负判定、提示、重排、计时、游戏模式等模块的设计思路适合正在学习数据结构、C或MFC开发的本科生参考。资源共包含1个文件为docx格式的实验报告文档大小约1.37MB内含实验目的、核心代码、算法流程与结果分析可直接用于课程设计或实验报告撰写。目前已有227人学习下载对于需要完成类似实验或进行MFC/数据结构实践训练的读者是一份结构完整、代码与思路并重的样例。1. 连连看实验从一张地图看数据结构与算法取舍「武汉理工大学数据结构与算法综合实验连连看」这类题目第一眼像图形匹配小游戏真正打开需求才发现硬骨头全在数据结构和算法上一张二维矩形地图、两个相同图案的格子能不能用不超过两个拐弯的折线连通。这个判定每次点击都会触发整个游戏的流畅度、地图是否可解、提示是否好用全压在这个函数上。对做课设的学生来说这是数组、队列和图遍历的打包练习对做网格路径搜索的工程师来说连连看的核心抽象与二维寻路完全一致。我按 C 语言路线把地图建模、BFS 消除判定、地图生成、死锁检测和提示功能串起来讲代码可以直接移植到其他语言。2. 矩阵地图与连通性判定数组选型与拐点 BFS 算法拆解2.1 地图用二维数组表示外圈必须留一层空白连连看的地图天然是等宽的矩形格子最直接的数据结构就是二维数组。数据结构 C 语言版教材里最常见的做法是int map[ROW2][COL2]下标从 1 开始用0 和 ROW1、COL1 那一圈全部留 0。0 表示空格非 0 表示图案编号。外圈留空白不是可选优化。连连看允许路径从地图边缘绕出去再绕回来如果数组不扩一圈边缘格子的可达性判定会少掉一整类合法路径。常见的错误是把地图定义成map[ROW][COL]然后在 canConnect 里写大量边界 if 判断改路径时边界条件四处漏风不如直接扩一圈数组把边界问题消掉。2.2 把「最多两个拐弯」翻译成 BFS 状态两个格子连通的本质是从起点出发沿上下左右四个方向延伸路径期间方向改变次数不超过 2。这可以直接建模成 BFS因为 BFS 天然按层扩展每次扩展一步检查是否走到终点第一次到达终点的路径就是满足条件的路径。但状态不能只存坐标还要存「当前方向」和「已经拐了几次」。为什么需要方向路径从上一个格子走到当前格子后下一步继续直走不增加拐弯次数换方向才增加。如果不记录方向就无法判断下一步该不该加一。所以每个状态至少包含四个字段x、y、dir、turns。起点位置没有上一步方向常见处理是把四个方向的初始状态全部入队turns 都记为 0等价于起点可以向任意方向免费出发。字段含义取值说明x, y当前格子坐标范围 0..ROW1 / 0..COL1dir进入当前格子的方向0 上、1 下、2 左、3 右turns已累计拐弯次数换方向时 1超过 2 直接剪枝2.3 判定函数的边界条件与复杂度canConnect 返回值用 0/1 就够了。进入函数先做三个前置检查两个格子必须非空、图案编号必须相等、两个坐标不能是同一个格子。这些条件不满足直接返回 0避免后面 BFS 白跑。真正的搜索过程是在 map 的空白格子上展开除了终点以外路径不允许经过任何非空格子。这里容易和最短路径算法混淆。连连看不要求路径最短只要求「存在性」和「拐弯数限制」所以 Dijkstra 或 A* 在这里不是必要的BFS 加拐弯剪枝是最简洁可靠的做法。如果题目改成「输出拐弯最少的路径」也可以用同样的 BFS 状态记录前驱节点在终点回溯得到完整路径。到这里可以估算复杂度。设地图有效格子数为 N每个格子最多以 4 个方向入队BFS 状态总数上限是 4N每个状态扩展 4 个邻居单次判定复杂度 O(4×(4N))对 10x10 或 12x12 的课设地图毫无压力。这一结论为后面死锁检测、提示功能反复调用提供了性能空间。3. 消除判定代码实现用 C 语言让数据结构算法落地3.1 用顺序队列实现 BFS 层次扩展BFS 需要一套先进先出的队列。课设阶段不需要引入链式队列或 STL用静态数组加头尾指针就够了入队操作写queue[tail] state;出队写cur queue[head];队列容量按(ROW2)*(COL2)*4分配刚好覆盖所有状态数。这样既避开动态内存管理也方便直观调试。队列之所以必要是因为 BFS 要求按层扩展先处理距离起点一步的状态再处理两步的状态。用栈代替队列会变成 DFS路径判定虽然也可能出结果但路径会钻到很深再回头剪枝逻辑容易出问题而且「先找到的路径」不一定是拐弯最少的。3.2 canConnect 完整函数与状态记录#include stdio.h #include string.h #define ROW 10 #define COL 10 #define MAX_TURNS 2 typedef struct { int x, y; int dir; int turns; } State; int canConnect(int map[ROW2][COL2], int x1, int y1, int x2, int y2) { if (map[x1][y1] 0 || map[x1][y1] ! map[x2][y2]) return 0; if (x1 x2 y1 y2) return 0; static int visited[ROW2][COL2][4]; memset(visited, 0x3f, sizeof(visited)); const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; State queue[(ROW2)*(COL2)*4]; int head 0, tail 0; for (int d 0; d 4; d) { queue[tail] (State){x1, y1, d, 0}; visited[x1][y1][d] 0; } while (head tail) { State cur queue[head]; if (cur.x x2 cur.y y2) return cur.turns MAX_TURNS; for (int nd 0; nd 4; nd) { int nt cur.turns (cur.dir ! nd ? 1 : 0); if (nt MAX_TURNS) continue; int nx cur.x dx[nd]; int ny cur.y dy[nd]; if (nx 0 || nx ROW2 || ny 0 || ny COL2) continue; if (!(nx x2 ny y2) map[nx][ny] ! 0) continue; if (visited[nx][ny][nd] nt) continue; visited[nx][ny][nd] nt; queue[tail] (State){nx, ny, nd, nt}; } } return 0; }逻辑说明前置检查排除空格子、图案不同、同一个格子三个明显错误。visited是一个三维数组记录「以某个方向进入某格子时的最小拐弯次数」初始化为 0x3f3f3f3f 表示无穷大。四个初始状态覆盖起点向上下左右四个方向免费出发的情况。参数说明map是已经扩边一圈的地图玩家实际可点区域是1..ROW、1..COLx1,y1,x2,y2是两个被点击格子的坐标返回值 1 表示可以消除0 表示不能。换方向时nt加一超过MAX_TURNS直接剪枝非终点且非空格的地方不能走。提示memset(visited, 0x3f, sizeof(visited))把每个 int 初始化为 0x3f3f3f3f比写循环赋值快是竞赛代码里的常见技巧。用 gcc 编译时建议加-stdc99因为结构体赋值用到了 C99 的复合字面量。3.3 最小可运行主函数与回归用例光有函数不好确认对错接一个最小可运行程序int main() { int map[ROW2][COL2] {0}; map[2][2] 1; map[2][4] 1; printf(line: %d\n, canConnect(map, 2, 2, 2, 4)); map[2][3] 2; printf(blocked: %d\n, canConnect(map, 2, 2, 2, 4)); return 0; }第一组测试期望输出 1因为同图、同行且中间全空0 拐直连。第二组期望输出 0因为 (2,3) 被别的图案挡住绕路要么超出拐弯限制要么路径不合法。这个最小 main 是验证核心判定函数最快的方式。用例地图布局期望同行直线(2,2)1, (2,4)1中间空1中间障碍(2,3)20相邻同图(2,2)1, (3,2)11绕外圈一拐(1,2)1, (3,2)1中间被挡1完整游戏还需要读入地图、响应鼠标点击、消除后刷新显示这些是壳子真正决定实验分数的是这个判定函数和后面要说的地图生成、死锁检测。4. 地图生成、死锁检测与提示功能数据结构与算法串成完整游戏4.1 洗牌算法生成可玩地图生成地图的常见做法是先统计总格数假设需要 k 对图案就把每个编号出现两次的序列按随机顺序填入数组。填充过程用 Fisher-Yates 洗牌从后往前逐个交换时间复杂度 O(n)。int tiles[ROW*COL]; for (int i 0; i ROW*COL; i) tiles[i] i / 2 1; for (int i ROW*COL - 1; i 0; i--) { int j rand() % (i 1); int t tiles[i]; tiles[i] tiles[j]; tiles[j] t; } for (int i 0; i ROW*COL; i) map[i/COL1][i%COL1] tiles[i];这里必须保证ROW*COL是偶数否则最后一个图案配对不齐。调用前先srand((unsigned)time(NULL))否则每次启动生成的盘面都一样。这样生成的地图保证每个图案出现偶数次但「偶数次」并不等于「一定有可消除的一对」两个相同图案可能被完全包围所以生成后还要做死锁检测。4.2 死锁检测的全图扫描与剪枝死锁检测就是「是否存在任意一对相同图案canConnect 返回 1」。最直接的写法是四重循环枚举所有非空格对调用 canConnect。课设地图 N 不超过一两百BFS 单次判定也很快全盘扫描在点击提示时完全可以接受。剪枝算法在这里有两个明显落点第一外层和内层只检查图案编号相同的格子图案不同直接跳过第二先检查曼哈顿距离距离太远的对往往需要绕很大一圈可以先不查。但注意第二个剪枝只是优化顺序不能作为判定依据。int hasMove(int map[ROW2][COL2]) { for (int r1 1; r1 ROW; r1) for (int c1 1; c1 COL; c1) if (map[r1][c1] ! 0) for (int r2 r1; r2 ROW; r2) for (int c2 (r2 r1) ? c1 1 : 1; c2 COL; c2) if (map[r2][c2] map[r1][c1] canConnect(map, r1, c1, r2, c2)) return 1; return 0; }循环扫描顺序固定配合 canConnect 的确定性结果不受地图渲染和玩家操作影响。每次玩家消完一组后调用 hasMove如果返回 0就洗牌重排剩余图案。这个时机很重要不要在每次点击前都全图扫描只在需要提示或判定死局时调用。4.3 提示功能复用判定函数与增量更新提示按钮的本质就是调用 hasMove并返回第一对可消除格子的坐标。但如果每次都重扫全图重复调用时会做很多无效 BFS。更好的做法是把「上一次找到的可消除对」缓存起来每次消除后先验证缓存里的对是否仍然有效无效再做增量扫描。另一个实用技巧是按图案编号分组收集坐标。提示时只遍历同组坐标对避免把所有非空格子两两配对。消灭一对后只有两个坐标变成 0其他组不受影响缓存的命中率会很高。这样提示功能从「全图重扫」变成「小范围验证」交互层几乎不会有卡顿感。5. 进一步优化排序、二分查找与回归验证5.1 复杂度估算先算清再决定优化地图 10x10 时单次 canConnect 是 O(4N)全盘死锁扫描是 O(N² × 4N)。N100 时状态扩展量级大约 40 万次单次点击完全感觉不到卡顿。但如果把地图扩到 20x20、图案 50 种每次提示都全盘扫描就会觉得迟滞这时就该用排序和二分查找做预筛。操作复杂度10x10 量级单次消除判定O(4N)约 400 状态全图死锁扫描O(N² × 4N)约 40 万状态分组加二分预筛后O(N log N) 少量 BFS显著低于全图扫描5.2 按图案分组排序二分查找缩小候选集常见做法是维护一个「图案编号到坐标列表」的映射列表中按行号升序排序。查找时对当前格子 (r,c)先用二分查找定位到同图案列表中行号等于 r 的位置然后在这个小区间里检查同行候选同理按列号排序后可以快速筛出同列候选。这样死锁检测的候选对数从全部同图案对缩小到同行、同列附近canConnect 的调用次数能降一个量级。这个思路和数据结构排序算法中的预排序思想一致用 O(N log N) 的排序把 O(N²) 的配对查找降下来再用二分查找定位。真正的连通判定仍然交给 canConnect排序只负责缩小候选集合不改变判定规则。5.3 用固定用例回归防止 BFS 改坏准备 4 组最小地图0 拐直线、1 拐经过外圈、2 拐绕过障碍、3 拐不可达。每次改动地图生成或提示逻辑后把这四组用例跑一遍能迅速发现 BFS 状态记录和剪枝是否被改坏。回归测试写在 main 里用断言实现即可不引入额外测试框架。如果提示偶尔变慢优先检查是不是每次消除后都在全图重扫把缓存和增量更新加上交互层的卡顿通常就消失了。本文还有配套的精品资源点击获取