Hurok észlelése egy csatolt listában C++ nyelven

A hurkot tartalmazó hivatkozott lista végcsomópontja ugyanabban a listában egy másik csomópontra fog hivatkozni, nem pedig a NULL-ra. Ha van egy hivatkozási listában olyan csomópont, amely a következő mutató követésével ismételten elérhető, akkor a lista a következőképpen szól: van ciklusa.

Általában a linkelt lista utolsó csomópontja egy NULL hivatkozásra hivatkozik, amely a lista következtetését jelöli. A hurkot tartalmazó csatolt listákban azonban a lista végcsomópontja egy kezdőcsomópontra, egy belső csomópontra vagy önmagára utal. Ezért ilyen körülmények között azonosítanunk kell és le kell zárnunk a hurkot úgy, hogy a következő csomópont hivatkozását NULL-ra állítjuk. Ez a cikk ismerteti a hurok észlelési részét egy hivatkozott listában.

A C++ nyelven számos módon kereshet hurkot egy hivatkozott listában:

Hash tábla alapú megközelítés : Ez a megközelítés a meglátogatott csomópontok címeit egy hash táblában tárolja. A hivatkozott listában van egy hurok, ha egy csomópont már szerepel a hash táblában, amikor ismét meglátogatja.

Floyd ciklus megközelítése : A „teknősbéka és nyúl” algoritmus, közismert nevén Floyd cikluskereső algoritmusa: Ez a technika két mutatót használ, az egyik lassabban mozog, mint a másik, a másik pedig gyorsabban. A gyorsabb mutató végül megelőzi a lassabb mutatót, ha van hurok a hivatkozott listában, felfedi a hurok létezését.

Rekurzív módszer : Ez a metódus úgy megy végig a linkelt listán, hogy újra és újra meghívja magát. A hivatkozott lista tartalmaz egy hurkot, ha az aktuális csomópontot korábban meglátogatták.

Stack alapú megközelítés : Ez a megközelítés a meglátogatott csomópontok címeit egy veremben tárolja. A hivatkozott listában van egy hurok, ha egy csomópont már ott van a veremben, amikor ismét meglátogatja.

Magyarázzuk el részletesen az egyes megközelítéseket, hogy megértsük a koncepciót.

1. megközelítés: HashSet megközelítés

A hash használata a legegyszerűbb módszer. Itt egyenként megyünk végig a listán, miközben egy hash táblát tartunk a csomópontok címeivel. Ezért egy hurok létezik, ha valaha is átfutjuk az aktuális csomópont következő címét, amely már szerepel a hash táblában. Ellenkező esetben nincs hurok a linkelt listában, ha NULL-ba futunk (azaz elérjük a linkelt lista végét).

Ezt a stratégiát meglehetősen könnyű megvalósítani.

A hivatkozott lista bejárása során egy unordered_hashmap-ot használunk, és folyamatosan adunk hozzá csomópontokat.

Most, ha találkozunk egy csomóponttal, amely már látható a térképen, tudni fogjuk, hogy elérkeztünk a hurok elejéhez.

• • Ezenkívül minden lépésnél két mutatót tartottunk, headNode az aktuális csomópontra mutatva és lastNode iteráció közben az aktuális csomópont előző csomópontjára mutat.
  • Mint a mienk headNode most a hurok kezdőcsomópontjára mutat és as lastNode arra a csomópontra mutatott, amelyre a fej mutatott (azaz a lastNode a hurok), mi headNode jelenleg a hurok kezdőcsomópontjára mutat.
  • A hurok megszakad az l beállításával astNode->next == NULL .

Ezzel a záró hurokcsomópont ahelyett, hogy a hurok kezdeti csomópontjára hivatkozna, NULL-ra kezd mutatni.

A kivonatolási módszer átlagos idő- és térbonyolultsága O(n). Az olvasónak mindig tisztában kell lennie azzal, hogy a beépített Hashing DataStructure programozási nyelvben való megvalósítása határozza meg a teljes időbonyolultságot a kivonatolás ütközése esetén.

C++ program megvalósítása a fenti metódushoz (HashSet):

Kimenet:

A kód lépésről lépésre történő magyarázata alább található:

1. 1. A kód tartalmazza a bits/stdc++.h> fejlécfájlt, amely az összes általános C++ könyvtárat tartalmazza.
   2. Létrejön egy „Node” nevű struktúra, amelynek két tagja van: egy hivatkozás a lista következő csomópontjára és egy „érték” nevű egész szám.
   3. Egy egész szám bemeneti értékével és a „next” mutató NULL-ra állításával a „newNode” függvény új csomópontot hoz létre ezzel az értékkel.
   4. A funkció ' functionHashMap' definiálva van, amely bemenetként egy mutatót vesz a hivatkozott lista fejcsomópontjára.
   5. Benne ' functionHashMap ‘ függvényt, akkor létrejön egy ‘hash_map’ nevű rendezetlen_leképezés, amely egy hash leképezési adatstruktúra megvalósítására szolgál.
   6. A lista utolsó csomópontjára mutató mutató NULL értékre inicializálódik.
   7. Egy while ciklust használnak a csatolt lista bejárására, amely a fejcsomóponttól kezdődik és addig folytatódik, amíg a fejcsomópont NULL lesz.
   8. A lastNode mutató az aktuális csomópontra frissül a while cikluson belül, ha az aktuális csomópont (headNode) még nincs jelen a hash leképezésben.
   9. Ha az aktuális csomópont megtalálható a térképen, az azt jelenti, hogy egy hurok található a hivatkozott listában. A hurok eltávolításához a következő mutató a lastNode be van állítva NULLA és a while hurok megszakad.
   10. A linkelt lista fejcsomópontja a „megjelenítés” nevű függvény bemeneteként szolgál, amely a lista minden egyes csomópontjának értékét adja ki az elejétől a végéig.
   11. Ban,-ben fő- függvény, hurkot hozva létre.
   12. A „functionHashMap” függvény meghívása a headNode mutatójával történik, ami eltávolítja a ciklust a listából.
   13. A módosított lista a „megjelenítés” funkcióval jelenik meg.

2. megközelítés: Floyd ciklusa

A Floyd-féle ciklusészlelési algoritmus, amelyet gyakran teknősbéka és nyúl algoritmusként is ismernek, biztosítja az alapot a ciklusok linkelt listában történő lokalizálására. Ebben a technikában a „lassú” és a „gyors” mutató, amelyek különböző sebességgel haladnak át a listán, a két mutató. A gyors mutató két lépést, míg a lassú mutató egy lépést tesz előre minden iterációban. A hivatkozott listában akkor van ciklus, ha a két pont valaha is szembekerül.

1. A linkelt lista fejcsomópontjával inicializálunk két gyors és lassú mutatót.

2. Most egy hurkot futtatunk a hivatkozott listában való mozgáshoz. A gyors mutatót minden iteráció lépésénél két hellyel a lassú mutató elé kell mozgatni.

3. A hivatkozott listában nem lesz ciklus, ha a gyorsmutató eléri a lista végét (fastPointer == NULL vagy fastPointer->next == NULL). Ha nem, a gyors és lassú mutatók végül találkoznak, ami azt jelenti, hogy a hivatkozott listának van egy ciklusa.

