Erkennen einer Schleife in einer verketteten Liste in C++

Der Endknoten einer verknüpften Liste mit einer Schleife verweist auf einen anderen Knoten in derselben Liste und nicht auf NULL. Wenn es einen Knoten in einer verknüpften Liste gibt, auf den wiederholt zugegriffen werden kann, indem dem nächsten Zeiger gefolgt wird, heißt die Liste Zyklus haben.

Typischerweise verweist der letzte Knoten der verknüpften Liste auf eine NULL-Referenz, um die Schlussfolgerung der Liste anzugeben. In einer verknüpften Liste mit einer Schleife bezieht sich der Endknoten der Liste jedoch auf einen Startknoten, einen internen Knoten oder sich selbst. Daher müssen wir unter solchen Umständen die Schleife identifizieren und beenden, indem wir die Referenz des nächsten Knotens auf NULL setzen. Der Erkennungsteil der Schleife in einer verknüpften Liste wird in diesem Artikel erläutert.

In C++ gibt es zahlreiche Möglichkeiten, Schleifen in einer verketteten Liste zu finden:

Hashtabellenbasierter Ansatz : Dieser Ansatz speichert die Adressen besuchter Knoten in einer Hash-Tabelle. Eine Schleife in der verknüpften Liste liegt vor, wenn ein Knoten beim erneuten Besuch bereits in der Hash-Tabelle vorhanden ist.

Floyds Zyklusansatz : Der „Schildkröten-und-Hasen“-Algorithmus, allgemein bekannt als Floyds Zyklusfindungsalgorithmus: Diese Technik verwendet zwei Zeiger, von denen sich einer langsamer als der andere und der andere schneller bewegt. Der schnellere Zeiger überholt schließlich den langsameren Zeiger, wenn es eine Schleife in der verknüpften Liste gibt, was die Existenz der Schleife offenbart.

Rekursive Methode : Diese Methode durchläuft die verknüpfte Liste, indem sie sich immer wieder selbst aufruft. Die verknüpfte Liste enthält eine Schleife, wenn der aktuelle Knoten zuvor besucht wurde.

Stapelbasierter Ansatz : Dieser Ansatz speichert die Adressen besuchter Knoten in einem Stack. Eine Schleife in der verknüpften Liste liegt vor, wenn ein Knoten bereits im Stack vorhanden ist, wenn er erneut besucht wird.

Lassen Sie uns jeden Ansatz im Detail erklären, um das Konzept zu verstehen.

Ansatz 1: HashSet-Ansatz

Die Verwendung von Hashing ist die einfachste Methode. Hier gehen wir die Liste nacheinander durch, während wir eine Hash-Tabelle mit den Knotenadressen führen. Daher existiert eine Schleife, wenn wir jemals auf die nächste Adresse des aktuellen Knotens stoßen, die bereits in der Hash-Tabelle enthalten ist. Andernfalls gibt es keine Schleife in der verknüpften Liste, wenn wir auf NULL stoßen (d. h. das Ende der verknüpften Liste erreichen).

Es wird ziemlich einfach sein, diese Strategie umzusetzen.

Beim Durchlaufen der verknüpften Liste verwenden wir eine unordered_hashmap und fügen ihr weitere Knoten hinzu.

Wenn wir nun auf einen Knoten stoßen, der bereits in der Karte angezeigt wird, wissen wir, dass wir am Anfang der Schleife angekommen sind.

• • Außerdem haben wir bei jedem Schritt zwei Zeiger beibehalten, headNode zeigt auf den aktuellen Knoten und letzter Knoten zeigt beim Iterieren auf den vorherigen Knoten des aktuellen Knotens.
  • Als unsere headNode zeigt nun auf den Startknoten der Schleife und as letzter Knoten auf den Knoten zeigte, auf den head zeigte (d.h. es bezieht sich auf die letzter Knoten der Schleife), unsere headNode zeigt derzeit auf den Startknoten der Schleife.
  • Die Schleife wird durch Setzen von l unterbrochen astNode->next == NULL .

