Деструктор для кругового связанного списка в с ++? - PullRequest
Новая
       23

Деструктор для кругового связанного списка в с ++?

2 голосов
/ 17 июня 2020

, когда деструктор 'class LL' ~ LL () вызывается для этого кольцевого односвязного списка, программа вылетает вместо того, чтобы освободить пространство кучи указателя. Как мне решить эту проблему? 

class Node {
public:
  int data;
  Node *next;
};

class LL {
private:
  Node *head, *tail;

public:
  LL() {
    head = NULL;
    tail = NULL;
  }
  // destructor
  ~LL() {
    Node *p = head;
    while (p->next != head) {
      p = p->next;
    }

    while (p != head) {
      p->next = head->next;
      delete head;
      head = p->next;
    }

    if (p == head) {
      delete head;
      head = nullptr;
    }
  }

  // circular singly Linked list

  void createLL() {
    int n, x;
    cin >> n;

    for (int i = 0; i < n; i++) {
      cin >> x;

      Node *t = new Node;
      t->data = x;
      t->next = NULL;

      if (head == NULL) {
        head = tail = t;
      } else {
        tail->next = t;
        tail = t;
      }
    }
    tail->next = head;
  }

Ответы [ 3 ]

1 голос
/ 17 июня 2020

Это можно сделать в два этапа:

  • Сделать список некруглым. Это имеет два подэтапа:
    • Определение l oop. Для этого существуют опубликованные алгоритмы. Изменить: в вашем списке есть хвостовой указатель, поэтому в вашем случае нет необходимости искать его.
    • Укажите узел обратной ссылки на ноль (или дозорный)
  • Удалите список, который теперь не является циклическим в al oop. Это банально.
0 голосов
/ 17 июня 2020

Есть несколько проблем со связанным списком.

  1. Деструктор связанного списка предполагает, что head не является нулем, хотя есть вероятность, что это может быть. Прежде чем пытаться очистить память, убедитесь, что заголовок не равен нулю. Как только это будет сделано, похоже, что ваш исходный деструктор должен работать.
  2. Функция createLL вызовет неопределенное поведение, если пользователь вводит размер меньше или равный 0. В частности, эта строка tail->next = head;
  3. TreateLL - это неправильное название, поскольку на самом деле он не «создает» новый список в ожидаемом смысле. Содержимое не очищается, поэтому элементы n добавляются в конец текущего списка.
  4. Кроме того, список с циклической связью может быть создан с помощью всего лишь одного указателя конца.

Однако, чтобы заставить вашу реализацию циклического связанного списка работать, выглядит так использовать nullptr вместо NULL, поскольку это окончательный тип указателя. Подробнее здесь

0 голосов
/ 17 июня 2020

При попытке удалить в al oop ваша циклическая ссылка приведет к удалению памяти и будет иметь неопределенное поведение. Итак, сначала подумайте о нарушении циркуляции: 

tail->next = 0;

Затем удалите в al oop

Node* p = head;
while(p)
{
    Node* temp = p;
    p = p->next;
    delete temp;
}

Кстати. tail-> next всегда будет указывать на голову. Таким образом, у вас всегда будет и голова, и хвост в одном указателе. Так что очистить память можно так: 

Node* p = tail->next; //this is head
tail->next = 0;
while(p)
{
    Node* temp = p;
    p = p->next;
    delete temp;
}
...