C语言 Donald Knuth Dancing Links 特殊指针实现

Question

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

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

在第 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 指针进行操作，并在此处递增计数器。