これは、二重リンクリストの複数配列表現の画像です。キー4のオブジェクトは、元のリンクリストのキー16のオブジェクトの後に続きます。ここでは、key [2]に4が表示され、key[5]に16が表示されます。ここでの概念は、ポインターとオブジェクトのない配列を使用して二重リンクリストを実装することです。誰かが要素が互いにどのようにリンクされているかを説明できますか？
2 に答える
2
最初のものはキー9を持ち、インデックスに保存されます[7]。Lリストの先頭のインデックスが含まれているので、これを知っています（7）。そして確かに、あなたはそれが「前の」値を持っていないのを見ることができます。
ここから、リスト内の次のアイテムがインデックスに保存されます[5]。（これは、インデックスの配列の「次へ」で示されます[7]。このセルのキーは16。です。
ここから[2]、キーを持っている、キーを持っ4ている、に進み[3]ます1。「次」がないため、これはリストの最後の項目です。
逆方向に移動したい場合は、「前の」値も確認できます。「next」と「prev」には、「key」とはまったく異なるタイプの番号が含まれていることに注意してください。NextとPrevは配列インデックスを参照しており、この実装では基本的にポインターの代わりになります。キーには、リスト内のその時点でのノードの実際の内容を表す数値が含まれています。
于 2013-02-16T03:46:58.003 に答える
0
データ構造は正常に機能します。C ++をコーディングしている場合は、nextとprevを定義するだけです。タイプsize_tの。しかし、私には何の価値もありません。
次の要素に進むには、追加の数学演算が必要です。ポインタでリンクされた従来のリストでは、pNextフィールドに格納されているアドレスにアクセスするだけです。リンクリストを使用して、次の要素のアドレスを計算するには、1回の乗算と1回の加算が必要です。
キャッシュを使いやすくするためにメモリレイアウトを最適化することが目標である場合、リストの一部の実装ではすでに実行されています。たとえば、ATLでのMicrosoftの実装はそれを行います。新しい演算子で要素を割り当てる代わりに、CAtlListクラスはそれらをバッチで割り当てます。そのため、標準のSTLリストは、Microsoftのバージョンに対してベンチマークした場合、通常2倍遅く動作します。
于 2013-02-16T04:05:30.517 に答える