Dadurch beginnt der Endknoten der Schleife, anstatt auf den Anfangsknoten der Schleife zu verweisen, auf NULL zu zeigen.

Die durchschnittliche Zeit- und Platzkomplexität der Hash-Methode beträgt O(n). Der Leser sollte sich immer bewusst sein, dass die Implementierung der eingebauten Hashing DataStructure in der Programmiersprache die Gesamtzeitkomplexität im Falle einer Kollision beim Hashing bestimmt.

C++-Programmimplementierung für die obige Methode (HashSet):

Ausgang:

Die Schritt-für-Schritt-Erklärung des Codes ist unten angegeben:

1. 1. Die Headerdatei bits/stdc++.h>, die alle gängigen C++-Bibliotheken enthält, ist im Code enthalten.
   2. Eine Struktur namens „Knoten“ wird erstellt und hat zwei Mitglieder: einen Verweis auf den nächsten Knoten in der Liste und eine Ganzzahl namens „Wert“.
   3. Mit einem ganzzahligen Wert als Eingabe und dem auf NULL gesetzten „Next“-Zeiger erstellt die Funktion „newNode“ einen neuen Knoten mit diesem Wert.
   4. Die Funktion ' functionHashMap’ definiert, die einen Zeiger auf den Kopfknoten der verketteten Liste als Eingabe nimmt.
   5. Im Inneren des ‘ functionHashMap ‘-Funktion wird eine unordered_map namens ‘hash_map’ erstellt, die verwendet wird, um eine Hash-Map-Datenstruktur zu implementieren.
   6. Ein Zeiger auf den letzten Knoten der Liste wird auf NULL initialisiert.
   7. Eine While-Schleife wird verwendet, um die verkettete Liste zu durchlaufen, die beim Kopfknoten beginnt und fortgesetzt wird, bis der Kopfknoten NULL ist.
   8. Der lastNode-Zeiger wird innerhalb der While-Schleife auf den aktuellen Knoten aktualisiert, wenn der aktuelle Knoten (headNode) nicht bereits in der Hash-Map vorhanden ist.
   9. Wenn der aktuelle Knoten in der Karte gefunden wird, bedeutet dies, dass eine Schleife in der verknüpften Liste vorhanden ist. Um die Schleife zu entfernen, wird der nächste Zeiger der letzter Knoten ist eingestellt auf NULL und die While-Schleife ist unterbrochen.
   10. Der Kopfknoten der verknüpften Liste wird als Eingabe für eine Funktion namens „Anzeige“ verwendet, die den Wert jedes Knotens in der Liste von Anfang bis Ende ausgibt.
   11. Im hauptsächlich Funktion, wodurch eine Schleife entsteht.
   12. Die Funktion „functionHashMap“ wird mit dem HeadNode-Zeiger als Eingabe aufgerufen, wodurch die Schleife aus der Liste entfernt wird.
   13. Die geänderte Liste wird mit der Funktion „Anzeigen“ angezeigt.

Ansatz 2: Floyds Zyklus

Floyds Zykluserkennungsalgorithmus, oft bekannt als Schildkröten- und Hasenalgorithmus, bildet die Grundlage für diese Methode zum Auffinden von Zyklen in einer verknüpften Liste. Der „langsame“ Zeiger und der „schnelle“ Zeiger, die die Liste mit unterschiedlichen Geschwindigkeiten durchlaufen, sind die beiden Zeiger, die bei dieser Technik verwendet werden. Der schnelle Zeiger rückt zwei Schritte vor, während der langsame Zeiger bei jeder Iteration einen Schritt vorrückt. Ein Zyklus in der verknüpften Liste existiert, wenn sich die beiden Punkte jemals gegenüberstehen.

1. Mit dem Kopfknoten der verknüpften Liste initialisieren wir zwei Zeiger, die schnell und langsam genannt werden.

