Donald Knuth Dancing Links特別なポインタの実装

Question

今、私はD.Kuth DLXアルゴリズム/データ構造の実装に取り​​組んでいます。

私は正確なカバーとダンスリンクの仕組みを知っています。しかし、私は質問があるhis paper:

5ページで、彼はアルゴリズムの実装について説明します。そして、彼の "データオブジェクトx"ノードは、対応する列の先頭の列オブジェクトに を指す "Cフィールド"を持っています。しかし、私は彼がなぜそれを必要とし、どのように使用するのかを完全に理解していません。そして、 "列オブジェクト"の "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

あなたが（行列の列にある同等に、どのように多くの1秒）の列にありますどのように多くのオブジェクトを示すために使用されますヘッダーオブジェクトへのポイントの話をしているポインタ。これは、アルゴリズムが、「列を決定論的に選択する」ステップで選択する列をヒューリスティックに決定できるようにするために使用されます。「列の数が最も少ない列を選択する」などがあります。 Cフィールドを使用すると、行列から行をスプライスするときに列ヘッダーを簡単に更新できます。削除された各エントリに対して、列ヘッダーのCポインターに沿ってカウンタを減らします。再挿入された各エントリに対して、列ヘッダーへのCポインタをたどり、そこでカウンタをインクリメントします。