Détecter une boucle dans une liste liée en C ++

Le nœud de fin d'une liste liée qui a une boucle se réfère à un autre nœud dans la même liste plutôt que le null.S'il y a un nœud dans une liste liée qui peut être accessible à plusieurs reprises en suivant le pointeur suivant, la liste aurait un cycle.

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

En C ++, il existe de nombreuses façons de trouver des boucles dans une liste lié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 liée existe si un nœud est déjà présent dans la table de hachage lors de sa visite à nouveau.

Approche cyclable 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 rapidement. Le pointeur plus rapide dépasse finalement le pointeur 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 passe par la liste liée en s'appelant encore et encore. La liste liée contient une boucle si le nœud actuel 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 liée est présente si un nœud est déjà là dans la pile lors de sa visite à nouveau.

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

Approche 1: Approche de Hashset

L'utilisation de hachage est la méthode la plus simple. Ici, nous passons par la liste une par une tout en gardant une table de hachage avec les adresses de nœud. Par conséquent, une boucle existe si nous avons déjà traversé l'adresse suivante du nœud actuel qui est déjà contenu dans le tableau de hachage. Sinon, il n'y a pas de boucle dans la liste liée si nous rencontrons null (i.e., atteindre la fin de la liste liée).

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

Tout en traversant la liste liée, nous utiliserons un non ordonné_hashmap et continuerons à y ajouter des nœuds.

Maintenant, une fois que nous avons rencontré un nœud qui est déjà montré 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, nez de tête pointant vers le nœud actuel et calendrier pointant vers le nœud précédent du nœud actuel, tout en itérant.
  • Comme notre nez de tête pointe maintenant vers le nœud de démarrage de la boucle et comme calendrier pointait vers le nœud auquel la tête pointait (je.e., il fait référence au calendrier de la boucle), notre nez de tête pointe actuellement vers le nœud de démarrage de la boucle.
  • La boucle sera cassée en réglant Lastnode-> 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 nul.

Le temps et la complexité du temps et de l'espace de la méthode de hachage sont O (n). Le lecteur doit toujours être conscient que la mise en œuvre de la datastructure de hachage intégrée dans le langage de programmation déterminera la complexité du temps totale en cas de collision de hachage.

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

#inclure
Utilisation de Namespace Std;
nœud struct
INT VALEUR;
nœud struct * suivant;
;
Nœud * newNode (INT Value)

Nœud * tempnode = nouveau nœud;
tempnode-> value = valeur;
tempnode-> next = null;
retour tempnode;

// identifier et éliminer toutes les boucles potentielles
// dans une liste liée à cette fonction.
void functionhashmap (nœud * headnode)

// a créé un non ordonné_map pour implémenter la carte de hachage
non ordonné_map hash_map;
// pointeur vers LastNode
Nœud * lastNode = null;
Pendant (Node de tête != Null)
// Si un nœud est absent sur la carte, ajoutez-le.
if (hash_map.find (headnode) == hash_map.fin())
hash_map [headnode] ++;
LastNode = headNode;
headnode = headnode-> suivant;

// Si un cycle est présent, définissez le prochain pointeur du nœud final vers NULL.
autre
LastNode-> next = null;
casser;



// Afficher la liste liée
VOID Affichage (Node * HEADNODE)

Pendant (Node de tête != Null)
couter headnode = headnode-> suivant;

couter << endl;

/* Fonction principale*/
int main()

Node * headnode = newNode (48);
headnode-> next = headnode;
headnode-> next = newNode (18);
headnode-> next-> next = newNode (13);
headnode-> next-> next-> next = newNode (2);
headnode-> next-> next-> next-> next = newNode (8);
/ * Créez une boucle dans LinkedList * /
headnode-> next-> next-> next-> next-> next = headnode-> next-> next;
functionhashmap (headnode);
printf ("Liste liée sans boucle \ n");
affichage (headnode);
retour 0;

Sortir:

Liste liée sans boucle
48 18 13 2 8

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

