Zaznavanje zanke na povezanem seznamu v C++

Končno vozlišče povezanega seznama, ki ima zanko, se bo sklicevalo na drugo vozlišče na istem seznamu in ne na NULL. Če je na povezanem seznamu vozlišče, do katerega je mogoče večkrat dostopati s sledenjem naslednjemu kazalcu, se za seznam reče, da imeti cikel.

Običajno se zadnje vozlišče povezanega seznama nanaša na referenco NULL, ki označuje zaključek seznama. Vendar se na povezanem seznamu z zanko končno vozlišče seznama nanaša na začetno vozlišče, notranje vozlišče ali samo sebe. Zato moramo v takih okoliščinah identificirati in prekiniti zanko tako, da referenco naslednjega vozlišča nastavimo na NULL. Zaznavni del zanke na povezanem seznamu je razložen v tem članku.

V C++ obstaja veliko načinov za iskanje zank na povezanem seznamu:

Pristop, ki temelji na zgoščevalni tabeli : Ta pristop shrani naslove obiskanih vozlišč v zgoščeno tabelo. Zanka na povezanem seznamu obstaja, če je vozlišče že prisotno v zgoščeni tabeli, ko je ponovno obiskano.

Floydov cikel pristopa : Algoritem »želve in zajca«, splošno znan kot Floydov algoritem za iskanje ciklov: ta tehnika uporablja dva kazalca, pri čemer se eden premika počasneje od drugega in drugi hitreje. Hitrejši kazalec bo na koncu prehitel počasnejši kazalec, če je na povezanem seznamu zanka, ki razkrije obstoj zanke.

Rekurzivna metoda : Ta metoda gre skozi povezani seznam tako, da se znova in znova kliče. Povezani seznam vsebuje zanko, če je bilo trenutno vozlišče že obiskano.

Pristop, ki temelji na skladih : Ta pristop shrani naslove obiskanih vozlišč v sklad. Zanka na povezanem seznamu je prisotna, če je vozlišče že tam v skladu, ko ga ponovno obiščete.

Za razumevanje koncepta podrobno razložimo vsak pristop.

Pristop 1: pristop HashSet

Uporaba zgoščevanja je najbolj preprosta metoda. Tukaj gremo skozi seznam enega za drugim, medtem ko ohranjamo zgoščeno tabelo z naslovi vozlišč. Zato obstaja zanka, če kdaj naletimo na naslednji naslov trenutnega vozlišča, ki je že vsebovan v zgoščevalni tabeli. V nasprotnem primeru na povezanem seznamu ni zanke, če naletimo na NULL (tj. dosežemo konec povezanega seznama).

To strategijo bo zelo enostavno izvajati.

Med prečkanjem povezanega seznama bomo uporabili unordered_hashmap in mu še naprej dodajali vozlišča.

Zdaj, ko naletimo na vozlišče, ki je že prikazano na zemljevidu, bomo vedeli, da smo prispeli na začetek zanke.

• • Poleg tega smo obdržali dva kazalca na vsakem koraku, headNode ki kaže na trenutno vozlišče in lastNode med ponavljanjem kaže na prejšnje vozlišče trenutnega vozlišča.
  • Kot naše headNode zdaj kaže na začetno vozlišče zanke in as lastNode je kazal na vozlišče, na katerega je kazala glava (tj. nanaša se na lastNode zanke), naš headNode trenutno kaže na začetno vozlišče zanke.
  • Z nastavitvijo l se bo zanka prekinila astNode->naslednji == NULL .

S tem se končno vozlišče zanke namesto sklicevanja na začetno vozlišče zanke začne kazati na NULL.

Povprečna časovna in prostorska kompleksnost metode zgoščevanja je O(n). Bralec se mora vedno zavedati, da bo izvedba vgrajene Hashing DataStructure v programskem jeziku določila skupno časovno kompleksnost v primeru kolizije pri zgoščevanju.

Implementacija programa C++ za zgornjo metodo (HashSet):

Izhod:

Spodaj je podana razlaga kode po korakih:

1. 1. Datoteka glave bits/stdc++.h>, ki vsebuje vse običajne knjižnice C++, je vključena v kodo.
   2. Konstruirana je struktura, imenovana 'Vozlišče', in ima dva člana: sklic na naslednje vozlišče na seznamu in celo število, imenovano 'vrednost'.
   3. S celoštevilsko vrednostjo kot vhodom in kazalcem »next«, nastavljenim na NULL, funkcija »newNode« ustvari novo vozlišče s to vrednostjo.
   4. Funkcija ' functionHashMap' definiran, ki kot vhod sprejme kazalec na glavno vozlišče povezanega seznama.
   5. Znotraj ' functionHashMap ' se ustvari unordered_map z imenom 'hash_map', ki se uporablja za implementacijo podatkovne strukture zgoščenega zemljevida.
   6. Kazalec na zadnje vozlišče seznama je inicializiran na NULL.
   7. Za prečkanje povezanega seznama se uporablja zanka while, ki se začne od glavnega vozlišča in nadaljuje, dokler ni glavno vozlišče NULL.
   8. Kazalec lastNode se posodobi na trenutno vozlišče znotraj zanke while, če trenutno vozlišče (headNode) še ni prisotno v zgoščenem zemljevidu.
   9. Če je trenutno vozlišče najdeno na zemljevidu, to pomeni, da je na povezanem seznamu prisotna zanka. Če želite odstraniti zanko, naslednji kazalec lastNode je nastavljeno na NIČ in medtem ko je zanka prekinjena.
   10. Glavno vozlišče povezanega seznama se uporablja kot vhod za funkcijo, imenovano 'prikaz', ki izpiše vrednost vsakega vozlišča na seznamu od začetka do konca.
   11. V glavni funkcijo, ki ustvarja zanko.
   12. Funkcija 'functionHashMap' se kliče s kazalcem headNode kot vhodom, kar odstrani zanko s seznama.
   13. Spremenjeni seznam je prikazan s funkcijo 'display'.

Pristop 2: Floydov cikel

Floydov algoritem za zaznavanje ciklov, pogosto znan kot algoritem želve in zajca, zagotavlja osnovo za to metodo lociranja ciklov na povezanem seznamu. Kazalca, ki se uporabljata v tej tehniki, sta »počasen« in »hiter« kazalec, ki prečkata seznam z različnimi hitrostmi. Hitri kazalec napreduje za dva koraka, medtem ko počasen kazalec napreduje za en korak vsako ponovitev. Cikel na povezanem seznamu obstaja, če se dve točki kadar koli srečata.

1. Z glavnim vozliščem povezanega seznama inicializiramo dva kazalca, imenovana hitri in počasni.

2. Zdaj zaženemo zanko za premikanje po povezanem seznamu. Hitri kazalec je treba pri vsakem koraku ponovitve premakniti za dve lokaciji pred počasnim kazalcem.

3. Na povezanem seznamu ne bo zanke, če hitri kazalec doseže konec seznama (fastPointer == NULL ali fastPointer->next == NULL). Če ne, se bosta hitri in počasni kazalec sčasoma srečala, kar pomeni, da ima povezani seznam zanko.

Implementacija programa C++ za zgornjo metodo (Floydov cikel):

Izhod:

Pojasnilo:

1. 1. Najprej so vključene ustrezne glave, kot sta »bits/stdc++.h« in »std::cout«.
   2. Struktura »Vozlišče«, ki pomeni vozlišče na povezanem seznamu, je nato deklarirana. Naslednji kazalec, ki vodi do naslednjega vozlišča na seznamu, je vključen skupaj s celim podatkovnim poljem v vsako vozlišče.
   3. Nato definira »deleteLoop« in »detectAndDeleteLoop«, dve funkciji. Zanka se odstrani s povezanega seznama s prvo metodo, zanka pa se zazna na seznamu z drugo funkcijo, ki nato pokliče prvo proceduro za odstranitev zanke.
   4. V glavni funkciji se ustvari nov povezan seznam s petimi vozlišči, zanka pa se vzpostavi z nastavitvijo naslednjega kazalca zadnjega vozlišča na tretje vozlišče.
   5. Nato pokliče metodo »detectAndDeleteLoop«, medtem ko posreduje glavno vozlišče povezanega seznama kot argument. Za prepoznavanje zank ta funkcija uporablja pristop »počasnih in hitrih kazalcev«. Uporablja dva kazalca, ki se začneta na vrhu seznama, slowPTR in fastPTR. Medtem ko hitri kazalec premakne dve vozlišči hkrati, počasen premakne samo eno vozlišče naenkrat. Hitri kazalec bo na koncu prehitel počasnega kazalca, če seznam vsebuje zanko, in obe točki bosta trčili v istem vozlišču.
   6. Funkcija prikliče funkcijo »deleteLoop«, če najde zanko, pri čemer kot vhode posreduje glavno vozlišče seznama in presečišče počasnega in hitrega kazalca. Ta postopek vzpostavi dva kazalca, ptr1 in ptr2, na glavno vozlišče seznama in prešteje število vozlišč v zanki. Nato premakne en kazalec k vozlišč naprej, kjer je k skupno število vozlišč v zanki. Nato, dokler se ne srečata na začetku zanke, obe točki napreduje eno vozlišče naenkrat. Zanka se nato prekine z nastavitvijo naslednjega kazalca vozlišča na koncu zanke na NULL.
   7. Po odstranitvi zanke kot zadnji korak prikaže povezani seznam.

Pristop 3: Rekurzija

Rekurzija je tehnika za reševanje problemov z razdelitvijo na manjše, lažje podprobleme. Rekurzijo je mogoče uporabiti za prečkanje enojno povezanega seznama v primeru, da je najdena zanka z neprekinjenim izvajanjem funkcije za naslednje vozlišče na seznamu, dokler ni dosežen konec seznama.

V enojno povezanem seznamu je osnovno načelo uporabe rekurzije za iskanje zanke, da začnete na začetku seznama, označite trenutno vozlišče kot obiskano na vsakem koraku in nato nadaljujete do naslednjega vozlišča z rekurzivnim klicem funkcije za to vozlišče. Metoda bo ponovila celoten povezan seznam, ker se kliče rekurzivno.

Seznam vsebuje zanko, če funkcija naleti na vozlišče, ki je bilo prej označeno kot obiskano; v tem primeru lahko funkcija vrne true. Metoda lahko vrne false, če doseže konec seznama, ne da bi tekla čez obiskano vozlišče, kar pomeni, da ni zanke.

Čeprav je ta tehnika za uporabo rekurzije za iskanje zanke na enem samem povezanem seznamu enostavna za uporabo in razumevanje, morda ni najučinkovitejša v smislu kompleksnosti časa in prostora.

Implementacija programa C++ za zgornjo metodo (rekurzija):

Izhod:

Pojasnilo:

1. 1. Funkcija detektLoopLinkedList() v tem programu sprejme glavo povezanega seznama kot vnos.
   2. Funkcija uporablja rekurzijo za ponavljanje po povezanem seznamu. Kot osnovni primer za rekurzijo se začne z ugotavljanjem, ali je trenutno vozlišče NULL. Če je tako, metoda vrne false, kar pomeni, da zanka ne obstaja.
   3. Vrednost lastnosti »obiskano« trenutnega vozlišča se nato preveri, ali je bilo vozlišče že obiskano. Če je bil obiskan, vrne true, kar pomeni, da je bila najdena zanka.
   4. Funkcija označi trenutno vozlišče kot obiskano, če je bilo že obiskano s spremembo njegove lastnosti »obiskano« na true.
   5. Vrednost obiskane spremenljivke se nato preveri, ali je bilo trenutno vozlišče že obiskano. Če je bila že uporabljena, mora obstajati zanka in funkcija vrne true.
   6. Nazadnje se funkcija s posredovanjem pokliče z naslednjim vozliščem na seznamu headNode->naprej kot argument. Rekurzivno , se to izvaja, dokler ni najdena zanka ali dokler niso obiskana vsa vozlišča. Pomeni, da funkcija nastavi obiskano spremenljivko na true, če trenutno vozlišče ni bilo nikoli obiskano, preden se je rekurzivno poklicalo za naslednje vozlišče na povezanem seznamu.
   7. Koda zgradi tri vozlišča in jih združi, da ustvari povezan seznam v glavna funkcija . Metoda detektLoopLinkedList() se nato prikliče v glavnem vozlišču seznama. Program proizvaja ' Zanka je odbita na povezanem seznamu 'če detektLoopLinkedList() vrne true; sicer izpiše ' Na povezanem seznamu ni zaznane zanke “.
   8. Koda nato vstavi zanko v povezani seznam tako, da nastavi naslednji kazalec zadnjega vozlišča na drugo vozlišče. Nato se glede na izid funkcije zažene detektLoopLinkedList() znova in proizvede bodisi ' Zanka je odbita na povezanem seznamu « ali » Na povezanem seznamu ni zaznane zanke .”

