C++删除链表数组

Question

我创建了存储桶来插入我的数据，除了删除所有节点外，一切正常。如果我使用 delete[] container 删除我的容器，那么只会删除我所有链表的第一个节点。我认为我所做的是合乎逻辑的，但它行不通。能告诉我为什么吗？（只关注函数的最后一个循环，其他代码供参考。）

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

struct bucket{
    int val;
    bucket* next;
};


int countDigit(int max){
    int digits = 0;
    while(max>0){
        max = max/10;
        digits++;
    }
    return digits;
}

int findMax(int* arr, int l, int r){
    int max = arr[l];
    for(int i = l+1; i<=r; i++){
        if(max<arr[i]){
            max = arr[i];
        }
    }
    return max;
}

void createBucket(int* arr, int l, int r){
    int max = findMax(arr, l, r);
    int digits = findDigit(max);
    int divide = pow(10, digits-1);
    int maxPos = max/divide;
    int pos;//position of elements in the container
    bucket* container = new bucket[maxPos+1];
    bucket* cursor;
    //copying elements to their respective buckets
    for(int i=l; i<=r; i++){

        pos = arr[i]/divide;

        if(container[pos].val == 0){
            container[pos].val = arr[i];
            container[pos].next = NULL;
        }
        else{
            bucket* node = new bucket;
            cursor = &container[pos];
            node->val = arr[i];
            while(cursor->next!=NULL){
                cursor = cursor->next;
            }
            cursor->next = node;
            node->next = NULL;
        }
    }
    //copying the elements from the buckets to their respective position
    int j = 0;
    for(int i = 0; i<maxPos+1; i++){
        cursor = &container[i]; 
        while(cursor!=NULL && cursor->val!=0){
            arr[j] = cursor->val;
            cursor = cursor->next;
            j++;
        }
    }
    //deleting all nodes
    bucket* tmp;
    for(int i= 0; i<maxPos+1; i++){
        cursor = &container[i];
        while(cursor!=NULL){
            tmp = cursor;
            cursor = cursor->next;
            delete tmp;
        }
    }
}

报错如下：

double free or corruption (out)
Aborted (core dumped)

Answer 1

最大的问题是你实际上没有链表。你有一个节点结构，你正试图将节点串在一起，但你缺少一个实际的 class 来为你维护你的数据结构。

当然，当您尝试删除数组时，只会删除每个索引的第一个节点。您有零代码来处理删除整个列表。

下面是一个链表的简短示例 class。它缺少相当多的功能，但足以展示一些良好的实践及其工作原理。

#include <iostream>

class IntList {
 public:
  IntList() = default;
  ~IntList();                           // Rule of 5
  IntList(const IntList& other);        // Rule of 5
  IntList(IntList&& other) noexcept;    // Rule of 5
  IntList& operator=(IntList other);    // Rule of 5
  IntList& operator=(IntList&& other);  // Rule of 5
  void push_back(int value);
  void print() const;  // Only here for ease of demo

  friend void swap(IntList& lhs, IntList& rhs);

 private:
  struct Node {
    int m_key = 0;
    Node* m_next = nullptr;

    Node(int key) : m_key(key) {}
  };

  Node* m_head = nullptr;
  Node* m_tail = nullptr;
};

IntList::~IntList() {
  while (m_head) {
    Node* tmp = m_head;
    m_head = m_head->m_next;
    delete tmp;
  }

  m_head = nullptr;
  m_tail = nullptr;
}

IntList::IntList(const IntList& other) {
  if (other.m_head) {
    // Set up first node
    this->m_head = new Node(other.m_head->m_key);
    m_tail = m_head;
    Node* otherWalker = other.m_head->m_next;
    while (otherWalker) {  // Handles the rest of the nodes
      m_tail->m_next = new Node(otherWalker->m_key);
      m_tail = m_tail->m_next;
      otherWalker = otherWalker->m_next;
    }
  }
}

IntList::IntList(IntList&& other) noexcept : IntList() { swap(*this, other); }

IntList& IntList::operator=(IntList other) {
  swap(*this, other);

  return *this;
}

IntList& IntList::operator=(IntList&& other) {
  swap(*this, other);

  return *this;
}

void IntList::push_back(int value) {
  Node* tmp = new Node(value);
  if (!m_head) {
    m_head = tmp;
    m_tail = m_head;
    return;
  }

  m_tail->m_next = tmp;
  m_tail = tmp;

  return;
}

void IntList::print() const {
  Node* walker = m_head;

  if (!walker) {
    std::cout << "Empty List.\n";
  }

  while (walker) {
    std::cout << walker->m_key << (walker->m_next ? ' ' : '\n');
    walker = walker->m_next;
  }
}

void swap(IntList& lhs, IntList& rhs) {
  using std::swap;

  swap(lhs.m_head, rhs.m_head);
  swap(lhs.m_tail, lhs.m_tail);
}

int main() {
  IntList one;
  one.push_back(42);
  one.push_back(55);

  IntList two(one);

  IntList three;
  three.push_back(350);
  three.push_back(240);
  three.push_back(609);

  IntList four(three);
  four.push_back(666);


  // While I can appreciate learning, there's no reason for a dynamically 
  // allocated array. SO trope of use a vector instead applies here. NOTE: a 
  // vector would not have helped with your code, it just takes away your 
  // responsibility to delete the array later. You'd still leak memory.
  IntList* const container = new IntList[4];
  container[0] = one;
  container[1] = two;
  container[2] = three;
  container[3] = four;

  for (int i = 0; i < 4; ++i) {
    container[i].print();
  }

  delete[] container;
}

IntList 是一个 class，表示整数的单链表。数据成员 m_head 和 m_tail 分别表示列表的开头和结尾。 m_tail 是可选的，但我发现如果您知道列表的结尾位置，它会让生活变得更轻松。当涉及到从中间擦除时，双向链表也让你的生活变得更容易，而且它们也没有那么难写。

列表由节点组成，其中一个节点指向下一个节点的位置。你已经知道了。

解决您问题的关键函数是析构函数，~IntList()。仔细检查该功能。注意它是如何在你的整个列表中移动的，随着它的移动删除每个节点。 这就是您所缺少的。 那，以及完成所有这些的实际列表 class。

因为每个IntList对象都有自己的内存，所以我只需要删除动态数组。当数组销毁自身时，它会调用每个元素的析构函数。这意味着在每个 IntList 元素自己清理完之后，数组内存就会被删除。没有泄漏，也没有双重释放。

有助于理解数据结构的最重要的事情就是把它画出来。

我提到的良好做法是 5 函数法则（Rule of 0/3/5）和复制交换惯用语。 5 的规则是必要的，因为链表 class 正在管理动态资源。主要功能是充分利用复制构造函数。请注意，该数组包含列表的副本。如果我不想要副本，我必须将数组声明为双指针并分配一个指向 IntLists 的指针数组。 IntList 将在主函数结束时自行清理。

copy-swap 惯用语只会让生活更轻松并减少代码重复。

C++删除链表数组

Deleting an array of linked list in c++

c++

singly-linked-list