Elimina i nodi duplicati da un elenco collegato non richiesto

In questo articolo, vedremo i diversi approcci per eliminare i nodi duplicati dall'elenco collegato usando la programmazione C ++. Cominciamo con una spiegazione di cosa significano i "nodi duplicati" in un elenco collegato.

Ci viene fornito un elenco collegato non richiesto in questa sfida e richiesto di eliminare eventuali membri duplicati dall'elenco. Usiamo alcuni esempi per tentare di cogliere il problema.

L'elenco collegato non disponibile input è il seguente:

Gli elementi 8, 10 e 9 appaiono più di una volta nell'elenco collegato, come mostrato nell'elenco precedente. Ciò indica che ci sono duplicati di 8, 10 e 9 nella lista collegata che dobbiamo eliminare. L'elenco collegato all'output è seguente una volta rimosse le voci duplicate:

Un modo rapido e semplice per scoprirlo è confrontare tutte le possibili coppie di nodi nell'elenco per vedere se hanno le stesse informazioni. Quando le loro informazioni coincidono, ci sbarazziamo del secondo nodo eliminandolo. Ma questo approccio richiede più tempo.

È possibile utilizzare una migliore efficienza hashing. L'obiettivo è lavorare attraverso l'elenco fornito e aggiungere ogni nodo a un set mentre si procede. Se il nodo attualmente visualizzato viene visualizzato nel set precedente, potrebbe essere ignorato in modo sicuro. Al termine del processo, l'elenco non conterrà più nodi duplicati.

Comprendiamo ogni approccio in dettaglio.

Approccio 1: usando due loop

Passi di algoritmo

1. Crea una funzione Elenco collegata, "CreateLinkedList“, Che può creare un elenco collegato.
2. Crea una funzione chiamata "deleteduplicatesnodes"Ciò può eliminare il nodo duplicato dall'elenco collegato.
3. Crea due puntatori locali, PTR1 e PTR2, all'interno del “deleteduplicatesnodes" funzione.
4. Assegnare il ptr1 = headnode E ptr2 = null Valori, dove PTR1 viene utilizzato per tracciare il nodo i cui duplicati devono essere verificati e PTR2 viene utilizzato per attraversare ciascun nodo dell'elenco collegato per verificare se i dati del nodo sono gli stessi dei dati del nodo PTR1.
5. Il puntatore del ciclo nidificato PTR2 continua a attraversare l'intero nodo dell'elenco collegato fino a quando non trova null.
6. Se i dati del nodo PTR1 sono simili ai dati del nodo PTR2 ad anello nidificato, elimina quel nodo dall'elenco collegato.
7. In caso contrario, incrementa il file PTR1-> Next e controlla i dati del nodo successivo per i duplicati.
8. I passaggi da 4 a 7 vengono ripetuti fino a quando PTR1 non è uguale a null, il che indica che ha raggiunto la fine dell'elenco collegato.
9. Infine, stampiamo l'elenco collegato.
10. Fine dell'algoritmo.

Implementazione del codice C ++ (utilizzando due loop)

Produzione:

Spiegazione:

Righe da 21 a 52: Creiamo una funzione con il nome "CreateLinkedList". Passiamo due parametri (un puntatore del dono al puntatore e un valore) in quella funzione. Come mostrato nel programma precedente, ogni volta che questa funzione viene chiamata, crea prima un nuovo nodo con un valore (che abbiamo passato) e un indirizzo nodo con un valore null.

/* Crea un nuovo nodo*/
Nodo* newNode = new node ();
Nodo * lastnode = * headnode;
newnode-> data = value; / * Aggiunta dei dati */
/* Indirizzo di questo nuovo nodo trattenuto nullo*/
newnode-> next = null;

Quindi, controlla se il riferimento a headnode è nullo. Se lo è, il nodo appena creato diventa la testa.

/* Controllare che il riferimento a headnode è nullo o no.
Se sì, allora il newnode diventerà il headnode*/
if (*headnode == null)
*headnode = newnode;
ritorno;

Se il riferimento a headnode non è nullo, si aggiunge all'ultimo tempo dell'elenco collegato. L'indirizzo di questo newnode appena creato è assegnato al LastNode in modo che possa iniziare a puntare il newnode appena creato.

/* In caso contrario, allora questo loop lo farà
eseguire e trovare l'ultimo nodo del collegamento
elenco, in modo che il newnode appena creato aggiunga all'ultimo*/
while (LastNode-> Next != Null)
LastNode = LastNode-> Next;