1. 1. Les bits / stdc++.H> Le fichier d'en-tête, qui contient toutes les bibliothèques C ++ courantes, est incluse dans le code.
   2. Une structure appelée «nœud» est construite, et elle a deux membres: une référence au nœud suivant dans la liste et un entier appelé «valeur."
   3. Avec une valeur entière comme entrée et le pointeur «suivant» définie sur NULL, la fonction «newNode» crée un nouveau nœud avec cette valeur.
   4. La fonction 'functionhashmap ' est défini, qui prend un pointeur vers le nœud de tête de la liste liée comme entrée.
   5. À l'intérieur de 'fundehashmap'Fonction, un non ordonné_map nommé' hash_map 'est créé, qui est utilisé pour implémenter une structure de données de cartographie de hachage.
   6. Un pointeur vers le dernier nœud de la liste est initialisé à Null.
   7. Une boucle de temps est utilisée pour traverser la liste liée, qui commence à partir du nœud de tête et se poursuit jusqu'à ce que le nœud de tête soit nul.
   8. Le pointeur LastNode est mis à jour vers 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 actuel se trouve dans la carte, cela signifie qu'une boucle est présente dans la liste liée. Pour supprimer la boucle, le pointeur suivant du calendrier est réglé sur NUL Et la boucle while est brisée.
   10. Le nœud de tête de la liste liée est utilisé comme entrée pour une fonction appelée «Affichage», qui étend la valeur de chaque nœud dans la liste depuis le début pour terminer.
   11. Dans le principal fonction, créant une boucle.
   12. La fonction 'functionhashmap' est appelée avec le pointeur de nœuds de tête comme entrée, qui supprime la boucle de la liste.
   13. La liste modifiée s'affiche à l'aide de la fonction 'Affichage'.

Approche 2: le cycle de Floyd

L'algorithme de détection de cycle de Floyd, souvent connu sous le nom de Tortoise et l'algorithme de lièvre, fournit la base de cette méthode de localisation des cycles dans une liste liée. Le pointeur «lent» et le pointeur «rapide», qui traversent la liste à différentes vitesses, sont les deux pointeurs utilisés dans cette technique. Le pointeur rapide progresse deux étapes tandis que le pointeur lent fait avancer une étape à chaque itération. Un cycle dans la liste liée existe si les deux points se retrouvent face à face.

1. Avec le nœud de tête de la liste liée, nous initialisons deux pointeurs appelés Fast and Slow.

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

3. Il n'y aura pas de boucle dans la liste lié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):

#inclure
Utilisation de Namespace Std;
/ * LIEN LIST NODE * /
nœud struct
données int;
nœud struct * suivant;
;
/ * Fonction pour supprimer la boucle. * /
void deleteleloop (nœud struct *, nœud struct *);
/ * Cette fonction localise et élimine les boucles de liste. Il donne 1
S'il y avait une boucle dans la liste; Sinon, il renvoie 0. * /
inttectandDeleteleloop (liste de nœud structure *)

struct nœud * slowptr = list, * fastptr = list;
// Itérater pour vérifier si la boucle est là.
while (slowptr && fastptr && fastptr-> suivant)
SlowPtr = SlowPtr-> Suivant;
fastptr = fastptr-> suivant-> suivant;
/ * Si SlowPtr et FastPtr se rencontrent à un moment donné, alors là
est une boucle * /
if (slowptr == Fastptr)
DeleleTeloop (SlowPtr, List);
/ * Retour 1 pour indiquer qu'une boucle a été découverte. * /
retour 1;


/ * Retour 0 pour indiquer qu'aucune boucle n'a été découverte.* /
retour 0;

/ * Fonction pour supprimer la boucle de la liste liée.
Loopnode pointe vers l'un des nœuds de boucle et le nœud de tête pointe
au nœud de démarrage de la liste liée * /
void deleteleloop (nœud struct * loopnode, struct nœud * headnode)

nœud struct * ptr1 = loopnode;
nœud struct * ptr2 = loopnode;
// compter le nombre de nœuds dans la boucle.
non signé int k = 1, i;
tandis que (ptr1-> suivant != ptr2)
ptr1 = ptr1-> suivant;
k ++;

// Correction d'un pointeur vers la tête de tête
ptr1 = headnode;
// et l'autre pointeur vers k nœuds après Node de tête
ptr2 = headnode;
pour (i = 0; i < k; i++)
ptr2 = ptr2-> Suivant;
/ * Lorsque les deux points sont déplacés simultanément,
Ils colliteront au nœud débutant de la boucle. * /
pendant que (ptr2 != ptr1)
ptr1 = ptr1-> suivant;
ptr2 = ptr2-> Suivant;

// Obtenez le dernier pointeur du nœud.
tandis que (ptr2-> suivant != ptr1)
ptr2 = ptr2-> Suivant;
/ * Pour fermer la boucle, définissez le suivant
nœud au nœud de terminaison de la boucle. * /
ptr2-> next = null;

/ * Fonction pour afficher la liste liée * /
void DisplayLinkEdList (nœud struct * nœud)

// Affiche la liste liée après la suppression de la boucle
while (nœud != Null)
couter Node = Node-> Suivant;


nœud struct * newNode (key int)

struct nœud * temp = new node ();
temp-> data = key;
temp-> next = null;
Tempère de retour;

// Code principal
int main()

