Modulo 13 — Algoritmi
Strutture Dati
Stack, Queue, Binary Search Tree, Heap, Hash Table e Trie — implementazione da zero in C.
Panoramica
| Struttura | Accesso | Ricerca | Inserimento | Cancellazione |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack/Queue | O(n) | O(n) | O(1) | O(1) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| BST (bilanciato) | O(log n) | O(log n) | O(log n) | O(log n) |
| Min Heap | O(1) min | O(n) | O(log n) | O(log n) |
| Hash Table | O(1) | O(1) | O(1) | O(1) |
1. Stack (Pila) — LIFO
CStack dinamico generico
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
void *dati;
int cima;
int capacita;
size_t elem_size;
} Stack;
Stack* stack_crea(size_t elem_size, int cap_iniz) {
Stack *s = malloc(sizeof(Stack));
s->dati = malloc(cap_iniz * elem_size);
s->cima = -1;
s->capacita = cap_iniz;
s->elem_size = elem_size;
return s;
}
int stack_empty(Stack *s) { return s->cima == -1; }
int stack_size(Stack *s) { return s->cima + 1; }
void stack_push(Stack *s, const void *elem) {
if (s->cima + 1 == s->capacita) {
s->capacita *= 2;
s->dati = realloc(s->dati, s->capacita * s->elem_size);
}
memcpy((char*)s->dati + (++s->cima) * s->elem_size, elem, s->elem_size);
}
int stack_pop(Stack *s, void *out) {
if (stack_empty(s)) return 0;
memcpy(out, (char*)s->dati + s->cima-- * s->elem_size, s->elem_size);
return 1;
}
void* stack_peek(Stack *s) {
if (stack_empty(s)) return NULL;
return (char*)s->dati + s->cima * s->elem_size;
}
void stack_distruggi(Stack *s) { free(s->dati); free(s); }
// Applicazione: valuta espressioni postfisse (Notazione Polacca Inversa)
// Es: "3 4 + 2 * 7 -" = (3+4)*2-7 = 7
double valuta_rpn(const char *expr) {
Stack *s = stack_crea(sizeof(double), 20);
double a, b, risultato = 0;
char *copia = strdup(expr);
char *token = strtok(copia, " ");
while (token) {
if (token[0] >= '0' && token[0] <= '9') {
double val = atof(token);
stack_push(s, &val);
} else {
stack_pop(s, &b);
stack_pop(s, &a);
switch (token[0]) {
case '+': risultato = a+b; break;
case '-': risultato = a-b; break;
case '*': risultato = a*b; break;
case '/': risultato = a/b; break;
}
stack_push(s, &risultato);
}
token = strtok(NULL, " ");
}
stack_pop(s, &risultato);
free(copia); stack_distruggi(s);
return risultato;
}
int main() {
printf("3 4 + 2 * 7 - = %.1f\n", valuta_rpn("3 4 + 2 * 7 -")); // 7
printf("5 1 2 + 4 * + 3 - = %.1f\n", valuta_rpn("5 1 2 + 4 * + 3 -")); // 14
return 0;
}2. Queue (Coda) — FIFO
CQueue circolare (array)
#include <stdio.h>
#include <stdlib.h>
#define MAX_Q 100
typedef struct {
int dati[MAX_Q];
int testa, coda, dimensione;
} Queue;
void queue_init(Queue *q) { q->testa = q->coda = q->dimensione = 0; }
int queue_empty(Queue *q) { return q->dimensione == 0; }
int queue_full(Queue *q) { return q->dimensione == MAX_Q; }
int queue_enqueue(Queue *q, int val) {
if (queue_full(q)) return 0;
q->dati[q->coda] = val;
q->coda = (q->coda + 1) % MAX_Q; // Avanzamento circolare
q->dimensione++;
return 1;
}
int queue_dequeue(Queue *q, int *out) {
if (queue_empty(q)) return 0;
*out = q->dati[q->testa];
q->testa = (q->testa + 1) % MAX_Q;
q->dimensione--;
return 1;
}
int queue_peek(Queue *q) { return q->dati[q->testa]; }
// Applicazione: BFS (Breadth-First Search) su un grafo
void bfs(int adj[][6], int n, int start) {
Queue q;
queue_init(&q);
int visitati[n];
for(int i=0;i<n;i++) visitati[i]=0;
visitati[start] = 1;
queue_enqueue(&q, start);
printf("BFS da %d: ", start);
while (!queue_empty(&q)) {
int curr;
queue_dequeue(&q, &curr);
printf("%d ", curr);
for (int v = 0; v < n; v++) {
if (adj[curr][v] && !visitati[v]) {
visitati[v] = 1;
queue_enqueue(&q, v);
}
}
}
printf("\n");
}
int main() {
Queue q;
queue_init(&q);
for (int i=1; i<=5; i++) queue_enqueue(&q, i*10);
int val;
while (!queue_empty(&q)) {
queue_dequeue(&q, &val);
printf("%d ", val);
}
printf("\n");
// BFS demo
int adj[6][6] = {
{0,1,1,0,0,0},
{1,0,0,1,1,0},
{1,0,0,0,0,1},
{0,1,0,0,0,0},
{0,1,0,0,0,0},
{0,0,1,0,0,0}
};
bfs(adj, 6, 0);
return 0;
}3. Binary Search Tree (BST)
CBST completo — inserisci, cerca, elimina, traversal
#include <stdio.h>
#include <stdlib.h>
typedef struct Nodo {
int val;
struct Nodo *sx, *dx;
} Nodo;
Nodo* nuovo(int v) {
Nodo *n = malloc(sizeof(Nodo));
return n->val=v, n->sx=n->dx=NULL, n;
}
Nodo* inserisci(Nodo *r, int v) {
if (!r) return nuovo(v);
if (v < r->val) r->sx = inserisci(r->sx, v);
else if (v > r->val) r->dx = inserisci(r->dx, v);
return r;
}
Nodo* cerca(Nodo *r, int v) {
if (!r || r->val==v) return r;
return v < r->val ? cerca(r->sx,v) : cerca(r->dx,v);
}
Nodo* minimo(Nodo *n) { return n->sx ? minimo(n->sx) : n; }
Nodo* elimina(Nodo *r, int v) {
if (!r) return NULL;
if (v < r->val) r->sx = elimina(r->sx, v);
else if (v > r->val) r->dx = elimina(r->dx, v);
else {
if (!r->sx) { Nodo *t=r->dx; free(r); return t; }
if (!r->dx) { Nodo *t=r->sx; free(r); return t; }
// Ha 2 figli: sostituisci con il successore (minimo del sottoalbero dx)
Nodo *succ = minimo(r->dx);
r->val = succ->val;
r->dx = elimina(r->dx, succ->val);
}
return r;
}
// Traversal
void inorder(Nodo *n) { if(n){inorder(n->sx); printf("%d ",n->val); inorder(n->dx);} }
void preorder(Nodo *n) { if(n){printf("%d ",n->val); preorder(n->sx); preorder(n->dx);} }
void postorder(Nodo *n){ if(n){postorder(n->sx); postorder(n->dx); printf("%d ",n->val);} }
int altezza(Nodo *n) {
if (!n) return 0;
int sx=altezza(n->sx), dx=altezza(n->dx);
return 1 + (sx>dx?sx:dx);
}
int main() {
int vals[] = {50,30,70,20,40,60,80,10,25,35,45};
Nodo *bst = NULL;
for(int i=0;i<11;i++) bst=inserisci(bst,vals[i]);
printf("In-order: "); inorder(bst);
printf("\nPre-order: "); preorder(bst);
printf("\nPost-order: "); postorder(bst);
printf("\nAltezza: %d\n", altezza(bst));
bst = elimina(bst, 30);
printf("Dopo elimina(30): "); inorder(bst); printf("\n");
return 0;
}4. Min Heap / Priority Queue
Un heap è un albero binario quasi completo dove ogni nodo è ≤ dei suoi figli. Permette di estrarre il minimo in O(log n). Usato in Dijkstra, A*, Huffman coding, ecc.
CMin Heap con array
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP 100
typedef struct {
int arr[MAX_HEAP];
int size;
} MinHeap;
void heap_init(MinHeap *h) { h->size = 0; }
// Indici: figlio_sx(i)=2i+1, figlio_dx(i)=2i+2, padre(i)=(i-1)/2
void sift_up(MinHeap *h, int i) {
while (i > 0) {
int padre = (i-1)/2;
if (h->arr[padre] > h->arr[i]) {
int t = h->arr[padre]; h->arr[padre]=h->arr[i]; h->arr[i]=t;
i = padre;
} else break;
}
}
void sift_down(MinHeap *h, int i) {
while (1) {
int minIdx = i;
int sx = 2*i+1, dx = 2*i+2;
if (sx < h->size && h->arr[sx] < h->arr[minIdx]) minIdx = sx;
if (dx < h->size && h->arr[dx] < h->arr[minIdx]) minIdx = dx;
if (minIdx != i) {
int t=h->arr[i]; h->arr[i]=h->arr[minIdx]; h->arr[minIdx]=t;
i = minIdx;
} else break;
}
}
void heap_push(MinHeap *h, int val) {
h->arr[h->size++] = val;
sift_up(h, h->size-1);
}
int heap_pop(MinHeap *h) {
int min = h->arr[0];
h->arr[0] = h->arr[--h->size];
sift_down(h, 0);
return min;
}
int heap_peek(MinHeap *h) { return h->arr[0]; }
// Heap Sort usando il Min Heap
void heap_sort(int arr[], int n) {
MinHeap h; heap_init(&h);
for(int i=0;i<n;i++) heap_push(&h, arr[i]);
for(int i=0;i<n;i++) arr[i] = heap_pop(&h);
}
int main() {
MinHeap h; heap_init(&h);
int vals[] = {5,3,8,1,9,2,7,4,6};
for(int i=0;i<9;i++) heap_push(&h, vals[i]);
printf("Estrazione in ordine: ");
while(h.size > 0) printf("%d ", heap_pop(&h));
printf("\n");
int arr[] = {64,25,12,22,11};
int n = 5;
heap_sort(arr, n);
printf("Heap Sort: ");
for(int i=0;i<n;i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}5. Hash Table
Mappa chiavi → valori con accesso O(1) medio. Usa una funzione hash per convertire la chiave in un indice, e gestisce le collisioni (chaining o open addressing).
CHash Table con chaining (lista collegata per collisioni)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 64
typedef struct Entry {
char *chiave;
int valore;
struct Entry *prossimo;
} Entry;
typedef struct {
Entry *bucket[TABLE_SIZE];
int size;
} HashTable;
// Funzione hash djb2 (buona distribuzione)
unsigned int hash(const char *key) {
unsigned int h = 5381;
while (*key) h = ((h << 5) + h) + *key++;
return h % TABLE_SIZE;
}
HashTable* ht_crea() {
HashTable *ht = calloc(1, sizeof(HashTable));
return ht;
}
void ht_set(HashTable *ht, const char *chiave, int valore) {
unsigned int idx = hash(chiave);
Entry *e = ht->bucket[idx];
// Cerca se la chiave esiste già
while (e) {
if (strcmp(e->chiave, chiave) == 0) {
e->valore = valore; // Aggiorna
return;
}
e = e->prossimo;
}
// Nuova entry (inserimento in testa)
Entry *nuovo = malloc(sizeof(Entry));
nuovo->chiave = strdup(chiave);
nuovo->valore = valore;
nuovo->prossimo = ht->bucket[idx];
ht->bucket[idx] = nuovo;
ht->size++;
}
int ht_get(HashTable *ht, const char *chiave, int *out) {
unsigned int idx = hash(chiave);
for (Entry *e = ht->bucket[idx]; e; e = e->prossimo) {
if (strcmp(e->chiave, chiave) == 0) {
*out = e->valore;
return 1;
}
}
return 0;
}
int ht_delete(HashTable *ht, const char *chiave) {
unsigned int idx = hash(chiave);
Entry **pp = &ht->bucket[idx];
while (*pp) {
if (strcmp((*pp)->chiave, chiave) == 0) {
Entry *da_eliminare = *pp;
*pp = da_eliminare->prossimo;
free(da_eliminare->chiave);
free(da_eliminare);
ht->size--;
return 1;
}
pp = &(*pp)->prossimo;
}
return 0;
}
void ht_stampa(HashTable *ht) {
for (int i=0; i<TABLE_SIZE; i++) {
if (ht->bucket[i]) {
printf("[%2d] ", i);
for (Entry *e = ht->bucket[i]; e; e = e->prossimo)
printf("%s=%d ", e->chiave, e->valore);
printf("\n");
}
}
}
int main() {
HashTable *ht = ht_crea();
ht_set(ht, "mario", 95);
ht_set(ht, "giulia", 88);
ht_set(ht, "luca", 72);
ht_set(ht, "anna", 95);
ht_set(ht, "mario", 98); // Update
int v;
if (ht_get(ht, "mario", &v)) printf("mario = %d\n", v);
if (ht_get(ht, "giulia", &v)) printf("giulia = %d\n", v);
ht_delete(ht, "luca");
printf("Dopo delete 'luca': size=%d\n", ht->size);
printf("\nContenuto:\n");
ht_stampa(ht);
return 0;
}🏋️ Esercizi
Implementa e usa le strutture dati fondamentali.
1
Usando uno stack, valida espressioni matematiche verificando che le parentesi (), [], {} siano bilanciate. Per ogni errore, indica quale riga e colonna dell'input è problematica.
C
#include <stdio.h>
#include <string.h>
#define MAX 1000
typedef struct { char c; int pos; } Elem;
int valida(const char *expr) {
Elem stack[MAX]; int top=-1;
for(int i=0; expr[i]; i++) {
char c=expr[i];
if(c=='('||c=='['||c=='{') {
stack[++top]=(Elem){c,i};
} else if(c==')'||c==']'||c=='}') {
if(top<0) { printf("Errore: '%c' in posizione %d senza apertura\n",c,i); return 0; }
char aperto=stack[top--].c;
if((c==')' && aperto!='(')||(c==']' && aperto!='[')||(c=='}' && aperto!='{')) {
printf("Errore: '%c' in posizione %d non corrisponde a '%c'\n",c,i,aperto);
return 0;
}
}
}
if(top>=0) { printf("Errore: '%c' in posizione %d mai chiusa\n",stack[top].c,stack[top].pos); return 0; }
return 1;
}
int main() {
const char *test[] = {"(a+b)*[c-d]/{e}", "((a+b)", "(a+[b)]", "{a+b}"};
for(int i=0;i<4;i++) {
printf("'%s' → %s\n\n", test[i], valida(test[i]) ? "OK ✓" : "ERRORE ✗");
}
return 0;
}2
Leggi un testo (da stdin o da file). Usa una hash table per contare la frequenza di ogni parola (case insensitive, ignora punteggiatura). Stampa le top-10 parole più frequenti.
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define TS 512
typedef struct E { char *k; int v; struct E *n; } E;
E *ht[TS] = {0};
unsigned int h(const char *k) {
unsigned int x=5381; while(*k) x=((x<<5)+x)+*k++; return x%TS;
}
void set(const char *k) {
unsigned int idx=h(k);
for(E *e=ht[idx];e;e=e->n) if(strcmp(e->k,k)==0){e->v++;return;}
E *n=malloc(sizeof(E)); n->k=strdup(k); n->v=1; n->n=ht[idx]; ht[idx]=n;
}
int cmp_freq(const void *a, const void *b) {
return ((E*)b)->v - ((E*)a)->v;
}
int main() {
char buf[1000000];
int len = fread(buf, 1, sizeof(buf)-1, stdin);
buf[len] = '\0';
char parola[100]; int pi=0;
for(int i=0;i<=len;i++) {
char c=tolower(buf[i]);
if(isalpha(c)) { parola[pi++]=c; }
else if(pi>0) { parola[pi]='\0'; set(parola); pi=0; }
}
// Raccogli tutte le entry
E *all[100000]; int n=0;
for(int i=0;i<TS;i++) for(E *e=ht[i];e;e=e->n) all[n++]=e;
qsort(all, n, sizeof(E*), cmp_freq);
printf("Top 10 parole più frequenti:\n");
for(int i=0;i<10&&i<n;i++)
printf("%3d. %-20s %d\n", i+1, all[i]->k, all[i]->v);
return 0;
}3
Implementa un albero AVL: un BST che si auto-bilancia dopo ogni inserimento. Ogni nodo tiene traccia del proprio "balance factor" (altezza destra - altezza sinistra). Se |bf| > 1, applica rotazioni (LL, RR, LR, RL) per ribilanciare. Testa inserendo i valori 1..10 e verifica che l'altezza rimanga O(log n).
C
#include <stdio.h>
#include <stdlib.h>
typedef struct N { int val, h; struct N *sx, *dx; } N;
int h(N *n) { return n ? n->h : 0; }
int bf(N *n) { return h(n->dx) - h(n->sx); }
void upd_h(N *n) { n->h = 1+(h(n->sx)>h(n->dx)?h(n->sx):h(n->dx)); }
N* rot_dx(N *y) {
N *x=y->sx; y->sx=x->dx; x->dx=y;
upd_h(y); upd_h(x); return x;
}
N* rot_sx(N *x) {
N *y=x->dx; x->dx=y->sx; y->sx=x;
upd_h(x); upd_h(y); return y;
}
N* ins(N *n, int v) {
if(!n){N*x=malloc(sizeof(N)); x->val=v; x->h=1; x->sx=x->dx=NULL; return x;}
if(v<n->val) n->sx=ins(n->sx,v);
else if(v>n->val) n->dx=ins(n->dx,v);
else return n;
upd_h(n);
int b=bf(n);
// LL
if(b<-1 && v<n->sx->val) return rot_dx(n);
// RR
if(b>1 && v>n->dx->val) return rot_sx(n);
// LR
if(b<-1 && v>n->sx->val){n->sx=rot_sx(n->sx); return rot_dx(n);}
// RL
if(b>1 && v<n->dx->val){n->dx=rot_dx(n->dx); return rot_sx(n);}
return n;
}
void inorder(N *n) { if(n){inorder(n->sx);printf("%d(h%d) ",n->val,n->h);inorder(n->dx);} }
int main() {
N *avl=NULL;
for(int i=1;i<=10;i++) avl=ins(avl,i);
printf("AVL inorder: "); inorder(avl); printf("\n");
printf("Altezza radice: %d (log2(10)≈3.3)\n", avl->h);
return 0;
}