двойное освобождение или коррупция в деструкторе стека

Question

Я почти уверен, что проблема в while (!empty()) pop();, потому что после того, как я закомментировал это.все отлично работаетно это не delete head.что не так с этой частью?

Цель состоит в следующем: LinkedList имеет два элемента данных, head и tail.Когда список пуст, оба должны быть равны 0.Когда список не пуст, то и head, и tail должны быть ненулевыми, и они должны ссылаться на первый и последний элементы в списке соответственно.И будет путь от head до tail через указатели next_.Если в списке есть только один элемент, то head == tail.

#include <iostream>
//stack using linked list
class LinkedList {
 public:
  LinkedList() : head(0), tail(0) {}
  ~LinkedList() {
    while (!empty()) pop();
    std::cout<< "~LinkedList" << std::endl;
  }
  void pop() {
    node* temp;
    temp = head;
    for ( ; temp->next_ != 0; temp = temp->next_) {
      tail = temp;
    } 
    delete temp; 
    tail->next_ = 0;
    std::cout << "pop()" << std::endl;
  } //removes, but does not return, the top element
  int top() {
    return tail->value_;
  } //returns, but does not remove, the top element
  bool empty() {
    return head == 0;
  }
  void push(const int& value) {
    node* element = new node(value);
    if (empty()) {
      head = tail = element;
    } else {
      tail->next_ = element;
      tail = element;
    }
  } //place a new top element
 private:
  class node {
   public:
    node(const int& input) : value_(input), next_(0) {};
    int value_; //store value
    node* next_; //link to the next element
  };
  node* head;
  node* tail;
};
int main() {
  LinkedList list;
  list.push(1);
  list.push(2);
  std::cout << list.top() << std::endl;
  list.pop();
  std::cout << list.top() << std::endl;
  return 0;
}

устранил проблему, изменив деструктор на следующие коды:

  ~LinkedList() {
    while (head != tail) pop();
    delete head;
    std::cout<< "~LinkedList" << std::endl;
  }

Answer 1

У вас есть одна часть вашей проблемы здесь

bool empty() {
    return head == 0;
}

Когда head установлен на 0 (NULL)? Никогда

Answer 2

pop() неверно. Когда у вас остался только один элемент, на него указывают и head, и tail. Итак, когда вы delete temp, вы фактически удаляете и head, и tail, тогда вы:

• доступ к tail, который теперь является освобожденным указателем, и

• не устанавливается tail или head обратно на 0

Answer 3

Вы можете добавить эти проверки в начале.Это скучное решение, и, возможно, вам следует изменить общий дизайн, но этот код должен исправить ваш текущий алгоритм для pop.В частности, при извлечении последнего предмета голова и хвост должны быть установлены на ноль.

Кроме того, оно должно быть delete tail->next_;, а не delete temp;, перед tail->next_ = 0;

  void pop() {
    if(head == 0) {
        // the list is empty, there's nothing to pop. This should be an error!
    }
    if((head != 0 && head == tail) {
        // there is only one item in the list
        delete head;
        head = 0;
        tail = 0;
    }
    node* temp;
    temp = head;
    for ( ; temp->next_ != 0; temp = temp->next_) {
      tail = temp;
    } 
    delete tail->next_; 
    tail->next_ = 0;
    std::cout << "pop()" << std::endl;
  }

Я не проверял это, но это должно решить некоторые проблемы.

Answer 4

Ваш pop() не исправляет this->head, если вы pop() последний элемент в списке.