Detekce smyčky v propojeném seznamu v C++

Koncový uzel propojeného seznamu, který má smyčku, bude odkazovat na jiný uzel ve stejném seznamu, nikoli na hodnotu NULL. Pokud je v propojeném seznamu uzel, ke kterému lze opakovaně přistupovat pomocí následujícího ukazatele, seznam se nazývá mít cyklus.

Poslední uzel propojeného seznamu obvykle odkazuje na odkaz NULL, který označuje závěr seznamu. V propojeném seznamu se smyčkou však koncový uzel seznamu odkazuje na počáteční uzel, vnitřní uzel nebo sám na sebe. Proto za takových okolností musíme identifikovat a ukončit smyčku nastavením odkazu dalšího uzlu na NULL. Část detekce smyčky v propojeném seznamu je vysvětlena v tomto článku.

V C++ existuje mnoho způsobů, jak najít smyčky v propojeném seznamu:

Přístup založený na hashovacích tabulkách : Tento přístup ukládá adresy navštívených uzlů do hašovací tabulky. Smyčka v propojeném seznamu existuje, pokud je uzel již přítomen v hašovací tabulce, když je znovu navštíven.

Floydův cyklus : Algoritmus „želvy a zajíce“, běžně známý jako Floydův algoritmus pro vyhledávání cyklu: Tato technika využívá dva ukazatele, jeden se pohybuje pomaleji než druhý a druhý rychleji. Rychlejší ukazatel nakonec předběhne pomalejší ukazatel, pokud je v propojeném seznamu smyčka, což odhalí existenci smyčky.

Rekurzivní metoda : Tato metoda prochází propojeným seznamem tím, že se znovu a znovu volá. Propojený seznam obsahuje smyčku, pokud byl aktuální uzel již dříve navštíven.

Stack-based přístup : Tento přístup ukládá adresy navštívených uzlů do zásobníku. Smyčka v propojeném seznamu je přítomna, pokud je uzel již v zásobníku, když je znovu navštíven.

Pojďme si každý přístup podrobně vysvětlit, abychom porozuměli konceptu.

Přístup 1: Přístup HashSet

Využití hashování je nejpřímější metoda. Zde procházíme seznam jeden po druhém, přičemž udržujeme hashovací tabulku s adresami uzlů. Smyčka tedy existuje, pokud někdy přejdeme přes další adresu aktuálního uzlu, která je již obsažena v hashovací tabulce. Jinak v Linked Listu není žádná smyčka, pokud narazíme na NULL (tj. dosáhneme konce Linked Listu).

Implementovat tuto strategii bude docela snadné.

Při procházení propojeného seznamu použijeme unordered_hashmap a budeme do něj průběžně přidávat uzly.

Nyní, jakmile narazíme na uzel, který je již zobrazen na mapě, budeme vědět, že jsme dorazili na začátek smyčky.

• • Kromě toho jsme v každém kroku ponechali dva ukazatele, headNode ukazující na aktuální uzel a lastNode ukazující na předchozí uzel aktuálního uzlu při iteraci.
  • Jako naše headNode nyní ukazuje na počáteční uzel smyčky a jako lastNode ukazoval na uzel, na který směřovala hlava (tj. odkazuje na lastNode smyčky), naše headNode aktuálně ukazuje na počáteční uzel smyčky.
  • Smyčka se přeruší nastavením l astNode->next == NULL .

Tímto způsobem koncový uzel smyčky namísto odkazování na počáteční uzel smyčky začne ukazovat na NULL.

Průměrná časová a prostorová složitost hašovací metody je O(n). Čtenář by si měl vždy uvědomit, že implementace vestavěné Hashovací DataStructure v programovacím jazyce určí celkovou časovou náročnost v případě kolize v hašování.

Implementace programu C++ pro výše uvedenou metodu (HashSet):

Výstup:

Vysvětlení kódu krok za krokem je uvedeno níže:

1. 1. V kódu je zahrnut hlavičkový soubor bits/stdc++.h>, který obsahuje všechny běžné knihovny C++.
   2. Je vytvořena struktura nazvaná „Uzel“ a má dva členy: odkaz na další uzel v seznamu a celé číslo nazvané „hodnota“.
   3. S celočíselnou hodnotou jako vstupem a ukazatelem „další“ nastaveným na NULL vytvoří funkce „newNode“ nový uzel s touto hodnotou.
   4. Funkce ' functionHashMap' je definován, který jako vstup vezme ukazatel na hlavní uzel propojeného seznamu.
   5. Uvnitř ' functionHashMap ‘ je vytvořena unordered_map s názvem ‘hash_map’, která se používá k implementaci datové struktury hash map.
   6. Ukazatel na poslední uzel seznamu je inicializován na hodnotu NULL.
   7. K procházení propojeného seznamu se používá smyčka while, která začíná od hlavního uzlu a pokračuje, dokud není hlavní uzel NULL.
   8. Ukazatel lastNode je aktualizován na aktuální uzel uvnitř smyčky while, pokud aktuální uzel (headNode) již není přítomen v hash mapě.
   9. Pokud je na mapě nalezen aktuální uzel, znamená to, že v propojeném seznamu je přítomna smyčka. Chcete-li odstranit smyčku, další ukazatel na lastNode je nastaveno na NULA a smyčka while je přerušena.
   10. Hlavní uzel propojeného seznamu se používá jako vstup pro funkci nazvanou „zobrazení“, která zobrazuje hodnotu každého uzlu v seznamu od začátku do konce.
   11. V hlavní funkce, vytvoření smyčky.
   12. Funkce ‚functionHashMap‘ je volána s ukazatelem headNode jako vstupem, který odstraní smyčku ze seznamu.
   13. Upravený seznam se zobrazí pomocí funkce „zobrazit“.

Přístup 2: Floydův cyklus

Floydův algoritmus detekce cyklu, často známý jako želvový a zajícový algoritmus, poskytuje základ pro tuto metodu lokalizace cyklů v propojeném seznamu. „Pomalý“ ukazatel a „rychlý“ ukazatel, které procházejí seznam různou rychlostí, jsou dva ukazatele používané v této technice. Rychlý ukazatel se posune vpřed o dva kroky, zatímco pomalý ukazatel o jeden krok v každé iteraci. Cyklus v propojeném seznamu existuje, pokud se dva body někdy setkají tváří v tvář.

1. S hlavním uzlem propojeného seznamu inicializujeme dva ukazatele nazývané rychlý a pomalý.

2. Nyní spustíme smyčku pro pohyb v propojeném seznamu. Rychlý ukazatel by se měl v každém kroku iterace posunout o dvě místa před pomalý ukazatel.

3. V propojeném seznamu nebude smyčka, pokud rychlý ukazatel dosáhne konce seznamu (fastPointer == NULL nebo fastPointer->next == NULL). Pokud ne, rychlé a pomalé ukazatele se nakonec setkají, což znamená, že propojený seznam má smyčku.

Implementace programu C++ pro výše uvedenou metodu (Floydův cyklus):

Výstup:

Vysvětlení:

1. 1. Nejprve jsou zahrnuty příslušné hlavičky, jako například „bits/stdc++.h“ a „std::cout“.
   2. Poté je deklarována struktura „Node“, která představuje uzel v propojeném seznamu. Další ukazatel, který vede na následující uzel v seznamu, je zahrnut spolu s celočíselným datovým polem v každém uzlu.
   3. Poté definuje dvě funkce „deleteLoop“ a „detectAndDeleteLoop“. Smyčka je odstraněna z propojeného seznamu pomocí první metody a smyčka je detekována v seznamu pomocí druhé funkce, která pak volá první proceduru k odstranění smyčky.
   4. V hlavní funkci se vytvoří nový propojený seznam s pěti uzly a nastavením dalšího ukazatele posledního uzlu na třetí uzel se vytvoří smyčka.
   5. Poté zavolá metodu „detectAndDeleteLoop“, přičemž předá hlavní uzel propojeného seznamu jako argument. K identifikaci smyček tato funkce používá přístup „pomalé a rychlé ukazatele“. Využívá dva ukazatele, které začínají na začátku seznamu, slowPTR a fastPTR. Zatímco rychlý ukazatel posouvá dva uzly najednou, pomalý ukazatel posouvá vždy pouze jeden uzel. Pokud seznam obsahuje smyčku, rychlý ukazatel nakonec předběhne pomalý ukazatel a dva body se střetnou ve stejném uzlu.
   6. Funkce vyvolá funkci „deleteLoop“, pokud najde smyčku, která jako vstup dodá hlavní uzel seznamu a průsečík pomalého a rychlého ukazatele. Tento postup vytvoří dva ukazatele, ptr1 a ptr2, na hlavní uzel seznamu a spočítá počet uzlů ve smyčce. Následně se posune o jeden ukazatel k uzlům, kde k je celkový počet uzlů ve smyčce. Poté, dokud se nepotkají na začátku smyčky, posouvá oba body jeden uzel po druhém. Smyčka se pak přeruší nastavením dalšího ukazatele uzlu na konci smyčky na hodnotu NULL.
   7. Po odstranění smyčky zobrazí propojený seznam jako poslední krok.

Přístup 3: Rekurze

Rekurze je technika pro řešení problémů jejich rozdělením na menší, jednodušší dílčí problémy. Rekurzi lze použít k procházení jednotlivě propojeného seznamu v případě, že je nalezena smyčka nepřetržitým spouštěním funkce pro další uzel v seznamu, dokud není dosaženo konce seznamu.

V jednoduše propojeném seznamu je základním principem použití rekurze k nalezení smyčky začít na začátku seznamu, označit aktuální uzel jako navštívený v každém kroku a poté přejít k dalšímu uzlu rekurzivním vyvoláním funkce pro ten uzel. Metoda bude iterovat přes celý propojený seznam, protože je volána rekurzivně.

Seznam obsahuje smyčku, pokud funkce narazí na uzel, který byl dříve označen jako navštívený; v tomto případě může funkce vrátit hodnotu true. Metoda může vrátit hodnotu false, pokud dosáhne konce seznamu, aniž by běžela přes navštívený uzel, což znamená, že neexistuje žádná smyčka.

Ačkoli je tato technika pro využití rekurze k nalezení smyčky v jediném propojeném seznamu přímočará na použití a pochopení, nemusí být z hlediska časové a prostorové složitosti nejúčinnější.

Implementace programu C++ pro výše uvedenou metodu (rekurze):

Výstup:

Vysvětlení:

1. 1. Funkce detectLoopLinkedList() v tomto programu přijímá jako vstup záhlaví propojeného seznamu.
   2. Rekurze je použita funkcí k iteraci přes propojený seznam. Jako základní případ rekurze začíná určením, zda je aktuální uzel NULL. Pokud ano, metoda vrátí false, což znamená, že žádná smyčka neexistuje.
   3. Hodnota „navštívené“ vlastnosti aktuálního uzlu se pak zkontroluje, aby se zjistilo, zda byl již dříve navštíven. Vrací hodnotu true, pokud byla navštívena, což naznačuje, že byla nalezena smyčka.
   4. Funkce označí aktuální uzel jako navštívený, pokud již byl navštíven, a to změnou jeho vlastnosti „navštívené“ na true.
   5. Hodnota navštívené proměnné se pak zkontroluje, zda byl aktuální uzel již dříve navštíven. Pokud byla použita dříve, musí existovat smyčka a funkce vrátí hodnotu true.
   6. Nakonec se funkce zavolá s dalším uzlem v seznamu předáním headNode->další jako argument. Rekurzivně , toto se provádí tak dlouho, dokud není nalezena smyčka nebo nejsou navštíveny všechny uzly. To znamená, že funkce nastaví navštívenou proměnnou na hodnotu true, pokud aktuální uzel nebyl nikdy navštíven, než se rekurzivně zavolal pro následující uzel v propojeném seznamu.
   7. Kód vytvoří tři uzly a spojí je, aby vytvořil propojený seznam v hlavní funkce . Metoda detectLoopLinkedList() se pak vyvolá na hlavním uzlu seznamu. Program vytváří „ Smyčka odečtena v propojeném seznamu “pokud detectLoopLinkedList() vrátí true; jinak to vypíše ' V propojeném seznamu nebyla zjištěna žádná smyčka “.
   8. Kód pak vloží smyčku do propojeného seznamu nastavením dalšího ukazatele posledního uzlu na druhý uzel. Poté se v závislosti na výsledku funkce spustí detectLoopLinkedList() znovu a produkuje buď „ Smyčka odečtena v propojeném seznamu “ nebo „ V propojeném seznamu nebyla zjištěna žádná smyčka .“

