Zistite slučku v prepojenom zozname v C++

Koncový uzol prepojeného zoznamu, ktorý má slučku, bude odkazovať na iný uzol v tom istom zozname a nie na NULL. Ak je v prepojenom zozname uzol, ku ktorému je možné opakovane pristupovať nasledujúcim ukazovateľom, zoznam sa nazýva mať cyklus.

Posledný uzol prepojeného zoznamu zvyčajne odkazuje na odkaz NULL na označenie záveru zoznamu. V prepojenom zozname so slučkou však koncový uzol zoznamu odkazuje na počiatočný uzol, interný uzol alebo sám na seba. Preto za takýchto okolností musíme identifikovať a ukončiť slučku nastavením odkazu ďalšieho uzla na NULL. Detekčná časť slučky v prepojenom zozname je vysvetlená v tomto článku.

V C++ existuje mnoho spôsobov, ako nájsť slučky v prepojenom zozname:

Prístup založený na hashovacích tabuľkách : Tento prístup ukladá adresy navštívených uzlov do hašovacej tabuľky. Slučka v prepojenom zozname existuje, ak sa uzol už nachádza v hašovacej tabuľke, keď je znovu navštívený.

prístup Floydovho cyklu : Algoritmus „korytnačky a zajaca“, bežne známy ako Floydov algoritmus hľadania cyklu: Táto technika využíva dva ukazovatele, jeden sa pohybuje pomalšie ako druhý a druhý sa pohybuje rýchlejšie. Rýchlejší ukazovateľ nakoniec predbehne pomalší ukazovateľ, ak je v prepojenom zozname slučka, čím sa odhalí existencia slučky.

Rekurzívna metóda : Táto metóda prechádza prepojeným zoznamom tak, že sa znova a znova volá. Prepojený zoznam obsahuje slučku, ak bol aktuálny uzol predtým navštívený.

Stack-based prístup : Tento prístup ukladá adresy navštívených uzlov do zásobníka. Slučka v prepojenom zozname je prítomná, ak sa uzol už nachádza v zásobníku, keď je znovu navštívený.

Vysvetlíme si každý prístup podrobne, aby sme pochopili koncept.

Prístup 1: Prístup hashSet

Využitie hashovania je najjednoduchšia metóda. Tu prechádzame zoznamom jeden po druhom, pričom zachovávame hašovaciu tabuľku s adresami uzlov. Preto existuje slučka, ak niekedy prejdeme cez ďalšiu adresu aktuálneho uzla, ktorá je už obsiahnutá v hašovacej tabuľke. V opačnom prípade v prepojenom zozname nie je žiadna slučka, ak narazíme na NULL (t. j. dosiahneme koniec prepojeného zoznamu).

Implementácia tejto stratégie bude celkom jednoduchá.

Pri prechádzaní prepojeným zoznamom použijeme mapu unordered_hashmap a budeme do nej neustále pridávať uzly.

Teraz, keď narazíme na uzol, ktorý je už zobrazený na mape, budeme vedieť, že sme sa dostali na začiatok slučky.

• • Okrem toho sme v každom kroku zachovali dva ukazovatele, headNode ukazujúce na aktuálny uzol a lastNode ukazovanie na predchádzajúci uzol aktuálneho uzla pri iterácii.
  • Ako náš headNode teraz ukazuje na počiatočný uzol slučky a ako lastNode ukazoval na uzol, na ktorý smerovala hlava (t. j. odkazuje na lastNode slučky), náš headNode momentálne ukazuje na počiatočný uzol slučky.
  • Slučka sa preruší nastavením l astNode->next == NULL .

Ak to urobíte, koncový uzol slučky namiesto odkazu na počiatočný uzol slučky začne ukazovať na NULL.

Priemerná časová a priestorová zložitosť hašovacej metódy je O(n). Čitateľ by si mal vždy uvedomiť, že implementácia vstavanej Hashing DataStructure v programovacom jazyku určí celkovú časovú náročnosť v prípade kolízie v hašovaní.

Implementácia programu C++ pre vyššie uvedenú metódu (HashSet):

Výkon:

Vysvetlenie kódu krok za krokom je uvedené nižšie:

