我创建了一个带有一些操作的链接列表类。
我正在尝试将两个链表合并在一起，如main函数所示。我能够成功地完成该操作并将其显示在屏幕上。
不过，我怀疑我在实现尾节点的next指针时可能做错了什么。调用析构函数时，我打开调试器以查看到底发生了什么。它成功删除了所有节点，并显示old->next和随后的head最终等于nullptr。我确保析构函数仅在空操作为 false 时才循环nullptr.
但是，由于某种原因，析构函数继续循环，程序给了我错误：
链接列表(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;
}
-
代码无法编译，因为类定义中缺少插入函数原型。
-
参见 insertNode 函数;在行
p->next = node中，if index 为 0，则此行将间接一个空指针并引发异常。 - 如果提供超出当前节点数的索引，则 insertNode 函数将泄漏内存- 1
- 如果当前列表为空，插入节点函数将泄漏内存
这是它应该的样子。
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;
}
结语：
尽量避免使用单个字母变量，除非它们用于迭代，否则(尤其是对于链表和指针杂耍(很难维护、调试和接收帮助。
但是
，由于某种原因，析构函数继续循环并且 [...]
我对此表示怀疑，但如果您没有足够仔细地观察(特别是观察this指针的值(，这似乎正在发生。在我看来，list3的析构函数将完成循环，此时list2的析构函数将开始(以与构造相反的顺序销毁(。如果您错过了这种转换，那么看起来析构函数很可能在继续，而实际上它正在第二次调用。
由于您从未更改过list2.head，它仍然指向已合并到list3中的一个节点。当list2的析构函数启动时，head仍然指向刚刚被list3的析构函数删除的节点之一。尝试删除已删除的节点是一个错误。