Realizzazione software
• Due fasi:
1. Specifica dell'algoritmo
1.a Definizione dei dati
1.b Definizione della modalità della loro elaborazione
2. Realizzazione algoritmo con un particolare linguaggio (traduzione)
Tipi di dati
• Tipo di dato astratto: oggetto matematico definito da tre componenti:
– insieme di valori che definisce il dominio – insieme di operazioni sul dominio
– insieme di costanti
• Esempio: tipo booleano:
• {true, false}
• and, or, not, ...
Tipi di dati
• Tipo di dato concreto: si riferisce all'uso del dato in un particolare linguaggio
• Per definire un tipo di dato concreto occorre:
– definire le proprietà astratte
– definire i vincoli imposti dal linguaggio scelto
• ad esempio: come dichiararlo, utilizzarlo, accedere alle sue parti,...
Rappresentazione di un nuovo tipo di dato
• Per rappresentare un nuovo tipo di
dato, può essere necessario utilizzare tipi di dati già esistenti
• Esempio: tipo di dato: "insieme [1..5]"
• Realizzato con un vettore di 5 elementi
• I metodi sono composizioni dei metodi
utilizzati dai dati componenti
Rappresentazione di un nuovo tipo di dato
• Esempio:
– inserimento di un elemento nell'insieme – rimozione di un elemento dall'insieme – svuotamento dell'insieme
– controllo della presenza di un elemento – controllo dello stato dell'insieme (pieno,
vuoto, stati intermedi)
Rappresentazione dei dati
• La rappresentazione di un nuovo dato non è univoca
• I criteri di scelta sono:
– la correttezza e
– l'efficienza della rappresentazione, misurata da:
• occupazione in memoria
Diverse rappresentazioni
• Esempio: insieme di interi [1..5]
– con un vettore di 5 elementi booleani – con un unico intero di 5 bit
• Differenza di efficienza:
– Inserimento di un el.:
– Controllo dello stato di un el.: – Azzeramento:
– Unione:
Vettori e matrici
• Si mettono in corrispondenza un insieme di indici e gli elementi del vettore
– Gli indici sono definiti interi – I metodi sono generalmente:
memorizza e accedi
• Una matrice è definita come un vettore a
due dimensioni
Rappresentazione di vettori
• In locazioni di memoria contigue
• Si definisce l'indirizzo della prima locazione e la dimensione di ogni elemento
• Accesso all'elemento i-esimo:
ind(el
i) = ind(el
0) + i*size(el)
Vettori a più dimensioni
• Esempio a due dimensioni:
– Row major order
• Accesso all'elemento (i,j)-esimo:
ind( el
i,j) = ind(el
0,0) + (j+i*N)*size(el)
• Facile estensione a più di due dimensioni
Rappresentazione compatta di vettori
• Matrici sparse con valore predominante
– per velocizzare l'elaborazione – per risparmiare memoria
• Esempio con vettore a tre componenti
– memorizzazione dimensione matrice e valore predominante
Rappresentazione compatta di vettori
• Metodi di accesso agli elementi:
– accedi (complesso)
– memorizza (molto complesso, richiede shift)
• Funzioni composte:
– controllo dello stato
– controllo del numero degli elementi
• Risparmio di memoria
Le liste semplici
• I valori di una lista sono sequenze di valori elementari, detti atomi
• Esempio di lista di interi mediante rappresentazione parentetica:
( 8 25 6 87 54 )
• Caratteristiche:
– lunghezza non definita a priori – presenza della lista nulla ( )
Metodi sulle liste
• Lunghezza (numero di elementi)
• cons(el, lista) per inserire un elemento in testa alla lista
• car(lista) determina il primo elemento
• cdr(lista) fornisce una copia della lista senza il primo elemento
• null(lista) verifica se la lista è vuota
Rappr. delle liste semplici
• Pochi linguaggi dispongono del tipo concreto lista
• Vi sono due tipi di rappresentazione:
– rappr. sequenziale – rappr. collegata
Rappresentazione sequenziale
• E' rappresentata da:
– un vettore monodimensionale i cui elementi contengono un atomo
– un intero (primo) che denota l'indice del vettore che identifica il primo elemento
– un intero (lunghezza) che denota il numero di elementi nella lista
Rappresentazione sequenziale
(5 1 21 45 78)
5 1 21 45 78 12 1 7
1 2 3 4 5 6 7 8
primo = 1 lunghezza = 5
Rappresentazione sequenziale
• Implementazione dei metodi
• Svantaggi:
– occupazione fissa di memoria – limiti nell'estensione della lista – inefficienza di alcuni metodi
Rappresentazione collegata
• Ad ogni elemento è associato un
riferimento che serve a determinare il successore
• La sequenza non è più rappresentata
dall'adiacenza fisica in memoria, ma da
una informazione logica
Rappresentazione collegata
• Implementazione dei metodi:
– eliminazione primo elemento
– aggiunta di un elemento in testa
– eliminazione di un elemento generico
– aggiunta di un elemento in una posizione generica
Rappresentazione collegata
• Vantaggio:
– non più necessario spostare elementi (solo modifiche ai riferimenti)
• Svantaggio:
– per accedere ad un elemento è necessario scandire tutta la lista (cioè non è noto
l'indirizzo del generico elemento)
Implementazione della rappresentazione collegata
• Vi sono due modi per implementare la rappresentazione collegata:
– utilizzando gli array – utilizzando i puntatori
Rappresentazione collegata mediante array
• Si associa ad ogni elemento della lista una componente dell'array costituita da:
– il valore dell'elemento della lista
– il riferimento all'elemento successivo (indice dell'array)
Rappresentazione collegata mediante array
(5 1 21 45 78)
21 5 ? 45 ? 1 78 ?
4 6 ? 7 ? 1 0 ?
1 2 3 4 5 6 7 8
Rappresentazione collegata mediante array
• Metodi:
– l'azzeramento e l'eliminazione di elementi sono operazioni semplici
– l'inserimento di elementi necessita della
determinazione di una posizione vuota che si può realizzare in due modi:
• scansione dell'intera lista
• utilizzo della lista libera (esempi)
Rappresentazione collegata mediante array
• Vantaggi:
– non vengono spostati elementi
– linguaggi in cui l'unico dato struttturato è l'array
• Svantaggi:
– gestione della lista libera
– rimane il problema della dimensione massima fissata dalla dimensione dell'array
Rappresentazione collegata mediante puntatore
• Il tipo puntatore è un tipo di dato i cui valori rappresentano indirizzi in memoria
• Le operazioni usualmente disponibili sono:
– accesso alla locazione puntata
– richiesta di una nuova locazione libera – rilascio della locazione non più utilizzata
Rappresentazione collegata mediante puntatore
• Ogni elemento della lista è composto da:
– il valore dell'elemento della lista
– un puntatore che identifica la locazione di memoria in cui è memorizzato l'elemento successivo
• L'elemento iniziale è un puntatore
Rappresentazione collegata mediante puntatore
• Vantaggi:
– stessi vantaggi della rappresentazione collegata mediante array e in più non c'è limite alla lunghezza massima
• Svantaggi:
– la ricerca richiede la scansione completa
L'utilizzo dei puntatori è critico
• L'utilizzo dei puntatori permette di
referenziare zone di memoria; è critico perché:
– permette di modificare aree di memoria che possono contenere informazioni vitali – se mal utilizzato, può portare
all'esaurimento della memoria disponibile (garbage collection)
Rappresentazione collegata
• Per migliorare l'efficienza di alcune operazioni sono state concepite due varianti:
– Rappresentazione collegata circolare – Rappresentazione collegata simmetrica
Rappresentazione collegata circolare
• L'ultimo elemento non contiene un riferimento nullo, ma il riferimento al primo elemento della lista
• Vantaggi:
– utilizzo come buffer circolare
Rappresentazione collegata simmetrica
• Ogni elemento contiene anche il riferimento all'elemento precedente
• Vantaggi:
– la lista si può scandire in entrambe le direzioni – si semplifica l'inserimento in posizione
precedente ad un dato elemento
Liste composite
• Estensione del concetto di lista
• Gli elementi della lista possono a loro volta essere delle liste
• Rappresentazione parentetica:
( 5 () 6 ( 7 8 ) ( 9 (12) 3 ) 14 )
• Nell'esempio, l'atomo può essere una
lista o un numero
Rappresentazione del singolo nodo
• Esistono due varianti:
– l'atomo contiene sia un puntatore ad una lista che lo spazio per memorizzare un
numero; un ulteriore booleano li seleziona – l'atomo contiene lo spazio per memorizzare
solo il più esteso tra il puntatore alla lista e il numero; un ulteriore booleano li seleziona
Rappresentazione del singolo nodo
• Le due varianti si riferiscono a:
strutture (struct) unioni (union)
typedef struct { typedef union { int giorno; int numero;
int mese; char nome[10];
int anno; } cliente;
} data;
Recupero della memoria
• Garbage collection
(recupero memoria non più utilizzata)
• Può avvenire:
– manualmente a carico del programmatore – automaticamente a carico del traduttore
del linguaggio (serve marcare le aree allocate e gestire la lista libera)
Le pile
• La pila è un tipo di dato con struttura LIFO
• Definizione:
– {pila, elemento, boolean}
– {top, push, pop, test_pila_vuota}
• top: pila elemento (cons)
• push: pila x elemento pila (cdr)
• pop: pila pila (car)
• test_pila_vuota: pila boolean (null)
Le pile
• A differenza delle liste gli inserimenti e le cancellazioni posso essere effettuati solo sulla cima della pila (non avvengono
spostamenti degli elementi)
• Tipo di dato fondamentale
Le code
• La coda è un tipo di dato con struttura FIFO
• Definizione:
– {coda, elemento, boolean}
– {primo, in_coda, out_coda, test_coda_vuota}
• primo: coda elemento (cons)
• in_coda: coda x elemento coda (cdr)
• out_coda: coda coda (car)
• test_coda_vuota: coda boolean (null)
Requisiti delle pile e delle code
• Requisiti delle pile:
– un puntatore che determini la cima – le operazioni di accesso sono semplici
• Requisiti delle code:
– due puntatori che puntino alla cima e alla coda
– le operazioni di accesso sono poco più complesse
