c - 实现异或链表。尺寸 1 或 2

Question

假设这是我的 XOR 链表结构......

结构 xList {
    整数数据；
    xList* 异或；
}

如果异或链表的大小是 1 或 2应该xor包含什么？

Answer 1

如果 xor 链表的大小是 1 或 2，xor 应该包含什么？

它应该包含prev ^ nextwhereprev是指向前一个元素next的指针，是指向下一个元素的指针，并且^是 XOR 运算符。列表中的第一个元素显然具有nil前一项，最后一项具有nil最后一项，因此您将分别获得nil ^ next和prev ^ nil那些元素。在大小为 1 的列表中，没有上一个或下一个元素，因此您可能可以弄清楚您将在该xor字段中存储什么。

异或链表的想法是，您必须已经知道列表中前一个或下一个元素的地址才能确定下一个或前一个元素。但是，如果您正在遍历列表，那没问题，而且由于这就是您对链接列表所做的事情，因此它可能是一个有用的优化。例如，如果您从头到尾进行迭代，则从指向列表中第一个元素的指针开始。前一个元素是nil，因此要获得您计算的下一个元素：next = prev ^ xor。在移动到下一个元素之前，您还必须记住指向当前元素的指针，以便您可以使用它来获取下一个元素。

Answer 2

您将（上一个 ^ 下一个）存储在 xorlink 指针中。

考虑

struct xList 
{
    int data;
    xList* xorlink;
}

A -> B -> C -> D

你从头开始。你知道 head 没有前一个 - 所以 xorlink 将指向 B 节点。您保存当前指针 (A) 并移动到下一个 (B)。您执行 (A ^ B->xorlink) 以获取指向 C 的指针。 (B ^ C->xorlink) 将为您提供指向 D 的指针。依此类推

反向遍历也是类似的。

无论如何，回答你的问题

1. 如果大小为 1，则第一个节点的 xorlink 应包含 NULL。
2. 如果大小为 2，则第一个节点的 xorlink 应包含指向第二个节点的指针。第二个节点的 xorlink 应该包含一个指向第一个节点的指针。