0

アルゴリズムの概要Ed3で、リンクリストに要素を挿入するための擬似コードアルゴリズムを読みましたが、中間の手順がわかりません。

x.prev = L.head
if L.head != NIL
    L.head.prev = x
L.head = x
x.prev = NIL

元のリンクリストがHEAD -- 4 -- 24である場合、手順は次のとおりです。

  1. HEAD-4--24

  2. x-4-24

  3. HEAD --x --4 --24

2.に対応

x.prev = L.head

頭の前にxを挿入する必要があるのはなぜですか

 if L.head != NIL
        L.head.prev = x

？

smbdyは明確にすることができますか？

4

2 に答える 2

1

ヒントはそれです

L：head：preは、L：headが指すオブジェクトのpre属性を示します

次に、アルゴは次のようになります

    //HEAD -- 4 -- 24

    x.next = l.head
    if L.head != NIL
        L.head.prev = x

    //x -- 4 -- 24

    L.head = x
    x.prev = NIL

   //HEAD -- x -- 4 --24
于 2013-03-27T09:19:57.850 に答える
1

たとえば、最初はヘッドがノード[Y]を指しています。つまり、[Y]が現在のヘッドです。リストのヘッドノードになる新しいノード[X]を挿入するので、ヘッドポインタは[X]を指します。

ここで、時間の初めに（リストに何かを挿入する前に）HeadがNiLを指すことを覚えておいてください。

次に、疑似コードをステップバイステップで実行して、何が起こっているかを確認します。

リストの現在の状況は次のとおりです。Head -> [Y], [Y].prev -> NiLヘッドが[Y]を指しているため、ヘッドポインターを変更するまで、ヘッドを使用するときはいつでも[Y]と考える/読むことができます。現在のヘッドノード[Y]は[X]の後に続くので、[X]=[Y]の次を設定しましょう

1. x.next = L.head

最初の声明の後、私たちは[X].next->[Y], Head->[Y], [Y].prev->NiL

2. if (L.head != NIL) //At the beginning Head might be pointing to NiL, and of course NiL.prev does not exist and we do not want to access illegal location.
    3. L.head.prev = x //if head is not pointing to Nil then it is pointing to [Y],
                       //in that case [X] will be the prev node of [Y], 
                    //so after this line, have Head->[Y], [X].next->[Y], [Y].prev->[X]

3行目以降、リストのヘッドポインタをポイント[X]に安全に設定できます。

4. L.head = x    
5. x.prev = NIL //You can write L.head.prev = NIL, as [X] is now the new head
于 2013-03-27T10:46:58.930 に答える