C++ program megvalósítása a fenti módszerhez (Floyd's Cycle):

Kimenet:

Magyarázat:

1. 1. Először a megfelelő fejlécek, például „bits/stdc++.h” és „std::cout” kerülnek bele.
   2. Ezután deklarálódik a „csomópont” struktúra, amely egy csomópontot jelent a hivatkozott listában. Egy következő mutató, amely a lista következő csomópontjához vezet, egy egész szám adatmezővel együtt minden csomópontban szerepel.
   3. Ezután meghatározza a „deleteLoop” és a „detectAndDeleteLoop” két funkciót. A hurok eltávolítása a hivatkozott listából az első módszerrel történik, a második függvény segítségével pedig egy hurkot észlel a listában, amely ezután meghívja az első eljárást a hurok eltávolítására.
   4. A fő függvényben létrejön egy új, öt csomóponttal összekapcsolt lista, és egy hurok jön létre úgy, hogy az utolsó csomópont következő mutatóját a harmadik csomópontra állítja.
   5. Ezután meghívja a „detectAndDeleteLoop” metódust, miközben argumentumként átadja a hivatkozott lista fejcsomópontját. A hurkok azonosításához ez a funkció a „Lassú és gyors mutatók” megközelítést használja. Két mutatót alkalmaz, amelyek a lista tetején kezdődnek, a slowPTR és a fastPTR. Míg a gyors mutató egyszerre két csomópontot mozgat, a lassú mutató egyszerre csak egy csomópontot mozgat. A gyors mutató végül megelőzi a lassú mutatót, ha a lista hurkot tartalmaz, és a két pont ugyanabban a csomópontban ütközik.
   6. A függvény meghívja a „deleteLoop” függvényt, ha hurkot talál, bemenetként megadva a lista fejcsomópontját és a lassú és gyors mutatók metszéspontját. Ez az eljárás két mutatót hoz létre, a ptr1-et és a ptr2-t a lista főcsomópontjához, és megszámolja a hurokban lévő csomópontok számát. Ezt követően egy k csomópontot lép előre, ahol k a ciklus csomópontjainak teljes száma. Ezután mindaddig, amíg a ciklus elején nem találkoznak, mindkét pontot előrelépi egy csomópontonként. A ciklus ezután megszakad, ha a ciklus végén lévő csomópont következő mutatóját NULL-ra állítja.
   7. A hurok eltávolítása után utolsó lépésként megjeleníti a hivatkozott listát.

3. megközelítés: Rekurzió

A rekurzió egy olyan technika, amellyel a problémákat kisebb, könnyebb részproblémákra osztva lehet megoldani. A rekurzió használható egy egyedileg csatolt lista bejárására abban az esetben, ha a rendszer a lista következő csomópontjához tartozó függvényt folyamatosan futtatva ciklust talál, amíg el nem éri a lista végét.

Egy egyedileg csatolt listában a rekurziós ciklus megtalálásának alapelve az, hogy a lista elején kezdjük, minden lépésnél megjelöljük az aktuális csomópontot látogatottként, majd a következő csomópontra ugorjuk a függvény rekurzív meghívásával. azt a csomópontot. A metódus a teljes csatolt listán ismétlődik, mert rekurzívan hívják.

A lista hurkot tartalmaz, ha a függvény egy korábban látogatottként megjelölt csomóponttal találkozik; ebben az esetben a függvény igazat adhat vissza. A metódus hamis értéket adhat vissza, ha eléri a lista végét anélkül, hogy egy látogatott csomóponton keresztül futna, ami azt jelzi, hogy nincs hurok.

Bár ez a technika a rekurzió felhasználására hurok keresésére egyetlen linkelt listában könnyen használható és érthető, az idő és tér bonyolultsága szempontjából nem biztos, hogy ez a leghatékonyabb.

C++ program megvalósítása a fenti metódushoz (Rekurzió):

Kimenet:

Magyarázat:

1. 1. A funkció detectLoopLinkedList() ebben a programban elfogadja a linkelt lista fejét bemenetként.
   2. A függvény a rekurziót használja a hivatkozott lista ismétlésére. A rekurzió alapeseteként annak meghatározásával kezdődik, hogy az aktuális csomópont NULL-e. Ha igen, a metódus false értéket ad vissza, jelezve, hogy nem létezik hurok.
   3. Az aktuális csomópont „látogatott” tulajdonságának értéke ezután ellenőrzi, hogy korábban meglátogatták-e. Igazat ad vissza, ha meglátogatták, ami arra utal, hogy hurkot találtak.
   4. A függvény az aktuális csomópontot meglátogatottként jelöli meg, ha azt már meglátogatták, ha a „látogatott” tulajdonságát igazra változtatja.
   5. A meglátogatott változó értékét ezután ellenőrzi, hogy az aktuális csomópontot korábban meglátogatták-e. Ha korábban használták, akkor léteznie kell egy ciklusnak, és a függvény true értéket ad vissza.
   6. Végül a függvény átadással hívja meg magát a lista következő csomópontjával headNode->next érvként. Rekurzívan , ezt addig hajtják végre, amíg vagy egy hurkot nem talál, vagy az összes csomópontot meg nem látogatták. Ez azt jelenti, hogy a függvény a meglátogatott változót igazra állítja, ha az aktuális csomópontot még soha nem látogatták meg, mielőtt rekurzívan hívná magát a következő csomóponthoz a hivatkozott listában.
   7. A kód három csomópontot épít fel, és összekapcsolja őket, hogy egy linkelt listát hozzon létre a fő funkció . A módszer detectLoopLinkedList() ezután meghívódik a lista fejcsomópontján. A program előállítja A hurok levonva a linkelt listában ” ha detectLoopLinkedList() igazat ad vissza; különben kiadja ' Nem észlelhető hurok a hivatkozott listában “.
   8. A kód ezután beszúr egy hurkot a hivatkozott listába úgy, hogy az utolsó csomópont következő mutatóját a második csomópontra állítja. Ezután a függvény eredményétől függően lefut detectLoopLinkedList() újra, és vagy ' A hurok levonva a linkelt listában ” vagy „ Nem észlelhető hurok a hivatkozott listában .”

4. megközelítés: Stack használata

A hivatkozott listában lévő hurkok verem és a „mélység-első keresés” (DFS) módszerrel találhatók meg. Az alapkoncepció az, hogy a hivatkozott listán végig kell ismételni, és minden csomópontot a verembe kell tolni, ha még nem látogatták meg. A ciklus akkor kerül felismerésre, ha egy már a veremben lévő csomópont ismét találkozik.

Íme az eljárás rövid leírása:

1. 1. Hozzon létre egy üres veremet és egy változót a meglátogatott csomópontok rögzítéséhez.
   2. Tolja a linkelt listát a verembe, a tetejétől kezdve. Jegyezze fel, hogy a fejet meglátogatták.
   3. Tolja a lista következő csomópontját a verembe. Adjon hozzá egy látogatási jelet ehhez a csomóponthoz.
   4. A lista bejárása közben minden új csomópontot a verembe tolva jelezze, hogy meglátogatták.
   5. Ellenőrizze, hogy egy korábban meglátogatott csomópont van-e a verem tetején, ha találkozik vele. Ha igen, akkor a rendszer egy hurkot talált, és a hurkot a veremben lévő csomópontok azonosítják.
   6. Vegye ki a csomópontokat a veremből, és folytassa a lista bejárását, ha nem található hurok.

C++ program implementáció a fenti metódushoz (Stack)

Kimenet:

Magyarázat:

Ez a program egy verem segítségével állapítja meg, hogy az egyszeri hivatkozású listában van-e ciklus.

• 1. A bemeneti/kimeneti adatfolyam-könyvtár és a veremkönyvtár egyaránt megtalálható az első sorban.

  2. A szabványos névtér a második sorban található, lehetővé téve számunkra, hogy hozzáférjünk a bemeneti/kimeneti adatfolyam-könyvtár funkcióihoz anélkül, hogy az „std::” előtagot kellene előtagoznunk.

  3. A következő sor definiálja a struct Node-ot, amely két tagból áll: egy „adat” nevű egész számból és egy másik csomópontra mutató mutatóból, amelyet „következőnek” neveznek.

  4. A linkelt lista fejléce a detectLoopLinkedList() metódus bemenete, amelyet a következő sorban definiálunk. A függvény logikai értéket állít elő, amely jelzi, hogy a rendszer talált-e hurkot vagy sem.

  5. A függvényen belül létrejön egy csomó csomóponti mutató, amelyet „veremnek” neveznek, és egy „tempNode” nevű csomópontra mutató mutatót, amely a headNode értékével van inicializálva.

  6. Ezután mindaddig, amíg a tempNode nem null mutató, beírunk egy while ciklust.

  (a) A verem legfelső elemének meg kell egyeznie az aktuális csomóponttal, hogy megállapíthassuk, nem üres. Igazat adunk vissza, ha ez a helyzet, mert hurkot találtunk.

  (b) Ha a fent említett feltétel hamis, akkor az aktuális csomópont-mutató a verembe kerül, és a tempNode a következő csomópontra kerül a hivatkozott listában.

  7. A while ciklus után false-t adunk vissza, mert nem figyeltünk meg ciklust.

  8. Összeállítunk három csomópont objektumot, és inicializáljuk őket a main() függvényben. Mivel az első példában nincs hurok, minden csomópont „következő” mutatóit megfelelően beállítottuk.

Következtetés:

Összefoglalva, a hivatkozások listájában található hurkok észlelésének legjobb módja az adott használati esettől és a probléma korlátaitól függ. A Hash Table és a Floyd cikluskereső algoritmusa hatékony módszerek, és széles körben használják a gyakorlatban. A verem és a rekurzió kevésbé hatékony módszerek, de intuitívabbak.