Rileva un ciclo in un elenco collegato in C ++

Il nodo finale di un elenco collegato che ha un ciclo si riferirà a un altro nodo nello stesso elenco piuttosto che NULL.Se c'è un nodo in un elenco collegato a cui è possibile accedere ripetutamente seguendo il puntatore successivo, si dice che l'elenco abbia un ciclo.

In genere, l'ultimo nodo dell'elenco collegato si riferisce a un riferimento nullo per indicare la conclusione dell'elenco. Tuttavia, in un elenco collegato con un ciclo, il nodo finale dell'elenco si riferisce a un nodo iniziale, un nodo interno o stesso. Pertanto, in tali circostanze, dobbiamo identificare e terminare il ciclo impostando il riferimento del nodo successivo a NULL. La parte di rilevamento del ciclo in un elenco collegato è spiegata in questo articolo.

In C ++, ci sono numerosi modi per trovare loop in un elenco collegato:

Approccio basato sulla tabella hash: Questo approccio memorizza gli indirizzi dei nodi visitati in una tabella hash. Esiste un ciclo nell'elenco collegato se un nodo è già presente nella tabella hash quando viene visitato di nuovo.

Approccio al ciclo di Floyd: L'algoritmo "Tartotae e lepre", comunemente noto come l'algoritmo di ricerca del ciclo di Floyd: questa tecnica utilizza due puntatori, uno che si muove più lentamente dell'altro e l'altro che si muove più rapidamente. Il puntatore più rapido alla fine supererà il puntatore più lento se c'è un loop nell'elenco collegato, rivelando l'esistenza del loop.

Metodo ricorsivo: Questo metodo passa attraverso l'elenco collegato chiamando più e più volte. L'elenco collegato contiene un ciclo se il nodo corrente è stato precedentemente visitato.

Approccio basato su stack: Questo approccio memorizza gli indirizzi dei nodi visitati in uno stack. Un ciclo nell'elenco collegato è presente se un nodo è già lì nello stack quando viene visitato di nuovo.

Spieghiamo ogni approccio in dettaglio per comprendere il concetto.

Approccio 1: approccio hashset

