c++ - "Aborted (core dumped)"队列类dequeue方法出错

Question

这个队列类的 dequeue 方法不能正常工作，我不确定为什么。当我运行它时，它显示“* `./a.out' 中的错误:双重释放或损坏(fasttop):0x00000000018dfe50 *”，然后是回溯，然后是“中止(核心转储)” .

起初我是直接删除底部节点，但我认为这可能是问题所以我改用另一种方式删除它们。

这是出列方法:

int Queue::dequeue() {
  if (isEmpty()) {
    cout << "ERROR: Can't dequeue from empty Queue"<< endl;
    return -1;
  } else {
    Node* n = top;
    if (n == NULL){
      bottom = top;
      return 0;
    }
    if (n->next == NULL){
      delete n;
      bottom = top;
      return 0;
    }
    while(n->next->next != NULL){
      n = n->next;
    }
    bottom = n;
    n = n->next;
    delete n;
    return 0;
  }
}

这是整个文件:

  #include <iostream>
  using namespace std;

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

  class Queue {
  public:
      Queue(); //constructor
      ~Queue(); //destructor
      void enqueue(int d); //enqueues node onto top of Queue
      int dequeue(); //dequeues bottom node off of Queue -- returns integer dequeued
      bool isEmpty(); //checks if Queue is empty
      void print(); //print contents of Queue from top to bottom

  private:
      Node* top; //points to top node in Queue
      Node* bottom; //points to bottom node in Queue
  };

  Queue::Queue() {
      top = NULL;
      bottom = NULL;
  }

  Queue::~Queue() {
    while (!isEmpty())
      dequeue();
  }

  void Queue::enqueue(int d) {
    Node* temp = new Node;
    temp->data = d;

    temp->next = top;
    top = temp;

    if (temp->next == NULL){
      delete bottom;
      bottom = temp;
    }
  }

  int Queue::dequeue() {
    if (isEmpty()) {
      cout << "ERROR: Can't dequeue from empty Queue"<< endl;
      return -1; //error
    } else {
      Node* n = top;
      if (n == NULL){
        bottom = top;
        return 0;
      }
      if (n->next == NULL){
        delete n;
        bottom = top;
        return 0;
      }
      while(n->next->next != NULL){
        n = n->next;
      }
      bottom = n;
      n = n->next;
      delete n;
      return 0;
    }
  }

  bool Queue::isEmpty() {
    return (top==NULL);
  }

  //Print Queue from top to bottom
  void Queue::print(){
    Node* n = top;
    while(n != NULL){
      cout << n->data << endl;
      n = n->next;
    }
    cout << endl;
  }

  int main(){
      Queue* s = new Queue();
      s->print();
      s->enqueue(20);
      s->enqueue(30);
      s->print();
      s->enqueue(40);
      s->enqueue(12);
      s->print();
      s->dequeue();
      s->print();
      s->dequeue();
      s->print();
      s->dequeue();
      delete s;

      return 0;
  }

Answer 1

每当你删除一个节点时，你需要更新所有指向被删除节点的指针。您需要在两个地方执行此操作。

首先，在n->next == NULL 的情况下，Queue 只有一个节点。在你调用delete n之后，top仍然指向这个现在删除的节点，你需要更新top(到NULL或nullptr ) 在改变 bottom 的值之前。

在最后一种情况下，列表中有多个节点，您删除了最后一个节点，但前一个节点的 next 指针仍然指向它。在n = n->next表达式之后，需要设置bottom->next指向现在n->next的节点指向(由于 n 是 Queue 中的最后一个节点，因此为 NULL)。