Oppdage en sløyfe i en koblet liste i C ++

Sluttnoden til en koblet liste som har en løkke vil referere til en annen node i samme liste i stedet for null.Hvis det er en node i en koblet liste som gjentatte ganger kan nås ved å følge neste peker, sies listen å ha en syklus.

Vanligvis refererer den koblede listens siste node til en nullhenvisning for å betegne listens konklusjon. Imidlertid, i en koblet liste med en loop, refererer sluttnoden til listen til en startnode, en intern node eller seg selv. Derfor må vi under slike omstendigheter identifisere og avslutte sløyfen ved å sette den neste nodens referanse til null. Deteksjonsdelen av løkken i en lenket liste er forklart i denne artikkelen.

I C ++ er det mange måter å finne løkker i en lenket liste:

Hash-tabellbasert tilnærming: Denne tilnærmingen lagrer adressene til besøkte noder i et hasjbord. En sløyfe i den koblede listen eksisterer hvis en node allerede er til stede i hasjbordet når den blir besøkt igjen.

Floyds syklus tilnærming: Algoritmen “Tortoise and Hare”. Den raskere pekeren vil til slutt overhale den langsommere pekeren hvis det er en sløyfe i den koblede listen, og avslører eksistensen av løkken.

Rekursiv metode: Denne metoden går gjennom den koblede listen ved å ringe seg om og om igjen. Den koblede listen inneholder en sløyfe hvis den gjeldende noden tidligere har blitt besøkt.

Stackbasert tilnærming: Denne tilnærmingen lagrer adressene til besøkte noder i en stabel. En sløyfe i den koblede listen er til stede hvis en node allerede er der i stabelen når den blir besøkt igjen.

La oss forklare hver tilnærming i detalj for å forstå konseptet.

Tilnærming 1: Hashset tilnærming

Å bruke hashing er den mest enkle metoden. Her går vi gjennom listen en etter en mens vi holder et hasjbord med nodeadressene. Derfor eksisterer en sløyfe hvis vi noen gang kjører over neste adresse til den gjeldende noden som allerede er inneholdt i hasjbordet. Ellers er det ingen sløyfe i den koblede listen hvis vi støter på null (i.e., nå slutten av den koblede listen).

Det vil være ganske enkelt å implementere denne strategien.

Mens vi krysser den koblede listen, bruker vi en uordnede_hashmap og fortsetter å legge til noder til den.

Når vi først kommer over en node som allerede er vist på kartet, vil vi vite at vi har kommet til Loops begynnelse.

• • I tillegg holdt vi to tips på hvert trinn, headnode peker på den nåværende noden og lastnode peker på den tidligere noden til den gjeldende noden, mens jeg itererer.
  • Som vår headnode peker nå på startnoden til loopen og som lastnode pekte på noden som hodet pekte på (jeg.e., det refererer til lastnode av sløyfen), vår headnode peker for øyeblikket på startnoden til loopen.
  • Løkken vil bli ødelagt ved å sette LAstNode-> Neste == NULL.

Ved å gjøre dette, begynner sluttsløyfeknuten i stedet for å referere til sløyfens innledende node, å peke på null.

Hashing -metodens gjennomsnittlige tid og romkompleksitet er O (n). Leseren skal alltid være klar over at implementeringen av den innebygde hashingdatastrukturen i programmeringsspråket vil avgjøre den totale tidskompleksiteten i tilfelle en kollisjon i hashing.

C ++ programimplementering for metoden ovenfor (Hashset):

#inkludere
ved hjelp av navneområdet STD;
struct node
int verdi;
struct node* Neste;
;
Node* newNode (int -verdi)

Node* tempnode = ny node;
tempnode-> verdi = verdi;
tempnode-> neste = null;
return tempnode;

// identifisere og eliminere potensielle løkker
// i en koblet liste med denne funksjonen.
void FunctionHashMap (Node* HeadNode)

// opprettet et uordnede_map for å implementere hash -kart
uordnede_map hash_map;
// peker til lastnode
Node* lastNode = null;
mens (headnode != Null)
// Hvis en node mangler fra kartet, kan du legge den til.
if (hash_map.finn (headnode) == hash_map.slutt())
hash_map [headnode] ++;
lastNode = headnode;
headnode = headnode-> neste;

// Hvis en syklus er til stede, sett den endelige nodens neste peker til NULL.
annet
lastNode-> neste = null;
gå i stykker;



// Vis koblet liste
void display (node* headnode)

mens (headnode != Null)
cout headnode = headnode-> neste;

cout << endl;

