Registrer en sløjfe i en sammenkædet liste i C++

Slutknuden på en sammenkædet liste, der har en sløjfe, vil referere til en anden node i den samme liste i stedet for NULL. Hvis der er en node i en sammenkædet liste, som kan tilgås gentagne gange ved at følge den næste markør, siges listen at have en cyklus.

Typisk refererer den linkede listes sidste node til en NULL-reference for at angive listens konklusion. I en sammenkædet liste med en sløjfe refererer listens slutknude til en startknude, en intern knude eller sig selv. Derfor skal vi under sådanne omstændigheder identificere og afslutte sløjfen ved at sætte den næste nodes reference til NULL. Detektionsdelen af ​​løkken i en sammenkædet liste er forklaret i denne artikel.

I C++ er der adskillige måder at finde sløjfer i en sammenkædet liste:

Hash tabel-baseret tilgang : Denne fremgangsmåde gemmer adresserne på besøgte noder i en hash-tabel. En løkke i den linkede liste eksisterer, hvis en node allerede er til stede i hash-tabellen, når den besøges igen.

Floyds cyklustilgang : 'Skildpadde og hare'-algoritmen, almindeligvis kendt som Floyds cyklusfindingsalgoritme: Denne teknik gør brug af to pointere, den ene bevæger sig langsommere end den anden, og den anden bevæger sig hurtigere. Den hurtigere pointer vil i sidste ende overhale den langsommere pointer, hvis der er en løkke i den sammenkædede liste, hvilket afslører løkkens eksistens.

Rekursiv metode : Denne metode går gennem den linkede liste ved at kalde sig selv igen og igen. Den sammenkædede liste indeholder en sløjfe, hvis den aktuelle node tidligere har været besøgt.

Stakbaseret tilgang : Denne tilgang gemmer adresserne på besøgte noder i en stak. En løkke i den linkede liste er til stede, hvis en node allerede er der i stakken, når den besøges igen.

Lad os forklare hver tilgang i detaljer for at forstå konceptet.

Fremgangsmåde 1: HashSet-tilgang

At bruge hashing er den mest ligetil metode. Her gennemgår vi listen én efter én, mens vi holder en hash-tabel med nodeadresserne. Derfor eksisterer der en løkke, hvis vi nogensinde løber over den næste adresse på den aktuelle node, som allerede er indeholdt i hash-tabellen. Ellers er der ingen løkke i den linkede liste, hvis vi løber ind i NULL (dvs. når slutningen af ​​den linkede liste).

Det vil være ret nemt at implementere denne strategi.

Mens vi krydser den linkede liste, bruger vi et unordered_hashmap og fortsætter med at tilføje noder til det.

Nu, når vi støder på en node, der allerede er vist på kortet, vil vi vide, at vi er nået til løkkens begyndelse.

• • Derudover holdt vi to pointere ved hvert trin, headNode peger på den aktuelle node og sidste Node peger på den tidligere node af den aktuelle node, mens den itereres.
  • Som vores headNode peger nu på startknudepunktet for sløjfen og som sidste Node pegede på knudepunktet, som hovedet pegede på (dvs. det refererer til sidste Node af løkken), vores headNode peger i øjeblikket på løkkens startknude.
  • Løkken vil blive brudt ved at indstille l astNode->næste == NULL .

Ved at gøre dette begynder slutsløjfeknudepunktet i stedet for at henvise til løkkens indledende knudepunkt at pege på NULL.

Hashingmetodens gennemsnitlige tid og rumkompleksitet er O(n). Læseren skal altid være opmærksom på, at implementeringen af ​​den indbyggede Hashing DataStructure i programmeringssproget vil bestemme den samlede tidskompleksitet i tilfælde af en kollision i hashing.

C++ programimplementering for ovenstående metode (HashSet):

Produktion:

Kodens trin-for-trin forklaring findes nedenfor:

1. 1. Bits/stdc++.h> header-filen, som indeholder alle de almindelige C++-biblioteker, er inkluderet i koden.
   2. En struktur kaldet 'Node' er konstrueret, og den har to medlemmer: en reference til den næste node på listen og et heltal kaldet 'værdi'.
   3. Med en heltalsværdi som input og den 'næste' markør sat til NULL, opretter funktionen 'newNode' en ny node med denne værdi.
   4. Funktionen ' functionHashMap' er defineret, som tager en pegepind til hovedknuden på den sammenkædede liste som input.
   5. Inde i ' functionHashMap ' funktion, oprettes et uordnet_map ved navn 'hash_map', som bruges til at implementere en hash-kortdatastruktur.
   6. En pointer til den sidste knude på listen initialiseres til NULL.
   7. En while-løkke bruges til at krydse den sammenkædede liste, som starter fra hovedknuden og fortsætter, indtil hovednoden er NULL.
   8. LastNode-markøren opdateres til den aktuelle node inde i while-løkken, hvis den aktuelle node (headNode) ikke allerede er til stede i hash-kortet.
   9. Hvis den aktuelle node findes i kortet, betyder det, at der er en sløjfe til stede i den sammenkædede liste. For at fjerne løkken, skal den næste markør på sidste Node er indstillet til NUL og while-løkken er brudt.
   10. Den linkede listes hovedknude bruges som input til en funktion kaldet 'display', som udsender værdien af ​​hver node på listen fra start til slut.
   11. I den vigtigste funktion, skabe en løkke.
   12. Funktionen 'functionHashMap' kaldes med headNode pointeren som input, hvilket fjerner loopen fra listen.
   13. Den ændrede liste vises ved hjælp af 'display'-funktionen.

Fremgangsmåde 2: Floyds cyklus

Floyds cyklusdetektionsalgoritme, ofte kendt som skildpadden og harealgoritmen, danner grundlaget for denne metode til at lokalisere cyklusser i en sammenkædet liste. Den 'langsomme' pointer og den 'hurtige' pointer, som krydser listen ved forskellige hastigheder, er de to pointere, der bruges i denne teknik. Den hurtige markør går to trin frem, mens den langsomme markør går et skridt frem for hver iteration. En cyklus i den sammenkædede liste eksisterer, hvis de to punkter nogensinde kommer ansigt til ansigt.

1. Med den linkede listes hovedknude initialiserer vi to pointere kaldet hurtig og langsom.

2. Nu kører vi en løkke for at bevæge os gennem den linkede liste. Den hurtige markør skal flyttes to steder foran den langsomme markør ved hver iterations trin.

3. Der vil ikke være en løkke i den linkede liste, hvis den hurtige pointer når slutningen af ​​listen (fastPointer == NULL eller fastPointer->next == NULL). Hvis ikke, vil de hurtige og langsomme pointere til sidst mødes, hvilket betyder, at den linkede liste har en løkke.

