c++ - C++ 异或链表

Question

所以我自己尝试用 C++ 实现 XOR 链表，我想出了这样的东西

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node* npx;
};

Node* XOR(Node* prev, Node* next) {
    return (Node *)((uintptr_t)(prev) ^ (uintptr_t)(next));
}

// add a new node to linked list head is the beginign of the list
void Add(Node **head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    if (head = NULL) {
        cout << "no head";
    }
    else {
        while (XOR(*head, (*head)->npx) != NULL) {
            *head = XOR(*head, (*head)->npx);
        }
        (*head)->npx = XOR(XOR((*head)->npx, XOR(*head, (*head)->npx)), newNode);

    }

}
//geting data from the list with given indx
int Get(int index, Node* head) {
    for (int i = 0; i <= index; i++) {
        if (XOR(head, head->npx) != NULL) {
            head = XOR(head, head->npx);
        }
        else {
            cout << "index out of range";
        }
    }
    return head->data;
}


int main()
{
    Node** newNode = new Node* ();

    Add(newNode, 10);
    Add(newNode, 2);
    cout << Get(1, *newNode);
    return 0;
}

但是即使使用硬编码测试它也不会返回任何内容，任何人都可以帮助我或展示解决方案应该是什么样子吗？

Answer 1

问题1:=用来代替==

if (head = NULL)

立即销毁head 指针。这个错误将被许多现代编译器标记。这不是编译器错误，即使在 if 语句中，将 head 设置为 NULL 也是完全合法的，但由于它几乎总是一个逻辑错误，一个好的编译器会引起你的注意。不过，有时您必须要求编译器来做。将警告级别调高到您可以容忍的最高水平，您通常会节省调试拼写错误和小错误的时间。

问题 2:Add 总是将头部推进到列表的末尾

由于head是通过指针传递的，前进head会更新调用者的head指针并丢失列表。 Add 确实需要更新 head 指针，但前提是列表为空。

问题3:前一个节点没有正确追踪

这使得 npx = previous ^ next 难以计算。你总是需要知道两个节点才能恢复第三个，而前一个节点可以恢复，但简单地坚持下去要容易得多。

解决方案:

我试图将其复杂化，如果代码愚蠢且优化不佳，请原谅我。关于我在做什么以及为什么嵌入代码中的评论。

#include <iostream>
#include <stdexcept>

using namespace std; // reconsider using this. It can have negative side 
                     // effects when your programs get more complicated 

struct Node; // Forward declaration 
             // XOR needs Node, and a small change to Node meant Node needed XOR
             // this struck me as the most-polite way to resolve the circle

// Unchanged
Node* XOR(Node* prev, Node* next) {
    return (Node *)((uintptr_t)(prev) ^ (uintptr_t)(next));
}

struct Node {
    int data;
    Node* npx;
    // add a constructor to make life easier. npx is always computed correctly
    Node(int data, Node* prev, Node * next): data(data), npx(XOR(prev, next))
    {

    }
    // TODO: GetNext and GetPrev functions could be useful here. eg:
    Node * GetNext(Node * prev)
    {
        return XOR(prev, npx);
    }
    // Along  with a link(prev, next) function this would let you hide the XOR and 
    // abstract away all external knowledge of how the linked list is connected from 
    // the user.
};

// add a new node to linked list head is the beginning of the list
void Add(Node * &head, int data) { // note: using reference rather than double pointer
    if (head == nullptr) { // no head, not much to do
        head = new Node(data, nullptr, nullptr); // there is no prev or next
                                                 // if there is only one node
    }
    else {
        // book keeping
        Node * prev = nullptr; // last node visited. On first node, so null
                               // NOTE: THIS IS A (sort of) LIE! This implementation 
                               // CANNOT be called with a Node from the the middle of a 
                               // a list. Sometimes you want this functionality (Why 
                               // search the whole damn list if you're already part 
                               // way through?) but to get it, you have to provide more 
                               // information so that you can recover the next pointer.
        Node * cur = head; // current node is head
        Node * next = XOR(prev, cur->npx); // next node is prev XOR npx
        // OR Node * next = cur->GetNext(prev);

        while (next != nullptr) { // there is a node here. Advance to next
            prev = cur;
            cur = next;
            next = XOR(prev, cur->npx);
        }
        // found last node. Append new node
        Node * newNode = new Node(data, cur, nullptr); // new tail node, so
                                                       // npx = current node XOR null
        cur->npx = XOR(prev, newNode); // current node now has a next. Update npx
                                       // here is where a cur->link(prev, newNode) function
                                       // would be handy.
    }
}

//getting data from the list with given index
int Get(int index, Node* cur) {
    Node * prev = nullptr; // is no previous node yet
    while (index && // exit when we've iterated far enough
            cur != nullptr) { // or we've run out of nodes
        Node * next =  XOR(prev, cur->npx); // find next node
        prev = cur; // update book keeping
        cur = next;
        index--; // one less iteration
    }
    if (index != 0) // oops.
    {
        // throwing exception rather than allowing the function to return an
        // incorrect value. Often the correct choice unless incorrect indexes
        // is a common occurrence. If something happens often it is not
        //exceptional and thus should not be an exception.
        throw std::out_of_range("index out of range");
    }
    return cur->data;
}


int main()
{
    Node* head = nullptr; //no need for dynamic allocation

    Add(head, 10); //
    Add(head, 2);
    Add(head, 42); // added one more just to be sure
    cout << Get(0, head) << '\n'; // testing that the program can read all elements
    cout << Get(1, head) << '\n';
    cout << Get(2, head) << '\n';

    // TODO: iterate through list and free all of the allocated memory
    return 0;
}