Le strutture dati permettono ai programmatori di memorizzare, organizzare e gestire i dati in modo efficiente. Semplici array o memorizzazione sequenziale spesso non sono sufficienti per compiti complessi, motivo per cui vengono utilizzate strutture come liste, alberi e tabelle hash.

In C, le strutture (struct) offrono un modo flessibile per implementare molte di queste strutture dati.

Liste collegate

Una lista collegata è utile quando il numero di elementi può variare dinamicamente. Ogni nodo contiene dati e un puntatore al nodo successivo.

Struttura di esempio di un nodo:

struct Node {
    int data;           // data in node
    struct Node* next;  // pointer to next node
};

Ogni nodo contiene un campo data e un puntatore next. Questo consente di aggiungere o rimuovere elementi in qualsiasi punto della lista senza dover riorganizzare l'intera struttura, a differenza degli array.

Tabella hash

Le tabelle hash consentono di recuperare rapidamente i dati utilizzando una chiave. Una funzione hash converte la chiave in un indice dell'array, dove viene memorizzato il valore.

Esempio di implementazione di una tabella hash:

struct Node {
    char* key;          // key
    int value;          // value
    struct Node* next;  // pointer to next node
};

struct HashTable {
    struct Node** table; // array of node pointers
    int size;            // table size
};

unsigned int hashFunction(char* key, int size) {
    unsigned int hash = 0;
    while (*key) {
        hash += *key++;
    }
    return hash % size;
}

Ogni elemento nella tabella hash è un nodo di lista collegata che contiene una chiave e un valore. La funzione di hash converte la chiave in un indice dell'array, consentendo ricerche rapide anche con grandi quantità di dati.

Alberi

Gli alberi sono utili per dati gerarchici, ricerca veloce, inserimento e cancellazione.

Un albero binario è una struttura in cui ogni nodo ha al massimo due figli: sinistro e destro.

Un esempio di implementazione di un albero binario:

struct node
{
	int data;
	struct node* left; 
	struct node* right; 
};

Un nodo può essere genitore dei propri figli e allo stesso tempo figlio del proprio genitore. Gli alberi binari consentono un'organizzazione efficiente dei dati e una ricerca rapida grazie alla loro struttura logica "sinistra-destra".

Stack

Utilizzato per modellare reti e relazioni.

Uno stack è una struttura dati in cui gli elementi vengono aggiunti (push) e rimossi (pop) secondo il principio LIFO - (Last In, First Out).

Esempio di stack utilizzando un array:

// Stack structure
typedef struct {
    int data[MAX_SIZE]; 
    int top;
} Stack;

MAX_SIZE - the maximum number of elements a stack can contain.

// Push an element onto the stack
void push(Stack *stack, int value) {
    stack->data[++stack->top] = value;  // Increment top and add the element
    printf("Element %d pushed onto the stack\n", value);
}

// Pop an element from the stack
int pop(Stack *stack) {
    int value = stack->data[stack->top--];  // Retrieve the element and decrement top
    printf("Element %d popped from the stack\n", value);
    return value;
}

L'elemento viene aggiunto in cima allo stack (top). Gli stack permettono un'aggiunta e una rimozione veloce degli elementi, con l'ultimo elemento aggiunto che è il primo ad essere rimosso.

L'utilizzo delle strutture in C consente di creare strutture dati flessibili e potenti come array, liste collegate, tabelle hash, alberi e stack. Ogni struttura è ottimizzata per compiti specifici, rendendo i programmi più organizzati ed efficienti.