Atklājiet cilpu saistītajā sarakstā programmā C++

Saistītā saraksta beigu mezgls, kuram ir cilpa, atsauksies uz citu mezglu tajā pašā sarakstā, nevis uz NULL. Ja saistītajā sarakstā ir mezgls, kuram var piekļūt atkārtoti, sekojot nākamajam rādītājam, tiek uzskatīts, ka saraksts ir šāds. ir cikls.

Parasti saistītā saraksta pēdējais mezgls attiecas uz NULL atsauci, lai apzīmētu saraksta secinājumu. Tomēr saistītajā sarakstā ar cilpu saraksta beigu mezgls attiecas uz sākuma mezglu, iekšējo mezglu vai sevi. Tāpēc šādos apstākļos mums ir jāidentificē un jāpārtrauc cilpa, iestatot nākamā mezgla atsauci uz NULL. Šajā rakstā ir izskaidrota cilpas noteikšanas daļa saistītajā sarakstā.

Programmā C++ ir vairāki veidi, kā saistītajā sarakstā atrast cilpas:

Uz jaukšanas tabulu balstīta pieeja : šī pieeja glabā apmeklēto mezglu adreses hash tabulā. Saistītajā sarakstā pastāv cilpa, ja mezgls jau atrodas jaucēj tabulā, kad tas tiek apmeklēts vēlreiz.

Floida cikla pieeja : “Bruņurupuča un zaķa” algoritms, kas plaši pazīstams kā Floida cikla noteikšanas algoritms. Šajā tehnikā tiek izmantoti divi rādītāji, no kuriem viens kustas lēnāk par otru un otrs ātrāk. Ātrākais rādītājs galu galā apsteigs lēnāko rādītāju, ja saistītajā sarakstā ir cilpa, atklājot cilpas esamību.

Rekursīvā metode : šī metode iet cauri saistītajam sarakstam, izsaucot sevi atkal un atkal. Saistītajā sarakstā ir cilpa, ja pašreizējais mezgls ir iepriekš apmeklēts.

Uz steku balstīta pieeja : šī pieeja glabā apmeklēto mezglu adreses kaudzē. Saistītajā sarakstā ir cilpa, ja mezgls jau atrodas kaudzē, kad tas tiek apmeklēts vēlreiz.

Detalizēti izskaidrosim katru pieeju, lai saprastu koncepciju.

1. pieeja: HashSet pieeja

Jaukšanas izmantošana ir visvienkāršākā metode. Šeit mēs ejam cauri sarakstam pa vienam, vienlaikus saglabājot jaucējtabulu ar mezglu adresēm. Tāpēc cilpa pastāv, ja mēs kādreiz saskaramies ar nākamo pašreizējā mezgla adresi, kas jau ir ietverta hash tabulā. Pretējā gadījumā saistītajā sarakstā nav cilpas, ja mēs saskaramies ar NULL (t.i., sasniedzam saistītā saraksta beigas).

Īstenot šo stratēģiju būs diezgan viegli.

Pārvietojot saistīto sarakstu, mēs izmantosim unordered_hashmap un turpināsim tam pievienot mezglus.

Tagad, kad mēs saskarsimies ar mezglu, kas jau ir parādīts kartē, mēs zināsim, ka esam nonākuši cilpas sākumā.

• • Turklāt katrā solī saglabājām divus rādītājus, headNode norādot uz pašreizējo mezglu un pēdējaisNode iterācijas laikā norāda uz pašreizējā mezgla iepriekšējo mezglu.
  • Kā mūsu headNode tagad norāda uz cilpas sākuma mezglu un kā pēdējaisNode norādīja uz mezglu, uz kuru norādīja galva (t.i., tas attiecas uz pēdējaisNode no cilpas), mūsu headNode pašlaik norāda uz cilpas sākuma mezglu.
  • Cilpa tiks pārtraukta, iestatot l astNode->next == NULL .

To darot, beigu cilpas mezgls tā vietā, lai atsauktos uz cilpas sākotnējo mezglu, sāk norādīt uz NULL.

Jaukšanas metodes vidējā laika un telpas sarežģītība ir O(n). Lasītājam vienmēr ir jāapzinās, ka iebūvētās jaukšanas datu struktūras ieviešana programmēšanas valodā noteiks kopējo laika sarežģītību jaukšanas sadursmes gadījumā.

C++ programmas ieviešana iepriekšminētajai metodei (HashSet):

Izvade:

Koda soli pa solim skaidrojums ir sniegts zemāk:

