Supprimer les nœuds en double d'une liste liée non triée

Dans cet article, nous allons voir les différentes approches pour supprimer les nœuds en double de la liste liée à l'aide de la programmation C ++. Commençons par une explication de ce que signifient les «nœuds en double» dans une liste liée.

On nous donne une liste liée non triée dans ce défi et nous avons demandé à supprimer tous les membres en double de la liste. Utilisons quelques exemples pour tenter de saisir le problème.

La liste liée à l'entrée non triée est la suivante:

Les éléments 8, 10 et 9 apparaissent plus d'une fois dans la liste liée, comme on le voit dans la liste précédente. Cela indique qu'il y a des doublons de 8, 10 et 9 dans la liste liée que nous devons éliminer. La liste liée à la sortie est la suivante une fois que les entrées en double sont supprimées de la liste:

Un moyen rapide et facile de le savoir est de comparer toutes les paires de nœuds possibles dans la liste pour voir s'ils ont les mêmes informations. Lorsque leurs informations coïncident, nous nous débarrassons du deuxième nœud en les supprimant. Mais cette approche prend plus de temps.

Une meilleure efficacité est possible en utilisant hachage. L'objectif est de travailler sur la liste fournie et d'ajouter chaque nœud à un ensemble au fur et à mesure que vous allez. Si le nœud actuellement vu apparaît dans l'ensemble précédent, il peut être ignoré en toute sécurité. Une fois le processus terminé, la liste ne contiendra plus de nœuds en double.

Comprenons chaque approche en détail.

Approche 1: en utilisant deux boucles

Étapes d'algorithme

1. Créer une fonction de liste liée, "CreateLinkedlist«, Qui peut créer une liste liée.
2. Créer une fonction appelée «DeleteDuplicate Nodes"Cela peut supprimer le nœud en double de la liste liée.
3. Créez deux pointeurs locaux, PTR1 et PTR2, à l'intérieur du «DeleteDuplicate Nodes" fonction.
4. Attribuer le PTR1 = Node de tête et ptr2 = null Valeurs, où PTR1 est utilisé pour suivre le nœud dont les doublons doivent être vérifiés et PTR2 est utilisé pour traverser chaque nœud de la liste liée pour vérifier si des données de nœud sont les mêmes que les données du nœud PTR1.
5. Le pointeur de boucle imbriqué PTR2 continue de traverser l'ensemble du nœud de liste lié jusqu'à ce qu'il trouve nul.
6. Si les données du nœud PTR1 sont similaires aux données de nœud PTR2 LOOP NEST.
7. Sinon, incrément le PTR1-> Suivant et vérifier les données du nœud suivant pour les doublons.
8. Les étapes 4 à 7 sont répétées jusqu'à ce que PTR1 ne soit pas égal à NULL, ce qui indique qu'il a atteint la fin de la liste liée.
9. Enfin, nous imprimons la liste liée.
10. Fin de l'algorithme.

Implémentation du code C ++ (en utilisant deux boucles)

Sortir:

Explication:

Lignes 21 à 52: Nous créons une fonction avec le nom, «CreateLinkedlist». Nous passons deux paramètres (un pointeur de nœuds de tête vers le pointeur et une valeur) dans cette fonction. Comme le montre le programme précédent, chaque fois que cette fonction est appelée, elle crée d'abord un nouveau nœud avec une valeur (que nous avons réussi) et une adresse de nœud avec une valeur nul.

/ * Créer un nouveau nœud * /
Node * newNode = new node ();
Node * LastNode = * HeadNode;
newNode-> data = valeur; / * Ajoutant les données * /
/ * L'adresse de ce nouveau nœud gardé null * /
newNode-> next = null;

Ensuite, il vérifie pour voir si la référence de Null Null est nul. Si c'est le cas, le nœud nouvellement créé devient la tête.

/ * Vérification de la référence de NODODE est nul ou non.
Si oui, alors le newNode deviendra le NODNODE * /
if (* headnode == null)
* headnode = newNode;
retour;

Si la référence de NUDODE n'est pas nu. L'adresse de ce newnode nouvellement créé est affectée au lastnode afin qu'il puisse commencer à pointer vers le NewNode nouvellement créé.

/ * Sinon, alors cette boucle
exécuter et trouver le lastnode du lien
Liste, de sorte que Newnode nouvellement créé appelle au dernier * /
while (LastNode-> Suivant != Null)
LastNode = LastNode-> Suivant;

Maintenant, le Newnode nouvellement créé devient le lastnode. Ce processus se poursuit jusqu'à ce moment où nous appelons cette fonction.

