Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

c++ - XOR Doubly Linked List

So I am trying to create a XOR Doubly Linked List as part of an exercise, but I keep getting a Segmentation fault on my removeFirst() function. I cannot figure out what is going wrong, does anybody have a clue?

This is what a node looks like:

class Node{

public:
    int data;
    Node *XOR;

};

I am using this function to calculate the XOR:

Node* returnXOR(Node *a, Node *b){
    return (Node*)((uintptr_t) (a) ^ (uintptr_t) (b));
}

This is my XOR Doubly Linked List class:

class XORDLL{

public:
Node *head;

XORDLL(){
    head = NULL;
}

void addFirst(int data){
    // Make a newNode pointer
    Node *newNode = new Node;

    // Set the variables
    newNode->data = data;
    newNode->XOR = returnXOR(head, NULL);   

    // If the head is not empty set the XOR of the head to the next XOR the newNode
    if(head != NULL){
        head->XOR = returnXOR(newNode, returnXOR(head->XOR, NULL));
    }   

    // Set the newNode to the head 
    head = newNode;
}

void removeFirst(){
    // If head is equal to NULL, do nothing
    if(head == NULL){
        return;
    }
    // Store current head
    Node *tmp = head;

    // Set head equal to the next address
    head = returnXOR(tmp->XOR, NULL);
    head->XOR = returnXOR(tmp->XOR, tmp);


    // Delete tmp variable
    delete tmp;
}

void printList(){
    Node *current = head;
    Node *prev = NULL;
    Node *next;
    while(current != NULL){
        printf("%d ", current->data);
        next = returnXOR(current->XOR, prev);
        prev = current;
        current = next;           
    }
    printf("
");
}
};

When I run this piece of code:

int main(){
    XORDLL l;
    l.addFirst(1);
    l.addFirst(2);
    l.addFirst(3);
    l.printList();
    l.removeFirst();
    l.printList();
    return 0;
}

This is the output:

3 2 1 Segmentation fault (core dumped)

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

You delete the malloc'ed data. You need to free it instead, or use new instead of malloc. Another bug is that you miss this line:

          void removeFirst(){
          // If head is equal to NULL, do nothing
          if(head == NULL){
              return;
          }
          // Store current head
          Node *tmp = head;

          // Set head equal to the next address
          head = returnXOR(tmp->XOR, NULL);
          head->XOR = returnXOR(head->XOR, tmp); <<<<<<<<<<<<<<<<<< Here

          // Free tmp variable
          free(tmp);
      }

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...