Donald Knuth Dancing Links реализация специального указателя

Question

Сейчас я работаю над своей реализацией алгоритма/структуры данных D.Kuth DLX.

Я знаю, что такое точное покрытие и как работают танцевальные ссылки. Но у меня есть вопрос по поводу his paper:

На странице 5 он описывает реализацию алгоритма. И там, его узлы «объект данных x» имеют «поле С», которое указывает на объект столбца во главе соответствующего столбца. Но я не совсем понимаю, зачем ему это нужно и как он его использует? И то же самое касается «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

Указатель вы говорите, указывает на объект заголовка, который используется, чтобы указать, сколько объектов есть в колонке (эквивалентно, сколько 1s в этом столбце матрицы). Это используется так, чтобы алгоритм мог эвристически определить, какой столбец выбрать в шаге «выбрать столбец детерминистически», так как вы можете сделать что-то вроде «выберите столбец с наименьшим количеством записей в нем». Поля C позволяют легко обновлять заголовки столбцов при сращивании строки из матрицы: для каждой удаленной записи следуйте указателю на заголовок столбца и уменьшите счетчик; для каждой введенной записи, следуйте указателю C на заголовок столбца и увеличивайте счетчик там.