L'utilizzo di hashing è il metodo più semplice. Qui, passiamo attraverso l'elenco uno per uno mantenendo una tabella hash con gli indirizzi del nodo. Pertanto, esiste un ciclo se mai attraversiamo il prossimo indirizzo dell'attuale nodo che è già contenuto nella tabella hash. Altrimenti, non esiste un loop nell'elenco collegato se ci incontriamo in null (i.e., raggiungere la fine dell'elenco collegato).

Sarà abbastanza facile implementare questa strategia.

Mentre attraverseremo l'elenco collegato, utilizzeremo un non ordinato_hashmap e continueremo ad aggiungere nodi ad esso.

Ora, una volta imbattuto in un nodo che è già mostrato nella mappa, sapremo che siamo arrivati ​​all'inizio del loop.

• • Inoltre, abbiamo tenuto due puntatori ad ogni passaggio, headnode indicando il nodo corrente e LastNode indicando il nodo precedente del nodo corrente, mentre si itetera.
  • Come il nostro headnode ora indica il nodo iniziale del loop e come LastNode indicava il nodo a cui indicava la testa (i.e., Si riferisce al LastNode del ciclo), nostro headnode è attualmente puntato al nodo iniziale del loop.
  • Il ciclo verrà interrotto impostando lAstnode-> Next == Null.

In questo modo, il nodo Loop finale invece di fare riferimento al nodo iniziale del loop, inizia a indicare Null.

La complessità medio del tempo e dello spazio del metodo di hashing è O (N). Il lettore dovrebbe sempre essere consapevole del fatto che l'implementazione della dati di hashing integrata nel linguaggio di programmazione determinerà la complessità del tempo totale in caso di collisione in hashing.

Implementazione del programma C ++ per il metodo sopra (hashset):

#includere
Utilizzo dello spazio dei nomi std;
nodo struct
valore int;
nodo struct* Next;
;
Nodo* newnode (valore int)

Nodo* tempNode = nuovo nodo;
tempNode-> value = value;
tempnode-> next = null;
restituire tempnode;

// Identifica ed elimina eventuali loop potenziali
// in un elenco collegato con questa funzione.
void functionhashmap (nodo* headnode)

// ha creato un non ordinato_map per implementare la mappa hash
UNORDERD_MAP hash_map;
// puntatore a LastNode
Nodo* lastnode = null;
mentre (headnode != Null)
// Se manca un nodo dalla mappa, aggiungilo.
if (hash_map.Trova (headnode) == hash_map.FINE())
hash_map [headnode] ++;
LastNode = headNode;
headNode = headNode-> Next;

// Se è presente un ciclo, imposta il prossimo puntatore del nodo finale su NULL.
altro
lastnode-> next = null;
rottura;



// Visualizza l'elenco collegato
void display (nodo* headnode)

mentre (headnode != Null)
cout headNode = headNode-> Next;

cout << endl;

/* Funzione principale*/
int main ()

Nodo* 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 un ciclo in Linkedlist */
HeadNode-> Next-> Next-> Next-> Next-> Next = HeadNode-> Next-> Next;
functionhashmap (headnode);
printf ("Elenco collegato senza loop \ n");
display (headnode);
restituzione 0;

Produzione:

Elenco collegato senza loop
48 18 13 2 8

La spiegazione passo-passo del codice è fornita di seguito:

1. 1. I bit/stdc++.H> File di intestazione, che contiene tutte le librerie C ++ comuni, è incluso nel codice.
   2. Viene costruita una struttura chiamata "nodo" e ha due membri: un riferimento al nodo successivo nell'elenco e un numero intero chiamato "valore."
   3. Con un valore intero come input e il puntatore "successivo" impostato su NULL, la funzione "newnode" crea un nuovo nodo con quel valore.
   4. La funzione 'functionhashmap ' è definito, che porta un puntatore al nodo principale dell'elenco collegato come input.
   5. Dentro il 'FunctionHashmap'Funzione, un non ordinato_map chiamato' hash_map ', che viene utilizzato per implementare una struttura dati della mappa hash.
   6. Un puntatore all'ultimo nodo dell'elenco viene inizializzato su NULL.
   7. Un ciclo di tempo viene utilizzato per attraversare l'elenco collegato, che inizia dal nodo della testa e continua fino a quando il nodo della testa è nullo.
   8. Il puntatore LastNode viene aggiornato al nodo corrente all'interno del ciclo while se il nodo corrente (headnode) non è già presente nella mappa hash.
   9. Se il nodo corrente si trova nella mappa, significa che un ciclo è presente nell'elenco collegato. Per rimuovere il ciclo, il prossimo puntatore del LastNode è impostato per NULLO E il ciclo while è rotto.
   10. Il nodo della testa dell'elenco collegato viene utilizzato come input per una funzione chiamata "Display", che emette il valore di ciascun nodo nell'elenco dall'inizio alla fine.
   11. Nel principale funzione, creazione di un ciclo.
   12. La funzione "functionhashmap" viene chiamata con il puntatore del dheadnode come input, che rimuove il ciclo dall'elenco.
   13. L'elenco modificato viene visualizzato utilizzando la funzione "Visualizza".

Approccio 2: il ciclo di Floyd

L'algoritmo di rilevamento del ciclo di Floyd, spesso noto come algoritmo di tartaruga e lepre, fornisce le basi per questo metodo di localizzazione dei cicli in un elenco collegato. Il puntatore "lento" e il puntatore "veloce", che attraversano l'elenco a varie velocità, sono i due puntatori usati in questa tecnica. Il puntatore rapido fa avanzare due passaggi mentre il puntatore lento fa avanzare un passo ogni iterazione. Un ciclo nell'elenco collegato esiste se i due punti si trovano mai faccia a faccia.

1. Con il nodo principale dell'elenco collegato, inizializzamo due puntatori chiamati Fast and Slow.

2. Ora eseguiamo un ciclo per spostarci attraverso l'elenco collegato. Il puntatore veloce deve essere spostato due posizioni davanti al puntatore lento al passo di ogni iterazione.

3. Non ci sarà un ciclo nell'elenco collegato se il puntatore veloce raggiunge la fine dell'elenco (FastPointer == Null o FastPointer-> Next == Null). In caso contrario, i puntatori veloci e lenti alla fine si incontreranno, il che significa che l'elenco collegato ha un ciclo.

Implementazione del programma C ++ per il metodo sopra (Floyd's Cycle):

#includere
Utilizzo dello spazio dei nomi std;
/ * Nodo dell'elenco dei collegamenti */
nodo struct
Int Data;
nodo struct* Next;
;
/* Funzione per rimuovere il ciclo. */
void deleteLoop (nodo struct*, nodo struct*);
/* Questa funzione individua ed elimina i loop di elenco. Produce 1
Se c'era un ciclo nell'elenco; altro, restituisce 0. */
Int DetectandDeleTeloop (elenco di nodo struct*)

nodo struct *slowptr = elenco, *FastPtr = elenco;
// iterazione per verificare se il ciclo è lì.
while (slowptr && FastPtr && FastPtr-> Next)
slowptr = slowptr-> next;
FastPtr = FastPtr-> Next-> Next;
/* Se SlowPtr e FastPtr si incontrano ad un certo punto, allora lì
è un ciclo */
if (slowptr == FastPtr)
deleteLoop (slowptr, elenco);
/* Restituisce 1 per indicare che è stato scoperto un ciclo. */
Ritorno 1;


/* Restituisce 0 per indicare che non è stato scoperto alcun ciclo.*/
restituzione 0;

/* Funzione per eliminare loop dall'elenco collegato.
Loopnode punta a uno dei nodi del loop e il dono è puntato
al nodo iniziale dell'elenco collegato */
void deleteloop (nodo struct* loopnode, nodo struct* headnode)

nodo struct* ptr1 = loopnode;
nodo struct* ptr2 = loopnode;
// Conta quanti nodi ci sono nel ciclo.
Unsigned int k = 1, i;
while (PTR1-> Next != ptr2)
PTR1 = ptr1-> Next;
K ++;

// fissa un puntatore a headnode
ptr1 = headnode;
// e l'altro puntatore ai nodi K dopo il dono
ptr2 = headnode;
per (i = 0; i < k; i++)
ptr2 = ptr2-> next;
/* Quando entrambi i punti vengono spostati contemporaneamente,
Si scontreranno nel nodo iniziale del loop. */
mentre (PTR2 != ptr1)
PTR1 = ptr1-> Next;
ptr2 = ptr2-> next;

// ottieni l'ultimo puntatore del nodo.
while (PTR2-> Next != PTR1)
ptr2 = ptr2-> next;
/* Per chiudere il ciclo, impostare il successivo
nodo al nodo terminale del loop. */
ptr2-> next = null;

/ * Funzione per visualizzare l'elenco collegato */
void DisplayLinkedList (nodo struct* nodo)

// Visualizza l'elenco collegato dopo eliminare il loop
mentre (nodo != Null)
cout node = nodo-> next;


Struct Node* newnode (tasto int)

Struct node* temp = new node ();
temp-> data = chiave;
temp-> next = null;
restituire temp;

// Codice principale
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 un loop */
HeadNode-> Next-> Next-> Next-> Next-> Next = HeadNode-> Next-> Next;
// Visualizza il ciclo nell'elenco collegato
// DisplayLinkEdList (HeadNode);
DetectandDeleTeloop (headnode);
cout << "Linked List after no loop \n";
DisplayLinkEdList (headnode);
restituzione 0;

Produzione:

Elenco collegato dopo nessun ciclo
48 18 13 2 8

Spiegazione:

1. 1. Le intestazioni pertinenti, come "Bits/STDC++.H "e" std :: cout ", sono inclusi per la prima volta.
   2. Viene quindi dichiarata la struttura "nodo", che sta per un nodo nell'elenco collegato. Un puntatore successivo che conduce al seguente nodo nell'elenco è incluso insieme a un campo di dati interi in ciascun nodo.
   3. Quindi, definisce "deleteLoop" e "DetectandDeleTeloop", due funzioni. Un ciclo viene rimosso da un elenco collegato utilizzando il primo metodo e un loop viene rilevato nell'elenco utilizzando la seconda funzione, che quindi chiama la prima procedura per rimuovere il loop.
   4. Una nuova lista collegata con cinque nodi viene creata nella funzione principale e viene stabilito un ciclo impostando il puntatore successivo dell'ultimo nodo sul terzo nodo.
   5. Quindi fa una chiamata al metodo "DetectandDeleTeloop" mentre passa il nodo della testa dell'elenco collegato come argomento. Per identificare i loop, questa funzione utilizza l'approccio "puntatori lenti e veloci". Impiega due puntatori che iniziano in cima alla lista, SlowPtr e FastPtr. Mentre il puntatore veloce sposta due nodi contemporaneamente, il puntatore lento muove solo un nodo alla volta. Il puntatore veloce alla fine supererà il puntatore lento se l'elenco contiene un ciclo e i due punti si scontreranno nello stesso nodo.
   6. La funzione invoca la funzione "deleteloop" se trova un ciclo, fornendo il nodo della testa dell'elenco e l'intersezione dei puntatori lenti e veloci come input. Questa procedura stabilisce due puntatori, PTR1 e PTR2, al nodo della testa dell'elenco e conta il numero di nodi nel loop. Successivamente, fa avanzare un puntatore K nodi, dove k è il numero totale di nodi nel ciclo. Quindi, fino a quando non si incontrano all'inizio del ciclo, fa avanzare entrambi i punti un nodo alla volta. Il ciclo viene quindi interrotto impostando il puntatore successivo del nodo alla fine del loop per null.
   7. Dopo aver rimosso il ciclo, visualizza l'elenco collegato come passaggio finale.

Approccio 3: ricorsione

La ricorsione è una tecnica per risolvere i problemi partizionandoli in sottoproblemi più piccoli e più facili. La ricorsione può essere utilizzata per attraversare un elenco singolarmente collegato nel caso in cui un ciclo venga trovato eseguendo continuamente una funzione per il nodo successivo nell'elenco fino al raggiungimento della fine dell'elenco.

In un elenco singolarmente collegato, il principio di base dietro l'uso della ricorsione per trovare un ciclo è iniziare a testa dell'elenco, contrassegnare il nodo corrente come visitato in ogni fase, quindi passare al nodo successivo invocando ricorsivamente la funzione per quel nodo. Il metodo iterirà nell'elenco collegato completo perché si chiama ricorsivamente.

L'elenco contiene un ciclo se un nodo che è stato precedentemente contrassegnato come visitato è riscontrato dalla funzione; In questo caso, la funzione può restituire vero. Il metodo può restituire falso se raggiunge la fine dell'elenco senza attraversare un nodo visitato, il che indica che non esiste un ciclo.

Sebbene questa tecnica per l'utilizzo della ricorsione per trovare un ciclo in un unico elenco collegato sia semplice da usare e comprendere, potrebbe non essere la più efficace in termini di complessità del tempo e dello spazio.

Implementazione del programma C ++ per il metodo sopra (ricorsione):

#includere
Utilizzo dello spazio dei nomi std;
nodo struct
Int Data;
Nodo* Next;
Bool ha visitato;
;
// funzione di rilevamento del loop elenco collegato
Bool DetectLoopLinkedList (nodo* headnode)
if (headnode == null)
restituire false; // Se l'elenco collegato è vuoto, il caso di base

// c'è un ciclo se il nodo corrente ha
// già è stato visitato.
if (headnode-> visitato)
restituire vero;

// Aggiungi un segno di visita al nodo corrente.
headnode-> visitato = true;
// Chiama ripetutamente il codice per il nodo successivo
restituire DETTACKLINKEDLIST (headnode-> next);

int main ()
Nodo* headNode = new node ();
Nodo* secondNode = new node ();
Nodo* terzoNode = new node ();
headnode-> data = 1;
HeadNode-> Next = SecondNode;
headnode-> visitato = false;
SecondNode-> data = 2;
SecondNode-> Next = ThirdNode;
SecondNode-> visitato = false;
ThirdNode-> data = 3;
ThirdNode-> Next = null; // Nessun loop
ThirdNode-> visitato = false;
if (DetectLoopLinkedList (headnode))
cout << "Loop detected in linked list" << endl;
altro
cout << "No loop detected in linked list" << endl;

// Creazione di un ciclo
ThirdNode-> Next = SecondNode;
if (DetectLoopLinkedList (headnode))
cout << "Loop detected in linked list" << endl;
altro
cout << "No loop detected in linked list" << endl;

restituzione 0;

Produzione:

Nessun ciclo rilevato nell'elenco collegato
Loop rilevato nell'elenco collegato

Spiegazione:

1. 1. La funzione DetectLoopLinkedList () In questo programma accetta il capo dell'elenco collegato come input.
   2. La ricorsione viene utilizzata dalla funzione per iterare attraverso l'elenco collegato. Come caso base per la ricorsione, inizia determinando se il nodo corrente è nullo. In tal caso, il metodo restituisce falso, indicando che non esiste alcun ciclo.
   3. Il valore della proprietà "visitato" del nodo corrente viene quindi verificato per vedere se è stata precedentemente visitata. Restituisce vero se è stato visitato, suggerendo che è stato trovato un ciclo.
   4. La funzione segna l'attuale nodo visitato se è già stato visitato cambiando la sua proprietà "visitata" in true.
   5. Il valore della variabile visitato viene quindi verificato per vedere se il nodo corrente è stato visitato in precedenza. Se è stato utilizzato in precedenza, deve esistere un ciclo e la funzione restituisce vera.
   6. Infine, la funzione si chiama con il nodo successivo nell'elenco passando headnode-> Next come argomento. Ricorsivamente, Questo viene eseguito fino a quando non viene trovato un ciclo o sono stati visitati tutti i nodi. Mezzi, la funzione imposta la variabile visitata su true se il nodo corrente non è mai stato visitato prima di chiamarsi ricorsivamente per il seguente nodo nell'elenco collegato.
   7. Il codice crea tre nodi e li unisce per produrre un elenco collegato nel funzione principale. Il metodo DetectLoopLinkedList () viene quindi invocato sul nodo della testa dell'elenco. Il programma produce "Loop detratto nell'elenco collegato" Se DetectLoopLinkedList () restituisce vero; altrimenti, produce "Nessun ciclo rilevato nell'elenco collegato".
   8. Il codice inserisce quindi un loop nell'elenco collegato impostando il puntatore successivo dell'ultimo nodo sul secondo nodo. Quindi, a seconda del risultato della funzione, funziona DetectLoopLinkedList () di nuovo e produce entrambi "Loop detratto nell'elenco collegato" O "Nessun ciclo rilevato nell'elenco collegato."

Approccio 4: usando lo stack

I loop in un elenco collegato sono disponibili utilizzando uno stack e il metodo "Profondità-prima di ricerca" (DFS). Il concetto fondamentale è quello di iterare attraverso l'elenco collegato, spingendo ogni nodo sullo stack se non è già stato visitato. Un ciclo viene riconosciuto se si incontra nuovamente un nodo che è già sullo stack.

Ecco una breve descrizione della procedura:

1. 1. Crea uno stack vuoto e una variabile per registrare i nodi che sono stati visitati.
   2. Spingi l'elenco collegato sullo stack, a partire dalla parte superiore. Prendi nota che la testa è stata visitata.
   3. Spingi il nodo successivo nell'elenco sullo stack. Aggiungi un segno di visita a questo nodo.
   4. Mentre attraversi l'elenco, spingere ogni nuovo nodo sullo stack per indicare che è stato visitato.
   5. Controlla se si incontra un nodo che è stato precedentemente visitato è nella parte superiore dello stack. In tal caso, è stato trovato un ciclo e il ciclo è identificato dai nodi nello stack.
   6. Fai scoppiare i nodi dallo stack e continua a attraversare l'elenco se non viene trovato nessun ciclo.

Implementazione del programma C ++ per il metodo sopra (Stack)

#includere
#includere
Utilizzo dello spazio dei nomi std;
nodo struct
Int Data;
Nodo* Next;
;
// funzione per rilevare loop in un elenco collegato
Bool DetectLoopLinkedList (nodo* headnode)
pila pila;
Nodo* tempNode = headnode;
mentre (tempnode != Null)
// Se l'elemento superiore dello stack corrisponde
// Il nodo corrente e lo stack non è vuoto
Se (!pila.vuoto () && stack.top () == tempNode)
restituire vero;

pila.push (tempnode);
tempNode = tempNode-> Next;

restituire false;

int main ()
Nodo* headNode = new node ();
Nodo* secondNode = new node ();
Nodo* terzoNode = new node ();
headnode-> data = 1;
HeadNode-> Next = SecondNode;
SecondNode-> data = 2;
SecondNode-> Next = ThirdNode;
ThirdNode-> data = 3;
ThirdNode-> Next = null; // Nessun loop
if (DetectLoopLinkedList (headnode))
cout << "Loop detected in linked list" << endl;
altro
cout << "No loop detected in linked list" << endl;

// Creazione di un ciclo
ThirdNode-> Next = SecondNode;
if (DetectLoopLinkedList (headnode))
cout << "Loop detected in linked list" << endl;
altro
cout << "No loop detected in linked list" << endl;

Produzione:

Nessun ciclo rilevato nell'elenco collegato
Loop rilevato nell'elenco collegato

Spiegazione:

Questo programma utilizza uno stack per scoprire se un elenco singolarmente collegato ha un ciclo.

• 1. La libreria di flusso di input/output e la libreria stack sono entrambi presenti nella prima riga.

  2. Lo spazio dei nomi standard è incluso nella seconda riga, permettendoci di accedere alle funzioni della libreria di flusso di input/output senza doverle prefigurare con "std ::."

  3. La riga seguente definisce il nodo struct, che consiste in due membri: un numero intero chiamato "dati" e un puntatore a un altro nodo chiamato "Avanti."

  4. La testa dell'elenco collegato è un input per il metodo DetectLoopLinkedList (), che è definito nella riga successiva. La funzione produce un valore booleano che indica se è stato trovato o meno un ciclo.

  5. Uno stack di puntatori del nodo chiamato "stack" e un puntatore a un nodo chiamato "tempnode" che viene inizializzato con il valore del headnode sono entrambi creati all'interno della funzione.

  6. Quindi, fintanto che il tempnode non è un puntatore nullo, entriamo un ciclo di tempo.

  (a) L'elemento superiore dello stack deve corrispondere al nodo corrente affinché noi non sia vuoto. Ritorniamo vero se questo è il caso perché è stato trovato un ciclo.

  (b) Se la condizione di cui sopra è falsa, il puntatore del nodo corrente viene spinto sullo stack e tempnode è impostato sul nodo seguente nell'elenco collegato.

  7. Ritorniamo falsi dopo il ciclo while perché non è stato osservato alcun ciclo.

  8. Costruiamo tre oggetti nodi e li iniziali nella funzione principale (). Dal momento che non esiste un loop nel primo esempio, impostiamo correttamente i puntatori "successivi" di ciascun nodo.

Conclusione:

In conclusione, il metodo migliore per rilevare i loop in un elenco collegato dipende dal caso d'uso specifico e dai vincoli del problema. La tabella hash e l'algoritmo di ricerca del ciclo di Floyd sono metodi efficienti e sono ampiamente utilizzati nella pratica. Lo stack e la ricorsione sono metodi meno efficienti ma sono più intuitivi.