需要帮助来理解伪代码函数，该函数旨在删除链表中指定内存地址中的元素-解网

问：

我正在研究 T Cormen 的《算法导论》一书中的链表。

书中有一段内容如下：

给定列表中的元素 x，x.next 指向链表中的后续元素，x.prev 指向其前一个元素。

如果 x.prev=NIL，则元素 x 没有前置元素，因此是列表的第一个元素或头部。如果 x.next=NIL，则元素 x 没有后继元素，因此是列表的最后一个元素或尾部。属性 L.head 指向列表的第一个元素。如果 L.head=NIL，则列表为空。

过程 LIST-DELETE 从链表 L 中删除元素 x。必须为它提供指向 x 的指针，然后通过更新指针将 x 从列表中“拼接”出来。

LIST-DELETE(L,x)
1 if x.prev!= NIL
2 x.prev.next = x.next
3 else L.head = x.next
4 if x.next !=
 NIL
5 x.next.prev = x.prev

但是，我没有得到文本中的任何部分。首先，它们检查 x 中包含的下一个可能的内存地址是否为 NIL。如果它不是 NIL，则它们将 x.prev.next 替换为 x.next。现在，x.prev.next 只是一个返回 x.key 内存地址的函数，即返回 x 中的地址。这意味着 x.prev.next 和 x 是相同的。最后，语句 x.prev.next=x.next 似乎是荒谬和荒谬的，因为 x.prev.next 不是一个变量，而是一个返回值的函数，将新值分配给“函数返回语句”是没有意义的。所以，我认为，他们试图暗示 x=x.next，因此，x 中的内存地址等于 x.key 之后下一个元素的内存地址。

接下来，他们检查 x.prev 是否等于 NIL，这意味着 x=L.head。在这种情况下，我们将 L.head 更改为 x.next，即使列表从 x.key 之后的元素开始。因此，x 中包含的内存地址中的元素将被删除。

最后，他们似乎检查 x.next 是否等于 NIL。如果不是，则 x.next.prev（=x）=x.prev。

因此，存储在 x 中的内存地址被 x.prev 返回的内存地址所取代。

但是我真的不知道如何完成删除 x 中包含的地址中元素的真正工作。我对此一无所知。

链接列表伪代码

例如，Python 和 Java 使用引用计数，这意味着它们会跟踪对一个对象存在多少个引用。当引用计数降至零时，这意味着无法再从任何位置访问此对象，因此垃圾回收器可以安全地回收其内存。这是自动完成的，因此您不必思考或做任何事情。

在 C 语言中，内存是手动管理的，因此您必须显式分配和释放内存。删除对元素的所有引用后，应使用显式释放内存。free(pointer_to_element)

编辑：最初，如前面的元素指向，而后面的元素指向。在伪代码（）的第二行中，这被更改了：现在之前的元素指向之后的元素。在最后一行（）中，现在之后的元素指针指向之前的元素。x.prev.next == x.next.prev == xnextxxprevxxx.prev.next = x.nextnextxxx.next.prev = x.prevprevxx

您可以想象队列的每个元素都保存在某个位置。在下表中，我将位置并排放置，但这不是必需的。

位置	0	1	2
元素	一个	X	B
昨日	零	0	1
下一个	1	2	零

最初，我们有这样的设置：

L.head = 0 (--> points to A as the first element of the queue)
A.prev = NIL (because it's at the start of the queue)
A.next = 1 (--> points to X)
X.prev = 0 (--> points to A)
X.next = 2 (--> points to B)
B.prev = 1 (--> points to X)
B.next = NIL (because it's at the end of  the queue)

现在我们一步一步地执行你的程序：不是 NIL，所以第二行被执行。在第二行之后，指针将如下所示（只是发生了变化）：X.prevA.next

|位置 |0 |1 |2 | |----------|---|---|---| |元素 |答 |十 |乙 | |上一页 |无 |0 |1 | |下一页 |2 |2 |无 | 第 3 行的语句未执行，因为该语句为 true。在第 4 行中，确实不是 NIL，因此执行第 5 行。之后，指针将如下所示（只是发生了变化）：elseifX.nextB.prev

位置	0	1	2
元素	一个	X	B
昨日	零	0	0
下一个	2	2	零

请注意，X 仍然存在，并且它自己的指针没有更改。这无关紧要，因为从队列（）的开头不再可以访问 X。如果我们现在按照指针遍历列表，就会发生这种情况：L.head

L.head points to location 0, we go there and find element A
A.next points to location 2, we go there and find element B
B.next points to NIL, so we know we have reached the last element and are done

如果位置与列表中的位置不对应，这也有效。我保留了列表的顺序（A -> X -> B），所以 L.head 指向 5（因为 A 是队列中的第一个元素）：

位置	0	1	2	3	4	5
元素	没有	X	没有	没有	B	一个
昨日	没有	5	没有	没有	1	零
下一个	没有	4	没有	没有	零	1

如果我们在此列表中运行该算法，结果将如下所示：

位置	0	1	2	3	4	5
元素	没有	X	没有	没有	B	一个
昨日	没有	5	没有	没有	5	零
下一个	没有	4	没有	没有	零	4

再次只是改变了。A.nextB.prev

需要帮助来理解伪代码函数，该函数旨在删除链表中指定内存地址中的元素

Need help in understanding the pseudocode function that aims to delete an element in a specified memory address in a linked list

评论

评论

评论