/* Hovedfunksjon*/
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);
/ * Lag en sløyfe i LinkedList */
headnode-> next-> next-> next-> next-> next = headnode-> next-> next;
funksjonHashMap (headnode);
printf ("Linked List Without Loop \ n");
display (headnode);
retur 0;

Produksjon:

Koblet liste uten loop
48 18 13 2 8

Kodenes trinn-for-trinn-forklaring er gitt nedenfor:

1. 1. Bitene/STDC++.H> overskriftsfil, som inneholder alle de vanlige C ++ -bibliotekene, er inkludert i koden.
   2. En struktur som heter "Node" er konstruert, og den har to medlemmer: en referanse til neste node i listen og et heltall kalt “Verdi.”
   3. Med en heltallverdi som inngang og "neste" peker satt til NULL, oppretter funksjonen "NewNode" en ny node med den verdien.
   4. Funksjonen 'FunctionHashMap ' er definert, som tar en peker til hodeknuten til den koblede listen som input.
   5. Inne i 'FunctionHashMap'Funksjon, en uordnede_map som heter' Hash_Map 'er opprettet, som brukes til å implementere en hash -kartdatastruktur.
   6. En peker til den siste noden på listen initialiseres til null.
   7. En stund loop brukes til å krysse den koblede listen, som starter fra hodeknuten og fortsetter til hodeknuten er null.
   8. LastNode -pekeren blir oppdatert til den gjeldende noden i While Loop hvis den gjeldende noden (headnode) ikke allerede er til stede på hash -kartet.
   9. Hvis den gjeldende noden finnes på kartet, betyr det at en sløyfe er til stede i den koblede listen. For å fjerne sløyfen, den neste pekeren til lastnode er satt til NULL Og mens sløyfen er ødelagt.
   10. Den koblede listens hodeknute brukes som inngang for en funksjon som kalles "display", som sender ut verdien til hver node i listen fra begynnelse til finish.
   11. I hoved- funksjon, lage en sløyfe.
   12. Funksjonen 'FunctionHashMap' kalles med headnode -pekeren som input, som fjerner løkken fra listen.
   13. Den modifiserte listen vises ved hjelp av "display" -funksjonen ".

Tilnærming 2: Floyds syklus

Floyds syklusdeteksjonsalgoritme, ofte kjent som skilpadden og Hare -algoritmen, gir grunnlaget for denne metoden for å lokalisere sykluser i en lenket liste. Den "langsomme" pekeren og den "raske" pekeren, som krysser listen i forskjellige hastigheter, er de to pekerne som brukes i denne teknikken. Den raske pekeren avanserer to trinn, mens den langsomme pekeren fremmer ett trinn hver iterasjon. En syklus i den koblede listen eksisterer hvis de to punktene noen gang kommer ansikt til ansikt.

1. Med den koblede listenes hodeknute, initialiserer vi to tips som heter Fast and Slow.

2. Nå kjører vi en løkke for å bevege oss gjennom den koblede listen. Den raske pekeren skal flyttes to steder foran den langsomme pekeren på hver iterasjons trinn.

3. Det vil ikke være en sløyfe i den koblede listen hvis den raske pekeren når slutten av listen (FastPointer == null eller FastPointer-> neste == null). Hvis ikke, vil de raske og sakte pekerne til slutt møtes, noe som betyr at den koblede listen har en loop.

C ++ programimplementering for metoden ovenfor (Floyds syklus):

#inkludere
ved hjelp av navneområdet STD;
/ * Linkeliste node */
struct node
int -data;
struct node* Neste;
;
/* Funksjon for å fjerne sløyfe. */
void Deleteloop (struct Node*, struct Node*);
/* Denne funksjonen lokaliserer og eliminerer listeløkker. Det gir 1
Hvis det var en sløyfe i listen; ellers returnerer det 0. */
int detectandDeleteloop (struct node* list)

Struct Node *SlowPtr = liste, *FastPtr = liste;
// iterere for å sjekke om løkken er der.
while (slowPtr && fastPtr && fastPtr-> neste)
SlowPtr = SlowPtr-> Neste;
FastPtr = FastPtr-> Neste-> Neste;
/* Hvis SlowPtr og FastPtr møtes på et tidspunkt der
er en sløyfe */
if (slowPtr == fastPtr)
Deleteloop (SlowPtr, liste);
/* Retur 1 for å indikere at en sløyfe er blitt oppdaget. */
retur 1;


/* Retur 0 for å indikere at ingen sløyfe er blitt oppdaget.*/
retur 0;

