Détecter une boucle dans une liste chaînée en C++

Le nœud de fin d'une liste chaînée qui a une boucle fera référence à un autre nœud dans la même liste plutôt qu'au NULL. S'il y a un nœud dans une liste chaînée auquel on peut accéder de manière répétée en suivant le pointeur suivant, la liste est dite avoir un cycle.

En règle générale, le dernier nœud de la liste chaînée fait référence à une référence NULL pour indiquer la conclusion de la liste. Cependant, dans une liste chaînée avec une boucle, le nœud de fin de la liste fait référence à un nœud de début, à un nœud interne ou à lui-même. Par conséquent, dans de telles circonstances, nous devons identifier et terminer la boucle en définissant la référence du nœud suivant sur NULL. La partie détection de la boucle dans une liste chaînée est expliquée dans cet article.

En C++, il existe de nombreuses façons de trouver des boucles dans une liste chaînée :

Approche basée sur la table de hachage : Cette approche stocke les adresses des nœuds visités dans une table de hachage. Une boucle dans la liste chaînée existe si un nœud est déjà présent dans la table de hachage lorsqu'il est à nouveau visité.

Approche cyclique de Floyd : L'algorithme 'tortue et lièvre', communément appelé algorithme de recherche de cycle de Floyd : cette technique utilise deux pointeurs, l'un se déplaçant plus lentement que l'autre et l'autre se déplaçant plus rapidement. Le pointeur le plus rapide dépassera finalement le pointeur le plus lent s'il y a une boucle dans la liste liée, révélant l'existence de la boucle.

Méthode récursive : Cette méthode parcourt la liste chaînée en s'appelant elle-même encore et encore. La liste chaînée contient une boucle si le nœud courant a déjà été visité.

Approche basée sur la pile : Cette approche stocke les adresses des nœuds visités dans une pile. Une boucle dans la liste chaînée est présente si un nœud est déjà présent dans la pile lorsqu'il est à nouveau visité.

Expliquons chaque approche en détail pour comprendre le concept.

Approche 1 : Approche HashSet

