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
