链表：如何实现析构函数、复制构造函数和复制赋值运算符？

Question

这是我的 C++ 代码：

#include <iostream>

using namespace std;

typedef struct Node
{   
    int data;
    Node* next;
}Node;

class LinkedList
{
private:
    Node* first;
    Node* last;
public:
    LinkedList() {first = last = NULL;};
    LinkedList(int A[], int num);
    ~LinkedList();

    void Display();
    void Merge(LinkedList& b);
  
};

// Create Linked List using Array
LinkedList::LinkedList(int A[], int n)
{   
    Node* t = new Node;
    if (t == NULL)
    {
        cout << "Failed allocating memory!" << endl;
        exit(1);
    }
    t->data = A[0];
    t->next = NULL;
    first = last = t;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        if (t == NULL)
        {
            cout << "Failed allocating memory!" << endl;
            exit(1);
        }
        t->data = A[i];
        t->next = NULL;
        
        last->next = t;
        last = t;
    }
}

// Deleting all Node in Linked List
LinkedList::~LinkedList()
{
    Node* p = first;
    Node* tmp;

    while (p != NULL)
    {
        tmp = p;
        p = p->next;
        delete tmp;
    }
}

// Displaying Linked List
void LinkedList::Display()
{
    Node* tmp;

    for (tmp = first; tmp != NULL; tmp = tmp->next)
        cout << tmp->data << " ";
    cout << endl;    
}

// Merge two linked list
void LinkedList::Merge(LinkedList& b)
{
    // Store first pointer of Second Linked List
    Node* second = b.first;
    Node* third = NULL, *tmp = NULL;

    // We find first Node outside loop, smaller number, so Third pointer will store the first Node
    // Then, we can only use tmp pointer for repeating process inside While loop
    if (first->data < second->data)
    {
        third = tmp = first;
        first = first->next;
        tmp->next = NULL;
    }
    else
    {
        third = tmp = second;
        second = second->next;
        tmp->next = NULL;
    }

    // Use while loop for repeating process until First or Second hit NULL
    while (first != NULL && second != NULL)
    {
        // If first Node data is smaller than second Node data
        if (first->data < second->data)
        {
            tmp->next = first;
            tmp = first;
            first = first->next;
            tmp->next = NULL;
        }
        // If first Node data is greater than second Node data
        else
        {
            tmp->next = second;
            tmp = second;
            second = second->next;
            tmp->next = NULL;
        }
    }

    // Handle remaining Node that hasn't pointed by Last after while loop
    if (first != NULL)
        tmp->next = first;
    else
        tmp->next = second;

    // Change first to what Third pointing at, which is First Node
    first = third;    

    // Change last pointer from old first linked list to new last Node, after Merge
    Node* p = first;
    while (p->next != NULL)
    {
        p = p->next;
    }    
    last = p;
    
    // Destroy second linked list because every Node it's now connect with first linked list
    // This also prevent from Double free()
    b.last = NULL;
    b.first = NULL;
}

int main()
{
    int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
    int arr2[] = {2, 6, 10, 16, 18, 22, 24};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    
    LinkedList l1(arr1, size1);
    LinkedList l2(arr2, size2);

    l1.Display();
    l2.Display();
    
    // Merge two linked list, pass l2 as reference
    l1.Merge(l2);
    l1.Display();

    return 0;
}

我是 C++ 初学者，在这段代码中，我练习了如何合并两个链表。这实际上非常有效。我已经按排序顺序成功合并了两个链表。

但是，有人说我应该在 C++ 上遵循三原则。其中实现：析构函数、复制构造函数和复制赋值运算符.

我看过很多关于那个的视频。我确实理解这基本上是处理 Shallow Copy 尤其是当我们不希望两个不同的对象指向同一内存地址时。但是，对于我的问题是，我仍然不知道如何在 Class 上实现它，就像我上面的代码一样在链表上工作。

有人说，在我的 main() 中，这段代码：l1.Merge(l2); 在某种程度上是不正确的，因为我没有明确的复制构造函数。