/* Funksjon for å slette loop fra koblet liste.
Loopnode peker på en av sløyfeknuter og headnode peker
til startnoden på den koblede listen */
void Deleteloop (struct Node* loopnode, struct node* headnode)

struct node* ptr1 = loopnode;
struct node* ptr2 = loopnode;
// tell hvor mange noder som er i løkken.
usignert int k = 1, i;
mens (ptr1-> neste != ptr2)
ptr1 = ptr1-> neste;
K ++;

// fikse en peker til headnode
ptr1 = headnode;
// og den andre pekeren til K -noder etter headnode
ptr2 = headnode;
for (i = 0; i < k; i++)
ptr2 = ptr2-> neste;
/* Når begge punktene flyttes samtidig,
De vil kollidere ved sløyfens begynnende node. */
mens (PTR2 != ptr1)
ptr1 = ptr1-> neste;
ptr2 = ptr2-> neste;

// få nodens siste peker.
mens (ptr2-> neste != PTR1)
ptr2 = ptr2-> neste;
/* For å lukke sløyfen, sett den påfølgende
Node til sløyfens avsluttende node. */
ptr2-> neste = null;

/ * Funksjon for å vise koblet liste */
void displayLinkedList (struct node* node)

// Vis den koblede listen etter sletting av sløyfen
mens (node != Null)
cout node = node-> neste;


struct node* newnode (int tast)

struktur node* temp = ny node ();
temp-> data = nøkkel;
temp-> neste = null;
Retur Temp;

// Hovedkode
int main ()

struct node* 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);
/ * Lag en sløyfe */
headnode-> next-> next-> next-> next-> next = headnode-> next-> next;
// Vis sløyfen i koblet liste
// displayLinkedList (headnode);
detectandDeleteloop (headnode);
cout << "Linked List after no loop \n";
displayLinkedList (headnode);
retur 0;

Produksjon:

Koblet liste etter ingen sløyfe
48 18 13 2 8

Forklaring:

1. 1. De relevante overskriftene, for eksempel “BITS/STDC++.H ”og“ std :: cout, ”er først inkludert.
   2. "Node" -strukturen, som står for en node i den koblede listen, blir deretter erklært. En neste peker som fører til følgende node i listen er inkludert sammen med et heltalldatafelt i hver node.
   3. Deretter definerer den "Deleteloop" og "DetectandDeleteloop", to funksjoner. En sløyfe fjernes fra en koblet liste ved hjelp av den første metoden, og en sløyfe blir oppdaget i listen ved hjelp av den andre funksjonen, som deretter kaller den første prosedyren for å fjerne sløyfen.
   4. En ny koblet liste med fem noder opprettes i hovedfunksjonen, og en sløyfe etableres ved å sette den siste nodens neste peker til den tredje noden.
   5. Det ringer deretter til metoden "DetectandDeleteloop" mens du passerer den koblede listenes hodeknute som et argument. For å identifisere løkker, bruker denne funksjonen "langsomme og raske pekere" -tilnærmingen. Den bruker to tips som begynner øverst på listen, SlowPTR og FastPTR. Mens den raske pekeren beveger to noder på en gang, beveger den langsomme pekeren bare en node om gangen. Den raske pekeren vil til slutt overhale den langsomme pekeren hvis listen inneholder en sløyfe, og de to punktene vil kollidere med samme node.
   6. Funksjonen påkaller "Deleteloop" -funksjonen hvis den finner en sløyfe, og gir hodeknuten på listen og skjæringspunktet mellom de langsomme og raske pekerne som innganger. Denne prosedyren etablerer to pekere, PTR1 og PTR2, til listenes hodeknute og teller antall noder i løkken. Etter det fremmer den en peker K -noder, der K er det totale antallet noder i løkken. Så inntil de møtes i starten av løkken, fremmer den begge peker en node om gangen. Løyfen blir deretter ødelagt ved å sette den neste pekeren til noden i enden av løkken til null.
   7. Etter å ha fjernet sløyfen, viser den den koblede listen som et siste trinn.

Tilnærming 3: rekursjon

Rekursjon er en teknikk for å løse problemer ved å dele dem inn i mindre, enklere underproblemer. Rekursjon kan brukes til å krysse en enkelt koblet liste i tilfelle at en sløyfe blir funnet ved kontinuerlig å kjøre en funksjon for neste node i listen til listenes slutt er nådd.

I en enkelt koblet liste er det grunnleggende prinsippet bak ved bruk Den noden. Metoden vil iterere over den fulle koblede listen fordi den kalles rekursivt.