C++ programimplementering for ovenstående metode (Floyd's Cycle):

Produktion:

Forklaring:

1. 1. De relevante overskrifter, såsom 'bits/stdc++.h' og 'std::cout,' inkluderes først.
   2. 'Node' strukturen, som står for en node i den sammenkædede liste, erklæres derefter. En næste pointer, der fører til den følgende node på listen, er inkluderet sammen med et heltalsdatafelt i hver node.
   3. Derefter definerer den 'deleteLoop' og 'detectAndDeleteLoop', to funktioner. En løkke fjernes fra en sammenkædet liste ved hjælp af den første metode, og en løkke detekteres i listen ved hjælp af den anden funktion, som derefter kalder den første procedure for at fjerne løkken.
   4. En ny sammenkædet liste med fem noder oprettes i hovedfunktionen, og en løkke etableres ved at sætte den sidste nodes næste pointer til den tredje node.
   5. Den foretager derefter et opkald til 'detectAndDeleteLoop'-metoden, mens den sender den linkede listes hovedknude som et argument. For at identificere sløjfer bruger denne funktion 'Slow and Fast Pointers'-tilgangen. Den bruger to pointere, der begynder øverst på listen, slowPTR og fastPTR. Mens den hurtige markør flytter to noder på én gang, flytter den langsomme markør kun én node ad gangen. Den hurtige pointer vil i sidste ende overhale den langsomme pointer, hvis listen indeholder en løkke, og de to punkter vil støde sammen ved den samme node.
   6. Funktionen aktiverer 'deleteLoop'-funktionen, hvis den finder en loop, der leverer listens hovedknudepunkt og skæringspunktet mellem de langsomme og hurtige pointere som input. Denne procedure etablerer to pointere, ptr1 og ptr2, til listens hovedknudepunkt og tæller antallet af noder i løkken. Efter det, fremfører den en pointer k noder, hvor k er det samlede antal knudepunkter i løkken. Derefter, indtil de mødes ved starten af ​​løkken, fremfører den begge punkter én node ad gangen. Sløjfen brydes derefter ved at sætte den næste pointer for noden i slutningen af ​​løkken til NULL.
   7. Efter at have fjernet løkken, viser den den sammenkædede liste som et sidste trin.

Fremgangsmåde 3: Rekursion

Rekursion er en teknik til at løse problemer ved at opdele dem i mindre, lettere underproblemer. Rekursion kan bruges til at krydse en enkelt-linket liste i tilfælde af, at en løkke er fundet ved kontinuerligt at køre en funktion for den næste node på listen, indtil listens ende er nået.

I en enkeltforbundet liste er grundprincippet bag brugen af ​​rekursion til at finde en sløjfe at starte i toppen af ​​listen, markere den aktuelle node som besøgt ved hvert trin og derefter gå videre til den næste node ved rekursivt at aktivere funktionen for den node. Metoden vil iterere over den fulde linkede liste, fordi den kaldes rekursivt.

Listen indeholder en løkke, hvis en node, der tidligere er blevet markeret som besøgt, støder på funktionen; i dette tilfælde kan funktionen returnere sand. Metoden kan returnere falsk, hvis den når slutningen af ​​listen uden at køre på tværs af en besøgt node, hvilket indikerer, at der ikke er nogen løkke.

Selvom denne teknik til at bruge rekursion til at finde en løkke i en enkelt linket liste er ligetil at bruge og forstå, er den måske ikke den mest effektive med hensyn til tid og rumkompleksitet.

C++ programimplementering for ovenstående metode (Rekursion):

Produktion:

Forklaring:

1. 1. Funktionen detectLoopLinkedList() i dette program accepterer hovedet af den linkede liste som input.
   2. Rekursion bruges af funktionen til at iterere på tværs af den linkede liste. Som det grundlæggende tilfælde for rekursionen begynder den med at bestemme, om den aktuelle node er NULL. Hvis det er tilfældet, returnerer metoden falsk, hvilket indikerer, at der ikke eksisterer en løkke.
   3. Værdien af ​​den aktuelle nodes 'besøgte' egenskab kontrolleres derefter for at se, om den tidligere er blevet besøgt. Det returnerer sandt, hvis det er blevet besøgt, hvilket tyder på, at der er fundet en løkke.
   4. Funktionen markerer den aktuelle node som besøgt, hvis den allerede er besøgt ved at ændre dens 'besøgte' egenskab til sand.
   5. Værdien af ​​den besøgte variabel kontrolleres derefter for at se, om den aktuelle node er blevet besøgt tidligere. Hvis det har været brugt før, skal der eksistere en løkke, og funktionen returnerer sand.
   6. Til sidst kalder funktionen sig selv med den næste node på listen ved at passere headNode->næste som et argument. Rekursivt , dette udføres indtil enten en sløjfe er fundet eller alle noder er besøgt. Betyder, at funktionen indstiller den besøgte variabel til sand, hvis den aktuelle node aldrig er blevet besøgt, før den rekursivt kalder sig selv for den følgende node i den sammenkædede liste.
   7. Koden bygger tre noder og forbinder dem for at producere en sammenkædet liste i hovedfunktion . Metoden detectLoopLinkedList() påkaldes derefter på listens hovedknude. Programmet producerer ' Løkke fratrukket i linket liste 'hvis detectLoopLinkedList() returnerer sandt; ellers udsender den ' Ingen sløjfe fundet i den linkede liste “.
   8. Koden indsætter derefter en løkke i den sammenkædede liste ved at sætte den sidste nodes næste pointer til den anden node. Derefter, afhængigt af resultatet af funktionen, kører den detectLoopLinkedList() igen og producerer enten ' Løkke fratrukket i linket liste ' eller ' Ingen sløjfe fundet i den linkede liste .'

Fremgangsmåde 4: Brug af stak

Sløjfer i en sammenkædet liste kan findes ved hjælp af en stak og metoden 'dybde-først søgning' (DFS). Det grundlæggende koncept er at gentage den linkede liste og skubbe hver node ind på stakken, hvis den ikke allerede er blevet besøgt. En løkke genkendes, hvis en knude, der allerede er på stakken, stødes på igen.

Her er en kort beskrivelse af proceduren:

1. 1. Opret en tom stak og en variabel for at registrere de noder, der er blevet besøgt.
   2. Skub den linkede liste over på stakken, startende øverst. Noter, at hovedet er blevet besøgt.
   3. Skub den næste node på listen over på stakken. Tilføj et besøgsmærke til denne node.
   4. Når du krydser listen, skal du skubbe hver ny node ind på stakken for at angive, at den er blevet besøgt.
   5. Tjek for at se, om en node, der tidligere er blevet besøgt, er øverst på stakken, hvis den stødes på. Hvis det er tilfældet, er der fundet en løkke, og løkken identificeres af noderne i stakken.
   6. Pop noderne af stakken, og fortsæt med at krydse listen, hvis der ikke findes en løkke.

C++ programimplementering for ovenstående metode (Stack)

Produktion:

Forklaring:

Dette program bruger en stak til at finde ud af, om en enkelt-linket liste har en loop.

• 1. Input/output-strømbiblioteket og stakbiblioteket er begge til stede i den første linje.

  2. Standardnavneområdet er inkluderet i den anden linje, hvilket giver os adgang til input/output stream-bibliotekets funktioner uden at skulle præfikse dem med 'std::.'

  3. Den følgende linje definerer strukturknuden, som består af to medlemmer: et heltal kaldet 'data' og en pointer til en anden knude kaldet 'næste'.

  4. Den linkede listes hoved er et input til metoden detectLoopLinkedList(), som er defineret på næste linje. Funktionen producerer en boolsk værdi, der angiver, om der blev fundet en sløjfe eller ej.

  5. En stak knudepunkter kaldet 'stack' og en pegepind til en knude ved navn 'tempNode', der er initialiseret med værdien af ​​headNode, oprettes begge inde i funktionen.

  6. Så, så længe tempNode ikke er en nul-pointer, går vi ind i en while-løkke.

  (a) Det øverste element i stakken skal matche den aktuelle node, for at vi kan fastslå, at den ikke er tom. Vi returnerer sandt, hvis dette er tilfældet, fordi der er fundet en loop.

  (b) Hvis den førnævnte betingelse er falsk, skubbes den aktuelle nodemarkør ind på stakken, og tempNode sættes til den følgende node i den sammenkædede liste.

  7. Vi returnerer falsk efter while-løkken, fordi der ikke blev observeret nogen loop.

  8. Vi bygger tre Node-objekter og initialiserer dem i main()-funktionen. Da der ikke er nogen loop i det første eksempel, indstiller vi de 'næste' pointere for hver Node korrekt.

Konklusion:

Som konklusion afhænger den bedste metode til at opdage sløjfer i en sammenkædet liste af den specifikke brugssituation og begrænsningerne for problemet. Hash Table og Floyds cyklusfindingsalgoritme er effektive metoder, og de bruges meget i praksis. Stack og rekursion er mindre effektive metoder, men de er mere intuitive.