2. Jetzt führen wir eine Schleife aus, um uns durch die verknüpfte Liste zu bewegen. Der schnelle Zeiger sollte bei jedem Iterationsschritt um zwei Stellen vor den langsamen Zeiger verschoben werden.

3. Es wird keine Schleife in der verknüpften Liste geben, wenn der schnelle Zeiger das Ende der Liste erreicht (fastPointer == NULL oder fastPointer->next == NULL). Wenn nicht, treffen sich die schnellen und langsamen Zeiger schließlich, was bedeutet, dass die verknüpfte Liste eine Schleife hat.

C++-Programmimplementierung für die obige Methode (Floyd’s Cycle):

Ausgang:

Erläuterung:

1. 1. Zunächst werden die relevanten Header wie „bits/stdc++.h“ und „std::cout“ eingebunden.
   2. Anschließend wird die Struktur „Node“ deklariert, die für einen Knoten in der verketteten Liste steht. Ein nächster Zeiger, der zu dem folgenden Knoten in der Liste führt, ist zusammen mit einem ganzzahligen Datenfeld in jedem Knoten enthalten.
   3. Dann definiert es „deleteLoop“ und „detectAndDeleteLoop“, zwei Funktionen. Eine Schleife wird unter Verwendung der ersten Methode aus einer verknüpften Liste entfernt, und eine Schleife wird in der Liste unter Verwendung der zweiten Funktion erkannt, die dann die erste Prozedur aufruft, um die Schleife zu entfernen.
   4. In der Hauptfunktion wird eine neue verknüpfte Liste mit fünf Knoten erstellt, und eine Schleife wird hergestellt, indem der nächste Zeiger des letzten Knotens auf den dritten Knoten gesetzt wird.
   5. Anschließend ruft es die Methode „detectAndDeleteLoop“ auf, während es den Kopfknoten der verknüpften Liste als Argument übergibt. Um Loops zu identifizieren, verwendet diese Funktion den „Slow and Fast Pointers“-Ansatz. Es verwendet zwei Zeiger, die am Anfang der Liste beginnen, slowPTR und fastPTR. Während der schnelle Zeiger zwei Knoten gleichzeitig bewegt, bewegt der langsame Zeiger jeweils nur einen Knoten. Der schnelle Zeiger überholt schließlich den langsamen Zeiger, wenn die Liste eine Schleife enthält, und die beiden Punkte kollidieren am selben Knoten.
   6. Die Funktion ruft die Funktion „deleteLoop“ auf, wenn sie eine Schleife findet, und liefert den Kopfknoten der Liste und den Schnittpunkt der langsamen und schnellen Zeiger als Eingaben. Diese Prozedur richtet zwei Zeiger, ptr1 und ptr2, auf den Kopfknoten der Liste ein und zählt die Anzahl der Knoten in der Schleife. Anschließend rückt er einen Zeiger um k Knoten vor, wobei k die Gesamtzahl der Knoten in der Schleife ist. Dann, bis sie sich am Anfang der Schleife treffen, werden beide Punkte jeweils um einen Knoten vorgerückt. Die Schleife wird dann unterbrochen, indem der nächste Zeiger des Knotens am Ende der Schleife auf NULL gesetzt wird.
   7. Nach dem Entfernen der Schleife zeigt es als letzten Schritt die verknüpfte Liste an.

Ansatz 3: Rekursion

Rekursion ist eine Technik zum Lösen von Problemen, indem sie in kleinere, einfachere Teilprobleme unterteilt werden. Rekursion kann verwendet werden, um eine einfach verknüpfte Liste zu durchlaufen, falls eine Schleife gefunden wird, indem eine Funktion für den nächsten Knoten in der Liste kontinuierlich ausgeführt wird, bis das Ende der Liste erreicht ist.

