0

現在、(現時点で) 約 5 つの連結リストを使用するプログラムを作成しています。これらの連結リストを変更または使用する関数は約 50 あります。ヘッドノードをどのように正確に実装する必要があるかについて、私はやや引き裂かれています。

実装 #1ダミーのヘッド ノードを使用する

ダミーのヘッド ノードを作成すると、リンク リストに表示するデータがなくても、headNode を削除する必要はありません。以下は、この考えを示す 2 つの異なるリンク リストです。

Format: (object)--name_of_pointer_to_next_object--> (next object)
(headNode)--headNode.pNext--> (Nothing/NULL)
(headNode)--headNode.pNext--> (dataNode1)--dataNode1.pNext--> (dataNode2)--dataNode2.pNext--> (Nothing/NULL)

この実装の利点は、リンクされたリストを操作する関数の場合、ヘッド ノードがNothingor (c++ の場合)の場合に特別なコードを用意する必要がないことNULLです。以下は、この実装を使用して、リンクされたリストの最後にノードを追加する例です。

Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_)
    dim lastNode as NODE_

    Set lastNode = theLinkedList

    Do While Not lastNode.pNext Is Nothing
        Set lastNode = lastNode.pNext
    Loop

    Set lastNode.pNext = theNewNode 
End Function

実装 #2 headNode は削除可能

headNode の削除を許可すると、問題が発生し、記述しなければならないコードの量が増えます。以下は同じデータ セットですが、今回は head がデータを含む正当なノードです。

Format: (object)--name_of_pointer_to_next_object--> (next object)
(Nothing/NULL)
(dataNode1)--dataNode1.pNext--> (dataNode2)--dataNode1.pNext--> (Nothing/NULL)

これは同じ関数ですが、今回はヘッド ノードがNothing/である可能性に注意する必要がありますNULL。

Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_)
    dim lastNode as NODE_

    If theLinkedList Is Nothing Then
        Set theLinkedList = theNewNode 
    Else
        Set lastNode = theLinkedList

        Do While Not lastNode.pNext Is Nothing
            Set lastNode = lastNode.pNext
        Loop

        Set lastNode.pNext = theNewNode 
    End If
End Function

明らかに、私は実装＃1に傾いています。リンクされたリストを使用するたびに、少なくとも 4 行少ないコードが必要です (これを何百回も行うという事実を考えると、その 4 行に 300 を掛けることができます。たとえば、1,200 を書く必要がなくなります)。コードの行)、そしておそらく最も重要なことは、プログラムの状態の量が削減されることです。プログラムが取り得るすべての状態は、 を探すだけで済みます。pNext Is Nothingこの時点で、状態の量を減らすことは非常に高く評価されます。多くの状態を処理しなければならない複雑なコード。

実装＃1がこれを行うための最良の方法であると考えるのは間違っていますか? 実装 #2 が優れている理由は 1 つも思いつきません。

4

1 に答える 1

1

リンクされたリストの最初と最後に特別な予約済みノードを持つことは非常に一般的です (必須ではありません)。これは通常、センチネル ノードと呼ばれます。

余談ですが、「これらのリンクされたリストを変更または使用する約50の関数」を取り、それらをカプセル化するクラスに移動することをお勧めします。

次のようなコードは使用しないでください。

Dim theLinkedList as NODE_
Set theLinkedList = New NODE_

'bunch of work with the list
'bunch of work with the list
'bunch of work with the list

Dim theNewNode as NODE_
Set theNewNode = New NODE_
Set theNewNode.Next = someDataObject

Call AppendNode(theLinkedList, theNewNode)

代わりに、コードは次のようになります。

Dim theList As LinkedList
Set theList = New LinkedList

'etc

Call theList.Append(someDataObject)

違いを見ます？LinkedList 呼び出しは、詳細をラップして非表示にします。先頭または末尾にセンチネル ノードがあるかどうかなども処理できるため、プロジェクトのコードの残りの部分はすべて無意識に認識されます。

于 2012-07-16T12:44:29.877 に答える