Přístup 4: Použití zásobníku

Smyčky v propojeném seznamu lze najít pomocí zásobníku a metody „vyhledávání do hloubky“ (DFS). Základním konceptem je iterovat propojený seznam a vložit každý uzel do zásobníku, pokud ještě nebyl navštíven. Smyčka je rozpoznána, pokud je znovu nalezen uzel, který je již v zásobníku.

Zde je stručný popis postupu:

1. 1. Vytvořte prázdný zásobník a proměnnou pro záznam uzlů, které byly navštíveny.
   2. Posuňte propojený seznam na hromádku, začněte nahoře. Poznamenejte si, že hlava byla navštívena.
   3. Posuňte další uzel v seznamu do zásobníku. Přidejte k tomuto uzlu značku návštěvy.
   4. Při procházení seznamu posuňte každý nový uzel do zásobníku, abyste označili, že byl navštíven.
   5. Zkontrolujte, zda je uzel, který byl dříve navštíven, na vrcholu zásobníku, pokud na něj narazíte. Pokud ano, smyčka byla nalezena a smyčka je identifikována uzly v zásobníku.
   6. Vyjměte uzly ze zásobníku a pokračujte v procházení seznamu, pokud není nalezena žádná smyčka.

Implementace programu C++ pro výše uvedenou metodu (Stack)

Výstup:

Vysvětlení:

Tento program používá zásobník ke zjištění, zda má jednotlivě propojený seznam smyčku.

• 1. Knihovna vstupního/výstupního toku a knihovna zásobníku jsou obě přítomny v prvním řádku.

  2. Standardní jmenný prostor je zahrnut na druhém řádku, což nám umožňuje přístup k funkcím knihovny vstupních/výstupních streamů, aniž bychom jim museli předponu „std::“.

  3. Následující řádek definuje strukturu Node, která se skládá ze dvou členů: celého čísla zvaného „data“ a ukazatele na jiný uzel s názvem „next“.

  4. Hlava propojeného seznamu je vstupem pro metodu detectLoopLinkedList(), která je definována na dalším řádku. Funkce vytváří booleovskou hodnotu, která označuje, zda byla či nebyla nalezena smyčka.

  5. Uvnitř funkce se vytvoří zásobník ukazatelů uzlu s názvem „stack“ a ukazatel na uzel s názvem „tempNode“, který je inicializován hodnotou headNode.

  6. Poté, dokud tempNode není nulový ukazatel, vstoupíme do while cyklu.

  (a) Horní prvek zásobníku musí odpovídat aktuálnímu uzlu, abychom mohli určit, že není prázdný. Vrátíme true, pokud tomu tak je, protože byla nalezena smyčka.

  (b) Pokud je výše uvedená podmínka nepravdivá, ukazatel aktuálního uzlu se přesune do zásobníku a tempNode se nastaví na následující uzel v propojeném seznamu.

  7. Po cyklu while vrátíme false, protože nebyl pozorován žádný cyklus.

  8. Vytvoříme tři objekty Node a inicializujeme je ve funkci main(). Protože v prvním příkladu není žádná smyčka, nastavíme „další“ ukazatele každého uzlu správně.

Závěr:

Na závěr, nejlepší metoda pro detekci smyček v propojeném seznamu závisí na konkrétním případu použití a omezeních problému. Hash Table a Floydův algoritmus pro vyhledávání cyklů jsou efektivní metody a v praxi jsou široce používány. Stack a rekurze jsou méně účinné metody, ale jsou intuitivnější.