-2

通常の 2 つ (next と prev) ではなく、アイテムごとに 1 つのポインター値 np[x] のみを使用して、二重にリンクされたリストを実装する方法を説明してください。すべてのポインター値は k ビットの整数として解釈できると仮定し、np[x] を np[x] = next[x] XOR prev[x]、next[x の k ビットの「排他的論理和」であると定義します。 ]および前[x]。(値 NIL は 0 で表されます。) リストの先頭にアクセスするために必要な情報を必ず記述してください。このようなリストに SEARCH、INSERT、および DELETE 操作を実装する方法を示します。そのようなリストを O(1) 時間で逆にする方法も示します。

出典: Cormen 第 3 版の CLRS 10.2-8

PS: これは宿題の質問ではありません。私はデータ構造を練習/修正しています。

4

1 に答える 1

1

ポインターを「通常の」整数として参照します。したがって、xor を含む任意の整数演算を実行できます。

ノードごとに、 を格納しxorValue = next ^ previousます。

なぜ役立つのですか？
最初から最後まで反復している場合previousは、 がどこにあるかを知っており、その値があるので、 で次に進むことができますnext = xorValue ^ previous。
last から first に反復する場合も同じ考え方が適用されます: previous = xorValue ^ next.

最後から最初へ、または最初から最後へ反復しなければ、リンクされたリストのどの場所にも到達できないため、これで十分です。したがって、previousORの値nextは既知であり、これまで見てきたように、もう一つの方。

これに基づいて作成できます (c のような擬似コード):

struct Node { 
   void* data;
   int xorValue;
}
Node* next(Node* node, void* previous) { 
    return (Node*)(node->xorValue ^ (int)previous));
}
Node* previous(Node* node, void* next) { 
    return (Node*)(node->xorValue ^ (int)next));
}

先頭/最後の要素の場合 - 前/次の値 (対応する) を単に NULL (0) と見なし、次の要素をそのまま格納します。それは以来動作しますnext ^ 0 = next

于 2013-02-01T08:49:19.717 に答える