algorithm - 循环异或链表？

Question

我正在阅读有关 XOR 链接列表的内容，我想到了一个问题，在我Is it possible to have a circular XOR linked list?看来，即使我们以某种方式构建这样一个列表，给定列表的头节点也不可能遍历它。例如 - 让链表包含 3 个节点：A、B 和 C。

|
v
A ---> B ---> C

A->xor = B ^ C
B->xor = A ^ C
C->xor = A ^ B

由于我们得到head了列表，即A在这种情况下，我们将无法向前或向后移动，因为我们必须至少知道BorC之一才能移动。由于我们无法遍历它，因此我们也无法构建它。

我的想法正确吗？还是我错过了什么？

score 5 · Accepted Answer

确实，您是对的，不可能遍历此列表，因为我们无法从xor链接中检索任何指针值。

此列表可遍历的最低要求是两条信息……例如指向当前节点的指针和指向下一个（或上一个）节点的指针。然后，您可以从xor链接中检索所有信息。

事实上，这就是维基百科文章所说的：

要从某个点开始沿任一方向遍历列表，您需要两个连续项目的地址，而不仅仅是一个

这仍然比为每个节点存储两个指针便宜，因为我们只需要每个节点一个链接，加上当前和下一个（或前一个）节点的两个指针。

score 1 · Accepted Answer

这很有趣！我写了一个小循环异或链表程序来证明它是可能的。1 和 2 节点的边缘情况有点奇怪，但只要您在某处跟踪头和尾指针，其他一切都会检查出来。（我也知道这是一个有 7 年历史的线程，但我有同样的问题，发现这几乎是唯一提到循环 XOR 链表的地方）

#include <stdlib.h> // for malloc
#include <stdio.h>  // for printf
#include <stdint.h> // for uintptr_t

typedef struct  s_list  t_list;

struct s_list
{
    char        *data;  // Contains a string.
    struct s_list   *npx;   // npx = previous XOR next
};

t_list  *create_elem(char *data, t_list *npx)
{
    t_list  *ret;

    ret = malloc(sizeof(*ret));
    ret->data = data;
    ret->npx = npx;
    return (ret);
}

t_list  *xor(t_list *a, t_list *b)
{
    return (t_list*)((uintptr_t)a ^ (uintptr_t)b);
}

void    insert(t_list **h, t_list **t, char *data)
{
    t_list  *last = *t;
    t_list  *first = *h;
    t_list  *new, npx;

    if (!last && !first)  // No nodes, populate first node
    {
        new = create_elem(data, NULL);  // self XOR self == NULL
        *h = ((*t = new));
    }
    else if (last == first)  // Only one node, set tail properly
        *t = create_elem(data, NULL);   // self XOR self == NULL
    else  // Multiple nodes, do a real add
    {
        // Create an element with npx = first XOR last
        // (it will be inserted at the end of the list)

        new = create_elem(data, xor(first, last));

        // If head or tail's npx == 0, we know its a list of size 2,
        // so each prev and next pointer is the same.
        // So, if it is a list with size 2
        //  last->npx = new XOR first
        //  first->npx = new XOR last
        // else
        //  last->npx = new XOR (last->npx XOR first)
        //  first->npx = new XOR (first->npx XOR last)

        last->npx = xor(new, ((!last->npx || !first->npx) ?
                first : xor(last->npx, first)));
        first->npx = xor(new, ((!last->npx || !first->npx) ?
                last : xor(first->npx, last)));

        // Set the new pointers for passed addresses.
        *h = first;
        *t = new;
    }
}

int traverse(t_list *h, t_list *t)
{
    t_list  *cur = h;
    t_list  *last = t;
    t_list  *tmp;

    while (cur)
    {
        printf("[%s]\n", cur->data);
        tmp = xor(cur->npx, last);
        last = cur;
        cur = tmp;
        if (cur == h)
            return (1);
    }
    return (1);
}

int main(void)
{
    char    s1[] = "Testing!";
    char    s2[] = "My!";
    char    s3[] = "Function!";
    char    s4[] = "For!";
    char    s5[] = "GeeksforGeeks!";

    // We need to keep track of head and tail pointers for
    // everything to work nicely.

    // Traversal will always require access to
    // two consecutive pointers.

    t_list  *head;
    t_list  *tail;

    head = NULL;
    tail = NULL;
    insert(&head, &tail, s1);
    insert(&head, &tail, s2);
    insert(&head, &tail, s3);
    insert(&head, &tail, s4);
    insert(&head, &tail, s5);
    traverse(head, tail);
}

score 0 · Accepted Answer

不可能用一个值遍历列表，但可以找到所有可行的遍历，在这种情况下，我们找到所有可以遍历树的 b 和 c：

a=5
for b in range(0, 16): 
    print(a, b, a ^ b)

5 0 5
5 1 4
5 2 7
5 3 6
5 4 1
5 5 0
5 6 3
5 7 2
5 8 13
5 9 12
5 10 15
5 11 14
5 12 9
5 13 8
5 14 11
5 15 10

score 0 · Accepted Answer

在非循环异或列表中，first节点指针用于将节点添加到列表中，last节点指针用于将节点添加到列表中。我们可以遍历只有一个指针的非循环 XOR 列表。但不是循环异或列表，其中first必须链接到last. 因此，要从一个first或last节点遍历循环异或列表并将节点添加到列表中，我们需要指向两者的指针。

algorithm - 循环异或链表？

4 回答 4

Related

Reference