struct nœud * headnode = newNode (48);
headnode-> next = newNode (18);
headnode-> next-> next = newNode (13);
headnode-> next-> next-> next = newNode (2);
headnode-> next-> next-> next-> next = newNode (8);
/ * Créer une boucle * /
headnode-> next-> next-> next-> next-> next = headnode-> next-> next;
// Affiche la boucle dans la liste liée
// DisplayLinkEdList (HeadNode);
DetectandDeleteleop (HeadNode);
couter << "Linked List after no loop \n";
DisplayLinkedList (HeadNode);
retour 0;

Sortir:

Liste liée après aucune boucle
48 18 13 2 8

Explication:

1. 1. Les en-têtes pertinents, tels que «BITS / STDC++.h ”et« std :: cout », sont d'abord inclus.
   2. La structure «nœud», qui représente un nœud dans la liste liée, est ensuite déclaré. Un pointeur suivant qui mène au nœud suivant dans la liste est inclus avec un champ de données entier dans chaque nœud.
   3. Ensuite, il définit «Deleteleloop» et «Detectanddeleteleloop», deux fonctions. Une boucle est supprimée d'une liste liée à l'aide de la première méthode, et une boucle est détectée dans la liste à l'aide de la deuxième fonction, qui appelle ensuite la première procédure pour supprimer la boucle.
   4. Une nouvelle liste liée à cinq nœuds est créée dans la fonction principale, et une boucle est établie en définissant le prochain pointeur du dernier nœud vers le troisième nœud.
   5. Il fait ensuite un appel à la méthode «DetectandDeleteleop» tout en passant le nœud de tête de la liste liée comme argument. Pour identifier les boucles, cette fonction utilise l'approche «pointeurs lents et rapides». Il utilise deux conseils 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 nœud à la fois. Le pointeur rapide dépasse finalement le pointeur lent si la liste contient une boucle, et les deux points se heurteront au même nœud.
   6. La fonction invoque la fonction «Deleteleloop» si elle trouve une boucle, fournissant le nœud de tête de la liste et l'intersection des pointeurs lents et rapides comme entrées. Cette procédure établit deux pointeurs, PTR1 et PTR2, au nœud de tête de la liste et compte le nombre de nœuds dans la boucle. Après cela, il fait avancer un pointeur k nœuds, où k est le nombre total de nœuds dans la boucle. Ensuite, jusqu'à ce qu'ils se réunissent au début de la boucle, cela fait progresser les deux points un nœud à la fois. La boucle est ensuite cassée en définissant le pointeur suivant du nœud à la fin de la boucle à Null.
   7. Après avoir retiré la boucle, il affiche la liste liée comme une dernière étape.

Approche 3: Recursion

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

Dans une liste liée individuellement, le principe de base derrière l'utilisation de la récursivité pour trouver une boucle est de commencer à la tête de la liste, de marquer le nœud actuel comme visité à chaque étape, puis de passer au nœud suivant en invoquant récursivement la fonction de Ce nœud. La méthode itérera sur la liste liée complète car elle s'appelle récursivement.

La liste contient une boucle si un nœud qui était auparavant marqué comme visité est rencontré par la fonction; Dans ce cas, la fonction peut retourner vrai. La méthode peut retourner false si elle atteint la fin de la liste sans courir sur 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é de trouver une boucle dans une seule liste liée soit simple à utiliser et à comprendre, elle pourrait ne pas être la plus efficace en termes de complexité de temps et d'espace.

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

#inclure
Utilisation de Namespace Std;
nœud struct
données int;
Nœud * suivant;
Bool visité;
;
// Fonction de détection de boucle de liste liée
bool DetectloopLinkEdList (node ​​* headnode)
if (headnode == null)
retourne false; // Si la liste liée est vide, le cas de base

// il y a une boucle si le nœud actuel a
// déjà visité.
if (headnode-> visité)
Retour Vrai;

// Ajouter une marque de visite au nœud actuel.
headnode-> visité = true;
// appelle le code pour le nœud suivant à plusieurs reprises
return DetectLoOpLinkEdList (headNode-> Suivant);

int main()
Node * headnode = new node ();
Node * secondNode = new node ();
Node * tiersnode = new node ();
headnode-> data = 1;
headnode-> next = secondNode;
headnode-> visité = false;
secondNode-> data = 2;
secondNode-> next = tiersnode;
secondNode-> visité = false;
ThirdNode-> data = 3;
ThirdNode-> next = null; // pas de boucle
ThirdNode-> Visited = false;
if (DetectLoopLinkEdList (headnode))
couter << "Loop detected in linked list" << endl;
autre
couter << "No loop detected in linked list" << endl;

// Création d'une boucle
tiersNode-> next = secondNode;
if (DetectLoopLinkEdList (headnode))
couter << "Loop detected in linked list" << endl;
autre
couter << "No loop detected in linked list" << endl;

retour 0;

Sortir:

Aucune boucle détectée dans la liste liée
Boucle détectée dans la liste liée

Explication:

1. 1. La fonction DetectloopLinkEdList () Dans ce programme, accepte le chef de la liste liée comme une entrée.
   2. La récursivité est utilisée par la fonction pour itérer sur la liste liée. Comme le cas de base pour la récursivité, il commence par déterminer si le nœud actuel est nul. Si c'est le cas, la méthode renvoie fausse, 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 si elle a été visitée précédemment. Il revient 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 modifiant sa propriété «visité» en vrai.
   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. S'il a été utilisé auparavant, une boucle doit exister et la fonction renvoie true.
   6. Enfin, la fonction s'appelle avec le nœud suivant de 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. Signifie, la fonction définit la variable visitée à true si le nœud actuel n'a jamais été visité avant de s'appeler récursivement pour le nœud suivant dans la liste liée.
   7. Le code construit trois nœuds et les rejoint pour produire une liste liée dans le fonction principale. La méthode DetectloopLinkEdList () est ensuite invoqué sur le nœud de tête de la liste. Le programme produit «Boucle déduite dans la liste liée" si DetectloopLinkEdList () Renvoie vrai; Sinon, il sortira "Aucune boucle détectée dans la liste liée".
   8. Le code insère ensuite une boucle dans la liste liée en définissant le prochain pointeur du dernier nœud vers le deuxième nœud. Ensuite, selon le résultat de la fonction, il fonctionne DetectloopLinkEdList () encore et produit soit "Boucle déduite dans la liste liée" ou "Aucune boucle détectée dans la liste liée."

Approche 4: Utilisation de pile

Des boucles dans une liste liée peuvent être trouvées à l'aide d'une pile et de la méthode de la «recherche en profondeur-première» (DFS). Le concept fondamental est d'itérer à travers la liste liée, 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 se trouve déjà sur la pile se retrouve à 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 liée sur la pile, en commençant en haut. Notez que la tête a été visitée.
   3. Poussez le nœud suivant dans la liste sur la pile. Ajoutez une marque de visite à ce nœud.
   4. Lorsque vous traversez la liste, poussez chaque nouveau nœud sur la pile pour indiquer qu'il a été visité.
   5. Vérifiez pour voir si un nœud qui a été visité auparavant est en haut de la pile s'il est rencontré. Si c'est le cas, une boucle a été trouvée et la boucle est identifiée par les nœuds de la pile.
   6. Éteignez les nœuds de la pile et continuez à traverser la liste si aucune boucle n'est trouvée.

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

#inclure
#inclure
Utilisation de Namespace Std;
nœud struct
données int;
Nœud * suivant;
;
// fonction à détecter la boucle dans une liste liée
bool DetectloopLinkEdList (node ​​* headnode)
empiler empiler;
Node * tempnode = headnode;
pendant (tempnode != Null)
// Si l'élément supérieur de la pile correspond
// le nœud actuel et la pile n'est pas vide
si (!empiler.vide () && pile.top () == tempnode)
Retour Vrai;

empiler.push (tempnode);
tempnode = tempnode-> suivant;

retourne false;

int main()
Node * headnode = new node ();
Node * secondNode = new node ();
Node * tiersnode = new node ();
headnode-> data = 1;
headnode-> next = secondNode;
secondNode-> data = 2;
secondNode-> next = tiersnode;
ThirdNode-> data = 3;
ThirdNode-> next = null; // pas de boucle
if (DetectLoopLinkEdList (headnode))
couter << "Loop detected in linked list" << endl;
autre
couter << "No loop detected in linked list" << endl;

// Création d'une boucle
tiersNode-> next = secondNode;
if (DetectLoopLinkEdList (headnode))
couter << "Loop detected in linked list" << endl;
autre
couter << "No loop detected in linked list" << endl;

Sortir:

Aucune boucle détectée dans la liste liée
Boucle détectée dans la liste liée

Explication:

Ce programme utilise une pile pour savoir si une liste liée individuelle a une boucle.

• 1. La bibliothèque de flux d'entrée / sortie et la bibliothèque de pile sont tous deux présents dans 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 nœud struct, qui se compose de deux membres: un entier appelé «données» et un pointeur vers un autre nœud appelé «Next."

  4. La tête de la liste lié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œuds appelés «pile» et un pointeur vers un nœud nommé «tempnode» qui est initialisé avec la valeur du nœud de tête est 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 de temps.

  (a) L'élément supérieur de la pile doit correspondre au nœud actuel afin que nous puissions déterminer qu'il n'est pas vide. Nous revenons vrai si tel est le cas parce qu'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 liée.

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

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

Conclusion:

En conclusion, la meilleure méthode pour détecter les boucles dans une liste lié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 ils sont largement utilisés dans la pratique. La pile et la récursivité sont des méthodes moins efficaces mais elles sont plus intuitives.