0

これが私の XOR 連結リスト構造体であるとします...

構造体xList {
    int データ;
    xList* xor;
}

xor リンク リストのサイズが 1 または 2 の場合、何をxor含める必要がありますか?

4

2 に答える 2

2

xor リンク リストのサイズが 1 または 2 の場合、xor には何を含める必要がありますか?

prev ^ nextwhereprevは前の要素へnextのポインター、 は次の要素へのポインター、および^XOR 演算子を含む必要があります。リストの最初の要素は明らかにnil前のアイテムを表し、最後のアイテムは最後のアイテムを表すため、それらの要素に対してそれぞれとをnil取得します。サイズ 1 のリストには、前の要素も次の要素もないため、おそらくフィールドに何を格納するかを理解できます。nil ^ nextprev ^ nilxor

xor リンク リストの考え方は、次または前の要素を決定するために、リスト内の前または次の要素のアドレスを知っている必要があるということです。ただし、リストを繰り返し処理している場合は問題ありません。これはリンクされたリストで行うことなので、最適化に役立ちます。たとえば、先頭から末尾に反復する場合は、リスト内の最初の要素へのポインターから開始します。前の要素はnilであるため、次の要素を取得するには、次のように計算しますnext = prev ^ xor。また、次の要素に移動するために使用できるように、次の要素に移動する前に現在の要素へのポインターを覚えておく必要があります。

于 2013-03-01T15:37:36.047 に答える
0

xorlink ポインターに (前の ^ 次の) を格納します。

検討

struct xList 
{
    int data;
    xList* xorlink;
}

A -> B -> C -> D

頭から始めます。head には previous がないことがわかっているため、xorlink は B ノードを指します。現在のポインターを保存し (A)、次のポインターに移動します (B)。(A ^ B->xorlink) を実行して、C へのポインターを取得します。(B ^ C->xorlink) を実行すると、D へのポインターが得られます。

逆トラバーサルも同様です。

とにかく、あなたの質問への答え

  1. サイズが 1 の場合、最初のノードの xorlink には NULL が含まれている必要があります。
  2. サイズが 2 の場合、最初のノードの xorlink には 2 番目のノードへのポインターが含まれている必要があります。2 番目のノードの xorlink には、1 番目のノードへのポインターが含まれている必要があります。
于 2013-03-01T15:47:35.197 に答える