如果你看一下我的 Merge() 函数，在最后一行，如果我不这样做： b.last = NULL; 和 b.first = NULL; ，这只会破坏第二个链表的指针，编译器给我警告：Double free() detected.

所以，我想我的问题是：

这段代码：l1.Merge(l2); 怎么可能与复制构造函数有关？
Double free() 是因为我没有执行三法则吗？如果是，如何解决？
如何根据我的代码写出三法则？何时或如何使用它们？
根据这个代码，有什么问题吗？如果我的程序只想合并链表，我还需要三原则吗？

谢谢。我希望有人能像我 10 岁一样向我解释。并希望有人能给我写一些代码。

Answer 1

此代码中应用了一些有问题的做法，并且还有一个错误。

首先，错误。当您创建一个列表时，它 new 包含它的所有节点并使用指针跟踪它们。当您将一个列表分配给另一个列表时，您实际上是在复制指针值。您现在不仅丢失了分配列表的节点（因为您覆盖了它们）并且发生了内存泄漏（因为现在没有指针指向分配的节点），您现在在两个不同的列表上也有相同的指针，指向相同的节点。当列表被销毁时，它们都尝试 delete 它们的节点，并且您最终释放了相同的内存两次。嗯。

这个错误的解决方案是实现赋值运算符。

然后，有问题的做法：

using namespace std; (Why is "using namespace std;" considered bad practice?)
您在构造函数主体中分配 LinkedList 的成员，而不是将值直接传递给初始化列表中它们的构造函数。 (What is this weird colon-member (" : ") syntax in the constructor?)
声明一个数组参数（int[]）就是声明一个指针。请注意它。
new不能returnNULL！检查它的 return 值是没有用的。如果它不能分配，它只会抛出一个异常。
NULL 是不合适的常量。您可以使用 nullptr，它是 NULL 的 C++ 等价物，但它是类型安全的。
使用 new 和 delete 进行手动内存管理很难做到正确（正如您自己发现的那样）。您可能有兴趣使用 std::unique_ptr 或 std::shared_ptr 来减轻负担。他们会发现这个错误。

现在，请：不要像用类写 C++ 那样写 C++。我知道您可能没有遇到我在这里介绍的所有功能，但无论如何您现在已经了解了它们:)

Answer 2

But, for my problem is, I still don't know how to Implement [Rule of Three] on a Class that working on a Linked List just like my code above.

您只需实现复制构造函数和复制赋值运算符来迭代输入列表，制作每个节点的副本并将它们插入到您的目标列表中。你已经有了一个有效的析构函数。对于复制赋值运算符，通常可以使用 copy-swap idiom to implement it using the copy constructor to avoid repeating yourself.

Someone said, in my main(), this code: l1.Merge(l2); is somehow incorrect because I don't have explicit Copy Constructor.

那你就错了。您的 Merge() 代码与复制构造函数没有任何关系。

And if you look at my Merge() function, in Last line, if I didn't to this: b.last = NULL; and b.first = NULL;, which simply destroy pointer of Second Linked list, the Compiler give me warning: Double free() detected.

正确。由于您正在 将节点从输入列表移动 到目标列表，因此您需要重置输入列表，使其不再指向移动的节点。否则，输入列表的析构函数将尝试释放它们，目标列表的析构函数也是如此。

How can this code: l1.Merge(l2); is have something to do with Copy Constructor?

与它没有任何关系。

Is Double free() happened because I don't implement the Rule of Three?

在您的特定示例中没有，因为您没有执行任何复制操作。但是，一般来说，不执行三规则会导致双重释放，是的。

How to write the Rule of Three based on my code?

查看下面的代码。

Do I still need the Rule of Three if my Program only want to Merge Linked List?

没有。仅当您想复制列表时。

话虽如此，这里是一个包含三法则的实现：

#include <iostream>
#include <utility>

struct Node
{
    int data;
    Node *next;
};