1. 1. Kodā ir iekļauts galvenes fails bits/stdc++.h>, kurā ir visas izplatītās C++ bibliotēkas.
   2. Tiek izveidota struktūra ar nosaukumu “Node”, un tai ir divi elementi: atsauce uz nākamo mezglu sarakstā un vesels skaitlis, ko sauc par “vērtību”.
   3. Ja kā ievades vērtība ir vesels skaitlis un rādītājs “next” ir iestatīts uz NULL, funkcija “newNode” izveido jaunu mezglu ar šo vērtību.
   4. Funkcija ' functionHashMap' ir definēts, kas kā ievadi izmanto rādītāju uz saistītā saraksta galveno mezglu.
   5. Iekšpusē ' FunctionHashMap ‘ funkcija, tiek izveidota unordered_map ar nosaukumu ‘hash_map’, ko izmanto jaucējkartes datu struktūras ieviešanai.
   6. Rādītājs uz saraksta pēdējo mezglu tiek inicializēts uz NULL.
   7. Lai šķērsotu saistīto sarakstu, tiek izmantota kamēr cilpa, kas sākas no galvenā mezgla un turpinās, līdz galvenais mezgls ir NULL.
   8. LastNode rādītājs tiek atjaunināts uz pašreizējo mezglu while cilpas iekšpusē, ja pašreizējais mezgls (headNode) jau nav iekļauts jaucējkartē.
   9. Ja pašreizējais mezgls ir atrasts kartē, tas nozīmē, ka saistītajā sarakstā ir cilpa. Lai noņemtu cilpu, nākamais rādītājs pēdējaisNode ir iestatīts uz NULL un kamēr cilpa ir pārtraukta.
   10. Saistītā saraksta galvenais mezgls tiek izmantots kā ievade funkcijai “displejs”, kas izvada katra saraksta mezgla vērtību no sākuma līdz beigām.
   11. Iekš galvenais funkciju, izveidojot cilpu.
   12. Funkcija “functionHashMap” tiek izsaukta ar headNode rādītāju kā ievadi, kas noņem cilpu no saraksta.
   13. Modificētais saraksts tiek parādīts, izmantojot displeja funkciju.

2. pieeja: Floida cikls

Floida cikla noteikšanas algoritms, kas bieži pazīstams kā bruņurupuča un zaķa algoritms, nodrošina pamatu šai metodei ciklu noteikšanai saistītā sarakstā. “Lēnā” un “ātrā” rādītāja, kas šķērso sarakstu dažādos ātrumos, ir divi šajā tehnikā izmantotie rādītāji. Ātrais rādītājs virzās uz priekšu divus soļus, savukārt lēnais rādītājs pavirzās par vienu soli katrā iterācijā. Cikls saistītajā sarakstā pastāv, ja abi punkti kādreiz saskaras aci pret aci.

1. Izmantojot saistītā saraksta galveno mezglu, mēs inicializējam divus rādītājus, ko sauc par ātru un lēnu.

2. Tagad mēs izpildām cilpu, lai pārvietotos pa saistīto sarakstu. Ātrais rādītājs katrā iterācijas solī ir jāpārvieto divas vietas priekšā lēnajam rādītājam.

3. Saistītajā sarakstā nebūs cilpa, ja ātrais rādītājs sasniegs saraksta beigas (fastPointer == NULL vai fastPointer->next == NULL). Ja nē, ātrie un lēnie rādītāji galu galā sastapsies, kas nozīmē, ka saistītajam sarakstam ir cilpa.

C++ programmas ieviešana iepriekšminētajai metodei (Floida cikls):

Izvade:

Paskaidrojums:

1. 1. Vispirms tiek iekļautas attiecīgās galvenes, piemēram, “bits/stdc++.h” un “std::cout”.
   2. Pēc tam tiek deklarēta struktūra “Node”, kas apzīmē mezglu saistītajā sarakstā. Nākamais rādītājs, kas ved uz nākamo mezglu sarakstā, ir iekļauts kopā ar veselu skaitļu datu lauku katrā mezglā.
   3. Pēc tam tas definē divas funkcijas “deleteLoop” un “detectAndDeleteLoop”. Cikla tiek noņemta no saistītā saraksta, izmantojot pirmo metodi, un sarakstā tiek noteikta cilpa, izmantojot otro funkciju, kas pēc tam izsauc pirmo procedūru, lai noņemtu cilpu.
   4. Galvenajā funkcijā tiek izveidots jauns saistīts saraksts ar pieciem mezgliem, un tiek izveidota cilpa, iestatot pēdējā mezgla nākamo rādītāju uz trešo mezglu.
   5. Pēc tam tas izsauc metodi “detectAndDeleteLoop”, kā argumentu nododot saistītā saraksta galveno mezglu. Lai identificētu cilpas, šī funkcija izmanto “Lēnās un ātrās norādes” pieeju. Tas izmanto divus norādes, kas sākas saraksta augšpusē, slowPTR un fastPTR. Kamēr ātrais rādītājs pārvieto divus mezglus vienlaikus, lēnais rādītājs vienlaikus pārvieto tikai vienu mezglu. Ātrais rādītājs galu galā apsteigs lēno rādītāju, ja sarakstā ir cilpa, un abi punkti saduras vienā un tajā pašā mezglā.
   6. Funkcija izsauc funkciju “deleteLoop”, ja tā atrod cilpu, kā ievadi nodrošinot saraksta galveno mezglu un lēno un ātro rādītāju krustpunktu. Šī procedūra izveido divus norādes, ptr1 un ptr2, uz saraksta galveno mezglu un saskaita mezglu skaitu cilpā. Pēc tam tas virza vienu rādītāju uz priekšu k mezglus, kur k ir kopējais mezglu skaits cilpā. Pēc tam, līdz tie satiekas cilpas sākumā, tas virza abus punktus pa vienam mezglam. Pēc tam cilpa tiek pārtraukta, iestatot nākamo mezgla rādītāju cilpas beigās uz NULL.
   7. Pēc cilpas noņemšanas tas parāda saistīto sarakstu kā pēdējo darbību.

3. pieeja: Rekursija

Rekursija ir paņēmiens problēmu risināšanai, sadalot tās mazākās, vieglākās apakšproblēmās. Rekursiju var izmantot, lai šķērsotu atsevišķi saistītu sarakstu, ja tiek atrasta cilpa, nepārtraukti izpildot funkciju nākamajam saraksta mezglam, līdz tiek sasniegts saraksta beigas.

Atsevišķi saistītā sarakstā rekursijas izmantošanas pamatprincips cilpas atrašanai ir sākt saraksta sākumā, katrā solī atzīmēt pašreizējo mezglu kā apmeklētu un pēc tam pāriet uz nākamo mezglu, rekursīvi izsaucot funkciju ka mezgls. Metode atkārtos visu saistīto sarakstu, jo tā tiek izsaukta rekursīvi.

Sarakstā ir cilpa, ja funkcija saskaras ar mezglu, kas iepriekš ir atzīmēts kā apmeklēts; šajā gadījumā funkcija var atgriezt patiesu. Metode var atgriezt false, ja tā sasniedz saraksta beigas, nepārskrienot apmeklēto mezglu, kas norāda, ka nav cilpas.

Lai gan šī metode rekursijas izmantošanai, lai atrastu cilpu vienā saistītā sarakstā, ir vienkārši lietojama un saprotama, tā var nebūt visefektīvākā laika un telpas sarežģītības ziņā.

C++ programmas ieviešana iepriekšminētajai metodei (Recursion):

Izvade:

Paskaidrojums:

1. 1. Funkcija detectLoopLinkedList() šajā programmā kā ievadi pieņem saistītā saraksta galveni.
   2. Funkcija izmanto rekursiju, lai atkārtotu saistīto sarakstu. Kā rekursijas pamatgadījums, tas sākas, nosakot, vai pašreizējais mezgls ir NULL. Ja tā, metode atgriež false, norādot, ka cilpa nepastāv.
   3. Pēc tam tiek pārbaudīta pašreizējā mezgla “apmeklētā” rekvizīta vērtība, lai redzētu, vai tas ir iepriekš apmeklēts. Tas atgriež patieso vērtību, ja tas ir apmeklēts, liekot domāt, ka ir atrasta cilpa.
   4. Funkcija atzīmē pašreizējo mezglu kā apmeklētu, ja tas jau ir apmeklēts, mainot tā rekvizītu “apmeklētais” uz patiesu.
   5. Pēc tam tiek pārbaudīta apmeklētā mainīgā vērtība, lai noskaidrotu, vai pašreizējais mezgls ir apmeklēts iepriekš. Ja tā ir izmantota iepriekš, cilpai ir jābūt, un funkcija atgriež true.
   6. Visbeidzot, funkcija izsauc sevi ar nākamo mezglu sarakstā, nododot garām headNode->nākamais kā arguments. Rekursīvi , tas tiek veikts, līdz tiek atrasta cilpa vai visi mezgli ir apmeklēti. Tas nozīmē, ka funkcija iestata apmeklēto mainīgo vērtību uz patiesu, ja pašreizējais mezgls nekad nav apmeklēts, pirms tiek rekursīvi izsaukts nākamajam mezglam saistītajā sarakstā.
   7. Kods izveido trīs mezglus un savieno tos, lai izveidotu saistīto sarakstu galvenā funkcija . Metode detectLoopLinkedList() pēc tam tiek izsaukts saraksta galvenajā mezglā. Programma veido ' Saistītajā sarakstā ir atņemta cilpa ” ja detectLoopLinkedList() atgriež patiesu; pretējā gadījumā tas izvada ' Saistītajā sarakstā nav konstatēta neviena cilpa “.
   8. Pēc tam kods ievieto cilpu saistītajā sarakstā, iestatot pēdējā mezgla nākamo rādītāju uz otro mezglu. Pēc tam atkarībā no funkcijas iznākuma tā tiek palaista detectLoopLinkedList() atkal un ražo vai nu Saistītajā sarakstā ir atņemta cilpa ” vai “ Saistītajā sarakstā nav konstatēta neviena cilpa ”.

