c -实现异或链表.1号或2号

Question

假设这是我的异或链表结构体…

<>之前struct xList {int数据;xList * xor;}之前

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

Answer 1

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

它应该包含prev ^ next，其中prev是指向前一个元素的指针，next是指向下一个元素的指针，^是异或操作符。显然，列表中的第一个元素的前一项具有nil，最后一个元素的最后一项具有nil，因此您将分别获得这些元素的nil ^ next和prev ^ nil。在大小为1的列表中，没有前面的或下一个元素，因此您可能可以计算出在xor字段中存储的内容。

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应该包含指向第一个节点的指针。