Ошибка сегментации при реализации связанных списков XOR

Question

Код довольно прост, и, возможно, я упускаю что-то очевидное, что вызывает ошибку сегментации.На первый взгляд код реализации двунаправленных связанных списков XOR (намеревается) создает три узла и пересекает их слева направо.узлы в списке.

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
}