对于我正在上的课，我们正在用c ++实现我们自己的单链接列表，以便我们可以更好地理解数据结构的功能。当前，我已经完成了通过所有测试用例的代码，但是运行valgrind时，我仍然发现内存泄漏。
我已经实现了应将每个Node对象从列表中删除的代码，但显然我做错了。 我对丢失的内存管理不了解什么？
我的代码通过了一些基本的测试，没有内存泄漏，但是当使用我的教授提供的更严格的测试用例时，valgrind会出现主要的内存泄漏问题。
这是我的链表类别：
template<typename T>
class LinkedList: public LinkedListInterface<T> {
private:
struct Node {
Node(T val) {
value = val;
next = NULL;
}
T value;
Node *next;
};
Node *head;
public:
LinkedList() {
head = NULL;
}
~LinkedList() {
}
void insertHead(T value) {
cout << "In insertHead function" << endl;
Node *newNode = new Node(value);
if(head == NULL){
head = newNode;
}
else {
newNode->next = head;
head = newNode;
}
}
//don't allow duplicate values in the list. Implement later.
void insertTail(T value) {
cout << "In insertTail function" << endl;
Node *newNode = new Node(value);
if(head == NULL) {
head = newNode;
}
else {
//find last node
Node *fakeIterator = head;
//while what fake iterator is pointing to is not NULL then make it point to the next pointer.
while (fakeIterator->next != NULL) {
fakeIterator = fakeIterator->next;
}
//set that node's next pointer to newNode
fakeIterator->next = newNode;
}
}
void insertAfter(T value, T insertionNode) {
cout << "In insertAfter function" << endl;
Node *fakeIterator = head;
while(fakeIterator != NULL) {
if (fakeIterator->value == insertionNode) {
Node *newNode = new Node(value);
newNode->next = fakeIterator->next;
fakeIterator->next = newNode;
break;
}
fakeIterator = fakeIterator->next;
}
}
string toString() {
cout << "In toString function" << endl;
stringstream ss;
Node *fakeIterator = head;
while (fakeIterator != NULL) {
if (fakeIterator->next == NULL)
ss << fakeIterator->value;
else
ss << fakeIterator->value << ", ";
fakeIterator = fakeIterator->next;
}
return ss.str();
}
void remove(T value) {
cout << "In remove function" << endl;
if (head != NULL) {
Node *fakeIterator = head;
if(head->value == value) {
Node *nodeToDelete = head;//new Node(value);
// nodeToDelete = head;
head = head->next;
delete nodeToDelete;
}
else {
while(fakeIterator->next != NULL) {
//if the value of the node after this one equals the value
if ( (fakeIterator->next)->value == value) {
//make a temp node to store the node being destroyed
Node *nodeToDelete = fakeIterator->next;
//change "next" to point to the item after the one being deleted
fakeIterator->next = fakeIterator->next->next;
//delete the node
delete nodeToDelete;
break;
}
fakeIterator = fakeIterator->next;
}
}
}
}
void clear() {
cout << "In clear function" << endl;
while (head != NULL) {
remove(head->value);
}
}
T at(int index) {
cout << "In at function" << endl;
Node *fakeIterator = head;
if (head == NULL) {
throw out_of_range("list is empty");
}
for (int i = 0; i < index ; i++) {
cout << "2" << endl;
if (fakeIterator->next == NULL) {
cout << "3" << endl;
throw out_of_range("index does not exist");
break;
}
fakeIterator = fakeIterator->next;
cout << "4" << endl;
}
return fakeIterator->value;
}
int size() {
cout << "In size function" << endl;
int sizeOfList = 0;
Node *fakeIterator = head;
while (fakeIterator != NULL) {
if (fakeIterator->next == NULL)
return sizeOfList;
else
sizeOfList++;
fakeIterator = fakeIterator->next;
}
}
};
这里是valgrind输出：
==14052== Process terminating with default action of signal 2 (SIGINT)
==14052== at 0x57BFFE0: __read_nocancel (in /lib64/libc-2.17.so)
==14052== by 0x574CB83: _IO_file_underflow@@GLIBC_2.2.5 (in /lib64/libc-2.17.so)
==14052== by 0x574DD51: _IO_default_uflow (in /lib64/libc-2.17.so)
==14052== by 0x5748729: getchar (in /lib64/libc-2.17.so)
==14052== by 0x4024C1: main (main.cpp:88)
==14052==
==14052== HEAP SUMMARY:
==14052== in use at exit: 16,468 bytes in 696 blocks
==14052== total heap usage: 2,924 allocs, 2,228 frees, 523,457 bytes allocated
==14052==
==14052== 96 (16 direct, 80 indirect) bytes in 1 blocks are definitely lost in loss record 10 of 18
==14052== at 0x4C29203: operator new(unsigned long) (vg_replace_malloc.c:334)
==14052== by 0x40442F: LinkedList<int>::insertHead(int) (LinkedList.h:58)
==14052== by 0x4034A0: void parse_instruction<int>(std::string, std::basic_ofstream<char, std::char_traits<char> >&, LinkedList<int>*) (main.cpp:101)
==14052== by 0x4023AC: main (main.cpp:67)
==14052==
==14052== 585 (16 direct, 569 indirect) bytes in 1 blocks are definitely lost in loss record 15 of 18
==14052== at 0x4C29203: operator new(unsigned long) (vg_replace_malloc.c:334)
==14052== by 0x403BEB: LinkedList<std::string>::insertHead(std::string) (LinkedList.h:58)
==14052== by 0x402C84: void parse_instruction<std::string>(std::string, std::basic_ofstream<char, std::char_traits<char> >&, LinkedList<std::string>*) (main.cpp:101)
==14052== by 0x402371: main (main.cpp:64)
==14052==
==14052== 15,528 (16 direct, 15,512 indirect) bytes in 1 blocks are definitely lost in loss record 18 of 18
==14052== at 0x4C29203: operator new(unsigned long) (vg_replace_malloc.c:334)
==14052== by 0x403DE3: LinkedList<std::string>::insertAfter(std::string, std::string) (LinkedList.h:94)
==14052== by 0x402DF6: void parse_instruction<std::string>(std::string, std::basic_ofstream<char, std::char_traits<char> >&, LinkedList<std::string>*) (main.cpp:111)
==14052== by 0x402371: main (main.cpp:64)
==14052==
==14052== LEAK SUMMARY:
==14052== definitely lost: 48 bytes in 3 blocks
==14052== indirectly lost: 16,161 bytes in 687 blocks
==14052== possibly lost: 0 bytes in 0 blocks
==14052== still reachable: 259 bytes in 6 blocks
==14052== of which reachable via heuristic:
==14052== stdstring : 259 bytes in 6 blocks
==14052== suppressed: 0 bytes in 0 blocks
==14052== Reachable blocks (those to which a pointer was found) are not shown.
==14052== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==14052==
==14052== For counts of detected and suppressed errors, rerun with: -v
==14052== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
首先，我想鼓励您参加有关数据结构的培训，我认为这是学习编程的最佳方法，从指针和内存到分治算法和多线程应用程序。
现在，我看到您的代码不严格遵循Stackoverflow Minimum Reproducible Example guidelines，因为它包含与泄漏无关的方法，例如'at'，'toString'和'size'，并且没有给出可能的情况用于再现您的valgrind输出。我建议您谨慎地遵循它们，否则您将来可能会赚到暴票。就我而言，我将利用它来尝试帮助您进一步改善LinkedList的实现。
我看到的主要问题是LinkedList析构函数不执行任何操作（仅释放自身使用的内存，而不释放其节点使用的内存），因此，如果您的程序在添加一个元素后结束，请说：
int main() {
auto l = new LinkedList<int>();
l->insertHead(1);
// remove(1);
delete l;
}
对应于1个节点（磁头）的内存将泄漏。我建议的实现是：
~LinkedList() {
while (head != NULL) {
Node *nodeToDelete = head;
head = head->next;
delete nodeToDelete;
}
}
如果您在创建的每个LinkedList上调用delete，或者如果您准备好了，则可以使用智能指针，当它们超出范围时，可以使用智能指针在您的LinkedList上调用delete，就像您没有使用过一样。指针。但是，使用它们，如果没有析构函数无法正确释放每个LinkedList节点，也会导致泄漏。希望对您有所帮助，下面我给您其他建议，以备您需要了解更多信息，并且有兴趣使所有LinkedList方法能够像您的教授所期望的那样工作。祝你好运。
另一方面，似乎您的clear方法只是删除了head，我将其与析构函数类似：
void clear() {
cout << "In clear function" << endl;
while (head != NULL) {
Node *nodeToDelete = head;
head = head->next;
delete nodeToDelete;
}
}
最后，当您的size方法不为null时，它似乎不计算头部。我可以简化为：
int size() {
cout << "In size function" << endl;
int sizeOfList = 0;
Node *fakeIterator = head;
while (fakeIterator != NULL) {
sizeOfList++;
fakeIterator = fakeIterator->next;
}
}
#include <memory>
int main() {
auto l = make_unique<LinkedList<int>>();
l->insertHead(1);
}
Valgrind输出：
==3288== Memcheck, a memory error detector
==3288== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3288== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3288== Command: ./run
==3288==
In insertHead function
==3288==
==3288== HEAP SUMMARY:
==3288== in use at exit: 0 bytes in 0 blocks
==3288== total heap usage: 4 allocs, 4 frees, 73,760 bytes allocated
==3288==
==3288== All heap blocks were freed -- no leaks are possible
==3288==
==3288== For counts of detected and suppressed errors, rerun with: -v
==3288== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)