0

二重リンクリストと単一リンクリストの両方からノードを削除するためのロジックを思い付くのに苦労しています。ヘルプからオンラインで調べましたが、簡単な例が見つかりませんでした。これが私が持っているものです：

二重にリンクされた削除。dCurrent削除するノードです。

if (dCurrent == dHead){
   dHead = dCurrent->next;
   dHead->prev = NULL;
}
else if(dCurrent == dTail){
   dTail = dCurrent->prev;
   dTail->next = NULL;
}
else{
   dCurrent->next->prev = dCurrent->prev;
   dCurrent->prev->next = dCurrent->next;   
}

これが私が単一リンクリストのために持っているものです。繰り返しsCurrentますが、削除するノードです。およびsPrev = sCurrent->prev。

if(sPrev == NULL){
   sHead = sCurrent->next;
}
else{
   sPrev->next = sCurrent->next;
}

問題は、両方のリストからランダムノードのコレクションを削除した後、二重にリンクされたリストが頭から尾まで正しく表示されますが、尾から頭までは正しく表示されないことです。単一リンクリストも正しく表示されません。

4

2 に答える 2

3

あなたの二重リンクリストの論理は私にはうまく見えます。私の唯一の懸念は、dCurrentがリスト内の唯一の要素である場合、これは次のことです。

if (dCurrent == dHead){
    dHead = dCurrent->next;
    dHead->prev = NULL;
}

ほとんどの場合、nullポインタを参照しようとします。（リストの設計方法によって異なります。ただし、通常の設計でdCurrentは、が唯一のノードである場合は、dCurrent->nextですNULL。）

「sPrev=sCurrent-> prev」という仮定を考えると、抽象的には、単一リンクリストのロジックも問題ないように見えます。しかし、私はその仮定がどのように正しいのか理解していません。単一リンクリストの場合、ポインタsCurrentはありません。prev

于 2011-11-30T21:00:49.197 に答える
0

私が見ることができる唯一の問題は、ヘッドまたはテールがNULLに更新されるシナリオではコードが正しく機能しないことです。

基本的に、唯一のノードを削除すると、dHeadはnullを指すため、次のような後続のステートメントの周りに「ガード」を配置する必要があります。

dHead->prev = NULL;

そのようです

if (dHead != NULL) {
  dHead->prev = NULL;
}

非常に多くの条件を「回避」する1つの方法は、NIL（タイプではない）要素を割り当てることです。

NILは、NULLを置き換える「ノード」です。これは「リストのデータ部分から外れている」ことを表すため、次はALWAYS NIL（循環参照）であり、前はALWAYS NIL（循環参照）です。このような場合、リストの外部でNILにアクセスできないようにし、head-> prev==NILおよびtail->next==NILであることを確認します。そうすれば、多くのif (tail != null) { ... }タイプステートメントを回避できます。

このような構成では、空のリストはhead == NIL && tail == NIL。これによりステートメントの数が劇的に減少しif (something == null)ますが、考慮すべきifステートメントが1つあります。ヘッドが（何かを削除した後）NILの場合、一貫性を保つためにテールをNILに設定する必要があります。

于 2011-11-30T21:06:26.220 に答える