Listen inneholder en sløyfe hvis en node som tidligere er blitt merket som besøkt, blir møtt av funksjonen; I dette tilfellet kan funksjonen komme tilbake. Metoden kan returnere falsk hvis den når slutten av listen uten å løpe over en besøkt node, noe som indikerer at det ikke er noen sløyfe.

Selv om denne teknikken for å bruke rekursjon for å finne en sløyfe i en enkelt koblet liste er enkel å bruke og forstå, er det kanskje ikke den mest effektive når det gjelder tid og romkompleksitet.

C ++ programimplementering for metoden ovenfor (rekursjon):

#inkludere
ved hjelp av navneområdet STD;
struct node
int -data;
Node* Neste;
Bool besøkte;
;
// Linked List Loop Detection Function
bool detectlooplinkedlist (node* headnode)
if (headnode == null)
return falsk; // Hvis den koblede listen er tom, er den grunnleggende saken

// det er en sløyfe hvis den nåværende noden har
// allerede blitt besøkt.
if (headnode-> besøkt)
return True;

// Legg til et besøksmerke til den nåværende noden.
headnode-> besøkte = true;
// å ringe koden for den påfølgende noden gjentatte ganger
returdetektloplinkedlist (headnode-> neste);

int main ()
Node* headnode = new node ();
Node* SecondNode = new Node ();
Node* ThirdNode = New Node ();
headnode-> data = 1;
headnode-> next = SecondNode;
headnode-> besøkte = falsk;
SecondNode-> Data = 2;
SecondNode-> Next = ThirdNode;
SecondNode-> Besøkt = falsk;
ThirdNode-> Data = 3;
ThirdNode-> neste = null; // Ingen sløyfe
ThirdNode-> Besøkt = falsk;
if (detectLooplinkedList (headnode))
cout << "Loop detected in linked list" << endl;
annet
cout << "No loop detected in linked list" << endl;

// lage en løkke
ThirdNode-> Neste = SecondNode;
if (detectLooplinkedList (headnode))
cout << "Loop detected in linked list" << endl;
annet
cout << "No loop detected in linked list" << endl;

retur 0;

Produksjon:

Ingen sløyfe oppdaget i koblet liste
Loop oppdaget i koblet liste

Forklaring:

1. 1. Funksjonen DetectLooplinkedList () I dette programmet aksepterer sjefen for den koblede listen som en inndata.
   2. Rekursjon brukes av funksjonen for å iterere på tvers av den koblede listen. Som den grunnleggende saken for rekursjonen begynner det med å avgjøre om den nåværende noden er null. I så fall returnerer metoden falsk, noe som indikerer at det ikke eksisterer noen sløyfe.
   3. Verdien av den nåværende nodens "besøkte" eiendom blir deretter sjekket for å se om den tidligere er blitt besøkt. Det returnerer sant hvis det er blitt besøkt, noe som antyder at det er funnet en sløyfe.
   4. Funksjonen markerer den nåværende noden som besøkt hvis den allerede har blitt besøkt ved å endre sin "besøkte" eiendom til True.
   5. Verdien av den besøkte variabelen blir deretter sjekket for å se om den gjeldende noden har blitt besøkt tidligere. Hvis den har blitt brukt før, må en sløyfe eksistere, og funksjonen returnerer sann.
   6. Til slutt kaller funksjonen seg med neste node i listen ved å passere headnode-> Neste som et argument. Rekursivt, Dette blir utført til enten en sløyfe er funnet eller at alle noder har blitt besøkt. Midler, funksjonen setter den besøkte variabelen til sann hvis den gjeldende noden aldri har blitt besøkt før de rekursivt ringer seg for følgende node i den koblede listen.
   7. Koden bygger tre noder og blir med dem for å produsere en koblet liste i hovedfunksjon. Metoden DetectLooplinkedList () blir deretter påkalt på listenes hodeknute. Programmet produserer “Loop trukket fra lenket liste”Hvis DetectLooplinkedList () Returnerer sann; ellers gir det ut "Ingen sløyfe oppdaget i koblet liste“.
   8. Koden setter deretter inn en loop i den koblede listen ved å angi den siste nodens neste peker til den andre noden. Avhengig av resultatet av funksjonen, kjører den DetectLooplinkedList () igjen og produserer enten "Loop trukket fra lenket liste”Eller“Ingen sløyfe oppdaget i koblet liste.”

Tilnærming 4: Bruke stabel

