El node final d'una llista enllaçada que té un bucle farà referència a un altre node de la mateixa llista en lloc del NULL. Si hi ha un node en una llista enllaçada al qual es pot accedir repetidament seguint el punter següent, es diu que la llista tenir un cicle.
Normalment, l'últim node de la llista enllaçada fa referència a una referència NULL per indicar la conclusió de la llista. Tanmateix, en una llista enllaçada amb un bucle, el node final de la llista es refereix a un node inicial, un node intern oa si mateix. Per tant, en aquestes circumstàncies, hem d'identificar i finalitzar el bucle establint la referència del següent node a NULL. En aquest article s'explica la part de detecció del bucle en una llista enllaçada.
En C++, hi ha moltes maneres de trobar bucles en una llista enllaçada:
Enfocament basat en taules hash : Aquest enfocament emmagatzema les adreces dels nodes visitats en una taula hash. Existeix un bucle a la llista enllaçada si un node ja està present a la taula hash quan es torna a visitar.
Enfocament del cicle de Floyd : L'algorisme 'tortuga i llebre', conegut comunament com l'algoritme de recerca de cicles de Floyd: aquesta tècnica fa servir dos punters, un es mou més lentament que l'altre i l'altre es mou més ràpidament. El punter més ràpid finalment superarà el punter més lent si hi ha un bucle a la llista enllaçada, revelant l'existència del bucle.
Mètode recursiu : Aquest mètode passa per la llista enllaçada cridant-se a si mateix una i altra vegada. La llista enllaçada conté un bucle si el node actual s'ha visitat prèviament.
Enfocament basat en pila : Aquest enfocament emmagatzema les adreces dels nodes visitats en una pila. Hi ha un bucle a la llista enllaçada si ja hi ha un node a la pila quan es torna a visitar.
Expliquem cada enfocament en detall per entendre el concepte.
Enfocament 1: Enfocament HashSet
Utilitzar hashing és el mètode més senzill. Aquí, repassem la llista una per una mentre mantenim una taula hash amb les adreces dels nodes. Per tant, existeix un bucle si mai ens trobem amb la següent adreça del node actual que ja està continguda a la taula hash. En cas contrari, no hi ha cap bucle a la llista enllaçada si ens trobem amb NULL (és a dir, arribem al final de la llista enllaçada).
Serà bastant fàcil implementar aquesta estratègia.
Mentre travessem la llista enllaçada, utilitzarem un mapa de hash desordenat i seguirem afegint-hi nodes.
Ara, un cop ens trobem amb un node que ja es mostra al mapa, sabrem que hem arribat a l'inici del bucle.
-
- A més, vam mantenir dos punters a cada pas, headNode assenyalant el node actual i lastNode apuntant al node anterior del node actual, mentre s'itera.
- Com el nostre headNode ara apunta al node inicial del bucle i as lastNode estava apuntant al node al qual apuntava el cap (és a dir, es refereix al lastNode del bucle), el nostre headNode actualment apunta al node inicial del bucle.
- El llaç es trencarà configurant l astNode->next == NULL .
En fer això, el node del bucle final en lloc de referir-se al node inicial del bucle, comença a apuntar a NULL.
La complexitat mitjana de temps i espai del mètode hash és O(n). El lector sempre ha de ser conscient que la implementació de l'estructura de dades hashing integrada en el llenguatge de programació determinarà la complexitat total del temps en cas de col·lisió en el hash.
Implementació del programa C++ per al mètode anterior (HashSet):
#inclou
utilitzant namespace std;
struct Node {
valor int;
struct Node * Pròxim;
} ;
Node * nouNode ( valor int )
{
Node * tempNode = nou Node;
tempNode- > valor = valor;
tempNode- > següent = NULL;
tornar tempNode;
}
// Identifiqueu i elimineu qualsevol bucle potencial
// en una llista enllaçada amb aquesta funció.
void functionHashMap ( Node * headNode )
{
// S'ha creat un mapa_desordenat per implementar el mapa Hash
mapa_desordenat < Node * , int > hash_map;
// punter a lastNode
Node * lastNode = NULL;
mentre ( headNode ! = NULL ) {
// Si falta un node al mapa, afegiu-lo.
si ( hash_map.find ( headNode ) == hash_map.end ( ) ) {
hash_map [ headNode ] ++;
lastNode = capçalera;
headNode = headNode- > Pròxim;
}
// Si hi ha un cicle, conjunt el node final El següent punter a NULL.
altrament {
lastNode->next = NULL;
trencar;
}
}
}
// Mostra la llista enllaçada
visualització buida (Node* headNode)
{
mentre que (headNode != NULL) {
cout << headNode->valor << ' ';
capNode = capNode->següent;
}
cout << endl;
}
/* Funció principal*/
int main()
{
Node* capNode = nouNode(48);
headNode->next = headNode;
headNode->next = nouNode(18);
headNode->next->next = nouNode(13);
headNode->next->next->next = nouNode(2);
headNode->next->next->next->next = nouNode(8);
/* Crea un bucle a linkedList */
headNode->next->next->next->next->next = headNode->next->next;
functionHashMap(headNode);
printf('Llista enllaçada sense bucle \n');
display(headNode);
retorn 0;
}
Sortida:
Llista enllaçada sense bucle
48 18 13 2 8
L'explicació pas a pas del codi es proporciona a continuació:
-
- El fitxer de capçalera bits/stdc++.h>, que conté totes les biblioteques comunes de C++, s'inclou al codi.
- Es construeix una estructura anomenada 'Node' i té dos membres: una referència al següent node de la llista i un nombre enter anomenat 'valor'.
- Amb un valor enter com a entrada i el punter 'següent' establert a NULL, la funció 'newNode' crea un nou node amb aquest valor.
- La funció ' functionHashMap' està definit, que pren un punter al node principal de la llista enllaçada com a entrada.
- Dins del ' functionHashMap ', es crea un mapa_desordenat anomenat 'hash_map', que s'utilitza per implementar una estructura de dades de mapa hash.
- Un punter a l'últim node de la llista s'inicialitza a NULL.
- S'utilitza un bucle while per recórrer la llista enllaçada, que comença des del node principal i continua fins que el node principal és NULL.
- El punter lastNode s'actualitza al node actual dins del bucle while si el node actual (headNode) encara no està present al mapa hash.
- Si el node actual es troba al mapa, vol dir que hi ha un bucle a la llista enllaçada. Per eliminar el bucle, el punter següent del lastNode està configurat a NUL i el bucle while està trencat.
- El node principal de la llista enllaçada s'utilitza com a entrada per a una funció anomenada 'visualització', que mostra el valor de cada node de la llista des del principi fins al final.
- En el principal funció, creant un bucle.
- La funció 'functionHashMap' es crida amb el punter headNode com a entrada, que elimina el bucle de la llista.
- La llista modificada es mostra mitjançant la funció 'visualització'.
Enfocament 2: el cicle de Floyd
L'algoritme de detecció de cicles de Floyd, conegut sovint com l'algoritme de la tortuga i la llebre, proporciona la base per a aquest mètode per localitzar els cicles en una llista enllaçada. El punter 'lent' i el punter 'ràpid', que recorren la llista a diverses velocitats, són els dos punters utilitzats en aquesta tècnica. El punter ràpid avança dos passos mentre que el punter lent avança un pas cada iteració. Existeix un cicle a la llista enllaçada si els dos punts es troben mai cara a cara.
1. Amb el node principal de la llista enllaçada, inicialitzem dos punters anomenats ràpid i lent.
2. Ara fem un bucle per moure's per la llista enllaçada. El punter ràpid s'ha de moure dues ubicacions davant del punter lent a cada pas de la iteració.
3. No hi haurà cap bucle a la llista enllaçada si el punter ràpid arriba al final de la llista (fastPointer == NULL o fastPointer->next == NULL). Si no és així, els punters ràpids i lents es trobaran, el que significa que la llista enllaçada té un bucle.
Implementació del programa C++ per al mètode anterior (cicle de Floyd):
#inclou
utilitzant namespace std;
/* Node de llista d'enllaços */
struct Node {
int dades;
struct Node * Pròxim;
} ;
/* Funció per eliminar bucle. */
void deleteLoop ( struct Node * , struct Node * ) ;
/* Això funció localitza i elimina els bucles de llista. Cedeix 1
si hi havia un bucle en la llista; altra cosa , torna 0 . */
int detectAndDeleteLoop ( struct Node * llista )
{
struct Node * slowPTR = llista, * fastPTR = llista;
// Itera per comprovar si el bucle és allà.
mentre ( PTR lent && ràpidPTR && FastPTR- > Pròxim ) {
slowPTR = slowPTR- > Pròxim;
fastPTR = fastPTR- > Pròxim- > Pròxim;
/* Si slowPTR i fastPTR es troben en algun moment aleshores allà
és un bucle */
si ( slowPTR == fastPTR ) {
deleteLoop ( slowPTR, llista ) ;
/* Tornar 1 per indicar que s'ha descobert un bucle. */
tornar 1 ;
}
}
/* Tornar 0 per indicar que no s'ha descobert cap bucle. */
tornar 0 ;
}
/* Funció per eliminar el bucle de la llista enllaçada.
loopNode apunta a un dels nodes de bucle i headNode apunta
al node inicial de la llista enllaçada */
void deleteLoop ( struct Node * loopNode, struct Node * headNode )
{
struct Node * ptr1 = loopNode;
struct Node * ptr2 = loopNode;
// Compteu quants nodes hi ha en el bucle.
sense signar int k = 1 , i;
mentre ( ptr1- > Pròxim ! = ptr2 ) {
ptr1 = ptr1- > Pròxim;
k++;
}
// Arregla un punter a headNode
ptr1 = headNode;
// I l'altre punter a k nodes després de headNode
ptr2 = headNode;
per ( i = 0 ; i < k; i++ )
ptr2 = ptr2- > Pròxim;
/* Quan els dos punts es mouen simultàniament,
xocaran al bucle node inicial de. */
mentre que (ptr2 != ptr1) {
ptr1 = ptr1->següent;
ptr2 = ptr2->següent;
}
// Obteniu el node' s darrer punter.
mentre ( ptr2- > Pròxim ! = ptr1 )
ptr2 = ptr2- > Pròxim;
/* Per tancar el bucle, conjunt el posterior
node al bucle és el node final. */
ptr2->next = NULL;
}
/* Funció per mostrar la llista enllaçada */
void displayLinkedList(struct Node* node)
{
// mostra la llista enllaçada després de suprimir el bucle
mentre (node != NULL) {
cout << node->dades << ' ';
node = node->següent;
}
}
struct Node* newNode (clau int)
{
struct Node* temp = nou Node();
temp->data = clau;
temp->següent = NULL;
temperatura de retorn;
}
// Codi principal
int main()
{
struct Node* headNode = nouNode(48);
headNode->next = nouNode(18);
headNode->next->next = nouNode(13);
headNode->next->next->next = nouNode(2);
headNode->next->next->next->next = nouNode(8);
/* Crear un bucle */
headNode->next->next->next->next->next = headNode->next->next;
// mostra el bucle a la llista enllaçada
//displayLinkedList(headNode);
detectAndDeleteLoop(headNode);
cout << 'Llista enllaçada després de cap bucle \n';
displayLinkedList(headNode);
retorn 0;
}
Sortida:
Llista enllaçada després de cap bucle
48 18 13 2 8
Explicació:
-
- Les capçaleres rellevants, com ara 'bits/stdc++.h' i 'std::cout', s'inclouen primer.
- Aleshores es declara l'estructura 'Node', que significa un node a la llista enllaçada. S'inclou un punter següent que condueix al següent node de la llista juntament amb un camp de dades enter a cada node.
- A continuació, defineix 'deleteLoop' i 'detectAndDeleteLoop', dues funcions. S'elimina un bucle d'una llista enllaçada mitjançant el primer mètode, i es detecta un bucle a la llista mitjançant la segona funció, que després crida al primer procediment per eliminar el bucle.
- Es crea una nova llista enllaçada amb cinc nodes a la funció principal i s'estableix un bucle posant el punter següent de l'últim node al tercer node.
- A continuació, fa una crida al mètode 'detectAndDeleteLoop' mentre passa el node principal de la llista enllaçada com a argument. Per identificar bucles, aquesta funció utilitza l'enfocament 'Apuntadors lents i ràpids'. Utilitza dos punters que comencen a la part superior de la llista, slowPTR i fastPTR. Mentre que el punter ràpid mou dos nodes alhora, el punter lent només mou un node alhora. El punter ràpid finalment superarà el punter lent si la llista conté un bucle, i els dos punts xocaran al mateix node.
- La funció invoca la funció 'deleteLoop' si troba un bucle, proporcionant el node principal de la llista i la intersecció dels punters lents i ràpids com a entrades. Aquest procediment estableix dos punters, ptr1 i ptr2, al node principal de la llista i compta el nombre de nodes del bucle. Després d'això, avança un punter k nodes, on k és el nombre total de nodes del bucle. Aleshores, fins que es troben a l'inici del bucle, avança els dos punts d'un node alhora. Aleshores, el bucle es trenca posant el següent punter del node al final del bucle a NULL.
- Després d'eliminar el bucle, mostra la llista enllaçada com a pas final.
Enfocament 3: Recursió
La recursivitat és una tècnica per resoldre problemes dividint-los en subproblemes més petits i més fàcils. La recurssió es pot utilitzar per recórrer una llista enllaçada individualment en el cas que es trobi un bucle executant contínuament una funció per al següent node de la llista fins que s'arribi al final de la llista.
En una llista enllaçada individualment, el principi bàsic de l'ús de la recursivitat per trobar un bucle és començar al cap de la llista, marcar el node actual com a visitat a cada pas i, a continuació, passar al node següent invocant recursivament la funció per aquell node. El mètode iterarà per tota la llista enllaçada perquè s'anomena recursivament.
La llista conté un bucle si la funció troba un node que prèviament s'ha marcat com a visitat; en aquest cas, la funció pot tornar true. El mètode pot tornar false si arriba al final de la llista sense passar per un node visitat, cosa que indica que no hi ha cap bucle.
Tot i que aquesta tècnica per utilitzar la recursivitat per trobar un bucle en una única llista enllaçada és senzilla d'utilitzar i comprendre, pot ser que no sigui la més eficaç en termes de complexitat de temps i espai.
Implementació del programa C++ per al mètode anterior (recursió):
#inclou
utilitzant namespace std;
struct Node {
int dades;
Node * Pròxim;
bool visitat;
} ;
// Detecció de bucles de llista enllaçada funció
bool detectLoopLinkedList ( Node * headNode ) {
si ( headNode == NULL ) {
tornar fals ; // Si la llista enllaçada està buida, la bàsica Caixa
}
// Hi ha un bucle si el node actual té
// ja s'ha visitat.
si ( headNode- > visitat ) {
tornar veritat ;
}
// Afegiu una marca de visita al node actual.
headNode- > visitat = veritat ;
// Cridant el codi per el node posterior repetidament
tornar detectLoopLinkedList ( headNode- > Pròxim ) ;
}
int principal ( ) {
Node * headNode = nou Node ( ) ;
Node * secondNode = nou Node ( ) ;
Node * thirdNode = nou Node ( ) ;
headNode- > dades = 1 ;
headNode- > següent = segonNode;
headNode- > visitat = fals ;
segon node- > dades = 2 ;
segon node- > següent = tercerNode;
segon node- > visitat = fals ;
tercer node- > dades = 3 ;
tercer node- > següent = NULL; // Sense bucle
tercer node- > visitat = fals ;
si ( detectLoopLinkedList ( headNode ) ) {
cout << 'Bucle detectat a la llista enllaçada' << endl;
} altra cosa {
cout << 'No s'ha detectat cap bucle a la llista enllaçada' << endl;
}
// Creació d'un bucle
tercer node- > següent = segonNode;
si ( detectLoopLinkedList ( headNode ) ) {
cout << 'Bucle detectat a la llista enllaçada' << endl;
} altra cosa {
cout << 'No s'ha detectat cap bucle a la llista enllaçada' << endl;
}
tornar 0 ;
}
Sortida:
No s'ha detectat cap bucle en llista enllaçada
Bucle detectat en llista enllaçada
Explicació:
-
- La funció detectLoopLinkedList() en aquest programa accepta el cap de la llista enllaçada com a entrada.
- La funció utilitza la recursió per iterar a través de la llista enllaçada. Com a cas bàsic de la recursivitat, comença determinant si el node actual és NULL. Si és així, el mètode retorna false, indicant que no existeix cap bucle.
- A continuació, es comprova el valor de la propietat 'visitada' del node actual per veure si s'ha visitat anteriorment. Torna veritable si s'ha visitat, cosa que suggereix que s'ha trobat un bucle.
- La funció marca el node actual com a visitat si ja s'ha visitat canviant la seva propietat 'visitada' a true.
- A continuació, es comprova el valor de la variable visitada per veure si el node actual s'ha visitat anteriorment. Si s'ha utilitzat abans, ha d'existir un bucle i la funció retorna true.
- Finalment, la funció s'anomena amb el següent node de la llista passant headNode->següent com a argument. Recursivament , això es porta a terme fins que es troba un bucle o s'han visitat tots els nodes. Vol dir que la funció estableix la variable visitada com a vertadera si el node actual no s'ha visitat mai abans de cridar-se recursivament al node següent de la llista enllaçada.
- El codi crea tres nodes i els uneix per produir una llista enllaçada al funció principal . El mètode detectLoopLinkedList() llavors s'invoca al node principal de la llista. El programa produeix “ Bucle deduït a la llista enllaçada ' si detectLoopLinkedList() retorna veritable; en cas contrari, surt ' No s'ha detectat cap bucle a la llista enllaçada “.
- A continuació, el codi insereix un bucle a la llista enllaçada configurant el següent punter de l'últim node al segon node. Després, depenent del resultat de la funció, s'executa detectLoopLinkedList() de nou i produeix o bé ' Bucle deduït a la llista enllaçada ' o ' No s'ha detectat cap bucle a la llista enllaçada .”
Enfocament 4: Ús de Stack
Els bucles d'una llista enllaçada es poden trobar mitjançant una pila i el mètode 'depth-first search' (DFS). El concepte fonamental és iterar a través de la llista enllaçada, empenyent cada node a la pila si encara no s'ha visitat. Es reconeix un bucle si es torna a trobar un node que ja està a la pila.
Aquí teniu una breu descripció del procediment:
-
- Creeu una pila buida i una variable per registrar els nodes que s'han visitat.
- Premeu la llista enllaçada a la pila, començant per la part superior. Anoteu que el cap ha estat visitat.
- Premeu el següent node de la llista a la pila. Afegiu una marca de visita a aquest node.
- Mentre recorreu la llista, premeu cada nou node a la pila per indicar que s'ha visitat.
- Comproveu si un node que s'ha visitat anteriorment es troba a la part superior de la pila si es troba. Si és així, s'ha trobat un bucle i el bucle s'identifica pels nodes de la pila.
- Treu els nodes de la pila i segueix recorrent la llista si no es troba cap bucle.
Implementació del programa C++ per al mètode anterior (Stack)
#inclou
#inclou
utilitzant namespace std;
struct Node {
int dades;
Node * Pròxim;
} ;
// Funció per detectar bucle en una llista enllaçada
bool detectLoopLinkedList ( Node * headNode ) {
pila < Node *> pila;
Node * tempNode = capçalera;
mentre ( tempNode ! = NULL ) {
// si l'element superior de la pila coincideix
// el node actual i la pila no està buida
si ( ! apilar.buit ( ) && stack.top ( ) == tempNode ) {
tornar veritat ;
}
apilar.empènyer ( tempNode ) ;
tempNode = tempNode- > Pròxim;
}
tornar fals ;
}
int principal ( ) {
Node * headNode = nou Node ( ) ;
Node * secondNode = nou Node ( ) ;
Node * thirdNode = nou Node ( ) ;
headNode- > dades = 1 ;
headNode- > següent = segonNode;
segon node- > dades = 2 ;
segon node- > següent = tercerNode;
tercer node- > dades = 3 ;
tercer node- > següent = NULL; // Sense bucle
si ( detectLoopLinkedList ( headNode ) ) {
cout << 'Bucle detectat a la llista enllaçada' << endl;
} altra cosa {
cout << 'No s'ha detectat cap bucle a la llista enllaçada' << endl;
}
// Creació d'un bucle
tercer node- > següent = segonNode;
si ( detectLoopLinkedList ( headNode ) ) {
cout << 'Bucle detectat a la llista enllaçada' << endl;
} altra cosa {
cout << 'No s'ha detectat cap bucle a la llista enllaçada' << endl;
}
Sortida:
No s'ha detectat cap bucle en llista enllaçada
Bucle detectat en llista enllaçada
Explicació:
Aquest programa utilitza una pila per esbrinar si una llista enllaçada individualment té un bucle.
- 1. La biblioteca de flux d'entrada/sortida i la biblioteca de pila estan presents a la primera línia.
2. L'espai de nom estàndard s'inclou a la segona línia, la qual cosa ens permet accedir a les funcions de la biblioteca de flux d'entrada/sortida sense haver de prefixar-les amb 'std::'.
3. La línia següent defineix l'estructura Node, que consta de dos membres: un enter anomenat 'data' i un punter a un altre Node anomenat 'next'.
4. La capçalera de la llista enllaçada és una entrada per al mètode detectLoopLinkedList(), que es defineix a la línia següent. La funció produeix un valor booleà que indica si s'ha trobat o no un bucle.
5. Dins de la funció es creen una pila de punters de Node anomenada 'pila' i un punter a un Node anomenat 'tempNode' que s'inicialitza amb el valor del headNode.
6. Aleshores, sempre que tempNode no sigui un punter nul, introduïm un bucle while.
(a) L'element superior de la pila ha de coincidir amb el node actual per tal que puguem determinar que no està buit. Tornem true si aquest és el cas perquè s'ha trobat un bucle.
(b) Si la condició esmentada anteriorment és falsa, el punter del node actual s'envia a la pila i tempNode s'estableix al node següent de la llista enllaçada.
7. Tornem false després del bucle while perquè no s'ha observat cap bucle.
8. Construïm tres objectes Node i els inicialitzem a la funció main(). Com que no hi ha cap bucle al primer exemple, establim els punters 'següents' de cada node correctament.
Conclusió:
En conclusió, el millor mètode per detectar bucles en una llista enllaçada depèn del cas d'ús específic i de les limitacions del problema. Hash Table i l'algorisme de cerca de cicles de Floyd són mètodes eficients i s'utilitzen àmpliament a la pràctica. La pila i la recursivitat són mètodes menys eficients però són més intuïtius.