1. 1. Hlavičkový súbor bits/stdc++.h>, ktorý obsahuje všetky bežné knižnice C++, je zahrnutý v kóde.
   2. Vytvorí sa štruktúra s názvom „Uzol“ a má dva členy: odkaz na nasledujúci uzol v zozname a celé číslo s názvom „hodnota“.
   3. S celočíselnou hodnotou ako vstupom a ukazovateľom „ďalší“ nastaveným na NULL, funkcia „newNode“ vytvorí nový uzol s touto hodnotou.
   4. Funkcia ' functionHashMap' je definovaný, ktorý berie ako vstup ukazovateľ na hlavný uzol prepojeného zoznamu.
   5. Vnútri ' functionHashMap ‘ sa vytvorí unordered_map s názvom ‘hash_map’, ktorá sa používa na implementáciu dátovej štruktúry hash mapy.
   6. Ukazovateľ na posledný uzol zoznamu je inicializovaný na NULL.
   7. Slučka while sa používa na prechádzanie prepojeného zoznamu, ktorý začína od hlavného uzla a pokračuje, kým hlavný uzol nemá hodnotu NULL.
   8. Ukazovateľ lastNode sa aktualizuje na aktuálny uzol v slučke while, ak aktuálny uzol (headNode) ešte nie je prítomný v hašovacej mape.
   9. Ak sa aktuálny uzol nájde na mape, znamená to, že v prepojenom zozname je prítomná slučka. Ak chcete slučku odstrániť, ďalší ukazovateľ na lastNode je nastavený na NULOVÝ a slučka while je prerušená.
   10. Hlavný uzol prepojeného zoznamu sa používa ako vstup pre funkciu nazývanú „zobrazenie“, ktorá zobrazuje hodnotu každého uzla v zozname od začiatku do konca.
   11. V Hlavná funkciu, vytvárajúcu slučku.
   12. Funkcia „functionHashMap“ sa volá s ukazovateľom headNode ako vstupom, ktorý odstráni slučku zo zoznamu.
   13. Upravený zoznam sa zobrazí pomocou funkcie „zobraziť“.

Prístup 2: Floydov cyklus

Floydov algoritmus detekcie cyklu, často známy ako algoritmus korytnačky a zajaca, poskytuje základ pre túto metódu lokalizácie cyklov v prepojenom zozname. „Pomalý“ ukazovateľ a „rýchly“ ukazovateľ, ktoré prechádzajú zoznamom rôznymi rýchlosťami, sú dva ukazovatele používané v tejto technike. Rýchly ukazovateľ sa posúva o dva kroky, zatiaľ čo pomalý ukazovateľ sa posúva o jeden krok pri každej iterácii. Cyklus v prepojenom zozname existuje, ak sa tieto dva body stretnú tvárou v tvár.

1. S hlavným uzlom prepojeného zoznamu inicializujeme dva ukazovatele nazývané rýchly a pomalý.

2. Teraz spustíme slučku na pohyb v prepojenom zozname. Rýchly ukazovateľ by sa mal v každom kroku iterácie presunúť o dve miesta pred pomalý ukazovateľ.

3. V prepojenom zozname nebude slučka, ak rýchly ukazovateľ dosiahne koniec zoznamu (fastPointer == NULL alebo fastPointer->next == NULL). Ak nie, rýchle a pomalé ukazovatele sa nakoniec stretnú, čo znamená, že prepojený zoznam má slučku.

Implementácia programu C++ pre vyššie uvedenú metódu (Floydov cyklus):

Výkon:

Vysvetlenie:

1. 1. Najprv sú zahrnuté príslušné hlavičky, ako napríklad „bits/stdc++.h“ a „std::cout“.
   2. Potom sa deklaruje štruktúra „Node“, ktorá predstavuje uzol v prepojenom zozname. Ďalší ukazovateľ, ktorý vedie na nasledujúci uzol v zozname, je zahrnutý spolu s celočíselným dátovým poľom v každom uzle.
   3. Potom definuje dve funkcie „deleteLoop“ a „detectAndDeleteLoop“. Slučka sa odstráni z prepojeného zoznamu pomocou prvej metódy a slučka sa v zozname zistí pomocou druhej funkcie, ktorá potom zavolá prvú procedúru na odstránenie slučky.
   4. V hlavnej funkcii sa vytvorí nový prepojený zoznam s piatimi uzlami a vytvorí sa slučka nastavením ďalšieho ukazovateľa posledného uzla na tretí uzol.
   5. Potom zavolá metódu „detectAndDeleteLoop“, pričom ako argument odovzdá hlavný uzol prepojeného zoznamu. Na identifikáciu slučiek táto funkcia používa prístup „pomalé a rýchle ukazovatele“. Používa dva ukazovatele, ktoré začínajú na začiatku zoznamu, slowPTR a fastPTR. Zatiaľ čo rýchly ukazovateľ pohybuje dvoma uzlami naraz, pomalý ukazovateľ pohybuje iba jedným uzlom naraz. Rýchly ukazovateľ nakoniec predbehne pomalý ukazovateľ, ak zoznam obsahuje slučku a tieto dva body sa zrazia v rovnakom uzle.
   6. Funkcia vyvolá funkciu „deleteLoop“, ak nájde slučku, pričom ako vstup poskytne hlavný uzol zoznamu a priesečník pomalého a rýchleho ukazovateľa. Tento postup vytvorí dva ukazovatele, ptr1 a ptr2, na hlavný uzol zoznamu a spočíta počet uzlov v slučke. Potom sa posunie o jeden ukazovateľ k uzlov, kde k je celkový počet uzlov v slučke. Potom, kým sa nestretnú na začiatku slučky, postupuje oba body o jeden uzol v čase. Cyklus sa potom preruší nastavením ďalšieho ukazovateľa uzla na konci cyklu na hodnotu NULL.
   7. Po odstránení slučky zobrazí prepojený zoznam ako posledný krok.

Prístup 3: Rekurzia

Rekurzia je technika na riešenie problémov ich rozdelením na menšie, jednoduchšie podproblémy. Rekurzia sa môže použiť na prechádzanie jednotlivo prepojeného zoznamu v prípade, že sa nájde slučka nepretržitým spustením funkcie pre ďalší uzol v zozname, až kým sa nedosiahne koniec zoznamu.

V jednoducho prepojenom zozname je základným princípom použitia rekurzie na nájdenie slučky začať na začiatku zoznamu, označiť aktuálny uzol ako navštívený v každom kroku a potom prejsť na ďalší uzol rekurzívnym vyvolaním funkcie pre ten uzol. Metóda bude iterovať celý prepojený zoznam, pretože sa volá rekurzívne.

Zoznam obsahuje slučku, ak funkcia narazí na uzol, ktorý bol predtým označený ako navštívený; v tomto prípade môže funkcia vrátiť hodnotu true. Metóda môže vrátiť hodnotu false, ak dosiahne koniec zoznamu bez toho, aby prešla cez navštívený uzol, čo znamená, že neexistuje žiadna slučka.

Hoci je táto technika na využitie rekurzie na nájdenie slučky v jednom prepojenom zozname jednoduchá na použitie a pochopenie, nemusí byť z hľadiska časovej a priestorovej zložitosti najefektívnejšia.

Implementácia programu C++ pre vyššie uvedenú metódu (rekurzia):

Výkon:

Vysvetlenie:

1. 1. Funkcia detectLoopLinkedList() v tomto programe akceptuje hlavičku prepojeného zoznamu ako vstup.
   2. Funkcia používa rekurziu na iteráciu cez prepojený zoznam. Ako základný prípad rekurzie sa začína určením, či je aktuálny uzol NULL. Ak áno, metóda vráti hodnotu false, čo znamená, že neexistuje žiadna slučka.
   3. Potom sa skontroluje hodnota „navštívenej“ vlastnosti aktuálneho uzla, aby sa zistilo, či už bol navštívený. Ak bola navštívená, vráti hodnotu true, čo naznačuje, že bola nájdená slučka.
   4. Funkcia označí aktuálny uzol ako navštívený, ak už bol navštívený, a to zmenou jeho vlastnosti „navštívené“ na hodnotu true.
   5. Potom sa skontroluje hodnota navštívenej premennej, aby sa zistilo, či bol aktuálny uzol navštívený už predtým. Ak už bola použitá, musí existovať slučka a funkcia vráti hodnotu true.
   6. Nakoniec sa funkcia zavolá s ďalším uzlom v zozname prechodom headNode->ďalší ako argument. Rekurzívne Toto sa vykonáva, kým sa nenájde slučka alebo kým sa nenavštívia všetky uzly. Znamená to, že funkcia nastaví navštívenú premennú na hodnotu true, ak aktuálny uzol nebol nikdy navštívený, kým sa rekurzívne zavolal pre nasledujúci uzol v prepojenom zozname.
   7. Kód vytvorí tri uzly a spojí ich, aby vytvorili prepojený zoznam v hlavná funkcia . Metóda detectLoopLinkedList() sa potom vyvolá v hlavnom uzle zoznamu. Program vytvára „ Slučka odpočítaná v prepojenom zozname “ak detectLoopLinkedList() vráti true; inak to vypíše “ V prepojenom zozname nebola zistená žiadna slučka “.
   8. Kód potom vloží slučku do prepojeného zoznamu nastavením ďalšieho ukazovateľa posledného uzla na druhý uzol. Potom sa v závislosti od výsledku funkcie spustí detectLoopLinkedList() znova a produkuje buď „ Slučka odpočítaná v prepojenom zozname “ alebo „ V prepojenom zozname nebola zistená žiadna slučka .“