In einer einfach verknüpften Liste besteht das Grundprinzip hinter der Verwendung der Rekursion zum Finden einer Schleife darin, am Kopf der Liste zu beginnen, den aktuellen Knoten bei jedem Schritt als besucht zu markieren und dann zum nächsten Knoten zu gehen, indem die Funktion rekursiv aufgerufen wird for dieser Knoten. Die Methode iteriert über die vollständige verknüpfte Liste, da sie rekursiv aufgerufen wird.

Die Liste enthält eine Schleife, wenn die Funktion auf einen zuvor als besucht markierten Knoten stößt; In diesem Fall kann die Funktion true zurückgeben. Die Methode kann false zurückgeben, wenn sie das Ende der Liste erreicht, ohne über einen besuchten Knoten zu laufen, was darauf hinweist, dass es keine Schleife gibt.

Obwohl diese Technik zum Verwenden der Rekursion zum Finden einer Schleife in einer einzelnen verknüpften Liste einfach zu verwenden und zu verstehen ist, ist sie möglicherweise nicht die effektivste in Bezug auf Zeit- und Raumkomplexität.

C++-Programmimplementierung für die obige Methode (Rekursion):

Ausgang:

Erläuterung:

1. 1. Die Funktion detectLoopLinkedList() in diesem Programm akzeptiert den Kopf der verknüpften Liste als Eingabe.
   2. Rekursion wird von der Funktion verwendet, um über die verknüpfte Liste zu iterieren. Als Basisfall für die Rekursion beginnt sie damit, zu bestimmen, ob der aktuelle Knoten NULL ist. Wenn dies der Fall ist, gibt die Methode false zurück, was darauf hinweist, dass keine Schleife vorhanden ist.
   3. Der Wert der „visited“-Eigenschaft des aktuellen Knotens wird dann überprüft, um festzustellen, ob er zuvor besucht wurde. Es gibt true zurück, wenn es besucht wurde, was darauf hindeutet, dass eine Schleife gefunden wurde.
   4. Die Funktion markiert den aktuellen Knoten als besucht, wenn er bereits besucht wurde, indem sie seine „visited“-Eigenschaft auf „true“ ändert.
   5. Der Wert der besuchten Variablen wird dann überprüft, um zu sehen, ob der aktuelle Knoten zuvor besucht wurde. Wenn es zuvor verwendet wurde, muss eine Schleife vorhanden sein, und die Funktion gibt wahr zurück.
   6. Zuletzt ruft sich die Funktion selbst mit dem nächsten Knoten in der Liste durch Übergeben auf headNode->weiter als Argument. Rekursiv , wird dies durchgeführt, bis entweder eine Schleife gefunden wird oder alle Knoten besucht wurden. Das heißt, die Funktion setzt die besuchte Variable auf wahr, wenn der aktuelle Knoten noch nie besucht wurde, bevor sie sich rekursiv für den folgenden Knoten in der verknüpften Liste aufruft.
   7. Der Code erstellt drei Knoten und verbindet sie, um eine verknüpfte Liste in der zu erstellen Hauptfunktion . Die Methode detectLoopLinkedList() wird dann auf dem Kopfknoten der Liste aufgerufen. Das Programm produziert „ Schleife in verketteter Liste abgezogen ' Wenn detectLoopLinkedList() gibt true zurück; andernfalls gibt es „ Keine Schleife in verknüpfter Liste erkannt “.
   8. Der Code fügt dann eine Schleife in die verknüpfte Liste ein, indem er den nächsten Zeiger des letzten Knotens auf den zweiten Knoten setzt. Dann wird es abhängig vom Ergebnis der Funktion ausgeführt detectLoopLinkedList() wieder und produziert entweder „ Schleife in verketteter Liste abgezogen ' oder ' Keine Schleife in verknüpfter Liste erkannt .“

Ansatz 4: Stack verwenden

