c - 如何解决链表中损坏的指针？

Question

如果我发现链表中的指针（链接）字段已损坏，我该如何解决这个问题？

我在面试中被问到这个问题。我说不行，解决不了。面试官说有可能。有什么办法吗？

Answer 1

假设它是一个双向链表：

如果损坏的是“下一个”指针，则可以从尾部开始并使用“上一个”指针，向头部遍历列表，同时保持对遍历的最后一个元素的引用。当您找到具有错误指针的元素时，您只需将该元素的“下一个”指针指向被遍历的最后一个元素。

如果双向链表中的“前一个”链接损坏，则可以反转该过程 - 从头部开始，遍历直到找到错误的“前一个”指针，并使用对遍历的最后一个元素的引用来修复它。

Answer 2

在双循环链表中，如果任何一个指针（前一个或下一个指针）损坏，我们可以解析损坏的指针。

如果下一个指针不正确，我们可以反向遍历链表，然后纠正它，否则如果前一个指针不正确，我们可以正向遍历链表纠正它。

现在我们必须考虑如何识别列表中损坏的链接（指针）。我们使用分别为每个节点分配动态内存（malloc或）。calloc如果我们调用malloc或calloc频繁调用小内存可能会影响系统的性能。而不是这样，我们可以在初始阶段分配一大堆堆内存，然后我们可以为每个节点创建实现自己的内存分配功能。并且也仅将其用于创建列表节点以识别列表的损坏链接。

这提高了系统的性能，也有助于通过检查分配给列表的初始内存的限制来识别节点的链接是否损坏。

一旦我们获得指向节点的指针，我们必须在访问该节点中的数据之前先进行以下检查。

check_limit(node);
check_limit(node->next);
check_limit(node->previous);

我们还可以检查 是否node->previous等于current_node。

在此之后，也有可能node->next指向错误的地址，但在初始内存限制之内。在这种情况下，我们可以读取node->next->previous（这不会导致崩溃，即使next指向错误的地址但在初始内存限制内）并检查它是否等于node。

并且应该NULL始终设置未使用的初始内存空间（使用memset）。

通过这些方式，我们可以找出列表中 99% 的损坏指针。

Answer 3

在开发我的嵌入式作业时，我经常使用前向链接队列。我记数以及头指针。队列有一个 check() 方法，该方法运行 [count] 个链接，如果结果指针与头部不同，则调用关键错误处理程序。它不是万无一失的，但它足以很好地捕获双推和其他此类常见的队列错误。

注意：在多线程应用程序中，队列必须被锁定才能安全检查。

Answer 4

在双循环链表中，如果损坏的指针指向节点的内存位置之一，则首先使用遍历和标记方法找到循环。这将给出具有损坏指针的节点的位置，然后以相反的顺序遍历，然后找出具有 prev 节点位置的节点作为第一步结果节点。在该节点旁边分配损坏节点的指针。问题已修复在反之亦然的场景中逆时针反转。上述解决方案需要 o(N) 空间来匹配遍历的节点地址。

Answer 5

也许你应该摆脱它？真的，在一般情况下这是不可能的，当我们不能只用其他人插入列表的任何元素时。