Обратно связанный список вызывает цикл - PullRequest
Новая
       4

Обратно связанный список вызывает цикл

1 голос
/ 06 мая 2020

Почему это вызывает al oop?

Я пытаюсь создать список с обратной связью, используя итеративный метод, но al oop возникает, когда головной узел перемещается (например, print () ). Я пробовал это с C#, и у меня не было проблем (конечно, с измененным синтаксисом). 

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

void
Reverse(Node& head_ref) {

  Node* current = &head_ref, *next = nullptr, *prev = nullptr;

  while (current != nullptr) {
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
  }
  head_ref = *prev; //strange phenomenon happened here after head_ref is set.
}

int
main() {

  Node* head = new Node();
  Node* first = new Node();

  head->data = 1;
  head->next = first;

  first->data = 2;
  first->next = nullptr;

  Reverse(*head);

  while (head != nullptr) { // <-- infinite loop
    cout << head->data << endl;
    head = head->next;
  }

  return 0;
}

prev переменная в Reverse (...) метод при возврате: 

0x0108ed10 {data=2 next=0x00eff190 {data=1 next=0x00000000 <NULL> } }
    data: 2
    next: 0x00eff190 {data=1 next=0x00000000 <NULL> }

After head_ref установлено, он создает связанный список цикла: 

0x0108ed10 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {...} } } } }
    data: 2
    next: 0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {...} } } } }

1 Ответ

1 голос
/ 06 мая 2020

head_ref = *prev; заменяет Node, потому что head_ref - это Node&, а не Node*&. Принимая во внимание, что вы собираетесь обновить указатель head, а не весь Node head_ref относится к.

Одно исправление будет: 

void Reverse(Node*& head) {
    Node* current = head;
    // ...
    head = prev;
}
// ...
Reverse(head);

Альтернативно: 

Node* Reverse(Node* head) {
    Node* current = head;
    // ...
    return prev;
}
// ...
head = Reverse(head);
...