我创建了bucket来插入数据，除了删除所有节点外，一切都很好。如果我使用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)
最大的问题是实际上没有链表。您有一个节点结构，并试图将节点串在一起，但缺少一个实际的类来为您维护数据结构。
当然，当您尝试删除数组时，只会删除每个索引的第一个节点。您没有任何代码可以处理删除整个列表。
下面是一个链表类的简短示例。它缺少了相当多的功能，但它有足够的功能来展示一些好的实践以及它是如何工作的。
#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是一个类，它表示一个单独链接的整数列表。数据成员m_head和m_tail分别表示列表的开始和结束。m_tail是可选的，但我发现如果你知道列表的末尾，它会让生活变得更轻松。当从中间删除时，双链接列表也会让你的生活变得容易得多，而且写起来也没有那么难。
该列表由节点组成，其中一个节点指向下一个节点的位置。你已经有这个了。
解决问题的关键函数是析构函数~IntList()。仔细检查该函数。请注意它是如何在整个列表中移动的，在移动过程中删除每个节点这就是你所缺少的那个，以及完成所有这些的实际列表类。
因为每个IntList对象都有自己的内存，所以我只需要删除动态数组。当数组破坏自身时，它将调用每个元素的析构函数。这意味着，在每个IntList元素清理完之后，阵列内存就会被删除。没有泄漏，也没有双重释放。
最有助于理解数据结构的是绘制数据结构。
我提到的好的实践是五规则函数(0/3/5规则(和复制交换习惯用法。规则5是必要的，因为链表类正在管理动态资源。主要功能是充分利用复制构造函数。请注意，数组包含列表的副本。如果我不想要副本，我将不得不将数组声明为双指针，并为IntLists分配一个指针数组。IntList将在主函数结束时自行清理。
复制交换习惯用法只会让生活变得更轻松，并减少代码重复。