堆栈析构函数中的双重释放或损坏

Question

我很确定问题出在 while (!empty()) pop(); 因为在我将其注释掉之后。一切正常。但它不会删除 head。这部分有什么问题吗？

其意图如下：LinkedList有两个数据成员，head和tail。当列表为空时，它们都应该等于0。当列表非空时，head 和 tail 都应非零，并且它们应分别引用列表中的第一项和最后一项。并且应该有一条通过 next_ 指针从 head 到 tail 的路径。如果列表只有一项，则 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 都指向它。因此，当您删除 temp 时，您实际上同时删除了 head 和 tail，那么您就是：

• 访问 tail< /code>，它现在是一个已释放的指针，并且

• 不设置 tail 或 head 回到 0

Answer 3

如果您 pop() 列表中的最后一个元素，您的 pop() 不会修复 this->head 。

Answer 4

您可以在开始时添加这些检查。这是一个无聊的解决方案，也许您应该更改整体设计，但此代码应该纠正您当前的 pop 算法。特别是，当弹出最后一项时，head 和 tail 都应该设置为零。

另外，它应该是 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;
  }

我还没有测试过这个，但它应该可以解决一些问题。