Ordina l'elenco collegato C ++

Lista collegata

Un elenco collegato è una sorta di struttura dei dati. Gli elementi all'interno dell'elenco collegato sono collegati utilizzando i puntatori. È una raccolta di nodi. Un nodo contiene due parti. Uno include i dati e la seconda parte è costituita dal puntatore. Questo puntatore viene utilizzato per archiviare l'indirizzo di memoria dell'elemento nodo adiacente ad esso nell'elenco collegato. Il vantaggio dell'elenco collegato di un array è che ha una dimensione dinamica.

Rappresentazione di un elenco collegato

Il primo nodo dell'elenco collegato è chiamato in anticipo. Il suo valore è nullo nel caso di un array vuoto. In C ++, utilizziamo una struttura per rappresentare un nodo.

Questo è un semplice codice C ++ della creazione di elenchi collegati. Abbiamo creato una classe in cui la sua porzione pubblica, una variabile di dati di tipo intero, viene creata con una variabile di tipo puntatore "successiva" che memorizzerà l'indirizzo del nodo.

Tre nodi vengono creati all'interno del programma principale, con il primo nodo in alto dichiarato come nodo "head". Tutti i tre puntatori di questi nodi sono vuoti, quindi inizialmente sono dichiarati null. Dopo averlo fatto, tutti e tre i nodi vengono assegnati in un mucchio. "head" secondo e terzo è assegnato con il nuovo nodo.

Ora assegneremo i dati e i dati possono essere qualsiasi valore casuale. Innanzitutto, assegneremo i dati nel primo nodo.

Head-> data = 1;

Questa dimostrazione dell'assegnazione dei dati mostra che la parte dei dati del primo nodo conterrà dati in essa. Dopo aver assegnato i dati, collegheremo il primo nodo con il secondo

Head-> next = secondo;

Collegiamo la parte del puntatore "successivo" con l'altro nodo per collegare due nodi. Assegneremo i dati archiviati nella parte dati del primo nodo. Mentre la parte "successiva" conterrà l'indirizzo di memoria del nodo presente dopo di esso. Allo stesso modo, ora assetteremo i dati al secondo nodo e il secondo nodo sarà collegato al terzo nodo. Ora aggiungi i dati nel terzo nodo. Dato che abbiamo creato solo tre nodi, non c'è altro nodo, quindi la parte successiva del terzo puntatore sarà dichiarata null; Ciò indica che l'elenco collegato è terminato.

Terzo-> Next = Null;

Esempio

Ordina elenco collegato

Qui abbiamo dichiarato una struttura che rappresenta un nodo di un singolo elenco collegato. Come descritto sopra, il concetto di dichiarazione di elenco collegati, la variabile di dati e le variabili del puntatore sono prese nella struttura. Come la parte del puntatore "successiva" che memorizza l'indirizzo, abbiamo anche dichiarato altre due variabili di tipo puntatore: testa del nodo e coda di nodo. Questi entrambi sono inizialmente dichiarati nulli.

Poiché il nodo di inserzione si occupa dell'inserimento del nodo di dati nell'elenco collegato, utilizzeremo una funzione per l'aggiunta di un nodo. I dati assegneranno anche questo nodo. Quindi il parametro di questa funzione conterrà i dati come argomento. Prima dell'inserimento, il nodo verrà creato con l'allocazione della memoria utilizzando una funzione Malloc (). La parte dei dati del nuovo nodo verrà assegnata con i dati passati.

Newnode-> data = data;

E allo stesso modo, la parte successiva è assegnata come null, in quanto non esiste una connessione tra questo nodo con nessun altro. Poiché le variabili della testa e della coda sono dichiarate per aiutare nell'ordinamento di inserimento. Ora li utilizzeremo qui. Innanzitutto, usando un'istruzione If-Else, verificheremo se la testa è nulla, come abbiamo dichiarato null sopra, il che significa che l'intero elenco è vuoto. Ecco perché la testa è vuota, quindi la testa e le variabili di coda indicheranno il nodo appena creato. Altrimenti, nella parte altro, se l'elenco non è vuoto, supponiamo che durante la creazione dell'elenco abbiamo inserito anche i dati, quindi, in questo caso, il nuovo nodo verrà aggiunto all'ultimo posto.

