迹忆客 专注技术分享

这篇简短的文章是关于具有深拷贝构造函数的基于 C++ 的链表实现。

C++ 中的复制构造函数

调用复制构造函数以使用同一类的另一个对象初始化对象。复制构造函数在多种情况下被调用，例如：

• 当使用另一个对象复制一个对象时。
• 当对象作为函数的值返回时。
• 当对象作为值传递给函数时。

在每个类中，总会有一个默认的拷贝构造函数，但它不执行深拷贝，而是执行浅拷贝。只有指针的地址被浅拷贝复制，并且两个对象（即调用者和传递的对象）都指向同一个内存。

相反，在深拷贝中，数据成员的值被复制到目标对象数据成员。

C++ 中的链表

链表数据结构以可以动态增长的数据节点的形式存储数据。它不需要连续的内存，因此可以有效地存储在内存中的任何位置。

C++ 中的链表实现

让我们开始实现链表。首先，我们需要创建一个类来获取数据节点：

template <class T >
class Node
{
public:
    T info;
    Node<T>* next;

    Node ( ){
        next = 0;
    }
    Node ( T val ){
        info = val;
        next = 0;
    }
};

Node 类有两个成员——一个用于存储数据（即 info），另一个是指向该类本身的指针，用于存储下一个节点的地址。该类被模板化，以便可以创建任何数据类型的列表。

上面的实现提供了两个构造函数。第一个是默认构造函数，另一个是参数化的。

我们来看一下链表的模板类：

template <class T>
class LSLL
{
private:
    Node<T> * head;
public:
    LSLL ( ){
        head = 0;
    }
};

LSLL 类只有一个指向 Node 类的指针，用于保存链表第一个节点的地址。

为了向用户提供将一个链表对象深度复制到另一个的功能，我们需要提供一个用户定义的复制构造函数实现，如下所示：

LSLL(LSLL& PassedObj)
{
    if (PassedObj.head == NULL) {
        head = NULL;
    }
    else {
        //copy all nodes of PassedObj to the caller object
        //attach first node to the head of the caller object
        Node<T>* newNode = new Node<T>();
        newNode->info = PassedObj.head->info;
        newNode->next = NULL;
        head = newNode;

        //Now deep-copy all the remaining nodes of the Passed linked list object
        Node<T>* PassedItr = PassedObj.head->next;
        Node<T>* CallerItr = head;
        while (PassedItr != NULL)
        {
            CallerItr->next = new Node<T>();
            CallerItr->next->info = PassedItr->info;
            CallerItr->next->next = NULL;
            CallerItr = CallerItr->next; //move to newly added node
            PassedItr = PassedItr->next; //move one node further
        }
    }
}

上面的代码段创建了传递对象的第一个节点的深层副本，并将其附加到调用者列表对象的 head。之后，传递对象的所有剩余节点都被深度复制并附加到调用者链表节点。

让我们对整个实现有一个认知的看法。

#include <iostream>
using namespace std;

template <class T >
class Node
{
public:
    T info;
    Node<T>* next;

    Node()
    {
        next = NULL;
    }
    Node(T val)
    {
        info = val;
        next = NULL;
    }
};

template <class T>
class LSLL
{
private:
    Node<T>* head;
public:
    LSLL()
    {
        head = NULL;
    }
    LSLL(LSLL& PassedObj)
    {

        if (PassedObj.head == NULL) {
            head = NULL;
        }
        else {
            //copy all nodes of PassedObj to the caller object
            //attach first node to the head of the caller object
            Node<T>* newNode = new Node<T>();
            newNode->info = PassedObj.head->info;
            newNode->next = NULL;
            head = newNode;

            //Now deep-copy all the remaining nodes of the Passed linked list object
            Node<T>* PassedItr = PassedObj.head->next;
            Node<T>* CallerItr = head;
            while (PassedItr != NULL)
            {
                CallerItr->next = new Node<T>();
                CallerItr->next->info = PassedItr->info;
                CallerItr->next->next = NULL;
                CallerItr = CallerItr->next; //move to newly added node
                PassedItr = PassedItr->next; //move one node further
            }
        }
    }
    void insertAtHead(T val)
    {
        Node<T>* x = new Node<T>(val);
        x->next = head;
        head = x;
    }
    void displayAll()
    {
        Node<T>* x = head;
        {
            while (x != 0)
            {
                cout << x->info << endl;
                x = x->next;
            }
        }
    }
    int isEmpty()
    {
        if (head == 0)
            return 1;
        return 0;
    }
    void insetAtTail(T val)
    {
        Node<T>* x = head;
        if (isEmpty())
        {
            insertAtHead(val);
            return;
        }

        while (x->next != 0)
        {
            x = x->next;
        }
        x->next = new Node<T>(val);
    }
    void insertAfter(T key, T val)
    {
        if (isEmpty())
            return;

        Node<T>* x = head;
        while (x != 0 && x->info == key)
            x = x->next;

        if (!x)
            return;

        Node<T>* temp = new Node<T>(val);

        temp->next = x->next;
        x->next = x;
    }
};
int main()
{
    LSLL<int> list;
    list.insertAtHead(200);
    list.insertAtHead(100);
    list.insetAtTail(300);
    list.displayAll();

    LSLL<int> list2(list);
    cout << "List2: " << endl;
    list2.displayAll();
    return 0;
}

主驱动代码首先创建一个 list 对象，在其中插入三个节点，然后调用 displayAll 函数。之后，它创建一个新的链表对象 list2 并以 list 作为参数调用其参数化的复制构造函数。

请注意，list2 对象是调用者对象，而 list 是传递对象。

输出：

100
200
300
List2:
100
200
300