Ora, il newnode appena creato diventa il LastNode. Questo processo continua fino a quel momento in cui chiamiamo questa funzione.

I passaggi precedenti creano l'elenco collegato secondo i nostri requisiti. Ora eliminiamo i nodi duplicati dall'elenco collegato.

Righe da 57 a 75: Creiamo una funzione denominata "deleteduplicatesnodes" che accetta un parametro che è il puntatore del headnode dell'elenco collegato. Creiamo due variabili a livello locale, PTR1 e PTR2, per tracciare l'elenco collegato quando lo facciamo per scoprire i duplicati nell'elenco collegato. Inizializzamo il PTR1 con il NNODE poiché questo sarà il ciclo superiore e il PTR2 con il valore nullo.

ptr1 = headnode;

PTR1: Questa variabile è al ciclo esterno e tiene traccia degli elementi i cui duplicati controlleremo.

PTR2: Questa variabile è all'interno del ciclo e continua a controllare i dati di ciascun nodo per scoprire se corrisponde ai dati di attesa PTR1. Se corrisponde, i suoi duplicati vengono rimossi dall'elenco collegato. Questo è controllato e continua fino a quando non raggiunge l'ultimo nodo il cui valore è nullo.

Quando ptr2-> next == null, il ciclo nidificato termina e il circuito esterno incrementi ptr1 = ptr1-> successiva con i dati del nodo successivo.

Nota: IL PTR2 termina quando il PTR1 Loop è finito perché PTR2 è all'interno del ciclo PTR1.

mentre (PTR1 != Null && ptr1-> next != Null)
ptr2 = ptr1;
while (PTR2-> Next != Null)
/* Se trovato, il codice di seguito eliminerà
duplicati nodo*/
if (ptr1-> data == ptr2-> next-> data)
duplicato = ptr2-> next;
ptr2-> next = ptr2-> next-> next;
eliminare (duplicato);
else /* Se non trovato, PTR2 verrà aggiornato
al nodo successivo*/
ptr2 = ptr2-> next;

PTR1 = ptr1-> Next;

Linee da 78 a 84: Questo visualizza l'elenco collegato finale senza alcuna duplicazione. In tal caso, passiamo il dono come parametro che è l'indirizzo dell'elenco collegato.

/* Questa funzione stamperà l'elenco collegato*/
void display (nodo* nodo)
while (node-> next)
printf ("%d ->", node-> data);
node = nodo-> next;

printf ("%d", dati node->);

Approccio 2: metodo di hashing

Passi di algoritmo

1. Crea una funzione di elenco collegato, "CreateLinkEdList", che può creare un elenco collegato.
2. Crea una funzione chiamata "deleteduplicatesnodes" che può eliminare il nodo duplicato dall'elenco collegato.
3. Crea due puntatori locali, CurrentNode e precedenteNode, all'interno della funzione "deleteduplicatesNodes".
4. Crea un hash non mobile set all'interno dei "EleteduplicatesNodes".
5. Assegna CurrentNode = headNode e precedentiNode = Null Valori dove viene utilizzato CurrentNode per tracciare il nodo i cui duplicati devono essere controllati e viene utilizzato il precedente NODE per tracciare il nodo precedente di CurrentNode.
6. Il ciclo while attraversa l'intero nodo dell'elenco collegato fino a CurrentNode == NULL.
7. Se i dati di CurrentNode sono già nel set di hash, il nodo viene eliminato.
8. In caso contrario, aggiunge i dati di quel nodo al set di hash.
9. I passaggi da 5 a 8 vengono ripetuti fino a quando la corrente non è uguale a null, il che indica che ha raggiunto la fine dell'elenco collegato.
10. Infine, stampiamo l'elenco collegato.
11. Fine dell'algoritmo.

Implementazione del codice C ++ (utilizzando il metodo hash)

Produzione:

Righe da 26 a 52: Creiamo una funzione con il nome "CreateLinkedList". In quella funzione, passiamo due parametri (un puntatore per il dono al puntatore e un valore). Come mostrato nel programma precedente, ogni volta che questa funzione viene chiamata, crea prima un nuovo nodo con un valore (che abbiamo passato) e un indirizzo con un valore null.

/* Crea un nuovo nodo*/
Nodo* newNode = new node ();
Nodo * lastnode = * headnode;
newnode-> data = value; / * Aggiunta dei dati */
/* Indirizzo di questo nuovo nodo trattenuto nullo*/
newnode-> next = null;

Quindi, controlla se il riferimento a headnode è nullo. Se lo è, il nodo appena creato diventa la testa.

