Cosa sono le strutture dati in C e come usarle?

introduzione

Per cominciare, una struttura di dati è una raccolta di elementi di dati che sono tenuti insieme sotto un nome o intestazione ed è un modo specifico di archiviare e assemblare i dati in modo che i dati possano essere utilizzati in modo efficiente.

Tipi

Le strutture dati sono prevalenti e utilizzate in quasi tutti i sistemi software. Alcuni degli esempi più comuni di strutture dati sono array, code, stack, elenchi collegati e alberi.

Applicazioni

Nella progettazione di compilatori, sistemi operativi, creazione di database, applicazioni di intelligenza artificiale e molti altri.

Classificazione

Le strutture dati sono classificate in due categorie: strutture dati primitive e strutture dati non primitive.

1. Primitivo: sono i tipi di dati di base supportati da un linguaggio di programmazione. Un esempio comune di questa classificazione sono numeri interi, caratteri e booleani.

2. Non primitivo: queste categorie di strutture dati vengono create utilizzando strutture dati primitive. Gli esempi includono stack collegati, elenchi collegati, grafici e alberi.

Matrici

Un array è una semplice raccolta di elementi di dati che hanno lo stesso tipo di dati. Ciò significa che una matrice di interi di tipo può memorizzare solo valori interi. Una matrice di tipo di dati float può memorizzare valori che corrispondono al tipo di dati float e nient'altro.

Gli elementi archiviati in un array sono accessibili in modo lineare e sono presenti in blocchi di memoria contigui a cui è possibile fare riferimento utilizzando un indice.

Dichiarazione di un array

In C, un array può essere dichiarato come:

tipo_dati nome[lunghezza];

Per esempio,

ordini int[10];

La riga di codice sopra crea una matrice di 10 blocchi di memoria in cui è possibile memorizzare un valore intero. In C, il valore dell'indice dell'array inizia da 0. Quindi i valori dell'indice andranno da 0 a 9. Se vogliamo accedere a un valore particolare in quell'array, dobbiamo semplicemente digitare:

printf(ordine[numero_indice]);

Un altro modo per dichiarare un array è il seguente:

tipo_dati nome_array[dimensione]={lista di valori};

Per esempio,

int mark[5]={9, 8, 7, 9, 8};

La riga di comando sopra crea un array con 5 blocchi di memoria con valori fissi in ciascuno dei blocchi. In un compilatore a 32 bit, la memoria a 32 bit occupata dal tipo di dati int è di 4 byte. Quindi, 5 blocchi di memoria occuperebbero 20 byte di memoria.

Un altro modo legittimo per inizializzare gli array è:

int segni [5] = {9 , 45};

Questo comando creerà una matrice di 5 blocchi, con gli ultimi 3 blocchi aventi 0 come valore.

Un altro modo legittimo è:

int segni [] = {9 , 5, 2, 1, 3,4};

Il compilatore C comprende che sono necessari solo 5 blocchi per inserire questi dati in un array. Inizializzerà quindi una matrice di contrassegni di nome di dimensione 5.

Allo stesso modo, un array 2D può essere inizializzato nel modo seguente

int mark[2][3]={{9,7,7},{6, 2, 1}};

Il comando precedente creerà un array 2D con 2 righe e 3 colonne.

Leggi: Idee e argomenti per progetti sulla struttura dei dati

Operazioni

Ci sono alcune operazioni che possono essere eseguite sugli array. Per esempio:

1. attraversando un array
2. Inserimento di un elemento nell'array
3. Ricerca di un particolare elemento nell'array
4. Eliminazione di un particolare elemento dall'array
5. Unendo i due array e,
6. Ordinamento dell'array — in ordine crescente o decrescente.

Svantaggi

La memoria allocata all'array è fissa. Questo in realtà è un problema. Supponiamo che abbiamo creato un array di dimensioni 50 e abbiamo avuto accesso a soli 30 blocchi di memoria. I restanti 20 blocchi occupano memoria senza alcun utilizzo. Pertanto, per affrontare questo problema, abbiamo un elenco collegato.

Lista collegata

Elenco collegato, proprio come gli array memorizza i dati in serie. La differenza principale è che non memorizza tutto in una volta. Memorizza invece i dati o rende disponibile un blocco di memoria come e quando richiesto. In un elenco collegato, i blocchi sono divisi in due parti. La prima parte contiene i dati effettivi.

La seconda parte è un puntatore che punta al blocco successivo in un elenco collegato. Il puntatore memorizza l'indirizzo del blocco successivo che contiene i dati. C'è un altro puntatore noto come puntatore della testa. head punta al primo blocco di memoria nell'elenco collegato. Di seguito è riportata la rappresentazione dell'elenco collegato. Questi blocchi sono anche chiamati "nodi".

