我有一个简单的循环链表，用于演示目的（我知道我应该使用智能指针，但这是内存和数据结构的教学练习）。
该过程的一部分也是为了演示递归，因此所有函数都是递归编写的。
当我从循环链表中释放内存时遇到了麻烦。
void CLL::clear() {
if (!rear) { return; }
clear(rear->next);
rear = nullptr;
}
void CLL::clear(Node*& curr) {
if (curr != rear) {
clear(curr->next);
}
delete curr;
curr = nullptr;
}
void CLL::clear() {
if (!rear) { return; }
clear(rear);
}
void CLL::clear(Node*& curr) {
if (curr->next != rear) { // continue recursion if we're not at the end
clear(curr->next);
}
delete curr;
curr = nullptr;
}
Breakpoint 1, CLL::clear (this=0x7fffffffdce8, curr=@0x55555556b6e8: 0x55555556b2b0) at CLL.cpp:36
36 if (curr != rear) {
(gdb) n
37 clear(curr->next);
(gdb)
Breakpoint 1, CLL::clear (this=0x7fffffffdce8, curr=@0x55555556b2b8: 0x55555556b6e0) at CLL.cpp:36
36 if (curr != rear) {
(gdb)
40 delete curr;
(gdb)
41 curr = nullptr;
(gdb)
42 }
(gdb)
CLL::clear (this=0x7fffffffdce8, curr=@0x55555556b6e8: 0x8954fb37e656c2a4) at CLL.cpp:40
40 delete curr;
(gdb)
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff78a53fe in __GI___libc_free (mem=0x8954fb37e656c2a4) at ./malloc/malloc.c:3368
3368 ./malloc/malloc.c: No such file or directory.
(gdb)
#include "CLL.h"
#include <iostream>
using std::cout, std::endl;
// [DE]CONSTRUCTORS
CLL::~CLL() {
clear();
}
// HELPER FUNCTIONS
void CLL::clear() {
if (!rear) { return; }
clear(rear->next);
rear = nullptr;
}
void CLL::clear(Node*& curr) {
if (curr != rear) {
clear(curr->next);
}
delete curr;
curr = nullptr;
}
void CLL::insert(int _data, size_t index) {
if (!rear) {
rear = new Node(_data);
rear->next = rear;
}
else {
insert(_data, index, rear->next);
}
}
void CLL::insert(int _data, size_t index, Node*& curr) {
// base case 1: insert after rear (this becomes the new rear)
if ((index == 1) and (curr == rear))
{
rear->next = new Node(_data, rear->next);
rear = rear->next;
}
// base case 2: insert before the rear
else if (index == 0) {
curr = new Node(_data, curr);
}
// recursive case
else {
insert(_data, index-1, curr->next);
}
}
void CLL::display() const {
display(rear->next);
cout << "->..." << endl;
}
void CLL::display(const Node* const & curr) const {
cout << curr->data;
if (curr != rear) {
cout << "->";
display(curr->next);
}
}
size_t CLL::size() const {
if (!rear) { return 0u; }
return size(rear->next);
}
size_t CLL::size(const Node* const & curr) const {
if (curr == rear) {
return 1;
}
else {
return 1 + size(curr->next);
}
}
#pragma once
#include <cstddef> //size_t
class CLL {
private:
struct Node {
int data;
Node* next;
Node(): data(0), next(nullptr) {}
Node(int _data): data(_data), next(nullptr) {}
Node(int _data, Node* _next):
data(_data), next(_next) {}
};
// HELPER FUNCTIONS
void clear();
// RECURSIVE FUNCTIONS
void clear(Node*&);
void insert(int, size_t, Node*&);
void display(const Node* const &) const;
size_t size(const Node* const &) const;
Node* rear;
public:
CLL(): rear(nullptr) {}
CLL(const CLL &) = delete; // don't copy (for now)
~CLL();
void insert(int, size_t);
void display() const;
size_t size() const;
};
#include "CLL.h"
#include <iostream>
#include <cstdlib> // rand(), srand(..)
#include <ctime> // time(..)
using std::cout, std::cerr, std::endl;
int main() {
CLL list;
srand(time(NULL));
// insert randomly in list
for (int n: {1,2}) {
size_t insert_index = rand() % (list.size() + 1);
// output info
cerr << "inserting " << n << "@" << insert_index;
if (insert_index == list.size()) {
cerr << " (rear)";
}
cerr << endl;
list.insert(n, insert_index);
list.display();
}
cout << '\n';
list.display();
cout << "The CLL has " << list.size() << " elements" << endl;
return 0;
}
我尝试更改数据量，但超出一个数据的任何内容似乎都会破坏代码。
我认为该错误与删除顺序有关，因为这是从原始解决方案到固定解决方案的唯一真正区别。我不确定是什么原因造成的。
虽然
rear使用
g++ -fsanitize=address ...$ ./a.out
inserting 1@0 (rear)
1->...
inserting 2@1 (rear)
1->2->...
1->2->...
The CLL has 2 elements
=================================================================
==2132753==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000038 at pc 0x5651fedd999c bp 0x7fff3f6e0970 sp 0x7fff3f6e0968
READ of size 8 at 0x502000000038 thread T0
#0 0x5651fedd999b in CLL::clear(CLL::Node*&) /tmp/CLL.cpp:24
#1 0x5651fedd98c9 in CLL::clear() /tmp/CLL.cpp:15
#2 0x5651fedd9851 in CLL::~CLL() /tmp/CLL.cpp:8
#3 0x5651fedd9680 in main /tmp/main.cpp:32
#4 0x7fd8e74456c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
#5 0x7fd8e7445784 in __libc_start_main_impl ../csu/libc-start.c:360
#6 0x5651fedd91c0 in _start (/tmp/a.out+0x21c0) (BuildId: a4b06b664799e1318f7f6a2da32ed21e49c613d4)
0x502000000038 is located 8 bytes inside of 16-byte region [0x502000000030,0x502000000040)
freed by thread T0 here:
#0 0x7fd8e7af55c8 in operator delete(void*, unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:164
#1 0x5651fedd99b4 in CLL::clear(CLL::Node*&) /tmp/CLL.cpp:24
#2 0x5651fedd997a in CLL::clear(CLL::Node*&) /tmp/CLL.cpp:21
#3 0x5651fedd98c9 in CLL::clear() /tmp/CLL.cpp:15
#4 0x5651fedd9851 in CLL::~CLL() /tmp/CLL.cpp:8
#5 0x5651fedd9680 in main /tmp/main.cpp:32
#6 0x7fd8e74456c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
previously allocated by thread T0 here:
#0 0x7fd8e7af46c8 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:95
#1 0x5651fedd9b69 in CLL::insert(int, unsigned long, CLL::Node*&) /tmp/CLL.cpp:42
#2 0x5651fedd9adb in CLL::insert(int, unsigned long) /tmp/CLL.cpp:34
#3 0x5651fedd95a8 in main /tmp/main.cpp:23
#4 0x7fd8e74456c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
SUMMARY: AddressSanitizer: heap-use-after-free /tmp/CLL.cpp:24 in CLL::clear(CLL::Node*&)
解决此问题的最佳方法是重写代码以避免递归（这对于当前的问题完全不合适）。