c - Donald Knuth Dancing Links 特殊指针实现

Question

现在我正在研究我的 D.Kuth DLX 算法/数据结构的实现。

我知道什么是确切的封面以及 Dancing links 的工作原理。但我对他的论文有一个问题：

在第 5 页，他描述了算法的实现。在那里，他的“数据对象 x”节点具有指向相关列头部的列对象的“C 字段”。但我不完全理解他为什么需要它以及他如何使用它？“列对象”的“C 文件”也是如此。

typedef struct Data{
  struct Data *left, *right, *up, *down;
  struct Column *c;
} Data;

typedef struct Column{
  struct Column *left, *right, *up, *down;
  struct Data *c;
  int size, name;
} Column;

Answer 1

您正在谈论的指针指向一个标题对象，该对象用于指示该列中有多少个对象（等效地，矩阵的该列中有多少个 1）。使用它是为了让算法可以在“确定性地选择列”步骤中启发式地确定要选择的列，因为您可能想要执行诸如“选择其中条目最少的列”之类的操作。当您从矩阵中拼接一行时，C 字段可以轻松更新列标题：对于删除的每个条目，按照 C 指针指向列标题并减少那里的计数器；对于重新插入的每个条目，按照 C 指针指向列标题并增加那里的计数器。