Kopieren den Konstruktor der verketteten Liste in C++
In diesem kurzen Artikel geht es um die C++-basierte Implementierung der Linked-List mit einem Deep-Copy-Konstruktor.
Kopieren Sie den Konstruktor in C++
Ein Kopierkonstruktor wird aufgerufen, um ein Objekt mit einem anderen Objekt derselben Klasse zu initialisieren. Der Kopierkonstruktor wird in mehreren Situationen aufgerufen, z. B.:
- Wenn ein Objekt mit einem anderen Objekt kopiert wird.
- Wenn das Objekt als Wert von der Funktion zurückgegeben wird.
- Wenn ein Objekt als Wert an eine Funktion übergeben wird.
In jeder Klasse gibt es immer einen Standardkopierkonstruktor, der jedoch keine tiefe Kopie, sondern eine flache Kopie durchführt. Nur die Adresse des Zeigers wird mit einer flachen Kopie kopiert, und beide Objekte (d. h. aufrufende und übergebene Objekte) zeigen auf denselben Speicher.
Umgekehrt werden beim Deep Copy die Werte der Datenelemente in die Datenelemente des Zielobjekts kopiert.
Verkettete Liste in C++
Die Datenstruktur der verknüpften Liste speichert Daten in Form von Datenknoten, die dynamisch wachsen können. Es erfordert keinen zusammenhängenden Speicher, sodass es überall im Speicher effizient gespeichert werden kann.
Linked-List-Implementierung in C++
Beginnen wir mit der Implementierung der verknüpften Liste. Zuerst müssen wir eine Klasse zum Abrufen von Datenknoten erstellen:
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = 0; }
Node(T val) {
info = val;
next = 0;
}
};
Die Klasse Node hat zwei Mitglieder – eines zum Speichern von Daten (d. h. info) und das andere ist der Zeiger auf die Klasse selbst zum Speichern der Adresse des nächsten Knotens. Die Klasse wird mit Vorlagen erstellt, sodass Listen mit beliebigen Datentypen erstellt werden können.
Die obige Implementierung stellt zwei Konstruktoren bereit. Der erste ist der Standardkonstruktor und der andere ist parametrisiert.
Schauen wir uns die Vorlagenklasse für die verknüpfte Liste an:
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
};
Die Klasse LSLL hat nur einen Zeiger auf die Klasse Node, die verwendet wird, um die Adresse des ersten Knotens der verknüpften Liste zu halten.
Um dem Benutzer die Funktionalität zum tiefen Kopieren eines verknüpften Listenobjekts in ein anderes bereitzustellen, müssen wir eine benutzerdefinierte Kopierkonstruktorimplementierung wie unten angegeben bereitstellen:
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
}
}
}
Das obige Codesegment erstellt eine tiefe Kopie des ersten Knotens des übergebenen Objekts und hängt sie an den Kopf des Anruferlistenobjekts an. Danach werden alle verbleibenden Knoten des übergebenen Objekts tief kopiert und an den Knoten der verknüpften Anruferliste angehängt.
Lassen Sie uns einen kognitiven Blick auf die gesamte Implementierung werfen:
#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;
}
Der Haupttreibercode erstellt zuerst ein list-Objekt, fügt drei Knoten darin ein und ruft die displayAll-Funktion auf. Danach erstellt es ein neues Linked-List-Objekt, list2, und ruft seinen parametrisierten Kopierkonstruktor mit list als Argument auf.
Beachten Sie, dass das Objekt list2 das aufrufende Objekt ist, während list das übergebene Objekt ist.
Ausgabe:
100
200
300
List2:
100
200
300
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