Tail-> Next = newnode;

E ora, questo nuovo nodo fungerà da nuovo racconto.

Tail = newnode;

Per ulteriori aggiunte, lo stesso processo continua, ma dobbiamo ordinare l'elenco collegato. Quindi abbiamo aggiunto un singolo nodo che funge da nodo temp per archiviare i dati temporaneamente.

Dopo aver aggiunto il nuovo nodo, useremo una funzione per ordinare/ disporre l'elenco. Poiché il tipo di ordinamento non è menzionato qui, per impostazione predefinita, l'elenco verrà ordinato in ordine crescente.

Tornando verso l'esempio, un altro puntatore corrente punta alla testa, come abbiamo dichiarato sopra. Questo viene utilizzato per ordinare gli elementi dell'elenco. Un'altra variabile di tipo puntatore verrà utilizzata qui e quindi dichiarata null. Un ulteriore utilizzo sarà nel programma in seguito.

Qui applicheremo un assegno per identificare se il puntatore del capo è in posizione null, quindi torneremo al programma principale. Altrimenti applicheremo la logica qui che seguirà un po '. Il puntatore dell'indice punterà alla parte successiva del nodo corrente. All'interno di quel loop, un altro While Loop viene utilizzato e questo durerà anche fino a quando il nodo corrente non è nullo. Qui utilizzeremo una sezione if per verificare se i dati nel nodo corrente sono maggiori dei dati all'interno del nodo dell'indice, i dati tra loro vengono scambiati.

La variabile Temp svolgerà un ruolo importante qui nello scambio di dati. Innanzitutto, i dati del nodo corrente vengono trasferiti su temp, quindi il nodo corrente è ora vuoto. A questo nodo verrà assegnato il valore dei dati dell'indice. E alla fine, il nodo indice vuoto è assegnato dai dati presenti nella variabile temp.

All'esterno della dichiarazione if, il nodo indice è anche incrementato con il nuovo valore di un indice. Allo stesso modo, al di fuori del ciclo, il nodo corrente è anche assegnato dal nuovo valore.

Successivamente, abbiamo usato una funzione di visualizzazione qui per visualizzare il valore di tutti i nodi. L'attuale puntatore punterà verso la testa. In un altro caso, un ciclo while visualizza tutti i valori fino a quando il nodo corrente non è nullo.

Ora considera il programma principale, la funzione di addNode () viene chiamata con i valori per aggiungere nuovi valori all'interno dell'elenco. Quindi la funzione di visualizzazione visualizzerà tutti i valori immessi prima dell'ordinamento. Quindi chiama la funzione Ordine (). E poi di nuovo, chiama la funzione di visualizzazione per visualizzare l'intero elenco ordinato.

Salva il file del codice e quindi eseguilo nel terminale Ubuntu con l'aiuto di un compilatore G ++.

file file file $ g ++ -o.C

$./file

Dal valore risultante, è possibile osservare che i valori sono disposti in ordine crescente in quanto sono stati inseriti casualmente nell'elenco collegato.

Conclusione

'Ordina Elenco collegato C ++' contiene la descrizione delle conoscenze di base riguardanti l'elenco collegato e la sua creazione. Un codice di esempio è sufficiente per dimostrare la creazione del nodo e il funzionamento di tutti i nodi nell'elenco collegato. Gli elementi all'interno dell'elenco collegato sono disposti in ordine crescente utilizzando un processo dettagliato aggiungendo nuovi nodi e quindi ordinando attraverso una variabile temporanea. La spiegazione con il codice viene eseguita per aiutare l'utente.