26

CLRSの教科書「アルゴリズム入門」には、そのような段落があります。258。

リストが二重にリンクされている場合、O（1）時間で要素を削除できます。（CHAINED-HASH-DELETEは、キーkではなく要素xを入力として受け取るため、最初にxを検索する必要はありません。ハッシュテーブルが削除をサポートしている場合、そのリンクリストは二重にリンクされている必要があります。アイテムをすばやく削除できます。リストが単一リンクのみの場合、要素xを削除するには、最初にリスト内でxを見つけて、xの前の属性の次の属性を更新できるようにする必要があります。単一リンクリストの場合、両方を削除します。検索の実行時間は同じです）。

私が困惑しているのは、この大きな括弧です。私はその論理を理解できませんでした。二重リンクリストの場合でも、削除するにはxを見つける必要がありますが、これは単一リンクリストとどのように異なりますか？私がそれを理解するのを手伝ってください！

4

8 に答える 8

32

ここで提示される問題は次のとおりです。ハッシュテーブルの特定の要素を見ていると考えてください。それを削除するのにどれくらいの費用がかかりますか？

単純なリンクリストがあるとします。

v ----> w ----> x ----> y ----> z
                |
            you're here

ここで、を削除xした場合は、に接続wしyてリストをリンクしたままにする必要があります。アクセスwして、ポイントするように指示する必要がありますy（必要ですw ----> y）。ただし、リンクされているだけなのでwアクセスできません。したがって、O（n）操作でx見つけるためにすべてのリストを調べてから、にリンクするように指示する必要があります。それは良くないね。wy

次に、二重にリンクされているとします。

v <---> w <---> x <---> y <---> z
                |
            you're here

かっこいい、ここからwとyにアクセスできるのでw <---> y、O（1）操作で2つ（）を接続できます！

于 2011-11-12T16:53:58.497 に答える
2

これのハッシュテーブル部分はほとんどが赤いニシンであるように私には思えます。本当の問題は、「リンクリストから現在の要素を一定時間で削除できるか、もしそうならどのように削除できるか」です。

答えは次のとおりです。少し注意が必要ですが、実際にはそうです。少なくとも通常は可能です。前の要素を見つけるために（通常）リンクリスト全体をトラバースする必要はありません。代わりに、現在の要素と次の要素の間でデータを交換してから、次の要素を削除することができます。

これに対する1つの例外は、リストの最後の項目を削除する必要がある場合/必要な場合/削除したい場合です。この場合、交換する次の要素はありません。あなたが本当にそれをしなければならないのなら、前の要素を見つけることを避ける本当の方法はありません。ただし、これを回避するために一般的に機能する方法があります。1つは、nullポインターではなくセンチネルでリストを終了することです。この場合、番兵値を持つノードを削除することはないため、リストの最後の項目を削除する必要はありません。これにより、次のような比較的単純なコードが残ります。

template <class key, class data>
struct node {
    key k;
    data d;
    node *next;
};

void delete_node(node *item) {
    node *temp = item->next;
    swap(item->key, temp->key);
    swap(item->data, temp->data);
    item ->next = temp->next;
    delete temp;
}
于 2011-11-12T17:10:32.273 に答える
1

一般的に、あなたは正しいです-あなたが投稿したアルゴリズムは、キーだけでなく要素自体を入力として受け取ります：

CHAINED-HASH-DELETEは、キーkではなく要素xを入力として受け取るため、最初にxを検索する必要がないことに注意してください。

要素xがあります-これはダブルリンクリストであるため、先行および後続へのポインタがあり、O（1）でこれらの要素を修正できます-単一のリンクリストでは、後続のみが使用可能になるため、次のようにする必要があります。 O（n）で先行を検索します。

于 2011-11-12T16:50:04.930 に答える
1

要素xを削除したい場合、二重リンクリストを使用すると、xの前の要素をxの次の要素に簡単に接続できます。したがって、すべてのリストを確認する必要はなく、O（1）になります。

于 2012-07-19T05:53:00.870 に答える
0

Find(x)一般に、チェーンハッシュテーブルの場合はO（1）です。単一リンクリストを使用するか、二重リンクリストを使用するかは重要ではありません。パフォーマンスは同じです。

実行した後の場合Find(x)、返されたオブジェクトを削除することにした場合、内部的には、ハッシュテーブルでオブジェクトを再度検索する必要がある場合があります。それでも通常はO（1）になり、大したことではありませんが、非常に多くを削除すると、もう少しうまくいくことができます。ユーザーの要素を直接返す代わりに、基になるハッシュノードへのポインターを返します。その後、いくつかの内部構造を利用できます。したがって、この場合、連鎖を表現する方法として二重リンクリストを選択した場合、削除プロセス中にハッシュを再計算してコレクションを再度検索する必要はありません。この手順は省略できます。座っている場所から削除を実行するのに十分な情報があります。送信するノードがヘッドノードである場合は、さらに注意が必要です。