fonte

Inizializzazione di elenchi collegati

Per inizializzare l'elenco dei collegamenti, creiamo un nodo di nomi di struttura. La struttura ha due cose. 1. I dati che contiene e 2. Il puntatore che punta al nodo successivo. Il tipo di dati del puntatore sarà quello della struttura in quanto punta al nodo della struttura.

nodo struttura

{

dati int;

nodo struttura *successivo;

};

In un elenco collegato, il puntatore dell'ultimo nodo non punterà a nulla o semplicemente punterà a null.

Leggi anche: Grafici nella struttura dei dati

Attraversamento elenco collegato

In un elenco collegato, il puntatore dell'ultimo nodo non punterà a nulla o semplicemente punterà a null. Quindi, per attraversare un'intera lista collegata, creiamo un puntatore fittizio che inizialmente punta alla testa. E, per la lunghezza dell'elenco collegato, il puntatore continua a spostarsi in avanti finché non punta a null o raggiunge l'ultimo nodo dell'elenco collegato.

Aggiunta di un nodo

L'algoritmo per aggiungere un nodo prima di un nodo specifico sarebbe il seguente:

1. imposta due puntatori fittizi (ptr e preptr) che puntano inizialmente alla testa
2. sposta il ptr fino a quando ptr.data è uguale ai dati prima che intendiamo inserire il nodo. preptr sarà 1 nodo dietro ptr.
3. Crea un nodo
4. Il nodo a cui puntava il preptr fittizio, il nodo successivo punterà a questo nuovo nodo
5. Il prossimo nodo del nuovo punterà al ptr.

L'algoritmo per aggiungere un nodo dopo un dato particolare verrebbe eseguito in modo simile.

Vantaggi dell'elenco collegato

1. Dimensione dinamica a differenza di un array
2. L'esecuzione dell'inserimento e dell'eliminazione è più semplice nell'elenco collegato che in un array.

Coda

La coda segue un tipo di sistema First In First Out o FIFO. In un'implementazione di array, avremo due puntatori per dimostrare il caso d'uso di Queue.

Fonte

FIFO significa sostanzialmente che il valore che entra per primo nello stack, lascia prima l'array. Nel diagramma della coda sopra, il puntatore in primo piano punta al valore 7. Se cancelliamo il primo blocco (elimina dalla coda), il fronte ora punterà al valore 2. Allo stesso modo, se inseriamo un numero (in coda), diciamo 3 in posizione 5. Quindi, il puntatore posteriore punterà alla posizione 5.

Condizioni di overflow e underflow

Tuttavia, prima di inserire un valore di dati nella coda, è necessario verificare le condizioni di overflow. Si verificherà un overflow quando si tenta di inserire un elemento in una coda che è già piena. Una coda sarà piena quando back = max_size–1.

Allo stesso modo, prima di eliminare i dati dalla coda, dovremmo verificare le condizioni di underflow. Si verificherà un underflow quando si tenta di eliminare un elemento da una coda che è già vuota, cioè se front = null e rear = null, la coda è vuota.

Pila

Uno stack è una struttura di dati in cui inseriamo ed eliminiamo elementi solo a un'estremità, nota anche come cima dello stack. L'implementazione dello stack viene quindi definita implementazione LIFO ( last-in, first-out). A differenza della coda, per lo stack è richiesto solo un puntatore in alto.

Se vogliamo inserire (push) elementi in un array, il puntatore superiore si sposta in alto o aumenta di 1. Se vogliamo eliminare (pop) un elemento, il puntatore in alto diminuisce di 1 o scende di 1 unità. Uno stack supporta tre operazioni di base: push, pop e peep. L'operazione Peep sta semplicemente visualizzando l'elemento più in alto nello stack.

Fonte

Impara i corsi di software online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.

Conclusione

In questo articolo abbiamo parlato di 4 tipi di strutture dati, ovvero array, elenchi collegati, code e stack. Spero che questo articolo ti sia piaciuto e resta sintonizzato per letture più interessanti. Fino alla prossima volta.

Se sei interessato a saperne di più su Javascript, lo sviluppo full-stack, dai un'occhiata al programma Executive PG di upGrad & IIIT-B in Full-stack Software Development, progettato per i professionisti che lavorano e offre oltre 500 ore di formazione rigorosa, oltre 9 progetti e incarichi, status di Alumni IIIT-B, progetti pratici pratici e assistenza sul lavoro con le migliori aziende.