XOR链表实现中的分段错误

Question

该代码非常简单，也许我遗漏了导致分段错误的显而易见的东西。乍一看，双重XOR链表实现代码（打算）创建了三个节点，并以从左到右的方式遍历它们。

#include <iostream>

using namespace std;

typedef struct node { int data = 0; struct node* npx = NULL; }n;

n *zor(n *a, n *b) {
    return (n*)((uintptr_t) a ^ (uintptr_t) b);
}

int main() {

    n *head, *a, *b;

    head = new n;
    a = new n;
    b = new n;

    head->npx = zor(NULL, a);
    a->npx = zor(head, b);
    b->npx = zor(a, NULL);

    n* ptr = head;
    while (ptr != NULL) {
        cout << ptr->data;
        ptr = zor(ptr, ptr->npx);
    }
}

我希望遍历列表中的所有节点后输出为“ 000”。

Answer 1

出了什么问题

链接已正确构建，将前一个指针与下一个指针结合在一起。

link = previous ^ next

不幸的是，稍后再恢复下一个指针时

ptr = zor(ptr, ptr->npx);

尝试再次使用]重建>

next = current ^ link
而不是

next = previous ^ link
导致下一个损坏。这意味着您需要更多记账以跟踪该先前节点。

可能的解决方案

n* current = head; // changed name to make code match description
n* previous = NULL; // no previous at the head
while (current != NULL) {
    cout << current->data;
    n* next = zor(previous, current->npx); // need a temp so we can update previous
    previous = current; // current becomes the next's previous
    current = next; // advance current to next
}