时间戳

首页 > 解决方案 > 如何在 c++ 的析构函数中为合并的 LL 正确释放内存？

c++ - 如何在 c++ 的析构函数中为合并的 LL 正确释放内存？

问题描述

我创建了一个包含一些操作的链接列表类。

我正在尝试将两个链表合并在一起，如main函数所示。我能够成功地执行该操作并将其显示在屏幕上。

next不过，我怀疑在实现尾节点的指针时我可能做错了什么。当调用析构函数时，我打开调试器以查看到底发生了什么。它成功删除了所有节点，并显示old->next并随后head最终等于nullptr。我确保析构函数仅在空操作为 false for 时循环nullptr。

但是，由于某种原因，析构函数继续循环，程序给了我错误：

LinkedList(2000,0x1000d3dc0) malloc: 对象 0x1007239d0 的错误: 被释放的指针未被分配

我知道解决方案可能很明显，但我完全被大便了。析构函数适用于非合并列表。

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

class LinkedList{
public:
    Node* head;
public:
    LinkedList()
    {head = nullptr;}
    ~LinkedList()
    {while (!empty()) remove();}
    void addDataBack(int data);
    void display();
    void remove();
    bool empty() const
    {return head == nullptr;}
    void merge(Node* list1, Node* list2);
};

void LinkedList::addDataBack(int data){
    Node *p = new Node;
    Node *t;
    t = head;
    p->data = data;
    p->next = nullptr;
    if (!head){
        head = p;
    }
    else{
        t = head;
        while(t->next){
            t = t->next;
        }
        t->next = p;
    }
}

void LinkedList::display(){
    Node *t = head;
    while (t){
        cout << t->data << endl;
        t = t->next;
    }
}

void LinkedList::remove(){
    Node *old = head;
    head = old->next;
    delete old;
}

void LinkedList::insertNode(int index, int data){
    Node *node = new Node;
    int i = 0;
    Node *t = head;
    Node *p = nullptr;
    node->data= data;
    while ( t!= NULL){
        if (index == i){
            p->next = node;
            node->next = t;
            break;
        }
        p = t;
        t = t->next;
        i++;
    }
}

void LinkedList:: merge(Node *list1, Node *list2){
    Node* t = list1;
    head = list1;
    while (t->next) {
        t = t->next;
    }
    t->next = list2;
}

int main(int argc, const char * argv[]) {
    LinkedList list;
    LinkedList list2;
    list.addDataBack(8);
    list.addDataBack(3);
    list.addDataBack(7);
    list.addDataBack(12);
    list.addDataBack(9);
    list.insertNode(2, 25);
    list2.addDataBack(4);
    list2.addDataBack(10);
    LinkedList list3;
    list3.merge (list.head, list2.head);
    list.display();

    return 0;
}

标签： c++linked-list

解决方案

  • 代码无法编译，因为您在类定义中缺少插入函数原型。

  • 见 insertNode 函数；在该行p->next = node中，如果 index 为 0，则该行将间接指向一个空指针并引发异常。

  • 如果您提供的索引超出当前节点数 - 1，则insertNode 函数将泄漏内存
  • 如果当前列表为空，insertNode 函数会泄漏内存

这是它的外观。

void LinkedList::insertNode(int index, int data) 
{
  Node* newNode = new Node;
  newNode->data = data;

  //Wrap this up quick if the list is already empty. 
  if (head == nullptr)
  {
    head = newNode;
    return;
  }

  int i = 0;
  Node* current = head;
  Node* prev = nullptr;
  while (current != nullptr)
  {
    if (index == i)
    {
      newNode->next = current;

      if (prev)
        prev->next = newNode;

      return;
    }
    prev = current;
    current = current->next;
    i++;
  }
  //if (index >= i)

    //Either delete the new node, or throw an out of bounds exception.
    //Otherwise this will result in a memory leak. Personally, I think 
    //throwing the exception is correct.
    delete newNode;
}

这是主要问题：

您的合并函数有点令人困惑，因为您实际上是从两个列表创建一个新列表，但不是通过构造函数，而是简单地合并它们。这将意味着 list1 在功能上等同于 list3，但地址都是混合的。这意味着当我们退出主函数作用域时，您将从 list1 中删除内存，然后当它销毁 list2 时，它也会再次删除它们，而 list3 也会这样做（尽管在此之前它会崩溃）。

为什么不简单地让它取一个列表，然后将两者合并呢？

#include <iostream>
#include <string>
using namespace std;

class Node{
public:
    int data;
    Node* next;
    friend class LinkedList;
};
class LinkedList{
public:
    Node* head;
public:
    LinkedList()
    {head = nullptr;}
    ~LinkedList();
    void addDataBack(int data);
    void display();
    void remove();
    void insertNode(int index, int data);
    bool empty() const
    {return head == nullptr;}
    void merge(LinkedList& otherList);
};
LinkedList::~LinkedList()
{
  while (!empty())
    remove();
}
void LinkedList::addDataBack(int data){
    Node *p = new Node;
    Node *t;
    t = head;
    p->data = data;
    p->next = nullptr;
    if (!head){
        head = p;
    }
    else{
        t = head;
        while(t->next){
            t = t->next;
        }
        t->next = p;
    }
}
void LinkedList::display(){
    Node *t = head;
    while (t){
        cout << t->data << endl;
        t = t->next;
    }
}
void LinkedList::remove(){
    Node *old = head;
    head = old->next;

    delete old;
    old = nullptr;
}
    void LinkedList::insertNode(int index, int data) 
{
  Node* newNode = new Node;
  newNode->data = data;

  //Wrap this up quick if the list is already empty. 
  if (head == nullptr)
  {
    head = newNode;
    return;
  }

  int i = 0;
  Node* current = head;
  Node* prev = nullptr;
  while (current != nullptr)
  {
    if (index == i)
    {
      newNode->next = current;

      if (prev)
        prev->next = newNode;

      return;
    }
    prev = current;
    current = current->next;
    i++;
  }
  //if (index >= i)

    //Either delete the new node, or throw an out of bounds exception.
    //Otherwise this will result in a memory leak. Personally, I think 
    //throwing the exception is correct.
    delete newNode;

}
void LinkedList:: merge(LinkedList& otherList){
    Node* thisTail = head;
    while (thisTail->next) {
        thisTail = thisTail->next;
    }

    thisTail->next = otherList.head;
    otherList.head = nullptr;
}

int main(int argc, const char * argv[]) {
    LinkedList list;
    LinkedList list2;
    list.addDataBack(8);
    list.addDataBack(3);
    list.addDataBack(7);
    list.addDataBack(12);
    list.addDataBack(9);
    list.insertNode(2, 25);
    list2.addDataBack(4);
    list2.addDataBack(10);
    list.merge(list2);
    list.display();
    list2.display();
    cout << "list2 is " << (list2.empty() ? "empty." : "not empty");

    return 0;
}

最后注：

尽量避免使用单字母变量，除非它们用于迭代，否则（尤其是链表和指针杂耍）很难维护、调试和获得帮助。

推荐阅读