* LISTE astrazione di dato che cattura l'idea di sequenza di lunghezza indefinita (e dinamica) di elementi
non necessariamente omogenei
liste di liste (oltre che di elementi atomici)
liste di elementi atomici eterogenei, eventualmente tipizzati dinamicamente
sia di lunghezza indefinita, ma limitata a priori (da 0 a n), che di lunghezza massima teoricamente illimitata
possibilmente con modalita' di accesso ristretta, e.g. sequenziale (non diretto), o solo al primo e/o all'ultimo elemento
definibile ricorsivamente
lista (definizione ricorsiva/costruttiva)
o e' una lista vuota
o e' un elemento (atomico o lista) seguito da una lista
* LISTE L’ordine degli elementi nella lista puo’ essere o no significativo, quindi una lista puo’ rappresentare:
Un insieme (non ordinato)
Una sequenza (ordinata), come un vettore
Sono le procedure d’accesso che stabiliscono cosa la lista rappresenta
Una proprieta' fondamentale delle liste e' che la struttura logica non e’ collegata a quella fisica (come e' invece per gli array)
Questo rende essenziale in una lista la nozione di riferimento esplicito da un elemento all’elemento successivo
In una lista la relazione di contiguita' logica tra elementi e' esplicita
N.B.: Un elemento puo’ appartenere contemporaneamente a diverse liste
e.g. rappresentazione mediante liste di una matrice sparsa:
ogni elemento appartiene a due liste, una che rappresenta la riga cui l’elemento appartiene, l’altra che rappresenta la colonna
* LISTE: implementazione Rappresentazione "normale" (che utilizzeremo di solito qui)
in memoria centrale
utilizzando puntatori e memoria dinamica
ma esistono anche altre rappresentazioni:
array con elementi (omogenei) liberi o occupati e indici come puntatori
nell'array sono in effetti contenute (almeno) due liste, quella degli elementi liberi e quella/e degli elementi occupati
file (file system ad allocazione linkata, FAT del DOS, ...)
Diverse rappresentazioni possono essere piu’ o meno adatte a supportare
liste diversamente vincolate nei contenuti
(e.g. una rappresentazione basata su array e' adatta solo per liste omogenee di elementi semplici)
diverse modalita’ (ristrette) di accesso alla lista
* LISTE: perche? Supponiamo di volere mantenere una sequenza ordinata di numeri, e di volere inserire in questa sequenza un nuovo numero.
Supponiamo di rappresentare la sequenza tramite un vettore ordinato. Allora per inserire il nuovo numero devo:
1. Cercare la posizione corretta dove effettuare l’inserimento
(il primo elemento, se gia’ esiste, che sia maggiore di quello che voglio inserire oppure la posizione successiva a quella dell’ultimo elemento significativo);
2. Spostare ordinatamente di una posizione tutti gli elementi maggiori di quello che voglio inserire (in ogni caso devo estendere il vettore);
3. Copiare nel “buco” cosi’ creato il nuovo elemento.
Complessita’ analoga ha la cancellazione di un elemento dalla sequenza.
Rappresentare una sequenza come una lista consente di:
Evitare il passo 2 della procedura, dato che la contiguita’ logica non e’ associata alla contiguita’ fisica;
Evitare di dovere necessariamente allocare a priori spazio di memoria per il numero massimo di elementi ipotizzabile.
* LISTE Possiamo considerare le liste da due punti di vista:
1. un tipo di dato astratto a se stante
2. una struttura dati (meglio, come vedremo nel seguito: una famiglia di strutture dati) utilizzabile per la rappresentazione concreta di altri tipi di dato astratto
normalmente ci limiteremo a considerare liste di elementi atomici omogenei
* Tipi di Dati a livello macchina si hanno solo stringhe di bit che assumono ciascuno valore 0 o 1
siamo noi (e le istruzioni macchina che mettiamo nel programma) che decidiamo quale significato dare a ciascuna stringa di bit
nei linguaggi di programmazione di livello medio e alto (dal C o Pascal in su) tutti i dati, variabili e valori, appartengono ciascuno ad un tipo, sono cioe' descritti non in termini di configurazione di una stringa di bit, ma attraverso proprieta' astratte:
insieme (possibilmente strutturato) dei valori possibili
(e.g. range INT_MIN..INT_MAX per il tipo int del C)
possibilita' di denotare questi valori
(e.g. 138, 0x20, 077, INT_MAX per il tipo int del C)
insieme delle operazioni primitive possibili su ciascun tipo di dato, e semantica di ciascuna operazione.
* Tipi di Dati, esempio: tipo BOOLEAN insieme dei valori possibili: {true, false}
denotazione di questi valori: TRUE, FALSE
operazioni: { NOT, AND, OR, PRED, SUCC, =, , <, , >, , ORD }
NOT: BOOLEAN BOOLEAN,
totalmente definita
NOT FALSE TRUE
NOT TRUE FALSE
AND: BOOLEANBOOLEAN BOOLEAN,
totalmente definita
FALSE AND FALSE FALSE
FALSE AND TRUE FALSE
TRUE AND FALSE FALSE
TRUE AND TRUE TRUE
SUCC: BOOLEAN BOOLEAN,
parzialmente definita
SUCC(FALSE) TRUE
SUCC(TRUE) non definito
* ADT: astrazione vs. implementazione non ci interessa come e' rappresentato un valore BOOLEAN in termini di stringa di bit (sizeof, bit-pattern per ciascun valore),
e ciascun linguaggio o ciascun sistema di programmazione lo puo' rappresentare come gli pare,
basta che il suo comportamento (behaviour) sia conforme alla definizione astratta: tipo di dato astratto o ADT
esempio: chi sa come sono rappresentati i double nel C Microsoft per Windows?
ovviamente un sistema di programmazione deve definire una rappresentazione concreta (stringa di bit, struttura dati) per ciascun valore di ciascun tipo; e.g.:
un byte con tutti i bit a 0 significa FALSE, un byte con almeno un bit a 1 significa TRUE
oppure
un byte con tutti i bit a 0 significa FALSE, un byte con il solo bit piu' leggero a 1 significa TRUE, e tutte le altre configurazioni di bit sono illegali
* ADT: citazione Antonio Natali:
"una delle metodologie piu' incisive per la costruzione di sistemi SW corretti, modulari, documentabili, consiste nel mantenere quanto piu' possibile separate le parti del programma che accedono e manipolano la rappresentazione concreta in memoria dei dati (detti gestori), dalle parti (clienti) che trattano i dati come enti concettuali, ignorandone i dettagli interni e realizzativi."
* ADT: cliente e implementatore tipo di dato astratto 2 punti di vista diversi
gestore dell'ADT:
vede la rappresentazione
implementa l'astrazione (e.g. le operazioni primitive) basandosi sulla rappresentazione del tipo
cliente dell'ADT:
non vede la rappresentazione
utilizza l'astrazione (e.g. le operazioni primitive) senza sapere come e' implementata
puo' definire (implementare) nuove operazioni, ma solo operazioni non primitive,
implementate a partire dalle operazioni gia' disponibili (e.g. le operazioni primitive)
e che (ovviamente) non si basano sulla conoscenza della rappresentazione concreta dei valori (che e' ignota)
* LISTE: definizione dell'ADT operazioni primitive su liste
null()
list BOOLEAN
data una lista L, restituisce TRUE se L e' vuota.
La lista vuota e' indicata come EMPTYLIST o () o <>
precondizioni: nessuna
cons()
element list list
dato un elemento E e una lista L, restituisce la lista (E L)
precondizioni: nessuna
N.B.: cons() e' un operatore funzionale come gli altri tre; parte da dei valori, e produce un valore: gli operandi non sono modificati
* LISTE: definizione dell'ADT operazioni primitive su liste
car() (detta anche head())
list element
data una lista L = (E RestOfL) ne restituisce il primo elemento E
precondizioni: !null(L)
cdr() (detta anche tail())
list list
data una lista L = (E RestOfL) ne restitusce la sottolista RestOfL (eventualmente vuota) degli elementi successivi al primo
precondizioni: !null(L)
* LISTE: definizione dell'ADT assiomi
vincoli che le operazioni devono soddisfare
descrizione della semantica delle operazioni
(insieme alle precondizioni)
null(EMPTYLIST)
!null(cons(e, l))
car(cons(e, l)) == e
cdr(cons(e, l)) == l
* LISTE: definizione dell'ADT note
N.B.: (E L) (E (L))
L non e' essa stessa un elemento di (E L), ma gli elementi di L costituiscono gli elementi di (E L) successivi ad E.
Notare che le operazioni sono definite in modo indipendente dalla rappresentazione delle liste.
Indipendentemente dalla rappresentazione che vorro' utilizzare per realizzare concretamente una lista, posso usare l'astrazione.
* ADT LISTA: esempi .1 int length (list l)
{
return (null(l) ? 0
: 1 + length(cdr(l)));
}
la dimostrazione di correttezza e' per induzione matematica sulla lunghezza di l (per esercizio)
* ADT LISTA: esempi .2 list append (list l1, list l2) {
// date due liste l1 e l2 ritorna una lista che e' la
// concatenazione delle due.
// N.B.: non una lista di due elementi, l1 ed l2, ma
// una lista contenente tutti gli elementi di l1,
// nell'ordine, seguiti da tutti gli elementi di l2,
// nell'ordine
// N.B.: l1 e l2 non vengono in alcun modo alterate
return (null(l1) ? l2
: cons(car(l1),
append(cdr(l1), l2)
)
);
}
la dimostrazione di correttezza e' per induzione matematica sulla lunghezza di l1 (per esercizio, vedi esempio seguente)
* ADT LISTA: esempi .3 list reverse (list l) { 1
return (null(l) ? l 2
: append(reverse(cdr(l)), 3
cons(car(l), 4
EMPTYLIST) 5
) 6
); 7
} 8
la dimostrazione di correttezza e' per induzione matematica sulla lunghezza di l
se l=() la funzione ritorna l (cioe' ()), che e' ovviamente la lista inversa di se stessa (riga 2)
se l() la funzione ritorna (righe 3-6) una lista formata dall'inverso di cdr(l) (per ipotesi induttiva, applicabile perche' cdr(l) contiene un elemento meno di l, e cdr(l) esiste perche' !null(l)) seguita da car(l), cioe' proprio la lista inversa di l
* ADT LISTA: completezza L'insieme delle operazioni primitive sopra indicato, unitamente all’operatore triadico del C (?:) e alla ricorsione (oltre che all’istruzione return) e' funzionalmente completo:
tutte le altre operazioni sulle liste possono essere realizzate utilizzando solo questo insieme di operazioni.
In realta’ si puo’ dimostrare (vedi Z. Manna, “Teoria matematica della computazione”) che questo sistema di programmazione e’ equivalente ad una Macchina di Turing, e che quindi ci consente di calcolare qualunque cosa sia calcolabile.
* ADT LISTA: Esercizio Esercizio: scrivere, basandosi solo sulle funzioni primitive prima definite, una funzione C che concateni un elemento in coda alla lista anziche' in testa (come fa cons()).
Dimostrarne anche la correttezza.
Il suo prototipo deve essere:
list tailCons(element e, list l);
Quale e' la complessita' di questa operazione?
O(n)!
Scrivere anche le due funzioni:
list tailCdr(list l);
element tailCar(list l);
che operano anch’esse sulla coda della lista e dal significato ovvio
Comments