时间戳

首页 > 解决方案 > 双链表混淆

c++ - 双链表混淆

问题描述

我在理解这段代码时遇到了一些麻烦。它工作得很好，但是我不明白它的某些部分。

给定的代码应该将文件添加到列表中。但我感到困惑的部分是

fNext->fPrevious = &aNode

fNext = &aNode

第一部分是为 fNext->fPrevious 赋值

但是，第二部分不是将 fNext 的值写入 &Node

在这种情况下，fNext->fPrevious 和 fNext 中的值不应该相同。

有人可以向我解释一下。我看过这些例子，但我理解双链表的概念，但我不明白这段代码。

也有人可以详细说明这部分

aNode.fPrevious = 这个。

 void DoublyLinkedNode<DataType>::append(Node& aNode)
{
    aNode.fPrevious = this;

    if (fNext != &NIL)
    {
        aNode.fNext = fNext;

        fNext->fPrevious = &aNode;

    }

    fNext = &aNode;   
}

DoubleLinkedNode 的构造函数是这样的。

template<class DataType>
DoublyLinkedNode<DataType>::DoublyLinkedNode(const DataType& aValue)
{
    fValue = aValue;
    fPrevious = &NIL;
    fNext = &NIL;
}

标签： c++algorithmdoubly-linked-list

解决方案

我目前感到困惑的是 fNext->fPrevious 和 fNext 之间的区别。两者都指向同一件事。

不，他们不是。是的，我们确实设置fNext->fPrevious为&aNode. 但是我们设置fNext为之后&aNode，fNext不是fPrevious我们设置的节点，而是aNode。所以fNext->fPrevious是aNode.fPrevious，这是this，不是aNode。

也许给所有这些节点命名会有所帮助，并以图形方式查看它。在你打电话之前append，你有这样的事情：

prev      this          next                   aNode
...   <-- fPrevious <-- fPrevious      NIL <-- fPrevious
fNext --> fNext     --> ...                    fNext     --> NIL

所以，首先你设置aNode.fPrevioustothis和aNode.fNextto fNext，所以它向后指向this和向前指向next：

prev      this          next                   aNode
...   <-- fPrevious <-- fPrevious     this <-- fPrevious
fNext --> fNext     --> ...                    fNext     --> next

然后你设置fNext->fPrevious为&aNode. 由于fNext当前是该next节点，因此您将next' 的后向指针更改为指向aNode：

prev      this          aNode         next
...   <-- fPrevious <-- fPrevious <-- fPrevious
fNext --> fNext \       fNext     --> ...
                 -------------------/

请注意，此时，两者都this认为aNode节点next是他们的fNext.

最后，我们通过设置fNext来解决这个问题&aNode：

prev      this          aNode         next
...   <-- fPrevious <-- fPrevious <-- fPrevious
fNext --> fNext     --> fNext     --> ...

现在aNode正确地插入到链表中，在this和之间next，每个人都同意一切。

推荐阅读