頻繁に交換する必要がある要素を格納するのに最も適したデータ構造はどれですか? リンクされたリストと配列の両方が、この種の操作のお気に入りとして名前が付けられましたが、その理由について疑問に思います...
質問する
919 次
1 に答える
2
正解は「まあ、状況によって異なりますが、通常は配列（ベクトル）が最適です。リンクリストについて話す場合、少なくとも二重リンクリストである必要があります。
いくつかの単一リンクリストがあると仮定しましょう：
...->$el1->$el2->$el3->$el4->$el5...
...そして$el2要素と$el4要素への参照があります（これは交換する必要があります）。技術的には、私たちがする必要があるのは...
1) assign the address of `$el4` (or `$el3->next`) to the `$el1->next` pointer
2) assign the address of `$el2` (or cached `$el1->next`) to the `$el3->next` pointer
3) assign the value of `$el4->next` to the `$el2->next` pointer
4) assign the value of `$el2->next` to the (previously cached) `$el4->next` pointer
...そしてそれだけです。本質的には0（1）の効率です。簡単ですね
ここでの落とし穴は、ここで「前の」要素（$el1および$el3）を取得する簡単な方法（= 0（1））がないことです。$el4とは、それぞれ（およびそれぞれ）$el2のアドレスのみを格納します。nexts$el5$el3
もちろん、代わりに二重リンクリストを使用することもできます。
...$el1<->$el2<->$el3<->$el4<->$el5...
ここでの要素の参照はprev要素と同じくらい簡単なnextので、次のことを行う必要があります...
1-2) swap values of `$el2->prev->next` and `$el4->prev->next`,
3-4) swap values of `$el4->next` and `$el2->next`
しかし、待ってください、もっとあります！prev今すぐポインタを更新する必要があります。
5-6) swap values of `$el4->prev` and `$el2->prev`
おそらくすでに見たように、ここでは3つの「値スワップ」操作です。
ベクトルの場合、これは単一のスワップです。
[$el1][$el2][$el3][$el4][$el5]
1) assign data-value of $el2 to some temp variable;
2) assign data-value of $el4 to $el2;
3) assign data-value of this temp variable to $el4;
もちろん、理論的には、これは以前のアプローチよりも遅くなる可能性があります（この「データ値」が非常に大きいため、ポインターを3回コピーするよりもコピーに時間がかかる場合）。しかし実際には、配列とリンクリストの両方に格納されているそのような巨大なデータへのポインタです。
于 2012-09-19T14:02:13.827 に答える