class LinkedList
{
private:
    Node *first;
    Node *last;
public:
    LinkedList();
    LinkedList(const LinkedList &src);
    LinkedList(int A[], int num);
    ~LinkedList();

    LinkedList& operator=(const LinkedList &rhs);

    void Display() const;
    void Merge(LinkedList &b);
};

// Create Linked List using default values
LinkedList::LinkedList()
    : first(NULL), last(NULL)
{
}

// Create Linked List using Array
LinkedList::LinkedList(int A[], int n)
    : first(NULL), last(NULL)
{
    Node **p = &first;

    for (int i = 0; i < n; ++i)
    {
        Node *t = new Node;
        t->data = A[i];
        t->next = NULL;

        *p = t;
        p = &(t->next);

        last = t;
    }
}

// Create Linked List by copying another Linked List
LinkedList::LinkedList(const LinkedList &src)
    : first(NULL), last(NULL)
{
    Node **p = &first;

    for (Node *tmp = src.first; tmp; tmp = tmp->next)
    {
        Node* t = new Node;
        t->data = tmp->data;
        t->next = NULL;

        *p = t;
        p = &(t->next);

        last = t;
    }
}

// Deleting all Node in Linked List
LinkedList::~LinkedList()
{
    Node *p = first;

    while (p)
    {
        Node *tmp = p;
        p = p->next;
        delete tmp;
    }
}

// Update Linked List by copying another Linked List
LinkedList& LinkedList::operator=(const LinkedList &rhs)
{
    if (&rhs != this)
    {
        LinkedList tmp(rhs);
        std::swap(tmp.first, first);
        std::swap(tmp.last, last);
    }
    return *this;
}

// Displaying Linked List
void LinkedList::Display() const
{
    for (Node *tmp = first; tmp; tmp = tmp->next)
        std::cout << tmp->data << " ";
    std::cout << std::endl;
}

// Merge two linked list
void LinkedList::Merge(LinkedList& b)
{
    if ((&b == this) || (!b.first))
        return;

    if (!first)
    {
        first = b.first; b.first = NULL;
        last = b.last; b.last = NULL;
        return;
    }

    // Store first pointer of Second Linked List
    Node *second = b.first;
    Node *third, **tmp = &third;

    // We find first Node outside loop, smaller number, so Third pointer will store the first Node
    // Then, we can only use tmp pointer for repeating process inside While loop
    // Use while loop for repeating process until First or Second hit NULL
    do
    {
        // If first Node data is smaller than second Node data
        if (first->data < second->data)
        {
            *tmp = first;
            tmp = &(first->next);
            first = first->next;
        }
        // If first Node data is greater than second Node data
        else
        {
            *tmp = second;
            tmp = &(second->next);
            second = second->next;
        }
        *tmp = NULL;
    }
    while (first && second);

    // Handle remaining Node that hasn't pointed by Last after while loop
    *tmp = (first) ? first : second;

    // Change first to what Third pointing at, which is First Node
    first = third;  

    // Change last pointer from old first linked list to new last Node, after Merge
    Node *p = first;
    while (p->next)
    {
        p = p->next;
    }   
    last = p;
    
    // Destroy second linked list because every Node it's now connect with first linked list
    // This also prevent from Double free()
    b.first = b.last = NULL;
}

int main()
{
    int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
    int arr2[] = {2, 6, 10, 16, 18, 22, 24};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    
    LinkedList l1(arr1, size1);
    LinkedList l2(arr2, size2);
    LinkedList l3(l1);
    LinkedList l4;

    l1.Display();
    l2.Display();
    l3.Display();
    l4.Display();
    
    // Merge two linked list, pass l2 as reference
    l3.Merge(l2);
    l4 = l3;

    l1.Display();
    l2.Display();
    l3.Display();
    l4.Display();

    return 0;
}

Demo

链表：如何实现析构函数、复制构造函数和复制赋值运算符？

Linked List: How to implement Destructor, Copy Constructor, and Copy Assignment Operator?

c++

linked-list

rule-of-three