/* Controllare che il riferimento a headnode è nullo o no.
Se sì, allora il newnode diventerà il headnode*/
if (*headnode == null)
*headnode = newnode;
ritorno;

Se il riferimento a headnode non è nullo, si aggiunge all'ultimo tempo dell'elenco collegato. L'indirizzo di questo newnode appena creato è assegnato al LastNode in modo che possa iniziare a puntare il newnode appena creato.

/* In caso contrario, allora questo loop lo farà
eseguire e trovare l'ultimo nodo del collegamento
elenco, in modo che il newnode appena creato aggiunga all'ultimo*/
while (LastNode-> Next != Null)
LastNode = LastNode-> Next;

Ora, il newnode appena creato diventa il LastNode. Questo processo continua fino a quel momento in cui chiamiamo questa funzione.

I passaggi precedenti creano l'elenco collegato secondo i nostri requisiti. Ora eliminiamo i nodi duplicati dall'elenco collegato.

Righe da 57 a 75: Creiamo una funzione denominata "deleteduplicatesnodes" che accetta un parametro che è il puntatore del headnode dell'elenco collegato. Creiamo un hashset hashshset. Creiamo anche due variabili a livello locale, CurrentNode E precedente, Per tracciare l'elenco collegato quando lo facciamo per scoprire i duplicati nell'elenco collegato. Inizializzamo la corrente corrente con il headnode poiché questo sarà il ciclo superiore e il precedente precedente con il valore null.

nodo struct* currentNode = headnode;
nodo struct* precedenteNode = null;

CurrentNode: Questa variabile è al ciclo esterno e tiene traccia degli elementi i cui duplicati controlleremo.

precedente: Questo gestisce il nodo precedente di CurrentNode. Creiamo un ciclo while che esegue fino a quando il CurrentNode non trova il valore null, il che significa alla fine dell'elenco collegato. Se i dati CurrentNode sono già nella mappa hash, assegnare il valore del CurrentNode's successivo puntatore al PrecedentiNode's Puntatore successivo.

PrecedenteNode-> Next = CurrentNode-> Next;

In caso contrario, aggiungi i dati di CurrentNode alla mappa hash e crea il precedente uguale a CurrentNode.

altro
hash.inserire (currentNode-> dati);
PrecedenteNode = CurrentNode;

Alla fine, assegnare il valore del puntatore successivo del precedente Nome di CurrentNode.

while (currentNode != Null)
/* Se i dati di CurrentNode sono già visitati, allora questo
Il codice eliminerà quel nodo
*/
Se (hash.Trova (CurrentNode-> Data) != hash.FINE())
PrecedenteNode-> Next = CurrentNode-> Next;
delete (currentNode);

/*
Se non visitato i dati CurrentNode, allora
inserire nell'hash
*/
altro
hash.inserire (currentNode-> dati);
PrecedenteNode = CurrentNode;

CurrentNode = precedenteNode-> Next;

Linee da 84 a 90: Questo visualizza l'elenco collegato finale senza alcuna duplicazione. In tal caso, passiamo il dono come parametro che è l'indirizzo dell'elenco collegato.

/* Questa funzione stamperà l'elenco collegato*/
void display (nodo* nodo)
while (node-> next)
printf ("%d ->", node-> data);
node = nodo-> next;

printf ("%d", dati node->);

Conclusione

Nel primo metodo, per sbarazzarsi dei duplicati, utilizziamo due loop: un ciclo esterno che itera nell'elenco collegato e seleziona un elemento e un secondo ciclo che ripete su quell'elemento per cercare eventuali duplicati. Non appena viene rilevato un duplicato, viene eliminato dall'elenco. Questo metodo utilizza un ciclo nidificato per esaminare ed eliminare i duplicati da un elenco collegato non richiesto che aumenta la complessità temporale del processo. La complessità del tempo è O (n²).

Nel secondo metodo, l'hashing può essere utilizzato per ridurre al minimo la complessità temporale di rimozione dei duplicati da un elenco collegato non richiesto. In questo caso, se il nodo appare nell'hashmap due volte, è una duplicazione e la prima occorrenza dovrebbe essere eliminata. Se manca un nodo dalla mappa, è perché ce n'è uno nuovo che deve essere aggiunto. Ci vuole tempo in media O (n) per riparare un elenco collegato di lunghezza "N" e controlla se i suoi nodi sono nella mappa. La complessità temporale per cercare un valore in una tabella hash è O (1). Considerando insieme i prerequisiti di cui sopra, la complessità del tempo totale è O (N).