Copier le constructeur de la liste chaînée en C++
Ce bref article concerne l’implémentation basée sur C++ de la liste liée ayant un constructeur de copie en profondeur.
Copier le constructeur en C++
Un constructeur de copie est appelé pour initialiser un objet en utilisant un autre objet de la même classe. Le constructeur de copie est appelé dans plusieurs situations telles que :
- Lorsqu’un objet est copié à l’aide d’un autre objet.
- Lorsque l’objet est renvoyé en tant que valeur de la fonction.
- Lorsqu’un objet est passé comme valeur à une fonction.
Dans chaque classe, il y a toujours un constructeur de copie par défaut, mais il n’effectue pas de copie profonde mais effectue une copie superficielle. Seule l’adresse du pointeur est copiée avec une copie superficielle, et les deux objets (c’est-à-dire l’appelant et les objets passés) pointent vers la même mémoire.
Inversement, en copie complète, les valeurs des membres de données sont copiées dans les membres de données de l’objet de destination.
Liste chaînée en C++
La structure de données de liste chaînée stocke les données sous la forme de nœuds de données qui peuvent croître de manière dynamique. Il ne nécessite pas de mémoire contiguë, il peut donc être stocké efficacement n’importe où dans la mémoire.
Implémentation de listes chaînées en C++
Commençons à implémenter la liste chaînée. Tout d’abord, nous devons créer une classe pour obtenir des nœuds de données :
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = 0; }
Node(T val) {
info = val;
next = 0;
}
};
La classe Node a deux membres - un pour stocker des données (c’est-à-dire info), et l’autre est le pointeur vers la classe elle-même pour stocker l’adresse du nœud suivant. La classe est modélisée afin que la liste de n’importe quel type de données puisse être créée.
L’implémentation ci-dessus fournit deux constructeurs. Le premier est le constructeur par défaut et l’autre est paramétré.
Examinons la classe de modèle pour la liste liée :
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
};
La classe LSLL n’a qu’un seul pointeur vers la classe Node, qui sera utilisé pour contenir l’adresse du premier nœud de la liste chaînée.
Pour fournir à l’utilisateur la fonctionnalité de copier en profondeur un objet de liste liée vers un autre, nous devons fournir une implémentation de constructeur de copie définie par l’utilisateur comme indiqué ci-dessous :
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
}
}
}
Le segment de code ci-dessus crée une copie complète du premier nœud de l’objet transmis et l’attache au head de l’objet de la liste des appelants. Après cela, tous les nœuds restants de l’objet transmis sont profondément copiés et attachés au nœud de la liste liée de l’appelant.
Ayons une vue cognitive de l’ensemble de l’implémentation :
#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;
}
Le code du pilote principal crée d’abord un objet list, y insère trois nœuds et appelle la fonction displayAll. Après cela, il crée un nouvel objet de liste liée, list2 et appelle son constructeur de copie paramétré avec la list comme argument.
Notez que l’objet list2 est l’objet appelant tandis que list est l’objet passé.
Production:
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