Schleifen in einer verknüpften Liste können mithilfe eines Stacks und der Methode „Tiefensuche“ (DFS) gefunden werden. Das grundlegende Konzept besteht darin, die verknüpfte Liste zu durchlaufen und jeden Knoten auf den Stapel zu verschieben, wenn er noch nicht besucht wurde. Eine Schleife wird erkannt, wenn ein Knoten, der sich bereits auf dem Stack befindet, erneut angetroffen wird.

Hier eine kurze Beschreibung des Verfahrens:

1. 1. Erstellen Sie einen leeren Stapel und eine Variable, um die besuchten Knoten aufzuzeichnen.
   2. Schieben Sie die verknüpfte Liste auf den Stapel, beginnend oben. Notieren Sie, dass der Kopf besucht wurde.
   3. Schieben Sie den nächsten Knoten in der Liste auf den Stapel. Fügen Sie diesem Knoten eine Besuchsmarkierung hinzu.
   4. Schieben Sie beim Durchlaufen der Liste jeden neuen Knoten auf den Stapel, um anzuzeigen, dass er besucht wurde.
   5. Überprüfen Sie, ob ein Knoten, der zuvor besucht wurde, sich an der Spitze des Stapels befindet, wenn er angetroffen wird. Wenn dies der Fall ist, wurde eine Schleife gefunden, und die Schleife wird durch die Knoten im Stapel identifiziert.
   6. Entfernen Sie die Knoten vom Stack und durchlaufen Sie die Liste weiter, wenn keine Schleife gefunden wird.

C++-Programmimplementierung für obige Methode (Stack)

Ausgang:

Erläuterung:

Dieses Programm verwendet einen Stack, um herauszufinden, ob eine einfach verkettete Liste eine Schleife hat.

• 1. Die Input/Output-Stream-Bibliothek und die Stack-Bibliothek sind beide in der ersten Zeile vorhanden.

  2. Der Standard-Namespace ist in der zweiten Zeile enthalten, sodass wir auf die Funktionen der Input/Output-Stream-Bibliothek zugreifen können, ohne ihnen „std::“ voranstellen zu müssen.

  3. Die folgende Zeile definiert den Strukturknoten, der aus zwei Elementen besteht: einer Ganzzahl namens „data“ und einem Zeiger auf einen anderen Knoten namens „next“.

  4. Der Kopf der verknüpften Liste ist eine Eingabe für die Methode detectLoopLinkedList(), die in der nächsten Zeile definiert wird. Die Funktion erzeugt einen booleschen Wert, der angibt, ob eine Schleife gefunden wurde oder nicht.

  5. Ein Stapel von Node-Zeigern namens „stack“ und ein Zeiger auf einen Node namens „tempNode“, der mit dem Wert des headNode initialisiert wird, werden beide innerhalb der Funktion erstellt.

  6. Solange tempNode kein Nullzeiger ist, treten wir dann in eine While-Schleife ein.

  (a) Das oberste Element des Stapels muss mit dem aktuellen Knoten übereinstimmen, damit wir feststellen können, dass es nicht leer ist. Wir geben true zurück, wenn dies der Fall ist, weil eine Schleife gefunden wurde.

  (b) Wenn die oben erwähnte Bedingung falsch ist, wird der aktuelle Knotenzeiger auf den Stapel geschoben und tempNode wird auf den folgenden Knoten in der verknüpften Liste gesetzt.

  7. Wir geben nach der While-Schleife false zurück, da keine Schleife beobachtet wurde.

  8. Wir bauen drei Node-Objekte und initialisieren sie in der Funktion main(). Da es im ersten Beispiel keine Schleife gibt, setzen wir die „Next“-Zeiger jedes Knotens richtig.

Abschluss:

Zusammenfassend lässt sich sagen, dass die beste Methode zum Erkennen von Schleifen in einer verknüpften Liste vom spezifischen Anwendungsfall und den Einschränkungen des Problems abhängt. Hash Table und der Zyklusfindungsalgorithmus von Floyd sind effiziente Methoden, die in der Praxis weit verbreitet sind. Stack und Rekursion sind weniger effiziente Methoden, dafür aber intuitiver.