Les étapes précédentes créent la liste liée selon nos exigences. Maintenant, nous supprimons les nœuds en double de la liste liée.

Lignes 57 à 75: Nous créons une fonction nommée «DeleteDuplicateSnodes» qui accepte un paramètre qui est le pointeur de nœuds de tête de la liste liée. Nous créons deux variables de niveau local, PTR1 et PTR2, pour suivre la liste liée lorsque nous la boucle pour découvrir les doublons dans la liste liée. Nous initialisons le PTR1 avec le nœud de tête car ce sera la boucle supérieure, et le PTR2 avec la valeur nul.

ptr1 = headnode;

PTR1: Cette variable est à la boucle extérieure et suit les éléments dont nous allons vérifier les doublons.

ptr2: Cette variable est à l'intérieur de la boucle et continue de vérifier les données de chaque nœud pour savoir si elle correspond aux données de maintien PTR1. S'il correspond, ses doublons sont supprimés de la liste liée. Ceci est vérifié et continue jusqu'à ce qu'il n'atteigne pas le dernier nœud dont la valeur est nul.

Quand ptr2-> suivant == null, la boucle imbriquée se termine et l'extérieur tandis que la boucle incrémente le PTR1 = PTR1-> Suivant avec les données de nœud suivantes.

Note: Le ptr2 se termine quand le PTR1 la boucle est terminée parce que ptr2 est à l'intérieur de la boucle PTR1.

Pendant que (PTR1 != Null && ptr1-> Suivant != Null)
ptr2 = ptr1;
tandis que (ptr2-> suivant != Null)
/ * Si trouvé, le code ci-dessous supprimera
Duplique le nœud * /
if (ptr1-> data == ptr2-> next-> data)
duplicate = ptr2-> suivant;
ptr2-> next = ptr2-> suivant-> suivant;
DELETE (DUPLICATE);
else / * Si vous n'êtes pas trouvé, PTR2 sera mis à jour
au nœud suivant * /
ptr2 = ptr2-> Suivant;

ptr1 = ptr1-> suivant;

Lignes 78 à 84: Cela affiche la liste liée finale sans aucune duplication. Dans ce cas, nous passons le Nodode Heads comme un paramètre qui est l'adresse de la liste liée.

/ * Cette fonction imprimera la liste liée * /
void affiche (nœud * nœud)
while (node-> suivant)
printf ("% d ->", nœud-> data);
Node = Node-> Suivant;

printf ("% d", nœud-> data);

Approche 2: Méthode de hachage

Étapes d'algorithme

1. Créer une fonction de liste liée, «CreateLinkedList», qui peut créer une liste liée.
2. Créer une fonction appelée «DeleteDuplicateSnodes» qui peut supprimer le nœud en double de la liste liée.
3. Créez deux pointeurs locaux, CurrentNode et PREVERNODODE, à l'intérieur de la fonction «DeleTeduplicateNodes».
4. Créez un hachage non trié à l'intérieur du «Deleteduplicate Nodes».
5. Attribuez des valeurs CurrentNode = HeadNode et PREVERNNODE = NULL où CurrentNode est utilisé pour suivre le nœud dont les doublons doivent être vérifiés et le Node précédent est utilisé pour suivre le nœud précédent de Current Node.
6. La boucle while traverse l'intégralité du nœud de liste lié jusqu'à ce que currentNode == null.
7. Si les données de courant Current sont déjà dans l'ensemble de hachage, le nœud est supprimé.
8. Sinon, il ajoute que les données de Node à l'ensemble de hachage.
9. Les étapes 5 à 8 sont répétées jusqu'à ce que le nœud de courant ne soit pas égal à NULL, ce qui indique qu'il a atteint la fin de la liste liée.
10. Enfin, nous imprimons la liste liée.
11. Fin de l'algorithme.

Implémentation du code C ++ (en utilisant la méthode de hachage)

Sortir:

Lignes 26 à 52: Nous créons une fonction avec le nom "CreateLinkedList". Dans cette fonction, nous passons deux paramètres (un pointeur de nœuds de tête vers le pointeur et une valeur). Comme le montre le programme précédent, chaque fois que cette fonction est appelée, elle crée d'abord un nouveau nœud avec une valeur (que nous avons réussi) et une adresse avec une valeur nul.

/ * Créer un nouveau nœud * /
Node * newNode = new node ();
Node * LastNode = * HeadNode;
newNode-> data = valeur; / * Ajoutant les données * /
/ * L'adresse de ce nouveau nœud gardé null * /
newNode-> next = null;

Ensuite, il vérifie pour voir si la référence de Null Null est nul. Si c'est le cas, le nœud nouvellement créé devient la tête.

