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

Question

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

我知道什么是确切的封面以及 Dancing 链接的工作原理。但我对 his paper: 有疑问

在第 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

您所说的指针指向一个 header 对象，该对象用于指示该列中有多少个对象(等效地，矩阵的该列中有多少个 1)。这是为了使算法可以启发式地确定在“确定性地选择一列”步骤中选择哪一列，因为您可能想要执行类似“选择其中条目最少的列”之类的操作。当您从矩阵中拼接一行时，C 字段可以很容易地更新列标题:对于每个被删除的条目，跟随指向列标题的 C 指针并在那里递减计数器；对于重新插入的每个条目，跟随指向列标题的 C 指针并在那里递增计数器。