Rileva un loop in un elenco collegato in C++

Il nodo finale di un elenco collegato che ha un ciclo farà riferimento a un altro nodo nello stesso elenco anziché al NULL. Se esiste un nodo in un elenco collegato a cui è possibile accedere ripetutamente seguendo il puntatore successivo, si dice che l'elenco avere un ciclo

In genere, l'ultimo nodo dell'elenco collegato fa riferimento a un riferimento NULL per denotare la conclusione dell'elenco. Tuttavia, in un elenco collegato con un loop, il nodo finale dell'elenco fa riferimento a un nodo iniziale, a un nodo interno o a se 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 è illustrata in questo articolo.

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

Approccio basato su tabelle 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.

L'approccio ciclico di Floyd : L'algoritmo 'tartaruga e lepre', comunemente noto come 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ù veloce alla fine sorpasserà 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 se stesso 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à presente nello stack quando viene visitato di nuovo.

Spieghiamo ogni approccio in dettaglio per comprendere il concetto.

Approccio 1: approccio HashSet

L'utilizzo dell'hashing è il metodo più semplice. Qui, esaminiamo l'elenco uno per uno mantenendo una tabella hash con gli indirizzi dei nodi. Pertanto, esiste un ciclo se ci imbattiamo nell'indirizzo successivo del nodo corrente che è già contenuto nella tabella hash. Altrimenti, non c'è nessun ciclo nell'elenco collegato se ci imbattiamo in NULL (cioè, raggiungiamo la fine dell'elenco collegato).

Sarà abbastanza facile attuare questa strategia.

Durante l'attraversamento dell'elenco collegato, utilizzeremo una hashmap unordered e continueremo ad aggiungere nodi ad essa.

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

• • Inoltre, abbiamo mantenuto due puntatori ad ogni passaggio, headNode che punta al nodo corrente e lastNode che punta al nodo precedente del nodo corrente, durante l'iterazione.
  • Come il nostro headNode ora punta al nodo iniziale del ciclo e as lastNode stava indicando il nodo a cui puntava la testa (cioè, si riferisce al lastNode del ciclo), il nostro headNode sta attualmente puntando al nodo iniziale del ciclo.
  • Il loop verrà interrotto impostando l astNode->next == NULL .

In questo modo, il nodo del ciclo finale invece di fare riferimento al nodo iniziale del ciclo, inizia a puntare a NULL.

Il tempo medio e la complessità spaziale del metodo di hashing è O(n). Il lettore dovrebbe sempre essere consapevole che l'implementazione della Hashing DataStructure incorporata nel linguaggio di programmazione determinerà la complessità temporale totale in caso di collisione nell'hashing.

Implementazione del programma C++ per il metodo precedente (HashSet):

Produzione:

La spiegazione dettagliata del codice è fornita di seguito:

1. 1. Il file di intestazione bits/stdc++.h>, 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 'next' impostato su NULL, la funzione 'newNode' crea un nuovo nodo con quel valore.
   4. La funzione ' funzioneHashMap' è definito, che accetta come input un puntatore al nodo principale dell'elenco collegato.
   5. Dentro il ' funzioneHashMap ‘, viene creata una mappa non ordinata denominata ‘hash_map’, che viene utilizzata per implementare una struttura di dati della mappa hash.
   6. Un puntatore all'ultimo nodo dell'elenco viene inizializzato su NULL.
   7. Un ciclo while viene utilizzato per attraversare l'elenco collegato, che inizia dal nodo head e continua fino a quando il nodo head è NULL.
   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 viene trovato nella mappa, significa che è presente un loop nell'elenco collegato. Per rimuovere il ciclo, il puntatore successivo del file lastNode è impostato per NULLO e il ciclo while è interrotto.
   10. Il nodo principale dell'elenco collegato viene utilizzato come input per una funzione chiamata 'visualizzazione', che emette il valore di ciascun nodo nell'elenco dall'inizio alla fine.
   11. Nel principale funzione, creando un ciclo.
   12. La funzione 'functionHashMap' viene chiamata con il puntatore headNode come input, che rimuove il ciclo dall'elenco.
   13. L'elenco modificato viene visualizzato utilizzando la funzione 'visualizza'.

Approccio 2: Ciclo di Floyd

L'algoritmo di rilevamento del ciclo di Floyd, spesso noto come l'algoritmo della tartaruga e della 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 utilizzati in questa tecnica. Il puntatore veloce avanza di due passi mentre il puntatore lento avanza di un passo ogni iterazione. Esiste un ciclo nell'elenco collegato se i due punti si trovano uno di fronte all'altro.

1. Con il nodo head della lista collegata, inizializziamo due puntatori chiamati fast e slow.

2. Ora eseguiamo un ciclo per spostarci nell'elenco collegato. Il puntatore veloce dovrebbe essere spostato di due posizioni davanti al puntatore lento ad ogni passo dell'iterazione.

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

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

Produzione:

Spiegazione:

1. 1. Le intestazioni pertinenti, come 'bits/stdc++.h' e 'std::cout', vengono prima incluse.
   2. Viene quindi dichiarata la struttura 'Node', che rappresenta un nodo nell'elenco collegato. Un puntatore successivo che porta al nodo seguente nell'elenco è incluso insieme a un campo dati intero in ogni nodo.
   3. Quindi, definisce 'deleteLoop' e 'detectAndDeleteLoop', due funzioni. Un ciclo viene rimosso da un elenco collegato utilizzando il primo metodo e un ciclo viene rilevato nell'elenco utilizzando la seconda funzione, che quindi chiama la prima procedura per rimuovere il ciclo.
   4. Nella funzione principale viene creato un nuovo elenco collegato con cinque nodi e viene stabilito un ciclo impostando il puntatore successivo dell'ultimo nodo sul terzo nodo.
   5. Quindi effettua una chiamata al metodo 'detectAndDeleteLoop' mentre passa il nodo principale dell'elenco collegato come argomento. Per identificare i loop, questa funzione utilizza l'approccio 'Slow and Fast Pointers'. Impiega due puntatori che iniziano in cima all'elenco, slowPTR e fastPTR. Mentre il puntatore veloce sposta due nodi contemporaneamente, il puntatore lento sposta solo un nodo alla volta. Il puntatore veloce alla fine sorpasserà il puntatore lento se l'elenco contiene un ciclo e i due punti si scontreranno sullo stesso nodo.
   6. La funzione invoca la funzione “deleteLoop” se trova un loop, fornendo come input il nodo head della lista e l'intersezione dei puntatori slow e fast. Questa procedura stabilisce due puntatori, ptr1 e ptr2, al nodo principale della lista e conta il numero di nodi nel ciclo. Successivamente, avanza di un puntatore k nodi, dove k è il numero totale di nodi nel ciclo. Quindi, finché non si incontrano all'inizio del ciclo, fa avanzare entrambi i punti di un nodo alla volta. Il ciclo viene quindi interrotto impostando il puntatore successivo del nodo alla fine del ciclo su NULL.
   7. Dopo aver rimosso il loop, visualizza l'elenco collegato come passaggio finale.

Approccio 3: ricorsione

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

In un elenco concatenato singolarmente, il principio di base alla base dell'utilizzo della ricorsione per trovare un ciclo è iniziare dall'inizio dell'elenco, contrassegnare il nodo corrente come visitato ad ogni passaggio e quindi passare al nodo successivo invocando in modo ricorsivo la funzione per quel nodo. Il metodo ripeterà l'intero elenco collegato perché viene chiamato in modo ricorsivo.

L'elenco contiene un ciclo se un nodo precedentemente contrassegnato come visitato viene incontrato dalla funzione; in questo caso, la funzione può restituire true. Il metodo può restituire false se raggiunge la fine dell'elenco senza attraversare un nodo visitato, il che indica che non è presente alcun ciclo.

Sebbene questa tecnica per utilizzare la ricorsione per trovare un ciclo in un singolo elenco collegato sia semplice da usare e comprendere, potrebbe non essere la più efficace in termini di complessità temporale e spaziale.

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

Produzione:

Spiegazione:

1. 1. La funzione detectLoopLinkedList() in questo programma accetta come input l'intestazione dell'elenco collegato.
   2. La ricorsione viene utilizzata dalla funzione per scorrere l'elenco collegato. Come caso base per la ricorsione, inizia determinando se il nodo corrente è NULL. In tal caso, il metodo restituisce false, indicando che non esiste alcun ciclo.
   3. Il valore della proprietà 'visitato' del nodo corrente viene quindi controllato per vedere se è stato precedentemente visitato. Restituisce true se è stato visitato, suggerendo che è stato trovato un loop.
   4. La funzione contrassegna il nodo corrente come visitato se è già stato visitato modificando la sua proprietà 'visited' in true.
   5. Il valore della variabile visitata viene quindi controllato per vedere se il nodo corrente è stato visitato in precedenza. Se è stato utilizzato in precedenza, deve esistere un ciclo e la funzione restituisce true.
   6. Infine, la funzione chiama se stessa con il nodo successivo nell'elenco passando headNode->successivo come argomento. Ricorsivamente , questo viene eseguito fino a quando non viene trovato un loop o tutti i nodi sono stati visitati. Significa che la funzione imposta la variabile visitata su true se il nodo corrente non è mai stato visitato prima di chiamare se stesso in modo ricorsivo per il nodo successivo nell'elenco collegato.
   7. Il codice crea tre nodi e li unisce per produrre un elenco collegato nel file funzione principale . Il metodo detectLoopLinkedList() viene quindi richiamato sul nodo head della lista. Il programma produce “ Ciclo detratto nell'elenco collegato ' Se detectLoopLinkedList() restituisce vero; altrimenti, emette ' Nessun loop rilevato nell'elenco collegato “.
   8. Il codice quindi inserisce un ciclo nell'elenco collegato impostando il puntatore successivo dell'ultimo nodo sul secondo nodo. Quindi, a seconda del risultato della funzione, viene eseguito detectLoopLinkedList() di nuovo e produce ' Ciclo detratto nell'elenco collegato ' O ' Nessun loop rilevato nell'elenco collegato .”

Approccio 4: utilizzo dello stack

I loop in un elenco collegato possono essere trovati utilizzando uno stack e il metodo 'depth-first search' (DFS). Il concetto fondamentale è scorrere l'elenco collegato, spingendo ogni nodo nello stack se non è già stato visitato. Un loop viene riconosciuto se si incontra nuovamente un nodo che si trova già nello 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 nello stack, iniziando dall'alto. Prendi nota che la testa è stata visitata.
   3. Spingi il nodo successivo nell'elenco nello stack. Aggiungi un segno di visita a questo nodo.
   4. Mentre attraversi l'elenco, inserisci ogni nuovo nodo nello stack per indicare che è stato visitato.
   5. Controlla se un nodo che è stato visitato in precedenza è in cima allo stack se viene incontrato. In tal caso, è stato trovato un loop e il loop è identificato dai nodi nello stack.
   6. Estrai i nodi dallo stack e continua a scorrere l'elenco se non viene trovato alcun loop.

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

Produzione:

Spiegazione:

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

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

  2. Lo spazio dei nomi standard è incluso nella seconda riga, consentendoci di accedere alle funzioni della libreria del flusso di input/output senza dover prefissare 'std::'.

  3. La riga seguente definisce il nodo struct, che consiste di due membri: un numero intero chiamato 'data' e un puntatore a un altro nodo chiamato 'next'.

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

  5. All'interno della funzione vengono creati uno stack di puntatori Node chiamato 'stack' e un puntatore a un Node denominato 'tempNode' inizializzato con il valore di headNode.

  6. Quindi, finché tempNode non è un puntatore nullo, entriamo in un ciclo while.

  (a) L'elemento superiore dello stack deve corrispondere al nodo corrente per consentirci di determinare che non è vuoto. Restituiamo vero se questo è il caso perché è stato trovato un ciclo.

  (b) Se la suddetta condizione è falsa, il puntatore del nodo corrente viene inserito nello stack e tempNode viene impostato sul nodo seguente nell'elenco collegato.

  7. Restituiamo false dopo il ciclo while perché non è stato osservato alcun ciclo.

  8. Costruiamo tre oggetti Node e li inizializziamo nella funzione main(). Poiché nel primo esempio non è presente alcun loop, impostiamo correttamente i puntatori 'next' 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. Hash Table e l'algoritmo di ricerca del ciclo di Floyd sono metodi efficienti e sono ampiamente utilizzati nella pratica. Stack e ricorsione sono metodi meno efficienti ma sono più intuitivi.