Pristop 4: Uporaba sklada

Zanke na povezanem seznamu je mogoče najti z uporabo sklada in metode »iskanje najprej v globino« (DFS). Temeljni koncept je iteracija po povezanem seznamu, pri čemer se vsako vozlišče potisne v sklad, če še ni bilo obiskano. Zanka je prepoznana, če se znova sreča vozlišče, ki je že v skladu.

Tukaj je kratek opis postopka:

1. 1. Ustvarite prazen sklad in spremenljivko za beleženje obiskanih vozlišč.
   2. Potisnite povezani seznam na sklad, začnite na vrhu. Zabeležite, da je bila glava obiskana.
   3. Potisnite naslednje vozlišče na seznamu na sklad. Temu vozlišču dodajte oznako obiska.
   4. Ko prečkate seznam, potisnite vsako novo vozlišče na sklad, da označite, da je bilo obiskano.
   5. Preverite, ali je vozlišče, ki je bilo predhodno obiskano, na vrhu sklada, če ga naletite. Če je tako, je bila najdena zanka in zanka je prepoznana po vozliščih v skladu.
   6. Odstranite vozlišča iz sklada in nadaljujte s prečkanjem seznama, če ni najdena nobena zanka.

Implementacija programa C++ za zgornjo metodo (Stack)

Izhod:

Pojasnilo:

Ta program uporablja sklad, da ugotovi, ali ima enojno povezan seznam zanko.

• 1. Knjižnica vhodno/izhodnega toka in knjižnica sklada sta prisotni v prvi vrstici.

  2. Standardni imenski prostor je vključen v drugo vrstico, kar nam omogoča dostop do funkcij knjižnice vhodno/izhodnega toka, ne da bi jim morali dodati predpono »std::«.

  3. Naslednja vrstica definira vozlišče struct, ki je sestavljeno iz dveh členov: celega števila, imenovanega »podatki«, in kazalca na drugo vozlišče, imenovanega »naslednji«.

  4. Glava povezanega seznama je vhod za metodo detectLoopLinkedList(), ki je definirana v naslednji vrstici. Funkcija ustvari logično vrednost, ki pove, ali je bila najdena zanka ali ne.

  5. Znotraj funkcije sta ustvarjena sklad kazalcev vozlišča, imenovan »stack«, in kazalec na vozlišče, imenovano »tempNode«, ki je inicializiran z vrednostjo headNode.

  6. Nato, dokler tempNode ni ničelni kazalec, vstopimo v zanko while.

  (a) Zgornji element sklada se mora ujemati s trenutnim vozliščem, da lahko ugotovimo, da ni prazno. Vrnemo true, če je temu tako, ker je bila najdena zanka.

  (b) Če je zgoraj omenjeni pogoj napačen, je kazalec trenutnega vozlišča potisnjen na sklad, tempNode pa je nastavljen na naslednje vozlišče na povezanem seznamu.

  7. Po zanki while vrnemo false, ker ni bila opažena nobena zanka.

  8. Zgradimo tri objekte Node in jih inicializiramo v funkciji main(). Ker v prvem primeru ni zanke, smo pravilno nastavili kazalce »naslednji« za vsako vozlišče.

Zaključek:

Skratka, najboljša metoda za odkrivanje zank na povezanem seznamu je odvisna od posebnega primera uporabe in omejitev težave. Hash Table in Floydov algoritem za iskanje ciklov sta učinkoviti metodi in se pogosto uporabljata v praksi. Stack in rekurzija sta manj učinkoviti metodi, vendar sta bolj intuitivni.