/ * Vérification de la référence de NODODE est nul ou non.
Si oui, alors le newNode deviendra le NODNODE * /
if (* headnode == null)
* headnode = newNode;
retour;

Si la référence de NUDODE n'est pas nu. L'adresse de ce newnode nouvellement créé est affectée au lastnode afin qu'il puisse commencer à pointer vers le NewNode nouvellement créé.

/ * Sinon, alors cette boucle
exécuter et trouver le lastnode du lien
Liste, de sorte que Newnode nouvellement créé appelle au dernier * /
while (LastNode-> Suivant != Null)
LastNode = LastNode-> Suivant;

Maintenant, le Newnode nouvellement créé devient le lastnode. Ce processus se poursuit jusqu'à ce moment où nous appelons cette fonction.

Les étapes précédentes créent la liste liée selon nos exigences. Maintenant, nous supprimons les nœuds en double de la liste liée.

Lignes 57 à 75: Nous créons une fonction nommée «DeleteDuplicateSnodes» qui accepte un paramètre qui est le pointeur de nœuds de tête de la liste liée. Nous créons un hachage de hashset non trié. Nous créons également deux variables de niveau local, NODE COURT et NODE PRETER, Pour suivre la liste liée lorsque nous la boucle pour découvrir les doublons dans la liste liée. Nous initialisons le nœud de courant avec le nœud de tête car ce sera la boucle supérieure, et le nœud précédent avec la valeur nul.

struct nœud * currentNode = headNode;
struct nœud * PREVERNODE = NULL;

NODE COURT: Cette variable est à la boucle extérieure et suit les éléments dont nous allons vérifier les doublons.

NODE PRETER: Cela gère le nœud précédent du courant de courant. Nous créons une boucle while qui s'exécute jusqu'à ce que le NULDODE Current ne trouve pas la valeur nul, ce qui signifie à la fin de la liste liée. Si les données de courant Current sont déjà dans la carte de hachage, attribuez la valeur du Current Node Pointeur suivant vers le PREVERNNODE pointeur suivant.

PREMERNNODE-> NEXT = COURTYNODE-> NEXT;

Sinon, ajoutez les données du Node Current à la carte de hachage et faites le NODE PRETER égal à NODE COURT.

autre
hacher.insert (currentNode-> data);
PREBERNODE = COURTHNODE;

À la fin, attribuez la valeur du pointeur suivant du NODODE PRET.

Pendant (courant de courant != Null)
/ * Si les données de courant de courant déjà visitées, alors ceci
Le code supprimera ce nœud
* /
si (hachage.Rechercher (currentNode-> données) != hachage.fin())
PREMERNNODE-> NEXT = COURTYNODE-> NEXT;
Delete (currentNode);

/ *
Si ce n'est pas visité les données de courant de courant, alors
insérer dans le hachage
* /
autre
hacher.insert (currentNode-> data);
PREBERNODE = COURTHNODE;

currentNode = PREVERNODE-> Suivant;

Lignes 84 à 90: Cela affiche la liste liée finale sans aucune duplication. Dans ce cas, nous passons le Nodode Heads comme un paramètre qui est l'adresse de la liste liée.

/ * Cette fonction imprimera la liste liée * /
void affiche (nœud * nœud)
while (node-> suivant)
printf ("% d ->", nœud-> data);
Node = Node-> Suivant;

printf ("% d", nœud-> data);

Conclusion

Dans la première méthode, pour se débarrasser des doublons, nous utilisons deux boucles: une boucle extérieure qui itère sur la liste liée et sélectionne un élément, et une deuxième boucle qui itère sur cet élément pour rechercher des doublons possibles. Dès qu'un double est détecté, il est supprimé de la liste. Cette méthode utilise une boucle imbriquée pour examiner et éliminer les doublons d'une liste liée non triée qui augmente la complexité temporelle du processus. La complexité du temps est o (n²).

Dans la deuxième méthode, le hachage peut être utilisé pour minimiser la complexité temporelle de la suppression des doublons d'une liste liée non triée. Dans ce cas, si le nœud apparaît dans le hashmap deux fois, c'est une duplication et que la première occurrence doit être supprimée. Si un nœud est absent de la carte, c'est parce qu'il y en a un nouveau qui doit être ajouté. Il faut en moyenne o (n) temps pour passer en revue une liste liée de la longueur «n» et vérifie si ses nœuds sont sur la carte. La complexité temporelle pour rechercher une valeur dans une table de hachage est O (1). Compte tenu des conditions préalables susmentionnées, la complexité du temps totale est O (n).