0

在 Introduction to Algorithm Ed 3 中，我阅读了用于在链表中插入元素的伪代码算法，但我不明白中间步骤。

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

如果我的原始链表是HEAD -- 4 -- 24，我了解步骤如下：

  1. 头 -- 4 -- 24

  2. x -- 4 -- 24

  3. 头 -- x -- 4 -- 24

与 2. 对应

x.prev = L.head

为什么我们必须在 head with 之前插入 x

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

?

smbdy 可以澄清一下吗？

4

2 回答 2

1

可以说，最初 Head 指向节点 [Y]，这意味着 [Y] 是当前头。我们将插入新节点 [X]，它将成为我们列表的头节点，因此头指针将​​指向 [X]。

这里请记住，在开始时间（在向列表中插入任何内容之前）Head 将指向 NiL。

现在让我们一步一步地用伪代码来看看发生了什么：

我们列表的当前情况是：Head -> [Y], [Y].prev -> NiL，因为 head 指向 [Y]，所以在我们更改 Head 指针之前，每当我们使用 Head 时，您都可以将其视为/读取为 [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 行之后，我们可以安全地将列表 Head 指针设置为点 [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 回答
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 回答