Donald Knuth Dancing Links spezielle Zeigerimplementierung

Question

Momentan arbeite ich an meiner Implementierung des D.Kuth DLX Algorithmus/Datenstruktur.

Ich weiß, was genaue Abdeckung und wie Dancing Links funktioniert. Aber ich habe eine Frage zu his paper:

Auf Seite 5 beschreibt er die Implementierung des Algorithmus. Und dort haben seine Knoten "Datenobjekt x" ein "C-Feld", das auf das Spaltenobjekt am Kopf der relevanten Spalte zeigt. Aber ich verstehe nicht ganz, warum er es braucht und wie er es benutzt? Dasselbe gilt für das "C-Feld" für das "Spaltenobjekt".

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

Der Zeiger Sie zeigt auf ein Header-Objekt im Gespräch sind, wie viele Objekte gibt es in der Spalte, um anzuzeigen, verwendet wird (äquivalent, wie es viele 1s in dieser Spalte der Matrix). Dies wird verwendet, damit der Algorithmus heuristisch bestimmen kann, welche Spalte im Schritt "Wählen Sie eine Spalte deterministisch" ausgewählt werden soll, da Sie möglicherweise etwas wie "Wählen Sie die Spalte mit den wenigsten Einträgen darin" ausführen möchten. Die C-Felder erleichtern das Aktualisieren der Spaltenüberschriften, wenn Sie eine Zeile aus der Matrix spleißen: Folgen Sie für jeden entfernten Eintrag dem C-Zeiger auf die Spaltenüberschrift und dekrementieren Sie den Zähler dort; Für jeden Eintrag, der erneut eingefügt wird, folgen Sie dem C-Zeiger auf die Spaltenüberschrift und erhöhen Sie den Zähler dort.