Linkitetyn luettelon loppusolmu, jossa on silmukka, viittaa toiseen solmuun samassa luettelossa NULL:n sijaan. Jos linkitetyssä luettelossa on solmu, jota voidaan käyttää toistuvasti seuraamalla seuraavaa osoitinta, luettelon sanotaan olevan on sykli.
Tyypillisesti linkitetyn listan viimeinen solmu viittaa NULL-viitteeseen, joka ilmaisee luettelon johtopäätöksen. Kuitenkin linkitetyssä luettelossa, jossa on silmukka, luettelon loppusolmu viittaa aloitussolmuun, sisäiseen solmuun tai itseensä. Siksi tällaisissa olosuhteissa meidän on tunnistettava ja päätettävä silmukka asettamalla seuraavan solmun viittaukseksi NULL. Tässä artikkelissa selitetään linkitetyn luettelon silmukan tunnistusosa.
C++:ssa on lukuisia tapoja löytää silmukoita linkitetystä luettelosta:
Hash-taulukkoon perustuva lähestymistapa : Tämä lähestymistapa tallentaa vierailtujen solmujen osoitteet hash-taulukkoon. Linkitetyssä luettelossa on silmukka, jos solmu on jo läsnä hash-taulukossa, kun siinä käydään uudelleen.
Floydin kiertolähestymistapa : Kilpikonna ja jänis -algoritmi, joka tunnetaan yleisesti Floydin syklin etsintäalgoritmina: Tämä tekniikka käyttää kahta osoitinta, joista toinen liikkuu hitaammin kuin toinen ja toinen nopeammin. Nopeampi osoitin ohittaa lopulta hitaamman osoittimen, jos linkitetyssä luettelossa on silmukka, mikä paljastaa silmukan olemassaolon.
Rekursiivinen menetelmä : Tämä menetelmä käy linkitettyjen luettelon läpi kutsumalla itseään yhä uudelleen ja uudelleen. Linkitetty luettelo sisältää silmukan, jos nykyisessä solmussa on vieraillut aiemmin.
Pinopohjainen lähestymistapa : Tämä lähestymistapa tallentaa vierailtujen solmujen osoitteet pinoon. Linkitetyssä luettelossa on silmukka, jos solmu on jo pinossa, kun siinä käydään uudelleen.
Selitetään jokainen lähestymistapa yksityiskohtaisesti käsitteen ymmärtämiseksi.
Lähestymistapa 1: HashSet-lähestymistapa
Hajautusmenetelmän käyttäminen on yksinkertaisin tapa. Tässä käymme luettelon läpi yksitellen pitäen samalla hash-taulukkoa solmuosoitteilla. Siksi silmukka on olemassa, jos koskaan törmäämme nykyisen solmun seuraavaan osoitteeseen, joka on jo sisällytetty hash-taulukkoon. Muuten linkitetyssä luettelossa ei ole silmukkaa, jos kohtaamme NULL-arvon (eli saavutamme linkitetyn luettelon loppuun).
Tämän strategian toteuttaminen tulee olemaan melko helppoa.
Kun käytämme linkitettyä luetteloa, käytämme unordered_hashmappia ja lisäämme siihen jatkuvasti solmuja.
Nyt kun törmäämme solmuun, joka näkyy jo kartalla, tiedämme, että olemme saapuneet silmukan alkuun.
-
- Lisäksi pidimme jokaisessa vaiheessa kaksi osoitinta, headNode osoittaa nykyiseen solmuun ja lastNode osoittaa nykyisen solmun aiempaan solmuun iteroitaessa.
- Kuin meidän headNode osoittaa nyt silmukan aloitussolmua ja as lastNode osoitti solmuun, johon pää osoitti (eli se viittaa lastNode silmukasta), meidän headNode osoittaa tällä hetkellä silmukan aloitussolmua.
- Silmukka katkeaa asettamalla l astNode->seuraava == NULL .
Näin tekemällä päättyvä silmukkasolmu alkaa viitata silmukan alkuperäiseen solmuun, vaan alkaa osoittaa NULL:aan.
Hajautusmenetelmän keskimääräinen aika- ja tilamonimutkaisuus on O(n). Lukijan tulee aina olla tietoinen siitä, että sisäänrakennetun hajautustietorakenteen toteutus ohjelmointikielessä määrittää kokonaisaikaisen monimutkaisuuden tiivistyksen törmäyksen sattuessa.
C++-ohjelman toteutus yllä olevalle menetelmälle (HashSet):
#include
käyttäen nimiavaruutta std;
struct Node {
int arvo;
struct Node * Seuraava;
} ;
Solmu * newNode ( int arvo )
{
Solmu * tempNode = uusi solmu;
tempNode- > arvo = arvo;
tempNode- > seuraava = NULL;
palata tempNode;
}
// Tunnista ja poista mahdolliset silmukat
// sisään linkitetty luettelo tällä toiminnolla.
void functionHashMap ( Solmu * headNode )
{
// Luotu unordered_map ottaaksesi käyttöön Hash-kartan
unordered_map < Solmu * , int > hash_map;
// osoitin lastNodeen
Solmu * lastNode = NULL;
sillä aikaa ( headNode ! = NULL ) {
// Jos solmu puuttuu kartasta, lisää se.
jos ( hash_map.find ( headNode ) == hash_map.end ( ) ) {
hash_map [ headNode ] ++;
lastNode = headNode;
headNode = headNode- > Seuraava;
}
// Jos sykli on olemassa, aseta viimeinen solmu Seuraava osoitin NULL.
else {
lastNode->next = NULL;
tauko;
}
}
}
// Näytä linkitetty luettelo
tyhjä näyttö (Node* headNode)
{
while (headNode != NULL) {
cout << headNode->arvo << ' ';
headNode = headNode->seuraava;
}
cout << endl;
}
/* Päätoiminto*/
int main()
{
Solmu* headNode = uusiSolmu(48);
headSolmu->seuraava = headNode;
headSolmu->seuraava = uusiSolmu(18);
headSolmu->seuraava->seuraava = uusiSolmu(13);
headSolmu->seuraava->seuraava->seuraava = uusiSolmu(2);
headSolmu->seuraava->seuraava->seuraava->seuraava = uusiSolmu(8);
/* Luo silmukka linkedListissä */
headNode->seuraava->seuraava->seuraava->seuraava->seuraava = headNode->seuraava->seuraava;
functionHashMap(headNode);
printf('Linkitetty lista ilman silmukkaa \n');
näyttö (headNode);
paluu 0;
}
Lähtö:
Linkitetty luettelo ilman silmukkaa
48 18 13 2 8
Alla on koodin vaiheittainen selitys:
-
- Bits/stdc++.h>-otsikkotiedosto, joka sisältää kaikki yleiset C++-kirjastot, sisältyy koodiin.
- Rakenne nimeltä 'Solmu' on rakennettu, ja siinä on kaksi jäsentä: viittaus luettelon seuraavaan solmuun ja kokonaisluku nimeltä 'arvo'.
- Kun syötteenä on kokonaisluku ja 'seuraava'-osoittimen arvoksi on asetettu NULL, funktio 'newNode' luo uuden solmun tällä arvolla.
- Toiminto ' functionHashMap' on määritelty, joka ottaa syötteeksi osoittimen linkitetyn luettelon pääsolmuun.
- Sisällä ' FunctionHashMap '-funktiossa luodaan 'hash_map'-niminen järjestämätön_kartta, jota käytetään hajautuskarttatietorakenteen toteuttamiseen.
- Osoitin luettelon viimeiseen solmuun alustetaan arvoon NULL.
- Linkitetyn listan läpi kulkemiseen käytetään while-silmukkaa, joka alkaa pääsolmusta ja jatkuu, kunnes pääsolmu on NULL.
- LastNode-osoitin päivitetään nykyiseen silmukan sisällä olevaan solmuun, jos nykyinen solmu (headNode) ei ole jo läsnä hash-kartassa.
- Jos nykyinen solmu löytyy kartasta, se tarkoittaa, että linkitetyssä luettelossa on silmukka. Poistaaksesi silmukan, seuraava osoitin lastNode on asetettu TYHJÄ ja while-silmukka katkeaa.
- Linkitetyn luettelon pääsolmua käytetään syötteenä funktiolle nimeltä 'näyttö', joka tulostaa luettelon jokaisen solmun arvon alusta loppuun.
- Vuonna pää toiminto, joka luo silmukan.
- Funktiota 'functionHashMap' kutsutaan HeadNode-osoitin syötteenä, joka poistaa silmukan luettelosta.
- Muokattu luettelo näytetään 'näyttö'-toiminnolla.
Lähestymistapa 2: Floydin sykli
Floydin syklintunnistusalgoritmi, joka tunnetaan usein nimellä kilpikonna- ja jänisalgoritmi, tarjoaa perustan tälle menetelmälle syklien paikantamiseksi linkitetystä luettelosta. 'Hidas' osoitin ja 'nopea' osoitin, jotka kulkevat luettelon läpi eri nopeuksilla, ovat kaksi tässä tekniikassa käytettyä osoitinta. Nopea osoitin siirtyy kaksi askelta eteenpäin, kun taas hidas osoitin siirtyy yhden askeleen joka iteraatio. Linkitetyssä luettelossa on sykli, jos nämä kaksi pistettä kohtaavat joskus vastakkain.
1. Linkitetyn luettelon pääsolmulla alustamme kaksi osoitinta, joita kutsutaan nopeaksi ja hitaaksi.
2. Nyt suoritamme silmukan siirtyäksemme linkitetyn luettelon läpi. Nopeaa osoitinta tulee siirtää kaksi paikkaa hitaan osoittimen eteen kunkin iteroinnin vaiheessa.
3. Linkitetyssä luettelossa ei ole silmukkaa, jos nopea osoitin saavuttaa luettelon loppuun (fastPointer == NULL tai fastPointer->seuraava == NULL). Jos ei, nopeat ja hitaat osoittimet kohtaavat lopulta, mikä tarkoittaa, että linkitetyssä luettelossa on silmukka.
C++-ohjelman toteutus yllä olevalle menetelmälle (Floyd's Cycle):
#include
käyttäen nimiavaruutta std;
/* Linkkiluettelon solmu */
struct Node {
int tiedot;
struct Node * Seuraava;
} ;
/* Toiminto silmukan poistamiseksi. */
void deleteLoop ( struct Node * , struct Node * ) ;
/* Tämä toiminto paikantaa ja poistaa luettelosilmukat. Se antaa periksi 1
jos siellä oli silmukka sisään lista; muu , se palaa 0 . */
int detectAndDeleteLoop ( struct Node * lista )
{
struct Node * hidasPTR = luettelo, * fastPTR = lista;
// Toista tarkistaaksesi jos silmukka on siellä.
sillä aikaa ( hidasPTR && nopea PTR && nopea PTR- > Seuraava ) {
hidasPTR = hidasPTR- > Seuraava;
fastPTR = nopea PTR- > Seuraava- > Seuraava;
/* Jos slowPTR ja fastPTR kohtaavat jossain vaiheessa sitten siellä
on silmukka */
jos ( hidasPTR == nopeaPTR ) {
Poista Loop ( hidasPTR, lista ) ;
/* Palata 1 osoittamaan, että silmukka on löydetty. */
palata 1 ;
}
}
/* Palata 0 osoittamaan, ettei silmukkaa ole löydetty. */
palata 0 ;
}
/* Toiminto silmukan poistamiseksi linkitetystä luettelosta.
loopNode osoittaa yhteen silmukkasolmuista ja headNode osoittaa
linkitetyn luettelon aloitussolmuun */
void deleteLoop ( struct Node * loopNode, struct Node * headNode )
{
struct Node * ptr1 = silmukkasolmu;
struct Node * ptr2 = silmukkasolmu;
// Laske kuinka monta solmua on sisään silmukka.
unsigned int k = 1 , i;
sillä aikaa ( ptr1- > Seuraava ! = ptr2 ) {
ptr1 = ptr1- > Seuraava;
k++;
}
// Korjaa yksi osoitin headNodeen
ptr1 = pääsolmu;
// Ja toinen osoitin k solmuun headNoden jälkeen
ptr2 = pääsolmu;
varten ( minä = 0 ; i < k; i++ )
ptr2 = ptr2- > Seuraava;
/* Kun molempia pisteitä siirretään samanaikaisesti,
ne törmäävät silmukassa n aloitussolmu. */
while (ptr2 != ptr1) {
ptr1 = ptr1->seuraava;
ptr2 = ptr2->seuraava;
}
// Hanki solmu' s kestää osoitin.
sillä aikaa ( ptr2- > Seuraava ! = ptr1 )
ptr2 = ptr2- > Seuraava;
/* Sulkeaksesi silmukan, aseta myöhempi
solmu silmukalle päättävä solmu. */
ptr2->seuraava = NULL;
}
/* Toiminto linkitettyjen luettelon näyttämiseen */
void displayLinkedList(struct Node* node)
{
// näyttää linkitetyn luettelon silmukan poistamisen jälkeen
while (solmu != NULL) {
cout << solmu->data << ' ';
solmu = solmu->seuraava;
}
}
struct Node* newNode(int-avain)
{
struct Node* temp = new Node();
temp->data = avain;
temp->seuraava = NULL;
paluulämpötila;
}
// Pääkoodi
int main()
{
struct Node* headNode = uusiSolmu(48);
headSolmu->seuraava = uusiSolmu(18);
headSolmu->seuraava->seuraava = uusiSolmu(13);
headSolmu->seuraava->seuraava->seuraava = uusiSolmu(2);
headSolmu->seuraava->seuraava->seuraava->seuraava = uusiSolmu(8);
/* Luo silmukka */
headNode->seuraava->seuraava->seuraava->seuraava->seuraava = headNode->seuraava->seuraava;
// näyttää silmukan linkitetyssä luettelossa
//displayLinkedList(headNode);
havaitaAndDeleteLoop(headNode);
cout << 'Linkitetty luettelo ilman silmukkaa \n';
displayLinkedList(headNode);
paluu 0;
}
Lähtö:
Linkitetty luettelo ilman silmukkaa
48 18 13 2 8
Selitys:
-
- Asiaankuuluvat otsikot, kuten 'bits/stdc++.h' ja 'std::cout', sisällytetään ensin.
- 'Solmu'-rakenne, joka tarkoittaa solmua linkitetyssä luettelossa, ilmoitetaan sitten. Seuraava osoitin, joka johtaa luettelon seuraavaan solmuun, ja jokaisessa solmussa on kokonaislukutietokenttä.
- Sitten se määrittelee 'deleteLoop' ja 'detectAndDeleteLoop', kaksi funktiota. Silmukka poistetaan linkitetystä luettelosta ensimmäisellä menetelmällä, ja silmukka tunnistetaan luettelosta toisella funktiolla, joka sitten kutsuu ensimmäistä proseduuria silmukan poistamiseksi.
- Päätoimintoon luodaan uusi linkitetty lista, jossa on viisi solmua, ja silmukka muodostetaan asettamalla viimeisen solmun seuraava osoitin kolmanteen solmuun.
- Sitten se kutsuu 'detectAndDeleteLoop' -menetelmää ja välittää linkitetyn luettelon pääsolmun argumenttina. Silmukoiden tunnistamiseen tämä toiminto käyttää 'Hitaat ja nopeat osoittimet' -lähestymistapaa. Se käyttää kahta osoitinta, jotka alkavat luettelon yläosasta, slowPTR ja fastPTR. Vaikka nopea osoitin siirtää kahta solmua kerralla, hidas osoitin siirtää vain yhtä solmua kerrallaan. Nopea osoitin ohittaa lopulta hitaan osoittimen, jos luettelo sisältää silmukan, ja kaksi pistettä törmäävät samassa solmussa.
- Funktio kutsuu “deleteLoop”-funktion, jos se löytää silmukan, syöttäen syötteinä listan pääsolmun sekä hitaiden ja nopeiden osoittimien leikkauskohdan. Tämä menettely määrittää kaksi osoitinta, ptr1 ja ptr2, luettelon pääsolmuun ja laskee silmukan solmujen määrän. Tämän jälkeen se siirtää yhden osoittimen k solmua eteenpäin, missä k on silmukan solmujen kokonaismäärä. Sitten, kunnes ne kohtaavat silmukan alussa, se siirtää molempia pisteitä eteenpäin yksi solmu kerrallaan. Silmukka katkaistaan sitten asettamalla silmukan lopussa olevan solmun seuraava osoitin arvoon NULL.
- Silmukan poistamisen jälkeen se näyttää linkitetyn luettelon viimeisenä vaiheena.
Lähestymistapa 3: Rekursio
Rekursio on tekniikka ongelmien ratkaisemiseksi jakamalla ne pienempiin, helpompiin osaongelmiin. Rekursiota voidaan käyttää yksitellen linkitetyn listan läpikulkuun siinä tapauksessa, että silmukka löytyy ajamalla jatkuvasti funktiota listan seuraavalle solmulle, kunnes listan loppu saavutetaan.
Yksittäin linkitetyssä luettelossa perusperiaate, jonka takana käytetään rekursiota silmukan etsimiseen, on aloittaa luettelon alusta, merkitä nykyinen solmu käydyksi jokaisessa vaiheessa ja jatkaa sitten seuraavaan solmuun kutsumalla rekursiivisesti funktio tuo solmu. Menetelmä toistuu koko linkitetyn luettelon yli, koska sitä kutsutaan rekursiivisesti.
Lista sisältää silmukan, jos funktio kohtaa solmun, joka on aiemmin merkitty vierailluksi; tässä tapauksessa funktio voi palauttaa tosi. Metodi voi palauttaa epätosi, jos se saavuttaa luettelon loppuun ilman, että se kulkee vieraillun solmun yli, mikä osoittaa, että silmukkaa ei ole.
Vaikka tämä tekniikka rekursion hyödyntämiseksi silmukan löytämiseksi yhdestä linkitetystä luettelosta on yksinkertaista käyttää ja ymmärtää, se ei ehkä ole tehokkain tekniikka ajan ja tilan monimutkaisuuden kannalta.
C++-ohjelman toteutus yllä olevalle menetelmälle (Recursion):
#include
käyttäen nimiavaruutta std;
struct Node {
int tiedot;
Solmu * Seuraava;
bool vieraili;
} ;
// Linkitetyn luettelon silmukan tunnistus toiminto
bool detectLoopLinkedList ( Solmu * headNode ) {
jos ( headNode == NULL ) {
palata väärä ; // Jos linkitetty luettelo on tyhjä, perus tapaus
}
// Siellä on silmukka jos nykyisellä solmulla on
// on jo vierailtu.
jos ( pääsolmu- > vieraili ) {
palata totta ;
}
// Lisää vierailumerkki nykyiseen solmuun.
pääsolmu- > vieraillut = totta ;
// Soittamalla koodia varten seuraava solmu toistuvasti
palata detectLoopLinkedList ( pääsolmu- > Seuraava ) ;
}
int main ( ) {
Solmu * headNode = uusi solmu ( ) ;
Solmu * secondNode = uusi solmu ( ) ;
Solmu * thirdNode = uusi solmu ( ) ;
pääsolmu- > data = 1 ;
pääsolmu- > seuraava = toinenSolmu;
pääsolmu- > vieraillut = väärä ;
toinen solmu- > data = 2 ;
toinen solmu- > seuraava = kolmassolmu;
toinen solmu- > vieraillut = väärä ;
kolmas solmu- > data = 3 ;
kolmas solmu- > seuraava = NULL; // Ei silmukkaa
kolmas solmu- > vieraillut = väärä ;
jos ( detectLoopLinkedList ( headNode ) ) {
cout << 'Silmukka havaittu linkitetyssä luettelossa' << endl;
} muu {
cout << 'Linkitetyssä luettelossa ei havaittu silmukkaa' << endl;
}
// Silmukan luominen
kolmas solmu- > seuraava = toinenSolmu;
jos ( detectLoopLinkedList ( headNode ) ) {
cout << 'Silmukka havaittu linkitetyssä luettelossa' << endl;
} muu {
cout << 'Linkitetyssä luettelossa ei havaittu silmukkaa' << endl;
}
palata 0 ;
}
Lähtö:
Silmukkaa ei havaittu sisään linkitetty lista
Silmukka havaittu sisään linkitetty lista
Selitys:
-
- Toiminto detectLoopLinkedList() tässä ohjelmassa hyväksyy linkitetyn luettelon pään syötteeksi.
- Funktio käyttää rekursiota toistaakseen linkitetyn luettelon. Rekursion perustapauksena se alkaa määrittämällä, onko nykyinen solmu NULL. Jos näin on, menetelmä palauttaa false, mikä osoittaa, että silmukkaa ei ole.
- Tämän jälkeen nykyisen solmun vieraillun ominaisuuden arvo tarkistetaan, jotta nähdään, onko siinä vieraillut aiemmin. Se palauttaa tosi, jos siinä on vieraillut, mikä viittaa siihen, että silmukka on löydetty.
- Funktio merkitsee nykyisen solmun vierailluksi, jos siinä on jo vierailtu muuttamalla sen 'vieraillut' -ominaisuuden arvoksi tosi.
- Vierailun muuttujan arvo tarkastetaan sitten, jotta nähdään, onko nykyisessä solmussa vierailtu aiemmin. Jos sitä on käytetty aiemmin, silmukan on oltava olemassa ja funktio palauttaa tosi.
- Lopuksi funktio kutsuu itseään luettelon seuraavan solmun kanssa ohittamalla headNode->seuraava argumenttina. Rekursiivisesti , tätä suoritetaan, kunnes joko silmukka löytyy tai kaikissa solmuissa on käyty. Tarkoittaa, että funktio asettaa vieraillun muuttujan arvoksi tosi, jos nykyisessä solmussa ei ole koskaan vierailtu ennen kuin se kutsuu itseään rekursiivisesti seuraavalle linkitetyn luettelon solmulle.
- Koodi rakentaa kolme solmua ja yhdistää ne tuottamaan linkitetyn luettelon päätoiminto . Menetelmä detectLoopLinkedList() kutsutaan sitten luettelon pääsolmussa. Ohjelma tuottaa ' Silmukka vähennetty linkitetystä luettelosta 'jos detectLoopLinkedList() palauttaa tosi; muuten se tulostaa ' Linkitetyssä luettelossa ei havaittu silmukkaa '.
- Koodi lisää sitten silmukan linkitettyyn luetteloon asettamalla viimeisen solmun seuraavan osoittimen toiseen solmuun. Sitten funktion tuloksesta riippuen se suoritetaan detectLoopLinkedList() uudelleen ja tuottaa joko ' Silmukka vähennetty linkitetystä luettelosta ' tai ' Linkitetyssä luettelossa ei havaittu silmukkaa .”
Lähestymistapa 4: Pinon käyttäminen
Linkitetyn luettelon silmukat löytyvät pinon ja 'depth-first search' (DFS) -menetelmän avulla. Perusajatuksena on iteroida linkitettyä luetteloa ja työntää jokainen solmu pinoon, jos siinä ei ole vielä vieraillut. Silmukka tunnistetaan, jos pinossa jo oleva solmu kohdataan uudelleen.
Tässä on lyhyt kuvaus menettelystä:
-
- Luo tyhjä pino ja muuttuja tallentaaksesi solmut, joissa on vieraillut.
- Työnnä linkitetty luettelo pinoon aloittaen ylhäältä. Tee muistiinpano, että pää on käynyt.
- Työnnä listan seuraava solmu pinoon. Lisää vierailumerkki tähän solmuun.
- Kun kuljet luetteloa, työnnä jokainen uusi solmu pinoon osoittaaksesi, että siinä on vieraillut.
- Tarkista, onko aiemmin vieraillut solmu pinon yläosassa, jos se havaitaan. Jos näin on, silmukka on löydetty, ja pinon solmut tunnistavat silmukan.
- Nosta solmut pois pinosta ja jatka luettelon läpikulkua, jos silmukkaa ei löydy.
C++-ohjelman toteutus yllä olevalle menetelmälle (pino)
#include
#sisällytä
käyttäen nimiavaruutta std;
struct Node {
int tiedot;
Solmu * Seuraava;
} ;
// Toiminto silmukan havaitsemiseksi sisään linkitetty lista
bool detectLoopLinkedList ( Solmu * headNode ) {
pino < Solmu *> pino;
Solmu * tempNode = headNode;
sillä aikaa ( tempNode ! = NULL ) {
// jos pinon ylin elementti vastaa
// nykyinen solmu ja pino eivät ole tyhjät
jos ( ! pino.tyhjä ( ) && pino.top ( ) == tempNode ) {
palata totta ;
}
pino.push ( tempNode ) ;
tempNode = tempNode- > Seuraava;
}
palata väärä ;
}
int main ( ) {
Solmu * headNode = uusi solmu ( ) ;
Solmu * secondNode = uusi solmu ( ) ;
Solmu * thirdNode = uusi solmu ( ) ;
pääsolmu- > data = 1 ;
pääsolmu- > seuraava = toinenSolmu;
toinen solmu- > data = 2 ;
toinen solmu- > seuraava = kolmassolmu;
kolmas solmu- > data = 3 ;
kolmas solmu- > seuraava = NULL; // Ei silmukkaa
jos ( detectLoopLinkedList ( headNode ) ) {
cout << 'Silmukka havaittu linkitetyssä luettelossa' << endl;
} muu {
cout << 'Linkitetyssä luettelossa ei havaittu silmukkaa' << endl;
}
// Silmukan luominen
kolmas solmu- > seuraava = toinenSolmu;
jos ( detectLoopLinkedList ( headNode ) ) {
cout << 'Silmukka havaittu linkitetyssä luettelossa' << endl;
} muu {
cout << 'Linkitetyssä luettelossa ei havaittu silmukkaa' << endl;
}
Lähtö:
Silmukkaa ei havaittu sisään linkitetty lista
Silmukka havaittu sisään linkitetty lista
Selitys:
Tämä ohjelma käyttää pinoa selvittääkseen, onko yksittäin linkitetyssä luettelossa silmukka.
- 1. Tulo/tulostusvirtakirjasto ja pinokirjasto ovat molemmat ensimmäisellä rivillä.
2. Vakionimiavaruus sisältyy toiselle riville, jolloin voimme käyttää syöttö-/tulostusvirtakirjaston toimintoja ilman, että niiden eteen tarvitsee liittää 'std::'.
3. Seuraavalla rivillä määritellään struct Node, joka koostuu kahdesta jäsenestä: kokonaisluvusta nimeltä 'data' ja osoittimesta toiseen solmuun nimeltä 'seuraava'.
4. Linkitetyn listan otsikko on syöte menetelmälle detectLoopLinkedList(), joka määritellään seuraavalla rivillä. Funktio tuottaa loogisen arvon, joka osoittaa, löytyikö silmukka vai ei.
5. Toiminnon sisälle luodaan pino solmuosoittimia nimeltä 'pino' ja osoitin solmuun nimeltä 'tempNode', joka on alustettu headNoden arvolla.
6. Sitten, niin kauan kuin tempNode ei ole nollaosoitin, syötetään while-silmukka.
(a) Pinon ylimmän elementin on vastattava nykyistä solmua, jotta voimme määrittää, ettei se ole tyhjä. Palautamme tosi, jos näin on, koska silmukka on löydetty.
(b) Jos edellä mainittu ehto on epätosi, nykyinen solmun osoitin työnnetään pinoon ja tempNode asetetaan linkitetyn luettelon seuraavaan solmuun.
7. Palautamme false while-silmukan jälkeen, koska silmukkaa ei havaittu.
8. Rakennamme kolme Node-oliota ja alustamme ne main()-funktiossa. Koska ensimmäisessä esimerkissä ei ole silmukkaa, asetamme kunkin solmun 'seuraavat' osoittimet oikein.
Johtopäätös:
Yhteenvetona voidaan todeta, että paras tapa havaita silmukoita linkitetyssä luettelossa riippuu tietystä käyttötapauksesta ja ongelman rajoituksista. Hash Table ja Floydin syklin etsintäalgoritmi ovat tehokkaita menetelmiä ja niitä käytetään laajasti käytännössä. Pino ja rekursio ovat vähemmän tehokkaita menetelmiä, mutta ne ovat intuitiivisempia.