Alberi di ricerca binaria PDF - Algoritmi e Strutture Dati

Alberi di ricerca binaria Utilizzato per la realizzazione di insiemi ordinati Operazioni efficienti di – ricerca – inserimento – cancellazione Alberi di ricerca binaria: definizione L’albero vuoto è un albero di ricerca binaria Se l’albero non è vuoto – ogni elemento del sottoalb...

Alberi di ricerca binaria Utilizzato per la realizzazione di insiemi ordinati Operazioni efficienti di – ricerca – inserimento – cancellazione Alberi di ricerca binaria: definizione L’albero vuoto è un albero di ricerca binaria Se l’albero non è vuoto – ogni elemento del sottoalbero di sinistra precede () la radice – i sottoalberi sinistro e destro sono alberi di ricerca binaria Osservazione: non ci sono elementi ripetuti Alberi di ricerca binaria: esempio 20 10 30 5 15 25 40 3 6 35  Operazioni: contains Ricerca di un elemento – Se l’albero è vuoto allora restituisce false – Se l’elemento cercato coincide con la radice dell’albero restituisce true – Se l’elemento cercato è minore della radice restituisce il risultato della ricerca dell’elemento nel sottoalbero sinistro – Se l’elemento cercato è maggiore della radice restituisce il risultato della ricerca dell’elemento nel sottoalbero destro Esempio: ricerca di 15 20 10 30 5 15 25 40 3 6 35  Operazioni: insert Inserimento di un elemento – Se l’albero è vuoto allora crea un nuovo albero con un solo elemento – Se l’albero non è vuoto se l’elemento coincide con la radice non fa niente se l’elemento è minore della radice allora lo inserisce nel sottoalbero sinistro se l’elemento è maggiore della radice allora lo inserisce nel sottoalbero destro Esempio: inserimento di 13 20 10 30 5 15 25 40 3 6 13 35  Operazioni: delete Cancellazione di un elemento e – Nessun problema se il nodo è una foglia – Se il nodo ha un solo sottoalbero di radice r se il nodo da rimuovere è la radice allora r prende il suo posto (diventa radice dell’albero) se il nodo ha un padre p, allora viene rimosso e r prende il suo posto (diventa figlio di p)  Esempio: Eliminazione di 35 20 20 10 30 10 30 5 15 25 40 5 15 25 40 3 6 35 3 6  Esempio: Eliminazione di 40 20 20 10 30 10 30 5 15 25 40 5 15 25 35 3 6 35 3 6  Operazioni: delete Cancellazione di un elemento e – Se il nodo ha entrambi i sottoalberi Si cerca l’elemento max nel sottoalbero sinistro (da notare che tale elemento non ha sottoalbero destro, la cui radice altrimenti sarebbe maggiore) – Alternativamente si cerca l’elemento minimo nel sottoalbero destro Il nodo contenente l’elemento max viene eliminato, mentre a quello contenente l’elemento da eliminare si assegna max – L’albero risultante è un albero di ricerca binaria  Esempio: Eliminazione di 10 20 20 10 30 6 30 5 15 25 40 5 15 25 35 3 6 35 3  Realizzare il modulo BST: header file BST.h // file BST.h typedef struct node *BST; // prototipi BST newBST(void); int emptyBST(BST T); BST figlioSX(BST T); BST figlioDX(BST T); BST insert(BST T, item elem); int contains(BST T, item elem); BST deleteNode(BST T, item elem);  Realizzazione di BST: file BST.c #include BST newBST (void) #include { #include “item.h” return NULL; #include “BST.h” } int emptyBST (BST T) struct node { { item value; return T == NULL; struct node *left; } struct node *right; }; int contains(BST T, item val) { item getItem(struct node *N); if (T == NULL) return 0; void setItem(struct node *N, item el); if (eq(val, getItem(T))) return 1; item getItem(struct node *N) if (minore(val, getItem(T))) { return (contains(figlioSX(T), val)); if (N == NULL) return NULLITEM; else return N->value; return (contains(figlioDX(T), val)); } } void setItem(struct node *N, item el) BST insert(BST T, item elem) { { } if (N==NULL) return; N->value = el; // correttezza di = BST deleteNode(BST T, item elem) } // dipende dal tipo item { }  Realizzazione di BST: file BST.c BST creaFoglia(item elem) { BST insert(BST T, item elem) struct node *N; { N = malloc (sizeof(struct node)); if (T==NULL) return creaFoglia(elem); if (N == NULL) return NULL; else if (minore(elem, getItem(T))) setItem (N, elem); T->left = insert(T->left, elem); N -> left = NULL; else if (minore(getItem(T), elem)) N -> right = NULL; T->right = insert(T->right, elem); return N; return T; } } // deve essere usata sempre nel modo // bst = insert(bst, elem);  Realizzazione di deleteNode(): file BST.c struct node* deleteNode(struct node* root, item key) { if (root == NULL) return root; if (minore(key, root->value)) root->left = deleteNode(root->left, key); else if (minore(root->value, key)) // Delete the inorder successor root->right = deleteNode(root->right, key); root->right = deleteNode(root->right, temp->value); } else return root; { } if (root->left == NULL) { struct node *temp = root->right; struct node * minValue(struct node* node) free(root); { return temp; struct node* current = node; } while (current->left != NULL) else if (root->right == NULL) current = current->left; { return current; struct node *temp = root->left; } free(root); return temp; } struct node* temp = minValue(root->right); root->value = temp->value;  Alberi perfettamente bilanciati e alberi  bilanciati Le operazioni sull’albero di ricerca binaria hanno complessità logaritmica se l’albero è (perfettamente) bilanciato – In un albero bilanciato tutti i nodi interni hanno entrambi i sottoalberi e le foglie sono a livello massimo – Se l’albero ha n nodi l’altezza dell’albero è log2 n Un albero di ricerca binaria si dice  bilanciato se per ogni nodo accade che la differenza (in valore assoluto) tra le altezze dei suoi due sottoalberi è minore o uguale a  – Si può dimostrare che l’altezza dell’albero è  + log2 n  Esempio di albero perfettamente bilanciato 20 10 30 5 15 25 40 3 6 12 18 23 27 35 50  Alberi AVL Per  = 1 si parla di alberi AVL – Dal nome dei suoi ideatori (Adel’son, Vel’skii e Landis) Per prevenire il non bilanciamento ad ogni nodo bisogna aggiungere un indicatore che può assumere i seguenti valori – –1, se l’altezza del sottoalbero sinistro è maggiore (di 1) dell’altezza del sottoalbero destro – 0, se l’altezza del sottoalbero sinistro è uguale all’altezza del sottoalbero destro – +1, se l’altezza del sottoalbero sinistro è minore (di 1) dell’altezza del sottoalbero destro Esempio di albero AVL -1 20 -1 10 30 0 +1 5 -1 15 0 25 40 -1 0 3 +1 6 12 0 0 23 0 27 35 0 0 8  Ribilanciamento di alberi AVL Un inserimento di una foglia può provocare uno sbilanciamento dell’albero – Per almeno uno dei nodi l’indicatore non rispetta più uno dei tre stati precedenti In tal caso bisogna ribilanciare l’albero con operazioni di rotazione (semplice o doppia) agendo sul nodo x a profondità massima che presenta un non bilanciamento – Tale nodo viene detto nodo critico e si trova sul percorso che va dalla radice al nodo foglia inserito Considerazioni simili si possono fare anche per la rimozione di un nodo …  Esempio di sbilanciamento: inserimento di 7 -1 20 -2 20 -1 10 30 0 -2 10 30 0 +1 5 -1 15 0 25 40 -1 +2 5 -1 15 0 25 40 -1 0 3 +1 6 12 0 0 23 0 27 35 0 0 3 +2 6 12 0 0 23 0 27 35 0 0 8 -1 8 nodo critico 7 0 7  Ribilanciamento di alberi AVL: Rotazione semplice x y y x   h     h+1 new new h+2  Ribilanciamento di alberi AVL: Rotazione doppia x z y y x  z h        h+1 new new h+2  Heap Un albero quasi perfettamente bilanciato di altezza h è un albero perfettamente bilanciato fino a livello h-1 Un heap è un albero binario con le seguenti proprietà – Proprietà strutturale: quasi perfettamente bilanciato e le foglie a livello h sono tutte addossate a sinistra – Proprietà di ordinamento: ogni nodo v ha la caratteristica che l’informazione ad esso associata è la più grande tra tutte le informazioni presenti nel sottoalbero che ha v come radice Usato per realizzare code a priorità – Le operazioni sono inserimento di un elemento e rimozione del max  ADT Code a priorità Struttura dati i cui elementi sono coppie (key, value) dette entry, dove key e value appartengono a due insiemi qualsiasi K e V Le entry vengono inserite in ordine qualsiasi, ma estratte in ordine di priorità secondo il valore della key – Ordinamento: sull’insieme delle chiavi è definita una relazione d’ordine ≤ – Priorità: per convenzione, una entry E1=(k1, v1) ha priorità su E2=(k2, v2) se e solo se k2 ≤ k1 Le operazioni fondamentali sono l’inserimento di una entry e la rimozione della entry con max priorità  Code a priorità SPECIFICA SINTATTICA TIPI: PRIORITYQUEUE, BOOLEAN, ITEM OPERATORI: newPQ : ( ) → PRIORITYQUEUE emptyPQ : (PRIORITYQUEUE) → BOOLEAN getMax : (PRIORITYQUEUE) → ITEM deleteMax : (PRIORITYQUEUE) → PRIORITYQUEUE insertPQ : (PRIORITYQUEUE, ITEM) → PRIORITYQUEUE  Code a priorità SPECIFICA SEMANTICA TIPI: PRIORITYQUEUE= insieme delle code a priorità, dove: ᴧ ϵ PRIORITYQUEUE (coda vuota) BOOLEAN = {vero, falso} ITEM = (K x V) è l’insieme delle coppie (k, v) con kϵK e vϵV K è un insieme qualsiasi non vuoto sul quale è definita una relazione d’ordine ≤ V è un insieme qualsiasi non vuoto 28  Code a priorità SPECIFICA SEMANTICA OPERATORI: newPQ ( ) = PQ pre: post: PQ = ᴧ emptyPQ (PQ) = v pre: post: se PQ è vuota, allora v = vero, altrimenti v = falso getMax (PQ) = elem pre: PQ non è vuota post: elem è la entry con la massima priorità fra quelle contenute in PQ 29  Code a priorità SPECIFICA SEMANTICA OPERATORI: deleteMax (PQ) = PQ’ pre: PQ non è vuota post: PQ’ contiene tutte le entry di PQ tranne quella con massima priorità insertPQ (PQ, elem) = PQ’ pre: post: PQ’ contiene elem e tutte le entry contenute in PQ 30  Realizzazione di code a priorità tramite heap Per semplicità, supponiamo che le chiavi siano valori interi Negli esempi e nel codice seguente vengono mostrate e considerate solo le chiavi, senza il valore ad esse associato  Esempio di Heap 15 12 14 10 7 6 9 2 5 3  Inserimento Si inserisce il nuovo nodo come ultima foglia Il nodo inserito risale lungo il percorso che porta alla radice per individuare la posizione giusta (eventualmente fino alla radice) Esempio: inserimento di 18 15 18 12 14 15 14 10 7 6 9 10 12 6 9 2 5 3 18 2 5 3 7  Rimozione Si rimuove sempre la radice (la chiave maggiore, in quanto un heap viene usato per realizzare code a priorità) e si pone l’ultima foglia al posto della radice Se la chiave della radice è più piccola di quella dei suoi figli, si scambia con il maggiore dei due, e si ripete il procedimento finché non si arriva alla condizione in cui il nodo corrente o non ha figli oppure i suoi figli hanno chiavi più piccole 18 7 15 15 14 15 14 12 14 10 12 6 9 10 12 6 9 10 7 6 9 2 5 3 7 2 5 3 2 5 3  Realizzazione di un heap Per le sue caratteristiche un heap può essere realizzato con un array – I nodi sono disposti nell’array per livelli La radice occupa la posizione 1 Se un nodo occupa la posizione i, il suo figlio sinistro occupa la posizione 2*i e il suo figlio destro occupa la posizione 2*i+1  Esempio di Heap 15 12 14 10 7 6 9 rappresentazione 2 5 3 15 12 14 10 7 6 9 2 5 3 0 1 2 3 4 5 6 7 8 9 10  Implementazione di Code a priorità con heap rappresentato con un array // file PQueue.h L’ADT coda a priorità è realizzato in maniera semplificata. typedef struct c_PQ *PQueue; // prototipi Vengono inserite solo chiavi di tipo intero, senza valori associati PQueue newPQ(void); int emptyPQ(PQueue q); Gli operatori insert() e deleteMax() restituiscono un int getMax(PQueue q); valore 0 se l’operazione fallisce, 1 int deleteMax(PQueue q); se termina con successo int insert (PQueue q, int key);  file PQueue.c #include #include #include “PQueue.h” #define MAXPQ 50 int emptyPQ(PQueue q) struct c_PQ { { int vet[MAXPQ]; if (!q) return 1; int numel; return q->numel == 0; }; } static void scendi (PQueue q); static void sali (PQueue q); int getMax(PQueue q) { PQueue newPQ(void) return q->vet; { // NON VERIFICA LA PQueue q; // PRECONDIZIONE q = malloc (sizeof(struct c_PQ)); // LA CODA NON PUO’ if (q == NULL) return NULL; // ESSERE VUOTA q->numel = 0; } return q; }  file PQueue.c int deleteMax(PQueue q) { if (!q || q->numel==0) return 0; // CODA VUOTA q->vet = q->vet[q->numel]; //SPOSTO L’ULTIMO ELEMENTO q->numel --; // IN POSIZIONE 1 scendi(q); // RIAGGIUSTO LO HEAP SCENDENDO return 1; } static void scendi (PQueue q) { int temp, n=q->numel, i=1, pos; while (1) { if (2*i+1 vet[i*2] > q->vet[i*2+1]) ? i*2 : i*2+1; else if (2*i vet[pos] > q->vet[i]) // SCAMBIO LE CHIAVI E PROSEGUO { temp = q->vet[i]; q->vet[i] = q->vet[pos]; q->vet[pos] = temp; i = pos; } else break; // NON CI SONO PIU’ SCAMBI DA FARE, MI FERMO } }  file PQueue.c int insert (PQueue q, int key) { if (!q || q->numel==MAXPQ) return 0; // CODA PIENA q->numel++; q->vet[q->numel] = key; // INSERISCI IN ULTIMA POSIZIONE sali(q); // AGGIUSTA LO HEAP RISALENDO return 1; } static void sali (PQueue q) { int temp, pos=q->numel, i=pos/2; while (pos>1) { if (q->vet[pos] > q->vet[i]) { temp = q->vet[i]; q->vet[i] = q->vet[pos]; q->vet[pos] = temp; pos = i; i = pos/2; } else break; } } ADT Albero binario  I Grafi Un grafo orientato G e’ una coppia dove N è un insieme finito non vuoto (insieme di nodi) e A ⊆ NxN è un insieme finito di coppie ordinate di nodi, detti archi (o spigoli o linee). Se < ui, uj > ∈ A nel grafo vi è un arco da ui ad uj Nell’esempio – N = {u1,u2,u3}, – A = {(u1,u1),(u1,u2),(u2,u1),(u1,u3)}. 2  Gli Alberi Il GRAFO è una struttura dati alla quale si possono ricondurre strutture più semplici: LISTE ed ALBERI L’ALBERO è una struttura informativa per rappresentare: – partizioni successive di un insieme in sottoinsiemi disgiunti – organizzazioni gerarchiche di dati – procedimenti decisionali enumerativi 3  Strutture dati: Alberi Strutture gerarchiche di dati Esempi – Il file system di un sistema operativo – L’organigramma di un’azienda – Alberi generali, alberi n-ari, alberi binari, …  Alberi Ogni nodo ha un unico arco entrante, tranne un nodo particolare, chiamato radice, che non ha archi entranti; Ogni nodo può avere zero o più archi uscenti Esiste un cammino fatto di archi che congiunge la radice con ciascuno dei nodi, e questo cammino è unico Non esistono cicli di archi I nodi senza archi uscenti sono detti foglie Un arco nell’albero induce una relazione padre-figlio A ciascun nodo è solitamente associato un valore, detto etichetta del nodo radice sottoalbero cammino foglia Gli Alberi 6  Alberi: Alcuni concetti Grado di un nodo: numero di figli del nodo Cammino: sequenza di nodi dove il nodo ni è padre del nodo ni+1, per 0  i < k – La lunghezza del cammino è k – Dato un nodo, esiste un unico cammino dalla radice dell’albero al nodo Livello di un nodo: lunghezza del cammino dalla radice al nodo – Definizione ricorsiva: il livello della radice è 0, il livello di un nodo non radice è 1 + il livello del padre Altezza dell’albero: la lunghezza del più lungo cammino nell’albero – Parte dalla radice e termina in una foglia Gli Alberi 8  Sottoalberi dato un albero ed un suo nodo u, i suoi discendenti costituiscono un albero detto sottoalbero di radice u 9  Gli Alberi La natura ricorsiva degli alberi – Un albero può essere definito ricorsivamente – Un albero è un insieme di nodi ai quali sono associate delle informazioni – Un albero può essere vuoto – Tra i nodi di un albero non vuoto esiste un nodo particolare che è la radice (livello 0) – Gli altri nodi sono partizionati in sottoinsiemi che sono a loro volta alberi (livelli successivi): Vuoto o costituito da un solo nodo (detto radice) Oppure è una radice cui sono connessi altri alberi 10  Gli Alberi La natura ricorsiva degli alberi T T1 T2 T3 Tk 11  Gli Alberi binari Alberi Binari – Sono particolari alberi ordinati in cui ogni nodo ha al più due figli e si fa sempre distinzione tra il figlio sinistro, che viene prima nell’ordinamento e il figlio destro. Nell’esempio gli alberi sono uva etichettati con interi e con caratteri – Un albero binario è un grafo orientato che o è vuoto o è costituito tre più da un solo nodo o è formato da un nodo n (detto radice) e da due sottoalberi binari, chiamati rispettivamente sottoalbero (o figlio) sinistro e sottoalbero (o figlio) destro con boa boa 12  Alberi binari Particolari alberi n-ari con caratteristiche molto importanti Ogni nodo può avere al più due figli – sottoalbero sinistro e sottoalbero destro Definizione ricorsiva: – un albero senza nodi (albero vuoto) è un albero binario – una terna (r, s, d), dove r è un nodo (la radice), s e d sono alberi binari (sottoalberi sinistro e destro) è un albero binario Alberi binari semplificati – Costruttore bottom-up – Operatori di selezione – Operatori di visita  Gli Alberi Binari SPECIFICA SINTATTICA TIPI: ALBEROBIN, BOOLEAN, NODO, ITEM OPERATORI: newBtree : ( ) → ALBEROBIN emptyBtree : (ALBEROBIN) → BOOLEAN getRoot : (ALBEROBIN) → NODO figlioSX : (ALBEROBIN) → ALBEROBIN figlioDX : (ALBEROBIN) → ALBEROBIN consBtree : (ITEM, ALBEROBIN, ALBEROBIN) → ALBEROBIN 14  Gli Alberi Binari SPECIFICA SEMANTICA TIPI: ALBEROBIN = insieme degli alberi binari, dove: ᴧ ϵ ALBEROBIN (albero vuoto) se N ϵ NODO, T1 e T2 ϵ ALBEROBIN allora ϵ ALBEROBIN BOOLEAN = {vero, falso} NODO è un qualsiasi insieme non vuoto ITEM è un qualsiasi insieme non vuoto disgiunto da NODO 15  Gli Alberi Binari SPECIFICA SEMANTICA OPERATORI: newBtree ( ) = T pre: post: T = ᴧ emptyBtree (T) = v pre: post: se T è vuoto, allora v = vero, altrimenti v = falso getRoot (T) = N’ pre: T = non è l’albero vuoto post: N = N’ figlioSX (T) = T’ pre: T = non è l’albero vuoto post: T’ = Tsx 16  Gli Alberi Binari SPECIFICA SEMANTICA OPERATORI: figlioDX (T) = T’ pre: T = non è l’albero vuoto post: T’ = Tdx consBtree (elem, T1, T2) = T’ pre: elem ≠ NULLITEM post: T’ = N è un nodo con etichetta elem 17  Alberi binari: realizzazione Realizzazione più diffusa: struttura a puntatori con nodi doppiamente concatenati Ogni nodo è una struttura con 3 componenti: – Puntatore alla radice del sottoalbero sinistro – Puntatore alla radice del sottoalbero destro – Etichetta (useremo il tipo generico ITEM per questo campo) Un albero binario è definito come puntatore ad un nodo: – Se l’albero binario è vuoto, puntatore nullo – Se l’albero binario non è vuoto, puntatore al nodo radice … e adesso un po’ di codice C  Dichiarazione del tipo nodo Per usare una lista concatenata serve una struttura che rappresenti i nodi La struttura conterrà i dati necessari (un intero nel seguente esempio) ed un puntatore al prossimo elemento della lista: struct node { item value; struct node *left; struct node *right; };  Dichiarazione del tipo Btree Il passo successivo è quello di dichiarare il tipo Btree typedef struct node *Btree; una variabile di tipo Btree punterà al nodo radice dell’albero Assegnare a T il valore NULL indica che l’albero è inizialmente vuoto Btree T = NULL;  Costruire un albero binario Un albero binario viene costruito in maniera bottom- up Man mano che costruiamo l’albero, creiamo dei nuovi nodi da aggiungere come nodo radice I passi per creare un nodo sono: 1. Allocare la memoria necessaria 2. Memorizzare i dati nel nodo 3. Collegare il sottoalbero sinistro e il sottoalbero destro, già costruiti in precedenza  Realizzare il modulo Btree: header file Btree.h // file Btree.h typedef struct node *Btree; L’ADT Btree è // prototipi indipendente dal tipo Btree newBtree(void); degli elementi contenuti. int emptyBtree(Btree T); Utilizziamo un tipo generico item definite in Btree figlioSX(Btree T); un file item.h Btree figlioDX(Btree T); Btree consBtree(item val, Btree sx, Btree dx); node *getRoot (Btree T);  Realizzazione di Btree: file Btree.c #include Btree newBtree(void) #include { #include “item.h” return NULL; #include “Btree.h” } int emptyBtree(Btree T) struct node { { item value; return T == NULL; struct node *left; } struct node *right; }; node *getRoot(Btree T) { item getItem(node *N); return T; void setItem(node *N, item el); } item getItem(node *N) Btree consBtree(item val, Btree sx, Btree dx) { { if (N == NULL) return NULLITEM; struct node *nuovo; return N->value; nuovo = malloc (sizeof(struct node)); } if (nuovo != NULL) { setItem(nuovo, val); void setItem(node *N, item el) nuovo->left = sx; { nuovo->right = dx; if (N==NULL) return; } N->value = el; // correttezza di = return nuovo; } // dipende dal tipo item } Realizzazione di Btree: file Btree.c Btree figlioSX(Btree T) Btree figlioDX(Btree T) { { if (T != NULL) if (T != NULL) return T->left; return T->right; else else return NULL; return NULL; } }  Alcune note sull’ADT Btree L’insieme degli operatori così definiti costituisce l’insieme degli operatori di base (il minimo insieme di operatori) di un albero binario Ogni altro operatore che si volesse aggiungere all’ADT albero binario potrebbe essere implementato utilizzando gli operatori dell’insieme di base E’ frequente la pratica di arricchire il tipo Btree con l’aggiunta di operatori per inserire o cancellare nodi in determinate posizioni dell’albero  Algoritmi di Visita La visita di un albero non vuoto consiste nel seguire una rotta di viaggio che consenta di esaminare ogni nodo dell’albero esattamente una volta. – Visita in pre-ordine: richiede dapprima l’analisi della radice dell’albero e, poi, la visita, effettuata con lo stesso metodo, dei due sottoalberi, prima il sinistro, poi il destro – Visita in post-ordine: richiede dapprima la visita, effettuata con lo stesso metodo, dei sottoalberi, prima il sinistro e poi il destro, e, in seguito, l’analisi della radice dell’albero – Visita simmetrica: richiede prima la visita del sottoalbero sinistro (effettuata sempre con lo stesso metodo), poi l’analisi della radice, e poi la visita del sottoalbero destro 27 Algoritmi di Visita 28  Algoritmi di Visita visita in preordine l’albero binario t { se l’albero non è vuoto allora visita la radice di t visita in preordine il sottoalbero sinistro di t visita in preordine il sottoalbero destro di t fine } 29  Algoritmi di Visita void inorder (Btree T) { if (emptyBtree(T)) return; inorder(figlioSX(T)); output_item(getItem(getRoot(T))); inorder(figlioDX(T)); } 30  Esercizi Realizzare una funzione inputBtree() per costruire ricorsivamente un albero binario Realizzare delle funzioni per determinare l’altezza e il numero di nodi di un albero binario Realizzare le tre visite dell’albero binario in maniera iterativa, con l’uso di uno stack, e in maniera ricorsiva  Realizzare una funzione inputBtree() per costruire ricorsivamente un albero binario l’albero è vuoto? // caso di base ritorna newBtree() inserisci la radice el T1 = inputBtree() // costruisci sottoalbero SX T2 = inputBtree() // costruisci sottoalbero DX // ricorsivamente ritorna consBtree(el, T1, T2) Realizzare una funzione inputBtree() per costruire ricorsivamente un albero binario Btree inputBtree(void) { Btree T1, T2; int ris; item el; printf("\nL'albero è vuoto? (1/0): "); scanf("%d", &ris); if (ris) return newBtree(); printf("\nInserisci la radice: "); input_item(&el); printf ("costruisco il sottoalbero SX\n"); T1 = inputBtree(); printf ("costruisco il sottoalbero DX\n"); T2 = inputBtree(); return consBtree(el, T1, T2); } Liste  Il tipo astratto Lista Una lista è una sequenza di elementi di un determinato tipo, in cui è possibile aggiungere o togliere elementi. Una sequenza vuota è detta lista vuota. A differenza dell’array, che è una struttura a dimensione fissa dove è possibile accedere direttamente ad ogni elemento specificandone l’indice, la lista è a dimensione variabile e si può accedere direttamente solo al primo elemento della lista. Per accedere ad un generico elemento, occorre scandire sequenzialmente gli elementi della lista.  ADT Lista: Specifica sintattica Tipo di riferimento: list Tipi usati: item, boolean Usiamo un tipo Operatori generico item in – newList() → list quanto l’ADT Lista è – emptyList(list) → boolean indipendente dal tipo – consList(item, list) → list degli elementi – tailList(list) → list – getFirst(list) → item contenuti nella lista  ADT Lista: Specifica semantica Tipo di riferimento list – list è l’insieme delle sequenze L=a1,a2,…,an di tipo item – L’insieme list contiene inoltre un elemento nil che rappresenta la lista vuota (priva di elementi)  ADT Lista: Specifica semantica Operatori – newList() → l Post: l = nil – emptyList(l) → b Post: se l=nil allora b = true altrimenti b = false – consList(e, l) → l’ Post: l = AND l’ = – tailList(l) → l’ Pre: l = n>0 Post: l’ = – getFirst(l) → e Pre: l = n>0 Post: e = a1  Il tipo astratto Lista … e adesso una possibile implementazione le liste concatenate  Le Liste Concatenate Ogni elemento di una lista concatenata è un nodo con un riferimento che serve da collegamento per il nodo successivo. Si accede alla struttura attraverso il riferimento al primo nodo. Il riferimenti dell’ultimo nodo contiene un valore nullo  Liste concatenate Una lista concatenata è più flessibile di un array; è più facile inserire o cancellare un elemento, utilizzando solo la memoria strettamente necessaria C’è uno svantaggio rispetto agli array: si perde la capacità di accedere in modo diretto agli elementi della lista, usando l’indice dell’array: – Ogni elemento di un array è accessibile direttamente usando il suo indice (tempo costante) – Per accedere all’i-esimo elemento di una lista occorre scorrere la lista dal primo all’i-esimo elemento (tempo proporzionale ad i) 8  Inserire un elemento in una lista concatenata Il modo più semplice per inserire un nuovo elemento in una lista concatenata L è inserire l’elemento in un nuovo nodo da aggiungere in testa alla lista 1. per prima cosa si crea il nuovo nodo, poi si aggiunge il collegamento con il record iniziale della lista N L  Inserire un elemento in una lista concatenata Il modo più semplice per inserire un nuovo elemento in una lista concatenata L è inserire l’elemento in un nuovo nodo da aggiungere in testa alla lista 1. per prima cosa si crea il nuovo nodo, poi si aggiunge il collegamento con il record iniziale della lista N L  Inserire un elemento in una lista concatenata Il modo più semplice per inserire un nuovo elemento in una lista concatenata L è inserire l’elemento in un nuovo nodo da aggiungere in testa alla lista 1. per prima cosa si crea il nuovo nodo, poi si aggiunge il collegamento con il nodo iniziale della lista N L 2. Poi si aggiorna L facendolo puntare al nodo appena aggiunto … e adesso un po’ di codice C Dichiarazione del tipo di un nodo Per usare una lista concatenata serve una struttura che rappresenti i nodi La struttura conterrà i dati necessari (un intero nel seguente esempio) ed un puntatore al prossimo elemento della lista: struct node { item value; struct node *next; };  Struttura auto-referenziata struct node { item value; struct node *next; }; node definisce una struttura che contiene un campo che punta ad un altra struttura di tipo node  Dichiarazione del tipo lista Il passo successivo è quello di dichiarare il tipo lista typedef struct node *list; una variabile di tipo lista punterà al primo nodo della lista: list L = NULL; // in questo caso, L rappresenta la lista vuota Assegnare a l il valore NULL indica che la lista è inizialmente vuota  Creare un nodo della lista Man mano che costruiamo la lista, creiamo dei nuovi nodi da aggiungere alla lista I passi per creare un nodo sono: 1. Allocare la memoria necessaria 2. Memorizzare i dati nel nodo 3. Inserire il nodo nella lista Vediamo i primi due passi per adesso  Creare un nodo della lista Per creare un nodo ci serve un puntatore temporaneo che punti al nodo: struct node *new_node; Possiamo usare malloc per allocare la memoria necessaria e salvare l’indirizzo in new_node: new_node = malloc(sizeof(struct node)); new_node adesso punta ad un blocco di memoria che contiene la struttura di tipo node:  Implementare il tipo astratto Lista: header file list.h // file list.h typedef struct node *list; L’ADT lista è indipendente dal // prototipi tipo degli elementi contenuti. list newList(void); Definiamo quindi un tipo int emptyList(list l); generico item in un file item.h list tailList(list l); list consList(item val, list l); item getFirst (list l);  I file item.h e item.c // file item.c // file item.h #define NULLITEM 0 #include #include “item.h” scanf(“%d”, x); } int eq(item x, item y); void input_item(item *x); void output_item(item x) { void output_item(item x); printf(“%d”, x); }  Implementare il tipo astratto Lista: file list.c int emptyList(list l) #include { #include return l == NULL; #include “item.h” } #include “list.h” list consList(item val, list l) struct node { { item value; struct node *nuovo; struct node *next; nuovo = malloc (sizeof(struct node)); }; if (nuovo != NULL) { nuovo->value = val; nuovo->next = l; l = nuovo; list newList(void) } { return l; return NULL; } } Implementare il tipo astratto Lista: file list.c Osservazione: per modificare una lista L con l’aggiunta di un nuovo elemento val, l’operatore consList() va usato nel modo seguente: list L; …………… …………… L = consList(val, list L);  file list.c list tailList(list l) { item getFirst (list l) list temp; { if (l != NULL) item e; temp = l->next; if(l != NULL) else e = l->value; temp = NULL; else return temp; e = NULLITEM; } return e; } // uso tipico dell’operatore: // L = tailList(L);  Alcune note sull’ADT lista L’insieme degli operatori così definiti costituisce l’insieme degli operatori di base (il minimo insieme di operatori) di una lista Ogni altro operatore che si volesse aggiungere all’ADT lista potrebbe essere implementato utilizzando gli operatori dell’insieme di base Alcuni esempi – calcolo della lunghezza di una lista – ricerca di un elemento in una lista – inserimento/cancellazione in una posizione intermedia – …  Aggiungiamo operatori alla lista Specifica sintattica – sizeList(list) → integer – posItem(list, item) → integer – searchItem(list, item) → boolean – reverseList(list) → list – removeItem(list, item) → list – getItem(list, integer) → item – insertList(list, integer, item) → list – removeList(list, integer) → list –… 24  Aggiungiamo operatori alla lista Specifica semantica – sizeList(l) → n Post: l = AND n ≥ 0 – searchItem(l, e) → b Post: se e è contenuto in l allora b = true, se no b = false – posItem(l, e) → p Post: se e è contenuto in l allora p è la posizione della prima occorrenza di e in l, altrimenti p = -1 – reverseList(l) → l’ Post: l = AND l’ = – removeItem(l, e) → l’ Post: se e è contenuto il l, allora l’ si ottiene da l eliminando la prima occorrenza di e in l, altrimenti l’ = l  Aggiungiamo operatori alla lista Specifica semantica – getItem(l, pos) → e Pre: pos >= 0 AND sizeList(l) > pos // assumiamo 0 come prima posizione Post: e è l’elemento che occupa in l la posizione pos – insertList(l, p, e) → l’ Pre: pos >=0 AND sizeList(l) ≥ p // assumiamo 0 come prima posizione Post: l’ si ottiene da l inserendo e in posizione p – removeList(l, p) → l’ Pre: pos >=0 AND sizeList(l) > p Post: l’ si ottiene da l eliminando l’elemento in posizione p NB: getItem(I, 0) = getFirst(l) insert(l, 0, val) = consList(val, l) remove(l, 0) = tailList(l) Vediamo alcune implementazioni Implementiamo alcuni dei nuovi operatori mediante l’uso degli operatori di base … Implementare i rimanenti come esercizio … Implementiamo anche due funzioni inputList e outputList utili per realizzare programmi con le liste …  Implementazione di sizeList Realizziamo la funzione sizeList(l) che restituisce il numero di elementi di una lista l L’algoritmo richiede una visita totale della lista: il ciclo si arresta quando la lista l termina Ad ogni iterazione aggiungiamo 1 ad un contatore n a cui inizialmente assegnamo il valore 0 In generale, per visitare una lista usiamo le operazioni getFirst(l) per accedere al primo elemento e tailList(l) per accedere alla parte restante della lista Schema di visita totale: while(!emptyList(l)) { operazioni specifiche sul primo elemento l = tailList(l); // continuiamo la visita }  Implementazione di sizeList int sizeList (list l) { int n=0; while (!emptyList(l)) // finché non raggiungiamo la fine della lista { n++; // il primo elemento contribuisce al conteggio l = tailList(l); // continuiamo la visita degli elementi successivi } return n; } Esempio di chiamata: int size = sizeList (L1); // la lista L1 non viene modificata  Implementazione di posItem Realizziamo la funzione posItem (l, val) che, dati una lista l e un elemento val, restituisce la posizione della lista in cui appare la prima occorrenza dell’elemento, oppure -1 se l’elemento non è presente Richiede una visita finalizzata della lista: usciamo da ciclo quando troviamo l’elemento cercato oppure quando raggiungiamo la fine della lista (usiamo una variabile booleana found che viene settata a 1 (true) quando troviamo l’elemento) Schema di visita finalizzata: found = 0; // all’inizio l’elemento non è stato trovato while (! emptyList(l) && ! found) { if(getFirst(l) è l’elemento cercato) found = 1; else { operazioni specifiche sul primo elemento l = tailList(l); // continuiamo la visita } }  Implementazione di posItem int posItem (list l, item val) { int pos =0; // contatore di posizione int found =0; while (!emptyList(l) && !found) { if (eq(getFirst(l), val)) found =1; else { pos++; // incrementa il contatore di posizione l = tailList(l); // continuiamo la visita degli elementi della lista } } if(!found) pos = -1; // se non trovato restituiamo come posizione -1 return pos; } Implementazione di posItem (vers. Ricorsiva) int posItem (list l, item val) { if emptyList(l) return -1; if (eq(getFirst(l), val)) return 0; else { int ris = posItem(tailList(l), val); if (ris== -1) return -1; else return 1 + ris; } }  Implementazione di getItem Realizziamo la funzione getItem(l, pos) che, dati una lista l e un intero pos, restituisce l’elemento in l di posizione pos, oppure l’elemento nullo se la lista ha meno di pos+1 elementi item getItem (list l, int pos) { item e; int i =0; if (pos < 0) return NULLITEM; // prima scorriamo la lista fino alla posizione pos … se esiste while (i < pos && !emptyList(l)) { i++; l = tailList(l); } if (!emptyList(l)) // se la lista ha almeno pos+1 elementi e = getFirst(l); // elemento di posizione pos else e = NULLITEM; return e; }  Implementazione di reverseList Realizziamo la funzione reverseList(l) che, dati una lista restituisce una nuova lista che ha gli elementi della lista in ordine inverso (schema di visita totale della lista) lst2 = reverseList(lst1); list reverseList (list l) { lst1 list rev; item val; rev = newList(); el6 el2 el3 el8 while (!emptyList(l)) { val = getFirst(l); lst2 rev = consList(val, rev); l = tailList(l); } return rev; el8 el3 el2 el6 }  Implementazione di outputList Realizziamo la funzione outputList(l) che prende visualizza in output gli elementi di una lista l (visita totale della lista) void outputList (list l) { int i =0; item val; while(!emptyList(l)) { val = getFirst(l); printf(“Elemento di posizione %d: ”, i); output_item(val); printf(“\n”); l = tailList(l); i++; } }  Implementazione di outputList (vers. Ricorsiva) Realizziamo la funzione outputList(l) che prende visualizza in output gli elementi di una lista l (visita totale della lista) void out_List (list l, int i) { item val; void outputList (list l) if (emptyList(l)) return; { val = getFirst(l); out_List(l, 0); printf(“Elemento di posizione %d: ”, i); } output_item(val); printf(“\n”); out_List(tailList(l), i+1); }  Implementazione di inputList Realizziamo la funzione inputList(n) che prende in ingresso un intero n e restituisce una lista di n elementi inseriti da standard input list inputList (int n) { item val; list l = newList(); for(int i = 0; i < n; i++) { printf(“Elemento di posizione %d: ”, i); input_item(&val); l = consList(val, l); } // alla fine del ciclo l contiene gli elementi della lista al contrario return reverseList(l); }  Fine prima lezione sulle liste Prossima lezione: operatori di inserimento/rimozione ADT CODA (QUEUE)  Il tipo di dati astratto Coda (queue) Una coda (spesso chiamata anche queue) è una sequenza di elementi di un determinato tipo, in cui gli elementi si aggiungono da un lato (tail) e si tolgono dall’altro lato (head). tail head Questo significa che la sequenza viene gestita con la modalità detta FIFO (First-in-first-out) cioè il primo elemento inserito nella sequenza sarà il primo ad essere eliminato. La coda è una struttura dati lineare a dimensione variabile in cui si può accedere direttamente solo alla testa (head) della lista. Non è possibile accedere ad un elemento diverso da head, se non dopo aver eliminato tutti gli elementi che lo precedono (cioè quelli inseriti prima).  ADT Queue: Specifica sintattica Tipo di riferimento: queue Tipi usati: item, boolean Operatori – newQueue() → queue – emptyQueue(queue) → boolean – enqueue(item, queue) → queue – dequeue(queue) → item  ADT Queue: Specifica semantica Tipo di riferimento queue – queue è l’insieme delle sequenze S=a1,a2,…,an di tipo item – L’insieme queue contiene inoltre un elemento nil che rappresenta la coda vuota (priva di elementi)  ADT Queue: Specifica semantica Operatori – newQueue() → q Post: q = nil – emptyQueue(q) → b Post: se q=nil allora b = true altrimenti b = false – enqueue(e, q) → q’ Post: se q = nil allora q’ = altrimenti se q = con n > 0 allora q’ = – dequeue(q) → a Pre: q = n>0 (q ≠ nil) Post: a = a1 e l’elemento a1 viene rimosso da q Implementare il tipo astratto Queue Tra le possibili implementazioni, le più usate sono realizzate tramite: Lista concatenata Array  Implementazione della queue con liste collegate A differenza dello stack, per gestire la politica FIFO conviene avere accesso sia al primo elemento (estrazione) sia all’ultimo (inserimento) Il tipo queue è definito come un puntatore ad una struct che contiene Un intero numelem che indica il numero di elementi della coda Un puntatore head ad uno struct nodo Un puntatore tail ad uno struct nodo tail 4 head  Implementazione di Queue: header file queue.h L’ADT queue è realizzato in modo // file queue.h da non dipendere dal tipo degli elementi contenuti. typedef struct c_queue *queue; // prototipi Utilizza il tipo generico item già visto in precedenza queue newQueue(void); int emptyQueue(queue q); dequeue toglie e restituisce l’elemento in testa alla coda item dequeue(queue q); int enqueue(item val, queue q); enqueue restituisce un intero che indica l’esito dell’operazione  file queue.c (versione con lista collegata) #include queue newQueue(void) #include { #include "item.h" struct c_queue *q; #include "queue.h" q = malloc (sizeof(struct c_queue)); if (q == NULL) struct node { return NULL; item value; struct node *next; q->numel = 0; }; q->head = NULL; q->tail = NULL; struct c_queue { return q; struct node *head,*tail; } int numel; }; int emptyQueue(queue q) { head tail if (q==NULL) 3 return -1; return q->numel == 0; 5 3 9 }  Inserire un item in coda Dobbiamo innanzitutto creare un nuovo nodo a cui dovrà puntare il puntatore tail Poi bisogna distinguere il caso in cui la coda di input è vuota e il caso in cui non è vuota Coda vuota: il puntatore head dovrà puntare al nuovo nodo tail tail head 0 1 head 10 Coda non vuota: il puntatore next dell’ultimo nodo dovrà puntare a nuovo tail tail 10 2 3 head head 5 15 5 15 file queue.c (versione con lista collegata) int enqueue(item val, queue q) { if (q==NULL) return -1; struct node *nuovo; nuovo = malloc (sizeof(struct node)); if (nuovo == NULL) return 0; nuovo->value = val; nuovo->next= NULL; if(q->head==NULL) q->head = nuovo; // caso coda vuota else q->tail->next= nuovo; // caso coda non vuota q->tail = nuovo; // tail punta al nuovo nodo (q->numel)++; // incrementare il numero di elementi return 1; }  Rimuovere elemento da coda Bisogna prima salvare il puntatore al nodo da eliminare (quello puntato da head) Head dovrà quindi puntare al successivo A questo punto si può deallocare la memoria del nodo da rimuovere Se la coda aveva un solo elemento, ora è vuota, per cui bisogna porre anche il puntatore tail a NULL file queue.c (versione con lista collegata) item dequeue(queue q) { if (q==NULL) return NULLITEM; if (q->numel == 0) return NULLITEM; // coda vuota item result = q->head->value; // item da restituire struct node *temp = q->head; // nodo da rimuovere q->head = q->head->next; // q->head avanza free(temp); // liberiamo memoria nodo da rimuovere if(q->head==NULL) // se la coda conteneva un solo elemento q->tail=NULL; (q->numel)--; return result; }  ADT QUEUE (CODA) Altre implementazioni  Implementazione semplice di queue con array La coda è implementata come un puntatore ad una struct c_queue che contiene due elementi: Un array di MAXQUEUE elementi Un intero che indica la posizione head della coda Un intero che indica la posizione tail della coda Quando la coda si riempie, non è possibile eseguire l’operazione enqueue … 0 1 2 3 4 5 6 7 8 9 out 4 6 7 24 20 in head = 0 tail = 5  queue rappresentata con array Se l’array viene gestito normalmente, cioè mantenendo head vet == NULL) { free (q); return NULL; } q->size = 0; // dimensione massima di default q->head = 0; q->tail = 0; return q; } int emptyQueue(queue q) { if(q==NULL) return -1; return (q->size == 0); } int enqueue(item val, queue q) file queue.c { if(q==NULL) return -1; if (q->size == MAXQUEUE-1) //coda piena return 0; (q->size)++; q->vet[q->tail]=val; // inserisco in coda q->tail= (q->tail + 1)%MAXQUEUE; return 1; } item dequeue(queue q) { if(q ==NULL || q->size == 0) return NULLITEM; item result = q->vet[q->head]; // item da restituire q->head = (q->head + 1) % MAXQUEUE; // operatore % per gestione circolare return result; }  Considerazioni Abbiamo visto due implementazioni diverse dell’ADT coda. – lista pro: è una implementazione espandibile (unico limite è la capacità della memoria) contro: la struttura è più complessa – vettore circolare pro: gli elementi sono memorizzati in modo contiguo e la struttura è più semplice contro: dimensione fissata, bisogna conoscere a priori il numero massimo di elementi che la coda deve contenere, parte dello spazio è inutilizzato – Note su vettore circolare Potrei usare la realloc per ridimensionare la coda (come fatto per lo stack) e poter quindi sempre inserire elementi ? Sì, ma devo considerare che l’ordine degli elementi della coda nell’array non necessariamente va dalla posizione 0 alla posizione n-1 … Farlo come esercizio … ADT STACK (PILA)  Il tipo di dati astratto Stack (pila) Una pila (spesso chiamata anche stack) è una sequenza di elementi di un determinato tipo, in cui è possibile aggiungere o togliere elementi, uno alla volta, esclusivamente da un unico lato (top dello stack). Questo significa che la sequenza viene gestita con la modalità detta LIFO (Last-in-first-out) cioè l’ultimo elemento inserito nella sequenza sarà il primo ad essere eliminato. La pila è una struttura dati lineare, omogenea, a dimensione variabile in cui si può accedere direttamente solo al primo elemento della lista. Non è possibile accedere ad un elemento diverso dal primo, cioè quello che è stato inserito per ultimo, se non dopo aver eliminato tutti gli elementi che lo precedono (cioè che sono stati inseriti dopo). Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete Un esempio di stack: una pila di monete  ADT Stack: Specifica sintattica Tipo di riferimento: stack Tipi usati: item, boolean Operatori – newStack() → stack – emptyStack(stack) → boolean – push(item, stack) → stack – pop(stack) → stack – top(stack) → item  ADT Stack: Specifica semantica Tipo di riferimento stack – stack è l’insieme delle sequenze S=a1,a2,…,an di tipo item – L’insieme stack contiene inoltre un elemento nil che rappresenta la pila vuota (priva di elementi)  ADT Stack: Specifica semantica Operatori – newStack() → s Post: s = nil – emptyStack(s) → b Post: se s=nil allora b = true altrimenti b = false – push(e, s) → s’ Post: s = AND s’ = – pop(s) → s’ Pre: s = n>0 Post: s’ = – top(s) → e Pre: s = n>0 Post: e = a1 Implementare il tipo astratto Stack Tra le possibili implementazioni, le più usate sono realizzate tramite: Array Lista concatenata  Implementazione semplice di stack con array Lo stack è implementato come un puntatore ad una struct c_stack che contiene due elementi: Un array di MAXSTACK elementi Un intero top che indica la posizione successiva a quella dell’elemento in cima allo stack, e quindi anche il numero di elementi presenti Quando lo stack si riempie, non è più possibile eseguire l’operazione push … Implementazione di Stack con array: header file stack.h // file stack.h typedef struct c_stack *stack; L’ADT stack è realizzato in modo // prototipi da non dipendere dal tipo degli elementi contenuti. stack newStack(void); int emptyStack(stack s); Utilizza il tipo generico item già visto in precedenza int pop(stack s); int push(item val, stack s); pop e push restituiscono un intero che indica l’esito item top (stack s); dell’operazione  file stack.c (versione con uso di array) #include #include #include "item.h" #include "stack.h" int emptyStack(stack s) #define MAXSTACK 50 { return s->top == 0; struct c_stack { } item vet[MAXSTACK]; int top; }; int push(item val, stack s) { stack newStack(void) if (s->top == MAXSTACK) { return 0; stack s; s->vet[s->top] = val; s = malloc (sizeof(struct c_stack)); (s->top)++; if (s == NULL) return NULL; return 1; s->top = 0; } return s; } file stack.c (versione con uso di array) item top(stack s) int pop(stack s) { { item e; if (s->top == 0) if(s->top > 0) return 0; e = s->vet[s->top-1]; (s->top)--; else return 1; e = NULLITEM; } return e; }  Esercizio sull’uso di stack: Espressioni aritmetiche con parentesi bilanciate Verificare se una data espressione aritmetica è ben bilanciata rispetto a tre tipi di parentesi: ( ) , [ ] , { } (4 + a) * {[1 – (2/x)] * (8 – a)} è ben bilanciata [x – (4y + 3] * (1 – x)) non è ben bilanciata N.B.: per semplicità supponiamo che non esista un ordine di priorità fra i tre tipi di parentesi (a + {b -1}) / [b + 2] è ammessa come valida  Parentesi bilanciate: analisi del problema (1 di 2) Vogliamo solo verificare se una data espressione aritmetica è ben bilanciata rispetto alle parentesi, non ci interessa sapere se gli operatori in essa contenuti sono corretti e se hanno il giusto numero di operandi Possiamo estrarre dall’espressione solo le parentesi, cancellando tutto il resto se l’espressione (4 + a) * {[1 – (2/x)] * (8 – a)} è ben bilanciata, lo valutiamo dalla sua versione semplificata: (){[()]()}  Parentesi bilanciate: analisi del problema (2 di 2) Dati in ingresso: una stringa exp Dati in uscita: un valore booleano ris Precondizione: Postcondizione: se la stringa exp è vuota, allora ris = true se la stringa exp non è vuota, allora ris=true se le parentesi in essa presenti sono bilanciate, ris=false se non lo sono  Parentesi bilanciate: progettazione Step 1: prendere in input una stringa exp Step 2: se exp è vuota, dare in output true Step 3: sia S uno stack di caratteri inizialmente vuoto Step 4: per ogni carattere car della stringa se car == ‘(‘ or car==‘[‘ or car==‘{‘ inserisci car in S se car == ‘)‘ or car==‘]‘ or car==‘}‘ se S è vuoto dare in output false estrarre un elemento da S e metterlo in t se car non corrisponde a t dare in output false Step 5: se S è vuoto dare in output true altrimenti dare in output false  Parentesi bilanciate: codifica int main (void) { // file: parentesi.c int ris; char expr[MAX_S_size]; #include #include printf ("Inserire una espressione "); printf ("senza spazi\n"); #include "item.h" scanf ("%s", expr); #include "stack.h" ris = verifica (expr); #define MAX_S_size 81 if (ris) int verifica (char *expr); printf ("parentesi bilanciate"); int corrisp(char a, char b); else printf ("parentesi sbilanciate");  Parentesi bilanciate: codifica int verifica (char *expr) { stack S = newStack(); int c, i = 0; if (emptyStack(S)) item top_el; return 1; else if (!expr) return 1; return 0; } while (expr[i] != '\0’) { c = expr[i]; int corrisp(char a, char b) if (c=='(' || c=='[' || c=='{') { push (chtoitem(c), S); if (a=='(' && b==')') if (c==')' || c==']' || c=='}') return 1; { if (a=='{' && b=='}') if (emptyStack(S)) return 1; return 0; if (a=='[' && b==']') top_el = top(S); return 1; pop(S); return 0; if (!corrisp(itemtoch(top_el), c)) } return 0; } i++; }  ADT STACK (PILA) Altre implementazioni  Esercizio: Implementare lo stack senza dimensione max Come facciamo ad evitare che lo stack abbia una capienza massima ? Bisogna usare l’allocazione dinamica della memoria e due costanti La prima STARTSIZE definisce la dimensione iniziale dello stack La seconda ADDSIZE definisce di quanto allargare lo stack nel caso in cui si riempia Questo significa che ci occorre anche una variabile size che ci dica quanti elementi può contenere lo stack in ogni momento #include #include file stack.c (versione #include “item.h” #include “stack.h” senza dimensione max) #define STARTSIZE 50 // dimensione iniziale stack #define ADDSIZE 20 // dimensione da aggiungere se pieno struct c_stack { item *vet; int size; // serve a mantenere la dimensione corrente int top; }; stack newStack(void) { stack s = malloc (sizeof(struct c_stack)); if (s == NULL) return NULL; s->vet = malloc(STARTSIZE * sizeof(item)); if (s->vet == NULL) return NULL s->size = STARTSIZE; s->top = 0; return s; } file stack.c (versione senza dimensione max) int emptyStack(stack s) { return s->top == 0; } int push(item val, stack s) { if (s->top == s->size) { // necessario il resizing dello stack item *tmp = realloc(s->vet, (s->size + ADDSIZE) * sizeof(item)); if (tmp == NULL) return 0; s->vet = tmp; s->size += ADDSIZE; } s->vet[s->top] = val; (s->top)++; return 1; } file stack.c (versione senza dimensione max) int pop(stack s) { if (s->top == 0) return 0; (s->top)--; return 1; } item top(stack s) { item e; if(s->top > 0) e = s->vet[s->top]; else e = NULLITEM; return e; }  Implementazione dello stack con liste collegate Il tipo stack è definito come un puntatore ad una struct che contiene Un intero numelem che indica il numero di elementi dello stack Un puntatore top ad una struct nodo (come per la lista)  file stack.c (versione con lista collegata) stack newStack(void) #include { #include stack s; #include “item.h” s = malloc (sizeof(struct c_stack)); #include "stack.h" if (s == NULL) return NULL; struct node { s->numel = 0; item value; s->top = NULL; struct node *next; return s; }; } struct c_stack { int emptyStack(stack s) struct node *top; { int numel; return s->numel == 0; }; } file stack.c (versione con lista collegata) int push(item val, stack s) { struct node *nuovo; nuovo = malloc (sizeof(struct node)); if (nuovo == NULL) return 0; nuovo->value = val; nuovo->next = s->top; s->top = nuovo; (s->numel)++; return 1; } file stack.c (versione con lista collegata) int pop (stack s) { item top (stack s) if (s->numel == 0) { return 0; item e; struct node *temp; if(s->numel > 0) temp = s->top; e = s->top->value; s->top = s->top->next; else free(temp); e = NULLITEM; (s->numel)--; return e; return 1; } }  Implementazione dello stack basata sull’uso del modulo lista Il tipo stack è definito come un puntatore ad una struct che contiene Un elemento top di tipo list Non serve più nemmeno l’intero numelem che indica il numero di elementi dello stack … Anche se abbiamo un solo elemento nella struct, continuiamo a definire il tipo stack come puntatore a struct c_stack per non cambiare la definizione nell’header file... file stack.c (versione con uso di modulo lista) #include #include int emptyStack(stack s) { #include “item.h” return emptyList(s->top); #include "stack.h” } #include “list.h” int push(item val, stack s) struct c_stack { { list top; return insertList(s->top, 0, val); }; } stack newStack(void) int pop (stack s) { { stack s; return removeList(s->top, 0); s = malloc (sizeof(struct c_stack)); } if (s == NULL) return NULL; item top (stack s) { s->top = newList(); return getFirst(s->top); return s; } }  E se volessimo realizzare una sola istanza di stack? In questo caso non abbiamo bisogno di definire ed esportare un tipo La struttura dati dello stack la manteniamo in variabili globali accessibili solo all’interno del modulo (dichiarazioni static) Gli operatori della lista non usano parametri di tipo stack, ma operano sulle variabili globali Quello che stiamo realizzando è un singolo oggetto stack Vediamo come si fa … implementiamo uno stack basato su array senza dimensione massima...  Implementazione di singola istanza di Stack con array // file stack.h Adesso non c’è la definizione del tipo stack nell’header file // prototipi Gli operatori non hanno int newStack(void); parametri di tipo stack int emptyStack(void); int pop(void); Gli operatori newStack, pop e int push(item val); push restituiscono un intero che indica il buon esito item top (void); dell’operazione #include #include file stack.c (versione #include “item.h” #include “stack.h” senza dimensione max) #define STARTSIZE 50 // dimensione iniziale stack #define ADDSIZE 20 // dimensione da aggiungere se pieno static struct c_stack { item *vet; int size; // serve a mantenere la dimensione corrente int top; } *s; // variabile statica usata dagli operatori int newStack(void) { s = malloc (sizeof(struct c_stack)); if (s == NULL) return 0; s->vet = malloc(STARTSIZE * sizeof(item)); if (s->vet == NULL) return 0; s->size = STARTSIZE; s->top = 0; return 1; } file stack.c (versione senza dimensione max) int emptyStack(void) { return s->top == 0; } int push(item val) { if (s->top == s->size) { // necessario il resizing dello stack item *tmp = realloc(s->vet, (s->size + ADDSIZE) * sizeof(item)); if (tmp == NULL) return 0; s->vet = tmp; s->size = s->size + ADDSIZE; } s->vet[top] = val; (s->top)++; return 1; } file stack.c (versione senza dimensione max) int pop(void) { NB: il corpo dei metodi non è if (s->top == 0) return 0; cambiato in maniera (s->top)--; sostanziale, solo che stavolta return 1; la variabile s non è un } parametro di tipo stack degli item top(void) operatori, ma una variabile { globale static item e; if(s->top > 0) e = s->vet[(s->top) - 1]; else e = NULLITEM; return e; }  Moduli e Astrazioni sui dati: Tipi di dati astratti e oggetti Tipo di dato astratto – Il modulo incapsula la definizione del tipo e gli operatori ed esporta il nome del tipo e la signature degli operatori – Il tipo di riferimento compare tra i parametri degli operatori – È consentito definire variabili di tale tipo (istanziazione) e utilizzarle (referenziazione) come parametri degli operatori Oggetto (astratto) – Il modulo incapsula una struttura dati (istanza) e gli operatori ed esporta la signature degli operatori – Non è consentito referenziare la struttura dati fuori dal modulo – L’uso e la manipolazione dell’oggetto consentiti unicamente attraverso i suoi operatori – Un oggetto ha uno stato che può cambiare in seguito all’applicazione di determinate operazioni Moduli e astrazioni sui dati: genericità Modulo generico: un template dal quale è possibile istanziare più moduli Tipicamente: parametrico rispetto a un tipo base o al numero di componenti di tipo base (parametri di struttura) – Esempio: l’ADT (o oggetto) stack generico Un modulo cliente dovrebbe prima istanziare il modulo specificando i parametri di struttura e poi … In C non abbiamo costrutti per fare questo …. – Invece dobbiamo definire un tipo generico item e delle costanti, che possiamo cambiare all’occorrenza 45  Esercizio su Libretto Universitario  Problema Si implementi, mediante l’uso di opportune strutture dati, un programma per la gestione dei libretti universitari degli studenti. Specificare e implementare l’ADT libretto: ogni libretto tiene traccia dei dati dello studente (cognome, nome, matricola) e degli esami sostenuti. Questi ultimi sono caratterizzati da nome, voto e data dell’esame. L’ADT libretto dovrà consentire di aggiungere esami al libretto e di ricercare un esame in base al nome. Realizzare il programma di test  Libretto: Specifica sintattica Tipo di riferimento: libretto Tipi usati: lista, item, int, string Operatori – newLibretto(int, string, string) → libretto – addEsame(libretto, item) → libretto – dammiEsami(libretto) → lista – cercaEsame(libretto, string) → item  libretto: Specifica semantica Tipo di riferimento libretto – Libretto è l’insieme delle quadruple L = (mat, cogn, nom, lis) in cui: mat è un numero intero cogn è una stringa nom è una stringa lis è una lista  libretto: Specifica semantica Operatori – newLibretto(mat, cogn, nom) → lib Post: lib = (mat, cogn, nom, nil) – addEsame(lib, es) → lib’ Post: se lib= (mat, cogn, nom, lis) e lis = allora lib’ = (mat, cogn, nom, lis’) con lis’= – dammiEsame(lib) → l Post: se lib= (mat, cogn, nom, lis) allora l= lis – cercaEsame(lib, nom_es) → a Post: se lib= (mat, cogn, nom, lis) se lis contiene un item a’ il cui nome è nom_es allora a = a’ altrimenti a = NULLITEM Abstract Data Types (ADT) Tipi di dati astratti  Astrazione Dati e Funzionale L’astrazione dati ricalca ed estende il concetto di astrazione funzionale. Così come l'astrazione funzionale permette di ampliare l'insieme dei modi di operare sui dati, cioè gli operatori sui tipi di dati già disponibili, l’astrazione di dati permette di ampliare i tipi di dati disponibili attraverso l'introduzione sia di nuovi tipi di dati che di nuovi operatori. L’astrazione funzionale stimola gli sforzi per evidenziare operazioni ricorrenti o ben caratterizzate all’interno della soluzione di un problema. L’astrazione di dati sollecita ad individuare le organizzazioni dei dati più adatte alla soluzione del problema.  Astrazione dati : Specifica e Realizzazione Specifica: descrivere un nuovo tipo di dati e gli operatori applicabili – La specifica descrive l’astrazione dati e il modo in cui può essere utilizzata attraverso i suoi operatori – Specifica sintattica e semantica … Realizzazione: come il nuovo dato e i nuovi operatori vengono ricondotti ai dati e agli operatori già disponibili – Utilizzo di meccanismi di programmazione modulare offerti dal linguaggio di programmazione utilizzato per mettere a disposizione l’astrazione attraverso un’interfaccia e nascondere i dettagli dell’implementazione 3  Specifica sintattica e semantica Specifica sintattica – i nomi del tipo di dati di riferimento e degli eventuali tipi di dati usati (già definiti) – i nomi delle operazioni del tipo di dati di riferimento – i tipi di dati di input e di output per ogni operatore 4  Specifica sintattica e semantica Specifica semantica – L’insieme dei valori associati al tipo di dati di riferimento – La funzione associata ad ogni nome di operatore, specificata dalle seguenti condizioni: i) precondizione: definita sui valori dei dati di input definisce quando l’operatore è applicabile ii) postcondizione: definita sui valori dei dati di output e di input, stabilisce la relazione tra argomenti e risultato 5  Esempio: il tipo di dato astratto libro Specifica dei tipi di dati Specifica sintattica – Tipo di riferimento: libro – Tipi usati: stringa, intero Specifica semantica – Il tipo libro è l’insieme delle quadruple (autore, titolo, editore, anno) dove autore, titolo e editore sono stringhe e anno è un intero 6  Esempio: il tipo di dato astratto libro Specifica degli operatori Specifica sintattica – creaLibro(stringa, stringa, stringa, intero)  libro – autore (libro)  stringa – titolo (libro)  stringa – editore (libro)  stringa – anno (libro)  intero 7  Esempio: il tipo di dato astratto libro Specifica degli operatori Specifica semantica Nel nostro esempio non ci sono precondizioni (o – creaLibro(aut, tit, ed, an) = lb meglio la precondizione Post: lb = (aut, tit, ed, an) è sempre verificata) – autore(lb) = aut Post: lb = (aut, tit, ed, an) NB: precondizioni e – titolo(lb) = tit postcondizioni sono espressioni logiche … Post: lb = (aut, tit, ed, an) L’operatore “=“ che – editore(lb) = ed compare in queste Post: lb = (aut, tit, ed, an) condizioni NON è un – anno(lb) = an assegnamento ! 8 Post: lb = (aut, tit, ed, an)  Esempio: il tipo di dato astratto libro Una possibile implementazione: file libro.h typedef struct lib { char autore; char titolo; char editore; int anno; } libro; libro creaLibro (char *aut, char *tit, char *ed, int anno); char *autore (libro l); char *titolo (libro l); char *editore (libro l); int anno (libro l); 9  Esempio: il tipo di dato astratto libro Una possibile implementazione: file libro.c #include “libro.h” libro creaLibro (char *aut, char *tit, char *ed, int anno) { libro l; strcpy(l.autore, aut); strcpy(l.titolo, tit); strcpy(l.editore, ed); l.anno = anno; return l; } 10  Esempio: il tipo di dato astratto libro char *autore (libro L) { file libro.c char *aut; aut = calloc (26, sizeof(char)); strcpy(aut, L.autore); return aut; } char *titolo (libro L) { char *tit; tit = calloc (53, sizeof(char)); strcpy(tit, L.titolo); return tit; } 11  Esempio: il tipo di dato astratto libro char *editore (libro L) { file libro.c char *ed; ed = calloc (26, sizeof(char)); strcpy(ed, L.editore); return ed; } int anno (libro L) { return L.anno; } 12  Esempio: il tipo di dato astratto punto Specifica dei tipi di dati Specifica sintattica – Tipo di riferimento: punto – Tipi usati: reale Specifica semantica – Il tipo punto è l’insieme delle coppie (ascissa, ordinata) dove ascissa e ordinata sono numeri reali 13  Esempio: il tipo di dato astratto punto Specifica degli operatori Specifica sintattica – creaPunto (reale, reale)  punto – ascissa (punto)  reale – ordinata (punto)  reale – distanza (punto, punto)  reale 14  Esempio: il tipo di dato astratto punto Specifica degli operatori Specifica semantica NB: precondizioni e – creaPunto(x, y) = p postcondizioni sono pre: true espressioni logiche … post: p = (x, y) – ascissa(p) = x L’operatore “=“ che pre: true compare in queste condizioni NON è un post: p = (x, y) assegnamento ! –… 15  Esempio: il tipo di dato astratto punto Specifica degli operatori Specifica semantica – ordinata(p) = y pre: true post: p = (x, y) – distanza(p1, p2) = d pre: true post: d = sqrt( (ascissa(p1)-ascissa(p2))2 + (ordinata(p1)-ordinata(p2))2 ) 16 Esempio: il tipo di dato astratto punto Una possibile implementazione: il file punto.h typedef struct { float x; float y; } punto; punto creaPunto (float x, float y); float ascissa (punto p); float ordinata (punto p); float distanza (punto p1, punto p2); 17  Esempio: il tipo di dato astratto punto Una possibile implementazione: il file punto.c #include float ordinata(punto p) { #include “punto.h” return p.y; } punto creaPunto(float x, float y) { punto p; float distanza(punto p1, punto p2) { p.x = x; float dx = p1.x – p2.x; p.y = y; float dy = p1.y – p2.y; return p; float d = sqrt(dx*dx + } dy*dy); return d; float ascissa(punto p) { } return p.x; } 18  Usiamo l’ADT punto Realizzare un programma che prende in ingresso una sequenza di punti e un numero reale d e restituisce il numero di m coppie di punti che hanno distanza minore di d 19  Specifica del programma Specifica – Dati di ingresso una sequenza sp di punti un numero reale d – Dati di uscita un intero m – Precondizione sp non vuota – Postcondizione m è il numero di coppie di punti p1 e p2 in sp tali che distanza(p1, p2) < d 20 Progettazione (versione senza file) 1. Input numero di punti n 2. Crea array a di punti di dimensione n 3. Input n punti e carica in array a 4. Input distanza d 5. Calcola il numero m di coppie in a con distanza minore di d 6. Output m I passi 1, 2 4 e 6 sono direttamente implementabili con istruzioni del linguaggio Realizziamo i sottoprogrammi per i passi 3 e 5 21 Fare analisi e progettazione come esercizio... #include #include #include “punto.h” Il main void input_punti(punto a[], int n); int coppie_vicine(punto a[], int n, float d); file: vicini.c int main() { float d; int n, m; punto *a; // array di punti printf(“Numero punti da caricare :”); scanf(“%d”, &n); // passo 1 a = malloc(n*sizeof(punto)) ; // passo 2 input_punti(a, n); // passo 3 printf(“Inserisci distanza: ”); scanf(“%f”, &d); // passo 4 m = coppie_vicine(a, n, d); // passo 5 printf(“Numero di coppie di punti con distanza”); printf(“ minore di %f: %d \n”, d, m); // passo 6 return 0; } 22  input_punti file: vicini.c void input_punti(punto a[], int n) { int i; float x, y; for(i = 0; i < n; i++) { printf( “Ascissa punto %d: ”, i); scanf(“%f”, &x); printf( “Ordinata punto %d:”, i); scanf(“%f”, &y); a[i] = creaPunto(x, y); } } 23  coppie_vicine file: vicini.c int coppie_vicine(punto a[], int n, float d) { int i, j, m; m = 0; for(i=0; i < n-1; i++) for(j=i+1; jy; float y; }; } punto creaPunto(float x, float y) { float distanza(punto p1, punto p2) { punto p = float dx = p1->x – p2->x; malloc(sizeof(*p)); float dy = p1->y – p2->y; p->x = x; float d = sqrt(dx*dx + p->y = y; dy*dy); return p; return d; 32  Note … Nell’header file punto.h non possiamo non dichiarare typedef struct pto *punto; perché all’atto della compilazione del modulo client, il compilatore non saprebbe quanta memoria allocare per una dichiarazione del tipo: punto p; Invece, essendo il tipo punto un puntatore, il compilatore sa quanta memoria deve allocare per una variabile di quel tipo, indipendentemente dalla dimensione dell’elemento puntato NB: il nome del tipo e l’interfaccia degli operatori non sono cambiati, per cui il programma client non necessita di modifiche 33  Esercizio: ADT Vettore Operatori – CreaVettore Crea un vettore di n elementi – LeggiVettore Legge l’elemento di posizione i del vettore – ScriviVettore Modifica l’elemento in posizione i del vettore Fare specifica e implementazione con array come esercizio … 34  Astrazione e Modularizzazione  Come organizziamo il codice ? Progettazione: l’insieme delle attività relative al concepimento della soluzione informatica di un problema dall’architettura, ai dati da manipolare, alle tecniche algoritmiche si sviluppa a partire da una specifica … … dal cosa al come Modularizzazione: dividere per gestire la complessità unità di programma Alcune già note: funzioni, procedure,...  Moduli Una unità di programma che mette a disposizione risorse e servizi computazionali (dati, funzioni, …) Fondamentale nella realizzazione dei concetti di: – Astrazione – Information Hiding Riuso di componenti già costruite e verificate – Ad esempio: una volta definite delle funzioni che consentono di risolvere sotto-problemi di utilità generale, come è possibile riusarle nella soluzione di altri problemi ?  Astrazione Procedimento mentale che consente da una parte di evidenziare le caratteristiche pregnanti di un problema e dall’altra di offuscare o addirittura ignorare gli aspetti che si ritengono secondari rispetto ad un determinato obiettivo – La nozione, mutuata dalla psicologia, di “astrazione” permette di concentrarsi su un problema ad un determinato livello di generalizzazione, senza perdersi nei dettagli irrilevanti dei livelli inferiori; l’uso dell’astrazione permette anche di lavorare con concetti e termini che sono familiari all’ambiente di definizione del problema, senza doverli forzatamente trasformare in strutture non altrettanto note … (Wasserman, ’83)  Astrazione Già fatto largo uso nello sviluppo di programmi procedurali mediante l’applicazione della decomposizione funzionale … Astrazione funzionale: concentrare l’attenzione su cosa fa un certo sottoprogramma, astraendo dal come esso realizza il suo compito Non è il solo tipo di astrazione possibile …  Tipi di astrazione Astrazione funzionale – una funzionalità è totalmente definita ed usabile indipendentemente dall’algoritmo che la implementa (es. algoritmi di ordinamento di un array) Astrazione sui dati – un dato o un tipo di dato è totalmente definito insieme alle operazioni che sul dato possono essere fatte; pertanto, sia le operazioni che il dato (o il tipo di dato) sono usabili a prescindere dalle modalità di implementazione Astrazione sul controllo – un meccanismo di controllo è totalmente definito ed usabile indipendentemente dalle modalità e dalle tecniche con cui è realizzato … l’enfasi in questo corso 6 sarà sul secondo tipo …  Information hiding Parnas, 1972: occultamento dell’informazione – La realizzazione di alti livelli di astrazione passa attraverso la definizione di strutture capaci di mettere a disposizione (esportare) risorse e servizi occultando, ovvero rendendo inaccessibili, i dettagli implementativi Astrazione: definire le entità funzionali o dati che compongono un sistema Information hiding: definire ed imporre vincoli di inaccessibilità ai dettagli funzionali e di rappresentazione della struttura dei dati  Modulo Una unità di programma costituita da: – Una Interfaccia definisce le risorse ed i servizi (astrazioni) messi a disposizione dei “clienti” (programma o altri moduli) completamente visibile ai clienti – Una sezione implementativa (body) implementa le risorse ed i servizi esportati completamente occultato Un modulo può usare altri moduli Un modulo può essere compilato indipendentemente dal modulo (o programma) che lo usa Modulo nome Usa nomi di moduli Interfaccia Una visione astratta dichiarazioni Implementazione dichiarazioni locali definizioni In C: un opportuno uso di Fine header e source files e delle regole di visibilità...  Moduli e C In C non esiste un apposito costrutto per realizzare un modulo; di solito un modulo coincide con un file Per esportare le risorse definite in un file (modulo), il C fornisce un particolare tipo di file, chiamato header file (estensione.h) – Un header file rappresenta l’interfaccia di un modulo verso gli altri moduli Per accedere alle risorse messe a disposizione da un modulo bisogna includere il suo header file – Concetto già incontrato per le librerie predefinite: ad esempio #include … – Per i moduli definiti dall’utente: #include “modulo.h”...  Moduli e C Modulo nome Usa nomi di moduli # include Interfaccia Header file: dichiarazioni dichiarazioni e prototipi Implementazione C file: dichiarazioni locali dichiarazioni static … definizioni definizioni Fine corpo delle funzioni  Moduli e librerie di funzioni Il modulo implementa astrazioni funzionali e mette a disposizione attraverso la sua interfaccia funzioni e procedure che realizzano le astrazioni – il modulo si presenta come una “libreria” di funzioni – per l’information hiding nessun effetto collaterale nessuna variabile globale funzioni di servizio nascoste // Interfaccia del modulo: file utile.h Modulo void scambia(int * x, int * y); utile // dichiarazione altre funzioni … // Implementazione del Modulo: file utile.c void scambia(int * x, int * y) {int temp = *x; Cliente: può *x = *y; usare le risorse *y = temp; e i servizi } esportati dal modulo // definizione altre funzioni …  Uso dei commenti I commenti relativi alla specifica di una funzione possono essere inseriti nell’header file prima del prototipo della funzione – … serve da documentazione per chi dovrà usare la funzione (modulo client) I commenti relativi alla progettazione e realizzazione di una funzione possono essere inseriti nel file.c prima della definizione della funzione – … serve da documentazione per chi dovrà eventualmente modificare la funzione void input_array(int a[], int n); vettore.h void output_array(int a[], int n); Modulo void ordina_array(int a[], int n); int ricerca_array(int a[], int n, int elem); vettore int minimo_array(int a[], int n); … #include vettore.c #include “utile.h” // contiene funzione scambia int minimo_i(int a[], int i, int n); // dichiarazione locale void input_array(int a[], int n) { … } void output_array(int a[], int n) { … } void ordina_array(int a[], int n) { … } int ricerca_array(int a[], int n, int elem) { … } int minimo_array(int a[], int n) { … } int minimo_i(int a[], int i, int n) { … } // usata da ordina_array …  Il programma principale // file ordina_array.c # include # include “vettore.h” # define MAXELEM 100 Modulo client del modulo vettore int main() { … }  Compilazione...