C++ Dancing Links X (DLX)精确覆盖问题怎么实现十字双向链表-C++-PHP中文网

dlx的十字双向链表是稀疏环形结构，所有节点（含列头、数据节点）同构，各存left/right/up/down四指针；列头节点含size字段并参与水平环，通过col指针是否为空区分角色。

c++ dancing links x (dlx)精确覆盖问题怎么实现十字双向链表

DLX 的核心不是“链表数组”或“二维指针矩阵”，而是一个稀疏的、每个非零元素只存四个指针（left、right、up、down）的环形十字链表。所有行首节点、列头节点、数据节点都统一用同一种 Node 结构，靠标志位或额外字段区分角色。

关键点在于：列头节点也是 Node，它不存实际约束值，但必须有 size 字段记录该列当前未覆盖的行数（用于启发式选列），还要能快速进入该列的数据节点链（down 指向第一个数据节点，up 指向最后一个）。

常见错误是把列头单独做成 ColumnHeader 类，导致插入/删除时类型转换麻烦、指针更新漏掉；更简洁的做法是让所有节点同构，仅用 col 指针是否为 nullptr 或是否指向自身来判断是否为列头。

假设你有一组行（每个行是若干列索引的集合），比如精确覆盖问题中的一组“选择项”。不能直接按矩阵大小分配内存——DLX 必须稀疏构建。

先创建一个虚拟的“根节点”root，它只参与列头环（left/right），不参与上下链
为每列 j 创建一个列头节点 col_node[j]，并用 right/left 连成水平环；col_node[j].size = 0
对每一行 i，遍历其所有列索引 j，为每个 (i,j) 创建数据节点 n；设置 n.col = &col_node[j]；然后插入到该列的垂直链尾（即 col_node[j].up.down = n，n.up = col_node[j].up，n.down = &col_node[j]，再更新 col_node[j].up = n）；同时用 left/right 把同一行的节点串成环
每插入一个数据节点，对应列头的 size 加 1

注意：行内节点环的构建必须在该行所有节点都建好后闭环，否则 right 指针会悬空；列头的 up 初始应指向自己，这样第一次插入时逻辑统一。

cover(col) 删除一列及其所有影响行，uncover(col) 必须原路倒序恢复。这不是风格问题，而是链表拓扑一致性的硬性要求——因为 cover() 中删节点是“跳过”，而恢复时若顺序错，up/down 指针就无法回到原始状态。

典型错误写法：cover() 先删列头水平连接，再删各数据节点的上下连接；uncover() 却先恢复上下、再恢复水平——这会导致列头从水平环脱钩。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

正确顺序（以 cover 为例）：

从列头 c 开始，沿 c.down 遍历每行节点 r
对每个 r，沿 r.right 遍历该行所有其他列节点 j，执行 j.up.down = j.down；j.down.up = j.up（即从列 j 的垂直链中摘除 j）
最后才把列头 c 从水平环中摘除：c.left.right = c.right；c.right.left = c.left

对应地，uncover() 必须先恢复水平环，再逐行恢复垂直链——顺序完全反过来。

DLX 搜索本身不保证解唯一，但实现不当会因剪枝或回溯路径出错导致漏解。最易忽略的是：列选择策略和回溯时机。

标准做法是每次递归前调用 select_column()，返回 size 最小的未覆盖列（最小剩余列启发式）。如果某列 size == 0，说明无解，立即回溯；如果所有列都已覆盖（即根节点 right == root），说明找到一个解。

容易踩的坑：

没在 cover() 后检查 c.size == 0 就继续递归，导致无效分支爆炸
在递归前未保存当前列头指针，uncover() 时传入错误列头
解存储时只拷贝行索引，但没考虑同一行可能被多次加入（因为行节点环里 row_id 字段没设或设错）——务必给每个数据节点存一个 row 成员，指向原始行号

另外，root 节点永远不进 down/up 链，只管水平列头环；它的存在就是为了快速判断是否所有列已覆盖（root.right == &root）。