Løkker i en lenket liste finner du ved hjelp av en stabel og metoden “Dybde-First Search” (DFS). Det grunnleggende konseptet er å iterere gjennom den koblede listen, skyve hver node på stabelen hvis den ikke allerede er besøkt. En sløyfe gjenkjennes hvis en node som allerede er på bunken, oppstår igjen.

Her er en kort beskrivelse av prosedyren:

1. 1. Lag en tom stabel og en variabel for å registrere nodene som er besøkt.
   2. Skyv den koblede listen på bunken, og start øverst. Noter at hodet er besøkt.
   3. Skyv neste node i listen på bunken. Legg til et besøksmerke i denne noden.
   4. Når du krysser listen, skyver du hver nye node på stabelen for å indikere at den er besøkt.
   5. Sjekk for å se om en node som tidligere er blitt besøkt, er øverst i stabelen hvis den oppstår. I så fall er det funnet en sløyfe, og sløyfen blir identifisert av nodene i stabelen.
   6. Pop nodene av stabelen og fortsett å krysse listen hvis ingen sløyfe er funnet.

C ++ programimplementering for metoden ovenfor (stabel)

#inkludere
#inkludere
ved hjelp av navneområdet STD;
struct node
int -data;
Node* Neste;
;
// Funksjon for å oppdage sløyfe i en koblet liste
bool detectlooplinkedlist (node* headnode)
stable stable;
Node* tempnode = headnode;
mens (tempnode != Null)
// Hvis det øverste elementet i stabelen stemmer overens
// Den gjeldende noden og stabelen er ikke tom
hvis (!stable.tom () && stabel.topp () == tempnode)
return True;

stable.push (tempnode);
tempnode = tempnode-> neste;

return falsk;

int main ()
Node* headnode = new node ();
Node* SecondNode = new Node ();
Node* ThirdNode = New Node ();
headnode-> data = 1;
headnode-> next = SecondNode;
SecondNode-> Data = 2;
SecondNode-> Next = ThirdNode;
ThirdNode-> Data = 3;
ThirdNode-> neste = null; // Ingen sløyfe
if (detectLooplinkedList (headnode))
cout << "Loop detected in linked list" << endl;
annet
cout << "No loop detected in linked list" << endl;

// lage en løkke
ThirdNode-> Neste = SecondNode;
if (detectLooplinkedList (headnode))
cout << "Loop detected in linked list" << endl;
annet
cout << "No loop detected in linked list" << endl;

Produksjon:

Ingen sløyfe oppdaget i koblet liste
Loop oppdaget i koblet liste

Forklaring:

Dette programmet bruker en stabel for å finne ut om en enkelt koblet liste har en loop.

• 1. Inngangs-/utgangsstrømbiblioteket og stabelbiblioteket er begge til stede i første linje.

  2. Standard navneområdet er inkludert i den andre linjen, slik at vi får tilgang til input/output stream -bibliotekets funksjoner uten å måtte prefiksere dem med “STD ::.”

  3. Følgende linje definerer strukturnoden, som består av to medlemmer: et heltall kalt “data” og en peker til en annen node kalt “Neste.”

  4. Hodet til den koblede listen er en inngang for metoden detektloplinkedlist (), som er definert på neste linje. Funksjonen produserer en boolsk verdi som indikerer om det ble funnet en sløyfe eller ikke.

  5. En bunke med nodekonkurranser kalt “Stack” og en peker til en node som heter “Tempnode” som initialiseres med verdien av headnode er begge opprettet inne i funksjonen.

  6. Så, så lenge tempnode ikke er en nullpeker, legger vi inn en stund loop.

  (a) Det øverste elementet i stabelen må samsvare med den nåværende noden for at vi skal bestemme at den ikke er tom. Vi returnerer sant hvis dette er tilfelle fordi en sløyfe er funnet.

  (b) Hvis den nevnte tilstanden er falsk, skyves den gjeldende nodepekeren på bunken, og tempnode er satt til følgende node i den koblede listen.

  7. Vi returnerer usant etter stundsløyfen fordi ingen sløyfe ble observert.

  8. Vi bygger tre nodeobjekter og initialiserer dem i hovedfunksjonen (). Siden det ikke er noen sløyfe i det første eksemplet, setter vi "neste" pekere i hver node ordentlig.

Konklusjon:

Avslutningsvis avhenger den beste metoden for å oppdage løkker i en koblet liste av den spesifikke brukssaken og begrensningene i problemet. Hash-tabell og Floyds sykkelfinningsalgoritme er effektive metoder, og de er mye brukt i praksis. Stabel og rekursjon er mindre effektive metoder, men de er mer intuitive.