トレードオフは、追加のポインターによって占有される保証されたスペースと、可能なより高速な削除（および少し複雑なコード）です。最新のデスクトップでは、通常、スペースが非常に安いため、これは妥当なトレードオフになる可能性があります。

于 2013-03-13T18:28:47.300 に答える
0

コーディングの観点：unordered_mapこれを実装するためにC++で使用できます。

unordered_map<value,node*>mp;

node*キー、左および右のポインタを格納する構造体へのポインタはどこにありますか？

使い方：

値がvあり、そのノードを削除したい場合は、次のようにします。

  1. のようなノード値にアクセスしますmp[v]。

  2. 次に、左側のポインタが右側のノードを指すようにします。

そして出来上がり、あなたは終わりです。

（念のために言っておきますが、C ++unordered_mapでは、格納されている特定の値にアクセスするために平均O（1）が必要です。）

于 2015-06-03T17:00:37.667 に答える
0

教科書を読んでいると、同じトピック（「x」が要素へのポインタなのか要素自体へのポインタなのか）についても混乱し、最終的にこの質問にたどり着きました。しかし、上記の議論を経て教科書をもう一度参照した後、本では「x」は暗黙的に「ノード」であると想定され、その可能な属性は「キー」、「次」であると思います。

いくつかの行が教科書を形成しています。

1）CHAINED-HASH-INSERT（T、x）リストの先頭にxを挿入T [h（x.key）]

2）リストが単独でリンクされている場合、要素xを削除するには、最初にリストT [h（x.key ）]でxを見つけて、xの前の属性の次の属性を更新できるようにする必要があります。

したがって、要素へのポインタが与えられていると仮定でき、Fezvezは尋ねられた質問に対して適切な説明を与えたと思います。

于 2019-01-06T03:41:26.487 に答える
-3

教科書が間違っています。リストの最初のメンバーには使用可能な「前の」ポインターがないため、要素がチェーンの最初である場合は、要素を見つけてリンクを解除するために追加のコードが必要です（通常、要素の30％がチェーンの先頭です。 N = M、（N個のアイテムをM個のスロットにマッピングする場合。各スロットには個別のチェーンがあります。））

編集：

バックリンクを使用するよりも良い方法は、私たちを指すリンクへのポインターを使用することです（通常、リスト内の前のノードの->次のリンク）

struct node {
   struct node **pppar;
   struct node *nxt;
   ...
   }

その後、削除は次のようになります。

*(p->pppar) = p->nxt;

また、このメソッドの優れた機能は、チェーンの最初のノード（ppparポインターがノードの一部ではないポインターを指している）でも同様に機能することです。

更新2011-11-11

人々は私の主張を理解できないので、私は説明しようとします。例として、ハッシュテーブルtable（基本的にはポインタの配列）と多数のノードoneがありtwo、threeそのうちの1つを削除する必要があります。

    struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one->next = two , two-next = three, three->next = NULL;
                one->prev = NULL, two->prev = one, three->prev = two;


    /* How to delete element one :*/
    if (one->prev == NULL) {
            table[31] = one->next;
            }
    else    {
            one->prev->next = one->next
            }
    if (one->next) {
            one->next->prev = one->prev;
            }

これで、上記のコードがO（1）であることは明らかですが、厄介なことがあります。それでもarray、とインデックスが必要な31ので、ほとんどの場合、ノードは「自己完結型」であり、ノードへのポインタで削除できます。チェーンの最初のノードである場合を除いて、チェーンからのそれ。その後、を検索するために追加情報が必要になりtableます31。

次に、ポインタからポインタへのバックリンクを使用した同等の構造を検討します。

    struct node {
            struct node *next;
            struct node **ppp;
            char payload[43];
            };

    struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one-next = two , two-next = three, three->next = NULL;
                one->ppp = &table[31], two->ppp = &one->next, three->ppp = &two-next;

    /* How to delete element one */
    *(one->ppp) = one->next;
    if (one->next) one->next->ppp = one->ppp;

注：特別な場合はなく、親テーブルを知る必要もありません。（ハッシュテーブルが複数あるが、ノードタイプが同じである場合を考えてみてください。削除操作では、ノードをどのテーブルから削除する必要があるかを知る必要があります）。

多くの場合、{prev、next}シナリオでは、二重リンクリストの先頭にダミーノードを追加することで、特殊なケースを回避できます。しかし、それも割り当てて初期化する必要があります。

于 2011-11-12T16:53:24.293 に答える