Donald Knuth Dancing Links 特殊指针实现

Question

现在我正在研究 D.Kuth DLX algorithm/data 结构的实现。

我知道什么是确切的封面以及 Dancing 链接的工作原理。但我有一个关于 his paper:

的问题

在第 5 页，他描述了算法的实现。在那里，他的 "data object x" 个节点有 "C field" 个指向到相关列头部的列对象。但是我不完全明白他为什么需要它以及他如何使用它？对于 "column object".

，"C filed" 也是如此

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

你说的指针指向一个headerobject，用来表示列中有多少个object（相当于，有多少个1矩阵的那一列）。这是为了让算法可以启发式地确定在 "choose a column deterministically" 步骤中选择哪一列，因为您可能想要执行类似 "choose the column with the fewest entries in it." 的操作 C 字段使更新列变得容易 headers 当你从矩阵中拼接一行时：对于每个被删除的条目，跟随 C 指针指向列 header 并在那里递减计数器;对于每个重新插入的条目，按照 C 指针指向列 header 并在那里增加计数器。

Donald Knuth Dancing Links 特殊指针实现

Donald Knuth Dancing Links special pointer implementation

c

algorithm

knuth