4. pieeja: Stack izmantošana

Saistītā saraksta cilpas var atrast, izmantojot steku un “dziļuma meklēšanas” (DFS) metodi. Pamatkoncepcija ir atkārtot saistīto sarakstu, nospiežot katru mezglu uz steku, ja tas vēl nav apmeklēts. Cikla tiek atpazīta, ja atkal tiek sastapts mezgls, kas jau atrodas kaudzē.

Šeit ir īss procedūras apraksts:

1. 1. Izveidojiet tukšu steku un mainīgo, lai reģistrētu apmeklētos mezglus.
   2. Nospiediet saistīto sarakstu uz kaudzītes, sākot no augšas. Atzīmējiet, ka galva ir apmeklēta.
   3. Nospiediet nākamo mezglu sarakstā uz steku. Pievienojiet šim mezglam apmeklējuma atzīmi.
   4. Pārvietojot sarakstu, uzspiediet katru jauno mezglu uz steku, lai norādītu, ka tas ir apmeklēts.
   5. Pārbaudiet, vai iepriekš apmeklēts mezgls atrodas steka augšdaļā, ja tas tiek atrasts. Ja tā, cilpa ir atrasta, un cilpa tiek identificēta pēc steka mezgliem.
   6. Noņemiet mezglus no kaudzes un turpiniet šķērsot sarakstu, ja cilpa netiek atrasta.

C++ programmas ieviešana iepriekšminētajai metodei (Stack)

Izvade:

Paskaidrojums:

Šī programma izmanto kaudzi, lai noskaidrotu, vai atsevišķi saistītam sarakstam ir cilpa.

• 1. Ievades/izvades straumes bibliotēka un steka bibliotēka atrodas pirmajā rindā.

  2. Standarta nosaukumvieta ir iekļauta otrajā rindā, ļaujot mums piekļūt ievades/izvades straumes bibliotēkas funkcijām, nepievienojot tām prefiksu “std::”.

  3. Sekojošā rinda definē struktūras mezglu, kas sastāv no diviem elementiem: vesela skaitļa, ko sauc par “datiem”, un rādītāja uz citu mezglu, ko sauc par “nākamo”.

  4. Saistītā saraksta virsraksts ir ievade metodei detectLoopLinkedList(), kas ir definēta nākamajā rindā. Funkcija rada Būla vērtību, kas norāda, vai cilpa tika atrasta.

  5. Funkcijā tiek izveidota mezgla rādītāju kaudze, ko sauc par “steku”, un rādītājs uz mezglu ar nosaukumu “tempNode”, kas inicializēts ar headNode vērtību.

  6. Pēc tam, kamēr tempNode nav nulles rādītājs, mēs ievadām cilpu while.

  (a) Steka augšējam elementam ir jāatbilst pašreizējam mezglam, lai mēs varētu noteikt, ka tas nav tukšs. Mēs atgriežam patiesu, ja tas tā ir, jo ir atrasta cilpa.

  (b) Ja iepriekš minētais nosacījums ir nepatiess, pašreizējā mezgla rādītājs tiek nospiests uz steku, un tempNode tiek iestatīts uz nākamo mezglu saistītajā sarakstā.

  7. Mēs atgriežam false pēc while cilpas, jo netika novērota neviena cilpa.

  8. Mēs izveidojam trīs Node objektus un inicializējam tos funkcijā main(). Tā kā pirmajā piemērā nav cilpas, mēs pareizi iestatījām katra mezgla “nākamos” rādītājus.

Secinājums:

Visbeidzot, labākā metode cilpu noteikšanai saistītajā sarakstā ir atkarīga no konkrētā lietošanas gadījuma un problēmas ierobežojumiem. Hash Table un Floyd cikla noteikšanas algoritms ir efektīvas metodes, un tās tiek plaši izmantotas praksē. Stack un rekursija ir mazāk efektīvas metodes, taču tās ir intuitīvākas.