2

ページ。プログラミング インタビュー公開本の 29 には、リンクされたリストから要素を削除する次のサンプル コードがあります。

bool deleteElement(IntElement **head, IntElement *deleteMe)
{

     IntElement *elem = *head;

     if(deleteMe == *head){ /*special case for head*/
         *head = elem->next;
         delete deleteMe;
         return true;
     }

     while (elem){
         if(elem->next == deleteMe){
             /*elem is element preceding deleteMe */
             elem->next = deleteMe->next;
             delete deleteMe;
             return true;
         }
         elem = elem->next;
     }

     /*deleteMe not found */
     return false;   
}

私の質問は、「delete deleteMe」ステートメントについてです。これは、実際にその位置の要素を削除するという、私たちが望む効果を達成していますか、それとも deleteMe 要素へのポインタのコピーを削除しているだけですか?

4

3 に答える 3

4

delete deleteMe;要素のデストラクタを呼び出し、関連するメモリを解放します。このコードはC++です。

コードの残りの部分は、データ構造であるリストを変更して、要素を隣接する要素からリンク解除します。

于 2012-10-04T04:12:16.173 に答える
3

あなたの質問はすでに答えられていますが、私が誰かにインタビューしていて、彼らがこのようにコードを書いたとしても、私はそれほど感銘を受けないだろうと指摘しなければなりません。

手始めに、ここでのポインターへのポインターの使用は、Cでは妥当ですが、C++では完全に不要です。代わりに、ポインターへの参照を表示したいと思います。第二に、constが正しいコードが一般的に望ましいです。

bool deleteElement(IntElement const *&head, IntElement const *deleteMe)
{
     IntElement *elem = head;

     if(deleteMe == head){ /*special case for head*/
         head = elem->next;
         delete deleteMe;
         return true;
     }    
     while (elem){
         if(elem->next == deleteMe){
             /*elem is element preceding deleteMe */
             elem->next = deleteMe->next;
             delete deleteMe;
             return true;
         }
         elem = elem->next;
     }    
     /*deleteMe not found */
     return false;   
}

最後に、リストの不要なトラバースを回避するために、もう1つの特殊なケースを追加します。削除するアイテムがたまたまリストの最後にない限り、トラバーサルを回避できます。IntElementが次のようなものであると仮定しましょう。

struct IntElement { 
    int data;
    IntElement *next;
};

この場合：

bool simple_delete(IntElement *deleteMe) {
    IntElement *temp = deleteMe->next;
    deleteMe->data = temp->data;
    deleteMe->next = temp->next;
    delete temp;
    return true;
}

リスト全体を検索して前の要素を見つけているので、後の要素を削除できます。代わりに、次のノードを現在のノードにコピーしてから、次のノードを削除します（注：コピーするよりもデータを交換する方が良い/速い場合があります）。また、他の何かが次のノードへのポインタを保持している可能性がある場合、これは物事を（かなり完全に）壊す可能性があることにも注意してください。

[その価値については、私はもともと、この手法をニクラウスヴィルトによるアルゴリズム+データ構造=プログラムから学びましたが、クヌースに端を発していると思います。]

deleteElementとにかく、それができたら、削除するノードがリストの最後でない限り、それを使用するためのコードを少し追加するだけです。

bool deleteElement(IntElement const *&head, IntElement *deleteMe) { 
    if (deleteMe->next != NULL)
        return simple_delete(deleteMe);
    // previous body of deleteElement
}

オリジナルが常に線形の複雑さを持っていた場合、これはほとんどの場合一定の複雑さを持っています。最後にNULLポインターの代わりに番兵値を持つリストを使用することにより、すべての場合で一定の複雑さを保証できます（そして、すべてのsimple_delete場合を処理します-残りのコードを完全に排除できます）。

于 2012-10-04T05:01:33.653 に答える
1

実際には、ノードのコピーではなく、ノード自体を削除しています。

于 2012-10-04T04:08:17.640 に答える