-2

解释如何实现双向链表，每个项目只使用一个指针值 np[x] 而不是通常的两个（下一个和上一个）。假设所有指针值都可以解释为 k 位整数，定义 np[x] 为 np[x] = next[x] XOR prev[x]，next[x 的 k 位“异或” ] 和上一个 [x]。（值 NIL 用 0 表示。）一定要描述访问列表头部需要哪些信息。展示如何在这样的列表上实现 SEARCH、INSERT 和 DELETE 操作。还展示了如何在 O(1) 时间内反转这样的列表。

资料来源：Cormen 第三版的 CLRS 10.2-8

PS：这不是作业问题。我正在练习/修改数据结构。

4

1 回答 1

1

将指针称为“常规”整数。因此，您可以对其进行任何整数运算，包括异或。

对于每个节点，存储xorValue = next ^ previous.

为什么有帮助？
如果你从前端迭代到后端——你知道在哪里previous，并且你有它的价值，所以你可以用next = xorValue ^ previous.
当从最后一个迭代到第一个时，同样的想法也适用：previous = xorValue ^ next.

这已经足够了，因为如果不从最后一个到第一个或从第一个到最后一个迭代，您将无法到达链表中的任何位置 - 所以previousOR的值next是您已知的，正如我们所看到的 - 这就是您获得另一个。

基于此，您可以创建（类似 c 的伪代码）：

struct Node { 
   void* data;
   int xorValue;
}
Node* next(Node* node, void* previous) { 
    return (Node*)(node->xorValue ^ (int)previous));
}
Node* previous(Node* node, void* next) { 
    return (Node*)(node->xorValue ^ (int)next));
}

对于头/尾元素 - 将上一个/下一个值（相应地）简单地视为 NULL (0)，并按原样存储下一个元素。它的工作原理是next ^ 0 = next

于 2013-02-01T08:49:19.717 回答