1

これは、リンクされたリストで実装されている辞書について話しているときのアルゴリズム設計マニュアルからのものです。

ここに画像の説明を入力

1 つは、「挿入時にlast->nextまだ NULL に等しいかどうかを確認する」という部分です。なぜそれを確認する必要があるのでしょうか?要素を挿入している場合、最後の項目が正しく NULL を指しているかどうかにどのように影響しますか?私たちは実装を正しく行っているのではないでしょうか? 次のようなことを言うことはできません:

last->next = nodeToInsert;
last = last->next;

なぜそれがうまくいかないのですか？

次に、最後から 2 番目の段落は、片方向リンク リストの最後の項目を削除し、新しい最後の項目を識別しなければならない場合について話しているのでしょうか? そして、(O(n) の複雑さで) 最後から 2 番目の項目にトラバースし、それを最後に設定し、前の最後を削除するだけでしょうか? そして、これを既存の削除メソッドと混ぜ合わせて、それが最後のアイテムかどうかのケースを追加するだけですか?

4

3 に答える 3

3

なぜそれを確認する必要があるのでしょうか。

おそらく、常にリストの最後に挿入しているわけでlastはないため、常に更新する必要はありません。

第二に、...

はい。

于 2013-01-13T19:05:59.433 に答える
1

このセクションは、ソートされたリストとして実装されている辞書について話していることに注意してください。

これは、挿入が正確に正しいポイントで行われる必要があることを意味します。提案されたコードがリストの最後に追加されます。

last->next = nodeToInsert;
last = last->next;

これは、ソートされていないリストでは正しいですが、ソートされているリストでは正しくありません。

また、作成者が通常のリンク リストに追加されるポインタとして last を使用していることにも注意してください。

最後は二重連結リスト構造の一部であるとあなたは信じていると思います。そうであれば、挿入中に更新する必要があったことは間違いありません。ただし、これは独立したポインターであるため、リンクされたリストとの一貫性を保つために、テキストで説明されている追加のコードが必要です。

于 2013-01-13T20:14:19.267 に答える
0 
if(last->next != NULL) {   // insertion occurred at the tail end
    last = nodeToInsert;   // so update tail pointer to point to inserted node
}

テールエンドの挿入は設定last->next済みです。NULL挿入のせいではなくなりました。それが、last更新する必要があることを示しています (last実際には ですlastButOne)。last->nextまだの場合はNULL、挿入が の前のどこかで発生したため、何もする必要はありませんlast。あなたの本の文言は、おそらく、少し誤解を招くものです。これは今意味がありますか？

于 2013-01-13T20:04:10.387 に答える