Prístup 4: Použitie zásobníka

Slučky v prepojenom zozname možno nájsť pomocou zásobníka a metódy „hľadania do hĺbky“ (DFS). Základným konceptom je iterovať prepojený zoznam a vložiť každý uzol do zásobníka, ak ešte nebol navštívený. Slučka sa rozpozná, ak sa znova nájde uzol, ktorý je už v zásobníku.

Tu je stručný popis postupu:

1. 1. Vytvorte prázdny zásobník a premennú na zaznamenanie navštívených uzlov.
   2. Posuňte prepojený zoznam do zásobníka, začnite zhora. Poznamenajte si, že hlava bola navštívená.
   3. Zatlačte ďalší uzol v zozname do zásobníka. Pridajte k tomuto uzlu značku návštevy.
   4. Pri prechádzaní zoznamom zatlačte každý nový uzol do zásobníka, aby ste označili, že bol navštívený.
   5. Skontrolujte, či je uzol, ktorý bol predtým navštívený, na vrchole zásobníka, ak naň narazíte. Ak áno, slučka bola nájdená a slučka je identifikovaná uzlami v zásobníku.
   6. Vyberte uzly zo zásobníka a pokračujte v prechádzaní zoznamu, ak sa nenájde žiadna slučka.

Implementácia programu C++ pre vyššie uvedenú metódu (Stack)

Výkon:

Vysvetlenie:

Tento program používa zásobník na zistenie, či má jednotlivo prepojený zoznam slučku.

• 1. Knižnica vstupno/výstupného toku a knižnica zásobníka sa nachádzajú v prvom riadku.

  2. Štandardný priestor názvov je zahrnutý v druhom riadku, čo nám umožňuje prístup k funkciám knižnice vstupných/výstupných tokov bez toho, aby sme im museli pridávať predponu „std::.“

  3. Nasledujúci riadok definuje štruktúru Node, ktorá pozostáva z dvoch členov: celého čísla nazývaného „údaje“ a ukazovateľa na iný uzol s názvom „next“.

  4. Hlavička prepojeného zoznamu je vstupom pre metódu detectLoopLinkedList(), ktorá je definovaná na nasledujúcom riadku. Funkcia vytvára boolovskú hodnotu, ktorá označuje, či bola alebo nebola nájdená slučka.

  5. V rámci funkcie sa vytvorí zásobník ukazovateľov uzla s názvom „stack“ a ukazovateľ na uzol s názvom „tempNode“, ktorý je inicializovaný hodnotou headNode.

  6. Potom, pokiaľ tempNode nie je nulový ukazovateľ, vstúpime do while cyklu.

  (a) Horný prvok zásobníka sa musí zhodovať s aktuálnym uzlom, aby sme mohli určiť, že nie je prázdny. Ak je to tak, vrátime hodnotu true, pretože bola nájdená slučka.

  (b) Ak je vyššie uvedená podmienka nepravdivá, ukazovateľ aktuálneho uzla sa presunie do zásobníka a tempNode sa nastaví na nasledujúci uzol v prepojenom zozname.

  7. Po slučke while vrátime hodnotu false, pretože nebola pozorovaná žiadna slučka.

  8. Vytvoríme tri objekty Node a inicializujeme ich vo funkcii main(). Keďže v prvom príklade nie je žiadna slučka, správne nastavíme „ďalšie“ ukazovatele každého uzla.

Záver:

Na záver, najlepšia metóda na detekciu slučiek v prepojenom zozname závisí od konkrétneho prípadu použitia a obmedzení problému. Hash Table a Floydov algoritmus na vyhľadávanie cyklov sú účinné metódy a v praxi sa široko používajú. Stack a rekurzia sú menej efektívne metódy, ale sú intuitívnejšie.