0

我目前正在编写一个程序，该程序（截至目前）使用大约五个链表，并且大约有 50 个函数可以修改或以其他方式使用这些链表。我对应该如何实现头节点感到有些不安。

实现 #1使用虚拟头节点

如果我创建一个虚拟头节点，则无需删除 headNode，即使该链表没有数据可以表示。下面是显示这个想法的两个不同的可能链接列表。

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)

这种实现的好处是，对于与链表一起工作的函数，它们不必为头节点为Nothing或（在 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，这会带来问题并增加我必须编写的代码量。下面是同一组数据，只是这次头是包含数据的合法节点。

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，并且在这一点上非常感谢减少状态量，因为这个程序将是一个怪物，最终将有大约 20k 行必须处理大量状态的复杂代码。

我认为实施＃1是最好的方法，我错了吗？我想不出实施#2 会更好的单一原因。

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 回答