Nodul final al unei liste conectate care are o buclă se va referi la un alt nod din aceeași listă, mai degrabă decât la NULL. Dacă există un nod într-o listă legată care poate fi accesat în mod repetat urmând următorul indicator, lista se spune că au un ciclu.
De obicei, ultimul nod al Listei legate se referă la o referință NULL pentru a indica concluzia listei. Cu toate acestea, într-o listă legată cu o buclă, nodul final al listei se referă la un nod de început, un nod intern sau el însuși. Prin urmare, în astfel de circumstanțe, trebuie să identificăm și să încheiem bucla setând referința următorului nod la NULL. Porțiunea de detectare a buclei dintr-o listă legată este explicată în acest articol.
În C++, există numeroase moduri de a găsi bucle într-o listă legată:
Abordare bazată pe tabel de hash : Această abordare stochează adresele nodurilor vizitate într-un tabel hash. O buclă în lista legată există dacă un nod este deja prezent în tabelul hash atunci când este vizitat din nou.
Abordarea ciclului lui Floyd : Algoritmul „țestoasă și iepure”, cunoscut în mod obișnuit ca algoritmul de găsire a ciclului al lui Floyd: Această tehnică folosește două indicatori, unul care se mișcă mai lent decât celălalt, iar celălalt se mișcă mai repede. Indicatorul mai rapid îl va depăși în cele din urmă pe indicatorul mai lent dacă există o buclă în lista legată, dezvăluind existența buclei.
Metoda recursiva : Această metodă trece prin lista legată apelându-se din nou și din nou. Lista legată conține o buclă dacă nodul curent a fost vizitat anterior.
Abordare bazată pe stivă : Această abordare stochează adresele nodurilor vizitate într-o stivă. O buclă în lista legată este prezentă dacă un nod este deja acolo în stivă când este vizitat din nou.
Să explicăm fiecare abordare în detaliu pentru a înțelege conceptul.
Abordarea 1: Abordarea HashSet
Utilizarea hashingului este cea mai simplă metodă. Aici, parcurgem lista unul câte unul, păstrând un tabel hash cu adresele nodurilor. Prin urmare, există o buclă dacă rulăm vreodată prin următoarea adresă a nodului curent care este deja conținută în tabelul hash. În caz contrar, nu există nicio buclă în Lista legată dacă ne întâlnim cu NULL (adică ajungem la sfârșitul Listei legate).
Va fi destul de ușor să implementați această strategie.
În timp ce parcurgem lista legată, vom folosi un hashmap non-ordonat și vom continua să adăugăm noduri la ea.
Acum, odată ce întâlnim un nod care este deja afișat pe hartă, vom ști că am ajuns la începutul buclei.
-
- În plus, am păstrat două indicatoare la fiecare pas, headNode arătând spre nodul curent și lastNode indicând către nodul anterior al nodului curent, în timp ce se repetă.
- Ca a noastră headNode indică acum către nodul de pornire al buclei și as lastNode indica nodul către care îndrepta capul (adică se referă la lastNode al buclei), nostru headNode în prezent indică către nodul de pornire al buclei.
- Bucla va fi întreruptă prin setarea l astNode->next == NULL .
Făcând acest lucru, nodul buclei de sfârșit, în loc să se refere la nodul inițial al buclei, începe să indice spre NULL.
Complexitatea medie în timp și spațiu a metodei hashing este O(n). Cititorul trebuie să fie întotdeauna conștient de faptul că implementarea Hashing DataStructure încorporată în limbajul de programare va determina complexitatea totală a timpului în cazul unei coliziuni în hashing.
Implementarea programului C++ pentru metoda de mai sus (HashSet):
#include
folosind namespace std;
struct Node {
valoare int;
struct Node * Următorul;
} ;
Nodul * newNode ( valoare int )
{
Nodul * tempNode = nou Nod;
tempNode- > valoare = valoare;
tempNode- > următorul = NULL;
întoarcere tempNode;
}
// Identificați și eliminați orice bucle potențiale
// în o listă legată cu această funcție.
void functionHashMap ( Nodul * headNode )
{
// S-a creat o hartă neordonată pentru a implementa harta Hash
hartă_neordonată < Nodul * , int > hash_map;
// pointer la lastNode
Nodul * lastNode = NULL;
in timp ce ( headNode ! = NULL ) {
// Dacă lipsește un nod de pe hartă, adăugați-l.
dacă ( hash_map.find ( headNode ) == hash_map.end ( ) ) {
hash_map [ headNode ] ++;
lastNode = headNode;
headNode = headNode- > Următorul;
}
// Dacă este prezent un ciclu, a stabilit nodul final următorul indicator către NULL.
else {
lastNode->next = NULL;
pauză;
}
}
}
// Afișează lista legată
void display (Node* headNode)
{
while (headNode != NULL) {
cout << headNode->valoare << ' ';
headNode = headNode->next;
}
cout << endl;
}
/* Functie principala*/
int main()
{
Nod* headNode = newNode(48);
headNode->next = headNode;
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Creați o buclă în linkedList */
headNode->next->next->next->next->next = headNode->next->next;
functionHashMap(headNode);
printf('Lista legata fara bucla \n');
display(headNode);
întoarce 0;
}
Ieșire:
Lista legată fără buclă
48 18 13 2 8
Explicația pas cu pas a codului este oferită mai jos:
-
- Fișierul antet bits/stdc++.h>, care conține toate bibliotecile comune C++, este inclus în cod.
- Este construită o structură numită „Nod” și are doi membri: o referință la următorul nod din listă și un număr întreg numit „valoare”.
- Cu o valoare întreagă ca intrare și indicatorul „următorul” setat la NULL, funcția „newNode” creează un nou nod cu acea valoare.
- Functia ' functionHashMap’ este definit, care ia ca intrare un pointer către nodul principal al listei legate.
- În interiorul ' functionHashMap „, este creată o hartă_neordonată numită „hartă_hash”, care este utilizată pentru a implementa o structură de date hărți hash.
- Un pointer către ultimul nod al listei este inițializat la NULL.
- O buclă while este folosită pentru a parcurge lista legată, care începe de la nodul principal și continuă până când nodul principal este NULL.
- Pointerul lastNode este actualizat la nodul curent din bucla while dacă nodul curent (headNode) nu este deja prezent în harta hash.
- Dacă nodul curent este găsit în hartă, înseamnă că o buclă este prezentă în lista legată. Pentru a elimina bucla, următorul indicator al lastNode este setat sa NUL iar bucla while este întreruptă.
- Nodul principal al listei legate este folosit ca intrare pentru o funcție numită „afișare”, care scoate valoarea fiecărui nod din listă de la început până la sfârșit.
- În principal funcția, creând o buclă.
- Funcția „functionHashMap” este apelată cu pointerul headNode ca intrare, care elimină bucla din listă.
- Lista modificată este afișată folosind funcția „afișare”.
Abordarea 2: Ciclul lui Floyd
Algoritmul de detectare a ciclurilor lui Floyd, adesea cunoscut sub numele de algoritmul broască țestoasă și iepure de câmp, oferă baza acestei metode de localizare a ciclurilor într-o listă conexă. Indicatorul „lent” și indicatorul „rapid”, care parcurg lista cu diferite viteze, sunt cele două indicatoare utilizate în această tehnică. Indicatorul rapid avansează cu doi pași, în timp ce indicatorul lent avansează cu un pas la fiecare iterație. Un ciclu în lista legată există dacă cele două puncte se întâlnesc vreodată față în față.
1. Cu nodul principal al listei legate, inițializam doi pointeri numiti rapid și lent.
2. Acum rulăm o buclă pentru a trece prin lista legată. Indicatorul rapid trebuie mutat cu două locații în fața indicatorului lent la fiecare pas de iterație.
3. Nu va exista o buclă în lista legată dacă indicatorul rapid ajunge la sfârșitul listei (fastPointer == NULL sau fastPointer->next == NULL). Dacă nu, indicatoarele rapide și lente se vor întâlni în cele din urmă, ceea ce înseamnă că lista legată are o buclă.
Implementarea programului C++ pentru metoda de mai sus (ciclul Floyd):
#include
folosind namespace std;
/* Nod listă de linkuri */
struct Node {
int date;
struct Node * Următorul;
} ;
/* Funcție pentru a elimina bucla. */
void deleteLoop ( struct Node * , struct Node * ) ;
/* Acest funcţie localizează și elimină buclele de listă. Se cedează 1
dacă era o buclă în lista; altfel , se întoarce 0 . */
int detectAndDeleteLoop ( struct Node * listă )
{
struct Node * slowPTR = listă, * fastPTR = listă;
// Repetați pentru a verifica dacă bucla este acolo.
in timp ce ( slowPTR && fastPTR && fastPTR- > Următorul ) {
slowPTR = slowPTR- > Următorul;
fastPTR = fastPTR- > Următorul- > Următorul;
/* Dacă slowPTR și fastPTR se întâlnesc la un moment dat apoi Acolo
este o buclă */
dacă ( slowPTR == fastPTR ) {
deleteLoop ( slowPTR, listă ) ;
/* Întoarcere 1 pentru a indica faptul că a fost descoperită o buclă. */
întoarcere 1 ;
}
}
/* Întoarcere 0 pentru a indica faptul că nu a fost descoperită nicio buclă. */
întoarcere 0 ;
}
/* Funcție de ștergere a buclei din lista legată.
loopNode indică către unul dintre nodurile buclei și headNode indică
la nodul de pornire al listei legate */
void deleteLoop ( struct Node * loopNode, struct Node * headNode )
{
struct Node * ptr1 = loopNode;
struct Node * ptr2 = loopNode;
// Numărați câte noduri sunt în bucla.
nesemnat int k = 1 , eu;
in timp ce ( ptr1- > Următorul ! = ptr2 ) {
ptr1 = ptr1- > Următorul;
k++;
}
// Remediați un indicator către headNode
ptr1 = headNode;
// Și celălalt pointer către k noduri după headNode
ptr2 = headNode;
pentru ( i = 0 ; i < k; i++ )
ptr2 = ptr2- > Următorul;
/* Când ambele puncte sunt mutate simultan,
se vor ciocni la buclă nodul de început al lui. */
în timp ce (ptr2 != ptr1) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
// Obține nodul' s ultimul indicator.
in timp ce ( ptr2- > Următorul ! = ptr1 )
ptr2 = ptr2- > Următorul;
/* Pentru a închide bucla, a stabilit ulterior
nodul la buclă nodul final al lui. */
ptr2->next = NULL;
}
/* Funcție de afișare a listei legate */
void displayLinkedList(struct Node* nod)
{
// afișează lista legată după ștergerea buclei
în timp ce (nodul != NULL) {
cout << nod->date << ' ';
nod = nod->next;
}
}
struct Node* newNode (cheie int)
{
struct Node* temp = new Node();
temp->data = cheie;
temp->next = NULL;
temperatura de retur;
}
// Codul principal
int main()
{
struct Node* headNode = newNode(48);
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Creați o buclă */
headNode->next->next->next->next->next = headNode->next->next;
// afișează bucla în lista legată
//displayLinkedList(headNode);
detectAndDeleteLoop(headNode);
cout << 'Lista legată după nicio buclă \n';
displayLinkedList(headNode);
întoarce 0;
}
Ieșire:
Lista legată după nicio buclă
48 18 13 2 8
Explicaţie:
-
- Anteturile relevante, cum ar fi „bits/stdc++.h” și „std::cout”, sunt incluse mai întâi.
- Structura „Nod”, care reprezintă un nod din lista legată, este apoi declarată. Un indicator următor care duce la următorul nod din listă este inclus împreună cu un câmp de date întreg în fiecare nod.
- Apoi, definește „deleteLoop” și „detectAndDeleteLoop”, două funcții. O buclă este eliminată dintr-o listă legată folosind prima metodă și o buclă este detectată în listă folosind a doua funcție, care apelează apoi prima procedură pentru a elimina bucla.
- O nouă listă legată cu cinci noduri este creată în funcția principală și se stabilește o buclă prin setarea următorului pointer al ultimului nod la al treilea nod.
- Apoi face un apel la metoda „detectAndDeleteLoop” în timp ce trece nodul principal al listei legate ca argument. Pentru a identifica buclele, această funcție folosește abordarea „Indicatoare lente și rapide”. Utilizează doi indicatori care încep în partea de sus a listei, slowPTR și fastPTR. În timp ce indicatorul rapid mută două noduri simultan, indicatorul lent mută doar un nod la un moment dat. Indicatorul rapid îl va depăși în cele din urmă pe indicatorul lent dacă lista conține o buclă, iar cele două puncte se vor ciocni la același nod.
- Funcția invocă funcția „deleteLoop” dacă găsește o buclă, furnizând nodul principal al listei și intersecția pointerelor lente și rapide ca intrări. Această procedură stabilește doi pointeri, ptr1 și ptr2, către nodul principal al listei și numără numărul de noduri din buclă. După aceea, avansează cu un pointer k noduri, unde k este numărul total de noduri din buclă. Apoi, până când se întâlnesc la începutul buclei, avansează ambele puncte câte un nod. Bucla este apoi întreruptă prin setarea următorului pointer al nodului de la sfârșitul buclei la NULL.
- După eliminarea buclei, afișează lista legată ca pas final.
Abordarea 3: Recursie
Recursiunea este o tehnică de rezolvare a problemelor prin împărțirea lor în subprobleme mai mici și mai ușoare. Recursiunea poate fi folosită pentru a parcurge o listă legată individual în cazul în care este găsită o buclă, rulând continuu o funcție pentru următorul nod din listă până când se ajunge la sfârșitul listei.
Într-o listă legată individual, principiul de bază din spatele utilizării recursiunii pentru a găsi o buclă este să începeți din capul listei, să marcați nodul curent ca vizitat la fiecare pas și apoi să treceți la următorul nod, invocând recursiv funcția pentru acel nod. Metoda va itera pe lista completă legată deoarece este apelată recursiv.
Lista conține o buclă dacă un nod care a fost marcat anterior ca vizitat este întâlnit de funcție; în acest caz, funcția poate returna true. Metoda poate returna false dacă ajunge la sfârșitul listei fără a rula peste un nod vizitat, ceea ce indică faptul că nu există nicio buclă.
Deși această tehnică de utilizare a recursiunii pentru a găsi o buclă într-o singură listă legată este ușor de utilizat și de înțeles, s-ar putea să nu fie cea mai eficientă din punct de vedere al complexității timpului și spațiului.
Implementarea programului C++ pentru metoda de mai sus (recursiune):
#include
folosind namespace std;
struct Node {
int date;
Nodul * Următorul;
bool vizitat;
} ;
// Detectarea buclei listei conectate funcţie
bool detectLoopLinkedList ( Nodul * headNode ) {
dacă ( headNode == NULL ) {
întoarcere fals ; // Dacă lista legată este goală, cea de bază caz
}
// Există o buclă dacă nodul curent are
// fost deja vizitat.
dacă ( headNode- > vizitat ) {
întoarcere Adevărat ;
}
// Adăugați un semn de vizitare la nodul curent.
headNode- > vizitat = Adevărat ;
// Apelarea codului pentru nodul următor în mod repetat
întoarcere detectLoopLinkedList ( headNode- > Următorul ) ;
}
int principal ( ) {
Nodul * headNode = Nod nou ( ) ;
Nodul * secondNode = Nod nou ( ) ;
Nodul * thirdNode = Nod nou ( ) ;
headNode- > date = 1 ;
headNode- > următorul = al doileaNod;
headNode- > vizitat = fals ;
al doilea nod- > date = 2 ;
al doilea nod- > următorul = al treileaNod;
al doilea nod- > vizitat = fals ;
al treilea nod- > date = 3 ;
al treilea nod- > următorul = NULL; // Fără buclă
al treilea nod- > vizitat = fals ;
dacă ( detectLoopLinkedList ( headNode ) ) {
cout << „Bucla detectată în lista conectată” << endl;
} altfel {
cout << „Nu a fost detectată nicio buclă în lista conectată” << endl;
}
// Crearea unei bucle
al treilea nod- > următorul = al doileaNod;
dacă ( detectLoopLinkedList ( headNode ) ) {
cout << „Bucla detectată în lista conectată” << endl;
} altfel {
cout << „Nu a fost detectată nicio buclă în lista conectată” << endl;
}
întoarcere 0 ;
}
Ieșire:
Nu a fost detectată nicio buclă în lista legată
Bucla detectată în lista legată
Explicaţie:
-
- Functia detectLoopLinkedList() în acest program acceptă capul listei legate ca intrare.
- Recursiunea este utilizată de funcție pentru a itera prin lista legată. Ca caz de bază pentru recursivitate, începe prin a determina dacă nodul curent este NULL. Dacă da, metoda returnează false, indicând că nu există nicio buclă.
- Valoarea proprietății „vizitate” a nodului curent este apoi verificată pentru a vedea dacă a fost vizitată anterior. Revine adevărat dacă a fost vizitat, sugerând că a fost găsită o buclă.
- Funcția marchează nodul curent ca vizitat dacă a fost deja vizitat prin schimbarea proprietății sale „vizitate” la true.
- Valoarea variabilei vizitate este apoi verificată pentru a vedea dacă nodul curent a fost vizitat anterior. Dacă a fost folosit înainte, trebuie să existe o buclă, iar funcția returnează true.
- În cele din urmă, funcția se autoapelează cu următorul nod din listă prin trecere headNode->next ca argument. Recursiv , aceasta se realizează până când fie se găsește o buclă, fie până când toate nodurile au fost vizitate. Înseamnă, funcția setează variabila vizitată la adevărat dacă nodul curent nu a fost niciodată vizitat înainte de a se apela recursiv pentru următorul nod din lista legată.
- Codul construiește trei noduri și le unește pentru a produce o listă legată în functie principala . Metoda detectLoopLinkedList() este apoi invocat pe nodul principal al listei. Programul produce „ Bucla dedusă în lista legată ' dacă detectLoopLinkedList() returnează adevărat; altfel, iese „ Nu a fost detectată nicio buclă în lista conectată „.
- Codul inserează apoi o buclă în lista legată, setând următorul pointer al ultimului nod la al doilea nod. Apoi, în funcție de rezultatul funcției, rulează detectLoopLinkedList() din nou și produce fie „ Bucla dedusă în lista legată ” sau ” Nu a fost detectată nicio buclă în lista conectată .”
Abordarea 4: Utilizarea Stivei
Buclele dintr-o listă conectată pot fi găsite folosind o stivă și metoda „căutare în profunzime” (DFS). Conceptul fundamental este de a repeta prin lista legată, împingând fiecare nod pe stivă dacă nu a fost deja vizitat. O buclă este recunoscută dacă un nod care este deja pe stivă este întâlnit din nou.
Iată o scurtă descriere a procedurii:
-
- Creați o stivă goală și o variabilă pentru a înregistra nodurile care au fost vizitate.
- Împingeți lista legată în stivă, începând din partea de sus. Notați că capul a fost vizitat.
- Împingeți următorul nod din listă pe stivă. Adăugați un semn de vizitare la acest nod.
- Pe măsură ce parcurgeți lista, împingeți fiecare nod nou pe stivă pentru a indica faptul că a fost vizitat.
- Verificați pentru a vedea dacă un nod care a fost vizitat anterior se află în partea de sus a stivei dacă este întâlnit. Dacă da, a fost găsită o buclă, iar bucla este identificată de nodurile din stivă.
- Scoateți nodurile din stivă și continuați să traversați lista dacă nu este găsită nicio buclă.
Implementarea programului C++ pentru metoda de mai sus (Stiva)
#include
#include
folosind namespace std;
struct Node {
int date;
Nodul * Următorul;
} ;
// Funcție de detectare a buclei în o listă legată
bool detectLoopLinkedList ( Nodul * headNode ) {
grămadă < Nodul *> grămadă;
Nodul * tempNode = headNode;
in timp ce ( tempNode ! = NULL ) {
// dacă elementul superior al stivei se potrivește
// nodul curent și stiva nu sunt goale
dacă ( ! stivă.gol ( ) && stivă.top ( ) == tempNode ) {
întoarcere Adevărat ;
}
stivă.împinge ( tempNode ) ;
tempNode = tempNode- > Următorul;
}
întoarcere fals ;
}
int principal ( ) {
Nodul * headNode = Nod nou ( ) ;
Nodul * secondNode = Nod nou ( ) ;
Nodul * thirdNode = Nod nou ( ) ;
headNode- > date = 1 ;
headNode- > următorul = al doileaNod;
al doilea nod- > date = 2 ;
al doilea nod- > următorul = al treileaNod;
al treilea nod- > date = 3 ;
al treilea nod- > următorul = NULL; // Fără buclă
dacă ( detectLoopLinkedList ( headNode ) ) {
cout << „Bucla detectată în lista conectată” << endl;
} altfel {
cout << „Nu a fost detectată nicio buclă în lista conectată” << endl;
}
// Crearea unei bucle
al treilea nod- > următorul = al doileaNod;
dacă ( detectLoopLinkedList ( headNode ) ) {
cout << „Bucla detectată în lista conectată” << endl;
} altfel {
cout << „Nu a fost detectată nicio buclă în lista conectată” << endl;
}
Ieșire:
Nu a fost detectată nicio buclă în lista legată
Bucla detectată în lista legată
Explicaţie:
Acest program folosește o stivă pentru a afla dacă o listă legată individual are o buclă.
- 1. Biblioteca fluxului de intrare/ieșire și biblioteca stivă sunt ambele prezente în prima linie.
2. Spațiul de nume standard este inclus în a doua linie, permițându-ne să accesăm funcțiile bibliotecii fluxului de intrare/ieșire fără a fi nevoie să le prefixăm cu „std::.”
3. Următoarea linie definește struct Node, care constă din doi membri: un întreg numit „date” și un pointer către un alt Nod numit „next”.
4. Capul listei legate este o intrare pentru metoda detectLoopLinkedList(), care este definită pe linia următoare. Funcția produce o valoare booleană care indică dacă a fost găsită sau nu o buclă.
5. O stivă de pointeri Node numită „stivă” și un pointer către un Nod numit „tempNode” care este inițializat cu valoarea headNode sunt ambele create în interiorul funcției.
6. Apoi, atâta timp cât tempNode nu este un pointer nul, introducem o buclă while.
(a) Elementul superior al stivei trebuie să se potrivească cu nodul curent pentru a putea determina că nu este gol. Revenim true dacă acesta este cazul deoarece a fost găsită o buclă.
(b) Dacă condiția menționată mai sus este falsă, indicatorul nodului curent este împins pe stivă, iar tempNode este setat la următorul nod din lista legată.
7. Revenim false după bucla while deoarece nu a fost observată nicio buclă.
8. Construim trei obiecte Node și le inițializam în funcția main(). Deoarece nu există nicio buclă în primul exemplu, setăm corect indicatorii „următorul” fiecărui Nod.
Concluzie:
În concluzie, cea mai bună metodă de a detecta bucle într-o listă legată depinde de cazul de utilizare specific și de constrângerile problemei. Hash Table și algoritmul de găsire a ciclurilor lui Floyd sunt metode eficiente și sunt utilizate pe scară largă în practică. Stiva și recursiunea sunt metode mai puțin eficiente, dar sunt mai intuitive.