C++ 中链表的复制构造函数

Muhammad Husnain 2023年1月30日 2022年7月18日
  1. C++ 中的复制构造函数
  2. C++ 中的链表
  3. C++ 中的链表实现
C++ 中链表的复制构造函数

这篇简短的文章是关于具有深拷贝构造函数的基于 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
Muhammad Husnain avatar Muhammad Husnain avatar

Husnain is a professional Software Engineer and a researcher who loves to learn, build, write, and teach. Having worked various jobs in the IT industry, he especially enjoys finding ways to express complex ideas in simple ways through his content. In his free time, Husnain unwinds by thinking about tech fiction to solve problems around him.

LinkedIn

相关文章 - C++ Constructor