HOWTO · C++
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