L'utilisation du hachage est la méthode la plus simple. Ici, on parcourt la liste une par une tout en gardant une table de hachage avec les adresses des nœuds. Par conséquent, une boucle existe si jamais nous rencontrons la prochaine adresse du nœud actuel qui est déjà contenue dans la table de hachage. Sinon, il n'y a pas de boucle dans la liste liée si nous rencontrons NULL (c'est-à-dire que nous atteignons la fin de la liste liée).

Il sera assez facile de mettre en œuvre cette stratégie.

Tout en parcourant la liste liée, nous utiliserons un unordered_hashmap et continuerons à y ajouter des nœuds.

Maintenant, une fois que nous rencontrons un nœud qui est déjà affiché sur la carte, nous saurons que nous sommes arrivés au début de la boucle.

• • De plus, nous avons gardé deux pointeurs à chaque étape, headNode pointant vers le nœud courant et dernierNoeud pointant vers le nœud précédent du nœud courant, lors de l'itération.
  • Comme notre headNode pointe maintenant vers le nœud de départ de la boucle et comme dernierNoeud pointait vers le nœud vers lequel head pointait (c'est-à-dire qu'il fait référence au dernierNoeud de la boucle), notre headNode pointe actuellement vers le nœud de départ de la boucle.
  • La boucle sera rompue en réglant l astNode->suivant == NULL .

En faisant cela, le nœud de boucle de fin au lieu de se référer au nœud initial de la boucle, commence à pointer vers NULL.

La complexité temporelle et spatiale moyenne de la méthode de hachage est O(n). Le lecteur doit toujours être conscient que l'implémentation de la structure de données de hachage intégrée dans le langage de programmation déterminera la complexité temporelle totale en cas de collision dans le hachage.

Implémentation du programme C++ pour la méthode ci-dessus (HashSet) :

Sortir:

L'explication étape par étape du code est fournie ci-dessous :

1. 1. Le fichier d'en-tête bits/stdc++.h>, qui contient toutes les bibliothèques C++ courantes, est inclus dans le code.
   2. Une structure appelée 'Nœud' est construite et comporte deux membres : une référence au nœud suivant dans la liste et un entier appelé 'valeur'.
   3. Avec une valeur entière en entrée et le pointeur 'next' défini sur NULL, la fonction 'newNode' crée un nouveau nœud avec cette valeur.
   4. La fonction ' fonctionHashMap' est défini, qui prend un pointeur vers le nœud principal de la liste chaînée en entrée.
   5. À l'intérieur de ' functionHashMap ', un unordered_map nommé 'hash_map' est créé, qui est utilisé pour implémenter une structure de données de carte de hachage.
   6. Un pointeur vers le dernier nœud de la liste est initialisé à NULL.
   7. Une boucle while est utilisée pour parcourir la liste chaînée, qui commence à partir du nœud principal et continue jusqu'à ce que le nœud principal soit NULL.
   8. Le pointeur lastNode est mis à jour sur le nœud actuel à l'intérieur de la boucle while si le nœud actuel (headNode) n'est pas déjà présent dans la carte de hachage.
   9. Si le nœud courant est trouvé dans la carte, cela signifie qu'une boucle est présente dans la liste chaînée. Pour supprimer la boucle, le pointeur suivant de la dernierNoeud est réglé sur NUL et la boucle while est cassée.
   10. Le nœud principal de la liste liée est utilisé comme entrée pour une fonction appelée 'affichage', qui affiche la valeur de chaque nœud de la liste du début à la fin.
   11. Dans le principal fonction, créant une boucle.
   12. La fonction 'functionHashMap' est appelée avec le pointeur headNode en entrée, ce qui supprime la boucle de la liste.
   13. La liste modifiée est affichée à l'aide de la fonction 'affichage'.

Approche 2 : Cycle de Floyd

L'algorithme de détection de cycle de Floyd, souvent connu sous le nom d'algorithme de la tortue et du lièvre, constitue la base de cette méthode de localisation des cycles dans une liste chaînée. Le pointeur 'lent' et le pointeur 'rapide', qui parcourent la liste à des vitesses différentes, sont les deux pointeurs utilisés dans cette technique. Le pointeur rapide avance de deux pas tandis que le pointeur lent avance d'un pas à chaque itération. Un cycle dans la liste chaînée existe si les deux points se retrouvent face à face.

1. Avec le nœud principal de la liste chaînée, nous initialisons deux pointeurs appelés rapide et lent.

2. Maintenant, nous exécutons une boucle pour parcourir la liste liée. Le pointeur rapide doit être déplacé de deux emplacements devant le pointeur lent à chaque étape d'itération.

3. Il n'y aura pas de boucle dans la liste chaînée si le pointeur rapide atteint la fin de la liste (fastPointer == NULL ou fastPointer->next == NULL). Sinon, les pointeurs rapides et lents finiront par se rencontrer, ce qui signifie que la liste liée a une boucle.

Implémentation du programme C++ pour la méthode ci-dessus (cycle de Floyd) :

Sortir:

Explication:

1. 1. Les en-têtes pertinents, tels que « bits/stdc++.h » et « std :: cout », sont d'abord inclus.
   2. La structure 'Node', qui représente un nœud dans la liste chaînée, est ensuite déclarée. Un pointeur suivant qui mène au nœud suivant dans la liste est inclus avec un champ de données entières dans chaque nœud.
   3. Ensuite, il définit « deleteLoop » et « detectAndDeleteLoop », deux fonctions. Une boucle est supprimée d'une liste chaînée à l'aide de la première méthode, et une boucle est détectée dans la liste à l'aide de la seconde fonction, qui appelle ensuite la première procédure pour supprimer la boucle.
   4. Une nouvelle liste chaînée avec cinq nœuds est créée dans la fonction principale et une boucle est établie en définissant le pointeur suivant du dernier nœud sur le troisième nœud.
   5. Il appelle ensuite la méthode 'detectAndDeleteLoop' en passant le nœud principal de la liste chaînée comme argument. Pour identifier les boucles, cette fonction utilise l'approche 'pointeurs lents et rapides'. Il utilise deux pointeurs qui commencent en haut de la liste, slowPTR et fastPTR. Alors que le pointeur rapide déplace deux nœuds à la fois, le pointeur lent ne déplace qu'un seul nœud à la fois. Le pointeur rapide dépassera finalement le pointeur lent si la liste contient une boucle, et les deux points entreront en collision au même nœud.
   6. La fonction invoque la fonction 'deleteLoop' si elle trouve une boucle, fournissant le nœud principal de la liste et l'intersection des pointeurs lent et rapide comme entrées. Cette procédure établit deux pointeurs, ptr1 et ptr2, vers le nœud principal de la liste et compte le nombre de nœuds dans la boucle. Ensuite, il avance d'un pointeur k nœuds, où k est le nombre total de nœuds dans la boucle. Ensuite, jusqu'à ce qu'ils se rencontrent au début de la boucle, il avance les deux points d'un nœud à la fois. La boucle est ensuite interrompue en définissant le pointeur suivant du nœud à la fin de la boucle sur NULL.
   7. Après avoir supprimé la boucle, il affiche la liste chaînée comme étape finale.

Approche 3 : récursivité

La récursivité est une technique permettant de résoudre des problèmes en les partitionnant en sous-problèmes plus petits et plus faciles. La récursivité peut être utilisée pour parcourir une liste à liaison simple dans le cas où une boucle est trouvée en exécutant en continu une fonction pour le nœud suivant de la liste jusqu'à ce que la fin de la liste soit atteinte.

Dans une liste à liaison unique, le principe de base de l'utilisation de la récursivité pour trouver une boucle est de commencer en tête de liste, de marquer le nœud actuel comme visité à chaque étape, puis de passer au nœud suivant en invoquant de manière récursive la fonction pour ce nœud. La méthode itérera sur la liste chaînée complète car elle est appelée de manière récursive.

La liste contient une boucle si un nœud précédemment marqué comme visité est rencontré par la fonction ; dans ce cas, la fonction peut renvoyer true. La méthode peut renvoyer false si elle atteint la fin de la liste sans passer par un nœud visité, ce qui indique qu'il n'y a pas de boucle.

Bien que cette technique d'utilisation de la récursivité pour trouver une boucle dans une seule liste chaînée soit simple à utiliser et à comprendre, elle n'est peut-être pas la plus efficace en termes de complexité temporelle et spatiale.

Implémentation du programme C++ pour la méthode ci-dessus (Récursivité) :

Sortir:

Explication:

1. 1. La fonction detectLoopLinkedList() dans ce programme accepte la tête de la liste chaînée comme entrée.
   2. La récursivité est utilisée par la fonction pour parcourir la liste chaînée. En tant que cas de base pour la récursivité, il commence par déterminer si le nœud actuel est NULL. Si tel est le cas, la méthode renvoie false, indiquant qu'aucune boucle n'existe.
   3. La valeur de la propriété 'visité' du nœud actuel est ensuite vérifiée pour voir s'il a déjà été visité. Il renvoie vrai s'il a été visité, suggérant qu'une boucle a été trouvée.
   4. La fonction marque le nœud actuel comme visité s'il a déjà été visité en changeant sa propriété 'visité' en true.
   5. La valeur de la variable visitée est ensuite vérifiée pour voir si le nœud actuel a été visité précédemment. Si elle a déjà été utilisée, une boucle doit exister et la fonction renvoie true.
   6. Enfin, la fonction s'appelle avec le nœud suivant dans la liste en passant headNode->suivant comme argument. récursivement , ceci est effectué jusqu'à ce qu'une boucle soit trouvée ou que tous les nœuds aient été visités. Cela signifie que la fonction définit la variable visitée sur true si le nœud actuel n'a jamais été visité avant de s'appeler de manière récursive pour le nœud suivant dans la liste chaînée.
   7. Le code construit trois nœuds et les joint pour produire une liste chaînée dans le fonction principale . La méthode detectLoopLinkedList() est alors invoqué sur le nœud principal de la liste. Le programme produit « Boucle déduite dans la liste chaînée ' si detectLoopLinkedList() renvoie vrai ; sinon, il sort ' Aucune boucle détectée dans la liste chaînée “.
   8. Le code insère ensuite une boucle dans la liste chaînée en définissant le pointeur suivant du dernier nœud sur le deuxième nœud. Ensuite, selon le résultat de la fonction, il exécute detectLoopLinkedList() à nouveau et produit soit ' Boucle déduite dans la liste chaînée ' ou ' Aucune boucle détectée dans la liste chaînée .”

Approche 4 : Utiliser Stack

Les boucles d'une liste chaînée peuvent être trouvées à l'aide d'une pile et de la méthode de « recherche en profondeur d'abord » (DFS). Le concept fondamental consiste à parcourir la liste chaînée, en poussant chaque nœud sur la pile s'il n'a pas déjà été visité. Une boucle est reconnue si un nœud qui est déjà sur la pile est rencontré à nouveau.

Voici une brève description de la procédure :

1. 1. Créez une pile vide et une variable pour enregistrer les nœuds qui ont été visités.
   2. Poussez la liste chaînée sur la pile, en commençant par le haut. Notez que la tête a été visitée.
   3. Poussez le nœud suivant de la liste sur la pile. Ajoutez une marque de visite à ce nœud.
   4. Au fur et à mesure que vous parcourez la liste, poussez chaque nouveau nœud sur la pile pour indiquer qu'il a été visité.
   5. Vérifiez si un nœud qui a déjà été visité se trouve en haut de la pile s'il est rencontré. Si tel est le cas, une boucle a été trouvée et la boucle est identifiée par les nœuds de la pile.
   6. Retirez les nœuds de la pile et continuez à parcourir la liste si aucune boucle n'est trouvée.

Implémentation du programme C++ pour la méthode ci-dessus (Stack)

Sortir:

Explication:

Ce programme utilise une pile pour savoir si une liste chaînée a une boucle.

• 1. La bibliothèque de flux d'entrée/sortie et la bibliothèque de piles sont toutes deux présentes sur la première ligne.

  2. L'espace de noms standard est inclus dans la deuxième ligne, ce qui nous permet d'accéder aux fonctions de la bibliothèque de flux d'entrée/sortie sans avoir à les préfixer avec 'std ::'.

  3. La ligne suivante définit le struct Node, qui se compose de deux membres : un entier appelé 'data' et un pointeur vers un autre nœud appelé 'next'.

  4. L'en-tête de la liste chaînée est une entrée pour la méthode detectLoopLinkedList(), qui est définie sur la ligne suivante. La fonction produit une valeur booléenne qui indique si une boucle a été trouvée ou non.

  5. Une pile de pointeurs de nœud appelée « stack » et un pointeur vers un nœud nommé « tempNode » qui est initialisé avec la valeur du headNode sont tous deux créés à l'intérieur de la fonction.

  6. Ensuite, tant que tempNode n'est pas un pointeur nul, nous entrons dans une boucle while.

  (a) L'élément supérieur de la pile doit correspondre au nœud actuel pour que nous puissions déterminer qu'il n'est pas vide. Nous renvoyons true si c'est le cas car une boucle a été trouvée.

  (b) Si la condition susmentionnée est fausse, le pointeur de nœud actuel est poussé sur la pile et tempNode est défini sur le nœud suivant dans la liste chaînée.

  7. Nous renvoyons false après la boucle while car aucune boucle n'a été observée.

  8. Nous construisons trois objets Node et les initialisons dans la fonction main(). Puisqu'il n'y a pas de boucle dans le premier exemple, nous définissons correctement les pointeurs 'suivants' de chaque nœud.

Conclusion:

En conclusion, la meilleure méthode pour détecter les boucles dans une liste chaînée dépend du cas d'utilisation spécifique et des contraintes du problème. La table de hachage et l'algorithme de recherche de cycle de Floyd sont des méthodes efficaces et largement utilisées dans la pratique. La pile et la récursivité sont des méthodes moins efficaces mais plus intuitives.