Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Liste e Puntatori
Copyright © 2006-2009 by Claudio Salati.
Lez. 6
1
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
2
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
3
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)
4
 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.
5
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
6
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.
7
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: BOOLEANBOOLEAN  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
8
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
9
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."
10
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)
11
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
12
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)
13
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
14
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.
15
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)
16
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)
17
ADT LISTA: esempi
.3
list reverse (list l) {
return (null(l) ? l
: append(reverse(cdr(l)),
cons(car(l),
EMPTYLIST)
)
);
}
1
2
3
4
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 di18l
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.
19
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
20
ovvio
Esempio di implementazione: lista di element 1
typedef . . . element;
struct listElement {
element
el;
struct listElement *next;
};
typedef struct listElement *list;
// tipicamente:
#define EMPTYLIST NULL
 poiche' secondo la definizione ricorsiva l'ultimo elemento della
lista e' seguito dalla lista vuota, il valore del campo next
dell'ultimo elemento della lista sara' NULL
21
Esempio di implementazione: lista di element 2
boolean null(list l) {
return (l==NULL); // meglio l==EMPTYLIST
}
list cons(element e, list l) {
// costruisce un altro valore list senza
// alterare il valore dell'operando l
list t = malloc(sizeof(listElem));
t->el = e;
t->next = l;
// structure sharing:
// gli elementi di l sono condivisi da l
// e dal nuovo valore
return t;
}
22
Esempio di implementazione: lista di element 3
element car(list l) {
// N.B. car non altera l
assert(!null(l));
return l->el;
}
list cdr(list l) {
// N.B. cdr non altera l
assert(!null(l));
return l->next;
}
23
LISTE: implementazione
.1
 Mentre e’ vero che le operazioni primitive definite ci consentono
di realizzare qualunque operazione su una lista, per quanto
complessa,
non e’ detto che ci consentano di farlo in modo efficiente.
 e.g. Inserire un elemento in testa alla lista ha costo costante,
inserirlo in coda alla lista ha costo O(n) essendo n la
dimensione della lista.
 Quello che ci interessa da qui in poi non e’ tanto il punto di vista
del cliente, ma quello dell’implementatore.
 Non ci interessa utilizzare l'ADT lista, ma piuttosto implementare
diversi ADT utilizzando una struttura dati "a lista" per la loro
rappresentazione concreta.
 ADT che ci possono interessare:
polinomi, vettori di lunghezza variabile, vettori e matrici sparse,
insiemi, ...
24
LISTE: implementazione
.2
 Diversi ADT offrono in generale operazioni molto diverse.
 Saranno quindi molto diverse le modalita' con cui diversi ADT
dovranno accedere alla struttura dati lista utilizzata per la loro
rappresentazione concreta.
 Quello che ci interessa qui non e’ il punto di vista del cliente dell'ADT
lista, ma quello dell’implementatore di diversi generi di lista:
 Come realizzare in modo efficiente una lista
una volta che siano note le modalita’ operative con cui voglio
poterla manipolare.
E.g.:
 Stack (pila) LIFO (Last-In-First-Out)
 Coda FIFO (Fist-In-First-Out)
 Potremo anche rimuovere il vincolo di operare in modo funzionale,
cioe' producendo valori a partire da valori, senza modificare i valori in
25
ingresso (in effetti e’ quello che faremo normalmente).
LISTE: implementazione
 Inserzione di un nuovo elemento nella lista:
 Alloco un nodo inutilizzato
 Gli assegno il valore dell’elemento da inserire
 Lo inserisco nella lista nel posto desiderato
 Per fare cio’ devo manipolare i riferimenti espliciti tra gli
elementi della lista adiacenti a quello che voglio inserire
 Rimozione di un elemento:
 Estraggo l’elemento dalla lista
 Per fare cio’ devo manipolare i riferimenti espliciti tra gli
elementi della lista adiacenti a quello che voglio
eliminare
 Disalloco il nodo non piu’ utilizzato
26
LISTE: implementazione
 Devo possedere una riserva di nodi non utilizzati
 Devo avere dei meccanismi per acquisire nodi dalla riserva e per rilasciare
nodi alla riserva
 Devo avere procedure per:
 Inizializzare una lista
 Inserire un elemento nella lista (in quale posizione?)
 Togliere un elemento dalla lista (da quale posizione?)
 Scandire gli elementi della lista
 Ogni nodo deve contenere almeno un campo riferimento che consenta di
descrivere la strutturazione logica della lista
 Devo avere la possibilita’ di indicare che il campo riferimento di un nodo
non e’ significativo (non riferisce nulla, e.g. nel caso dell’ultimo elemento
della lista)
 Devo avere una testata che mi consenta di accedere alla lista (e.g. al suo
“primo” elemento)
27
Puntatori
 una variabile o un valore che riferisce una variabile
 esiste in C una funzione/operatore che si applica ad una
variabile (meglio, ad una denotazione di variabile) e ne ritorna
l'indirizzo (e' l'operatore unario &)
 un puntatore puo' riferire variabili di qualunque classe di
allocazione (statica, automatica, dinamica)
 regole di compatibilita' di tipo? vedi relazioni tra tipi
 in C e' definita la costante NULL di tipo void*, compatibile con
tutti i tipi puntatore: un puntatore che ha valore NULL ha un
valore ben definito, ma non riferisce alcuna variabile
–
#define NULL ((void *) 0)
–
definita nella libreria standard: sia in stdio.h che in stdlib.h
 il tipo void* del C e' definito come compatibile con tutti i tipi
puntatore
28
Puntatori
 operazioni su puntatori in C
 assegnamento
 confronto
 uguaglianza
 disuguaglianza
 relazioni d'ordine (con certi limiti)
 aritmetica dei puntatori
 somma con un intero
 sottrazione di un intero
 sottrazione di puntatori
 indiciamento
 funzioni della libreria standard (stdlib)
 void *malloc(size_t size);
 void free(void *p);
 calloc() e realloc()
 dereferenziamento
29
Allocazione e Inizializzazione di Variabili in C
 C++ prevede che ogni volta che viene creata una variabile, essa
venga anche inizializzata tramite l'invocazione dell'opportuno
costruttore di tipo
 pertanto tutte le variabili in C++ sono comunque inizializzate;
 un comportamento analogo si ha per il C con le variabili statiche
(che sono quindi sempre inizializzate), per le quali sono previsti
 un costruttore di assegnamento (o copia: copia la
rappresentazione del valore indicato), invocabile
esplicitamente nel programma
 un costruttore di default (che "azzera" la variabile) che viene
utilizzato in assenza di utilizzo esplicito del costruttore di
copia
 per le variabili automatiche il costruttore (solo assegnamento)
deve essere invocato esplicitamente (e non esiste il costruttore
default)
 per le variabili dinamiche non esiste la nozione di costruttore, per
cui esse sono sempre non inizializzate
30
Allocazione e Inizializzazione di Variabili in C
codice
int *pi;
pi=malloc(sizeof(int));
*pi=5;
memoria
statica
pi =
memoria
dinamica o heap
NULL
pi =
?
pi =
5
31
Allocazione e Inizializzazione di Variabili in C
codice
int *pi;
pi=malloc(sizeof(int));
*pi=5;
memoria
automatica
pi =
memoria
dinamica o heap
?
pi =
?
pi =
5
32
Allocazione e Inizializzazione di Variabili in C
codice
memoria
automatica
memoria
dinamica o heap
int *pi=NULL;
pi =
pi=malloc(sizeof(int));
pi =
?
*pi=5;
pi =
5
NULL
33
Definizione di Puntatori in C
• non sono consentiti riferimenti (in avanti) a nomi typedef non ancora
definiti
• sono consentiti (ma deprecati) riferimenti (in avanti) a nomi tag non
ancora definiti
• e' infatti possibile pre-dichiarare parzialmente un nome tag, per
poterlo riferire prima della definizione
struct nomeStruct;
• (pre-) dichiara che nomeStruct e' il nome tag di una struct.
• da questo momento il nome tag nomeStruct e' riferibile.
• la struttura e' ancora opaca: non si sa come e' fatta!
Se mi basta solo riferirla tramite puntatori non e' nemmeno
necessario (ne' opportuno) completarne la definizione
• quando si definisce un tipo puntatore, il tipo puntato e' bene che sia
gia' stato definito/dichiarato (salvo quanto detto prima).
• la definizione di tipi (strutture dati) ricorsivi, in particolare di record
(struct) uno dei cui campi riferisce il record stesso, avviene
34
utilizzando il nome tag del record
Definizione di Strutture Dati Ricorsive in C
typedef struct structTag {
...
struct structTag *next;
// a questo punto il nome tag
// della struct e' gia' definito
} typedefName;
 sfruttando riferimenti in avanti e' possibile anche la definizione di
tipi mutuamente ricorsivi (vedi anche dichiarazioni parziali!)
struct s {
...
struct t *tRef;
// riferimento in avanti
};
struct t {
...
struct s *sRef;
};
35
Memoria dinamica e puntatori
 il sistema di programmazione deve supportare la mancanza di una
disciplina di dis/allocazione predefinita
 evitando frammentazione
 ricompattando blocchi di memoria al momento della loro
liberazione
 in modo efficiente
 struttura dati detta heap: algoritmi ben noti (vedi lezione 7).
 una variabile dinamica puo' essere creata in una procedura e
sopravviverle
 l'indirizzo delle variabili dinamiche e' definito solo a tempo di
esecuzione
 le variabili dinamiche sono visibili se c'e' un puntatore statico o
automatico visibile che, direttamente o indirettamente, le riferisce
36
Memoria dinamica e puntatori
 problemi
 garbage
 variabili dinamiche allocate, non piu' visibili nel
programma, e quindi non rilasciabili
 ... p = malloc(); p = NULL; ...
 dangling reference
 puntatore che riferisce una variabile dinamica che e' gia'
stata disallocata
 ... p = malloc(); q = p; free(p); ...
 N.B.: dato che in C il passaggio dei parametri e' per
valore, dopo la chiamata free(p), p e'
necessariamente un dangling reference!
37
Stack LIFO
 La disciplina di inserzione/cancellazione degli elementi e’ LIFO
(Last In - First Out): l’ultimo elemento inserito e’ il primo
elemento estratto
 E’ sufficiente:
 Un riferimento tra gli elementi della lista
 Un marker per indicare che un riferimento e’ non
significativo (e.g. per l’ultimo elemento della lista)
 Una testata per accedere alla lista (alla sua testa)
 Le operazioni di inserimento e cancellazione (entrambe in testa!)
hanno costo costante (O(1))
testata
el.n
•••
el.2
el.1

38
Stack LIFO: definizione e implementazione
struct node {
element
struct node
value;
*next; };
typedef struct node *stack;
void stackInit(stack *s) {
// P = {}
*s = NULL;
}
boolean stackEmpty(stack s) {
// P = { s e' gia stato inizializzato }
return(s == NULL);
}
39
Stack LIFO: definizione e implementazione
void stackPush(stack *s, element v) {
// P = { s e' gia stato inizializzato }
struct node *t = malloc(sizeof(struct node));
t->value = v;
t->next = *s;
*s = t;
}
element stackPop(stack *s) {
// P = { s e' gia stato inizializzato;
//
s e' non vuoto }
assert(*s!=NULL);
struct node *t = *s;
element v = t->value;
*s = t->next;
free(t);
return v;
}
40
Coda FIFO : doppio puntatore di testata
 La disciplina di inserzione/cancellazione degli elementi e’ FIFO (First
In - First Out): il primo elemento inserito e’ il primo elemento estratto
 Inserzione ed estrazione avvengono agli estremi opposti della lista
 L' operazione di cancellazione in testa ha costo costante (O(1))
(anche quella di inserimento in testa, ma non ci interessa!)
 L'operazione di inserimento in fondo ha costo costante (O(1))
 Con un solo puntatore di testata una delle due operazioni
(l’inserimento in fondo) avrebbe un costo O(n) (dovrei scandire tutta
la lista)
 Con due puntatori di testata, uno al primo e l'altro all'ultimo elemento
della lista, si riconducono entrambe le operazioni a complessita'
costante
Testata
- first
- last
el.1
el.2
•••
el.n

41
Coda FIFO : doppio puntatore di testata
 Esaminando RadixSort abbiamo visto che c’e’ un’altra operazione su liste che
sarebbe utile poter eseguire in tempo costante: la concatenazione di 2 liste.
 L'operazione di concatenazione porta alla scomparsa di entrambe le liste
iniziali e alla creazione di una nuova lista che e’ l’unione delle due.
 Gli elementi delle liste iniziali sono riutilizzati per la costruzione della lista
finale.
 L' operazione di concatenazione e’ ordinata: nella lista risultato gli elementi
di una lista seguono, in modo ordinato, gli elementi dell’altra.
 Quanto costa concatenare tra loro due liste fondendole in una singola?
 Se la lista e’ uno stack LIFO O(n)
 Se la lista e’ una coda FIFO con doppio puntatore di testata O(1)
 L’implementazione dell’operazione di concatenazione e’ lasciata come esercizio
 Un’altra operazione interessante e’ l'eliminazione di un elemento qualunque della
lista (possedendone il riferimento): questa operazione e’ richiesta ad esempio
dall’algoritmo dei boundary tag.
 Quanto costa?
 Se la lista e’ una coda FIFO con doppio puntatore di testata O(n)
 Devo scandire tutta la lista fino ad identificare l’elemento precedente quello
42
che voglio eliminare.
Coda FIFO: definizione e implementazione
struct node {
element
struct node
value;
*next; };
struct queue {
struct node *first;
struct node *last; };
typedef struct queue queue;
void queueInit(queue *q) {
q->first = q->last = NULL;
}
boolean queueEmpty(queue *q) {
return(q->first == NULL);
}
43
Coda FIFO: definizione e implementazione
void queueInsert(queue *q, element v) {
if (q->first == NULL) {
// caso lista vuota
q->first = malloc(sizeof(struct node));
q->last = q->first;
} else {
q->last->next = malloc(sizeof(struct node));
q->last = q->last->next;
}
q->last->value = v;
q->last->next = NULL;
}
44
Coda FIFO: definizione e implementazione
element queueRemove(queue *q) {
assert(q->first!=NULL);
struct node *t = q->first;
element v = t->value;
q->first = t->next;
if (q->first == NULL)
// caso lista vuota
q->last = NULL;
// end if
free(t);
return v;
}
45
Complessita' delle operazioni
operazione
lista semplicemente
linkata con testata
con doppio puntatore
lista semplicemente
linkata con testata
con singolo puntatore
Inserzione di un elemento in testa
O(1)
O(1)
Inserzione di un elemento in coda
O(1)
O(n)
Rimozione di un elemento in testa
O(1)
O(1)
Rimozione di un elemento in coda
O(n)
O(n)
Concatenazione di liste
O(1)
O(n)
Rimozione di un elemento dato
qualunque
O(n)
O(n)
 Perche' tanta parte del codice scritto e' dedicato a trattare il caso
particolare di lista vuota?
 Si puo' migliorare questa situazione?
 Complessita’ temporale delle operazioni
 Casi particolari
46
Coda FIFO : lista circolare
 Immaginiamo che l'ultimo elemento della lista, anziche' avere un
riferimento marcato come non significativo, riferisca il primo
elemento della lista
testata
el.1
el.2
•••
el.n
 Si possono liberare tutti i nodi di una lista in tempo O(1)
inserendoli in una lista dei liberi
testata
liberi


el.1
el.1

el.2
•••
el.n
el.2
•••
el.n

 Ma: la rimozione del primo elemento implica l'aggiornamento del
riferimento nell'ultimo elemento ( scandire l'intera lista): O(n)
 Analogamente le altre operazioni, e.g. l'inserzione di un elemento
47
in fondo alla coda
Coda FIFO : lista circolare
con testata che riferisce l'ultimo elemento della lista
 Immaginiamo una lista circolare in cui la testata riferisca l'ultimo
elemento anziche' il primo:
testata
el.1
el.2
•••
el.n
 Si puo' inserire in tempo costante un elemento sia in testa che in
coda alla lista
 Si puo' cancellare in tempo costante l'elemento in testa alla lista
 Si possono liberare tutti i nodi di una lista in tempo costante
inserendoli in una lista dei liberi
 La cancellazione dell'elemento in coda alla lista ha costo O(n)
 L'eliminazione di un elemento qualunque della lista
(possedendone il riferimento) ha tempo O(n)
48
Coda FIFO : lista circolare
con testata che riferisce l'ultimo elemento della lista
 Esercizio: scrivere in C le procedure per:
 L'inserimento di un elemento in testa alla lista
 L'inserimento di un elemento in coda alla lista
 La cancellazione di un elemento in testa alla lista
 La liberazione di tutti i nodi di una lista inserendoli in una
lista dei liberi
 L'eliminazione di un elemento qualunque della lista
(possedendone il riferimento, che e' un parametro di
ingresso alla procedura)
49
Eliminazione dei casi particolari
-1
 Consideriamo di avere una lista ordinata di interi rappresentata
come in figura:
testata
el.1
el.2
•••
el.n

dove el.1  el.2  …  el.n
e di volere scrivere una procedura per l'inserzione ordinata di un
nuovo elemento:
struct node {
int
struct node
value;
*next; };
typedef struct node *sortedIntList;
50
Eliminazione dei casi particolari
-2
struct node *ordInsert(sortedIntList *l,
int newEl) {
if (*l == NULL) {
// caso 1: lista vuota
*l = malloc(sizeof(struct node));
(*l)->value = newEl;
(*l)->next = NULL;
return (*l);
} else if (newEl <= (*l)->value) {
// caso 2: inserisco elemento minimo, al primo posto
struct node *t = *l;
*l = malloc(sizeof(struct node));
(*l)->value = newEl;
(*l)->next = t;
return (*l);
} else {
// caso 3 : inserisco elemento non minimo
//
in lista non vuota
// continua alla prossima pagina
51
Eliminazione dei casi particolari
-3
struct node *s = *l;
// individua il nodo precedente il nuovo
// elemento
while (s->next != NULL &&
s->next->value < newEl) {
s = s->next;
}
struct node *t = malloc(sizeof(struct node));
t->value = newEl;
t->next = s->next;
s->next = t;
return (t);
}
}
52
Eliminazione dei casi particolari
-4
 I casi 1 e 2 rappresentano casi particolari,
a fronte del caso 3 che e' il caso generale.
(N.B.: in realta' la distinzione tra i casi 1 e 2 e' stata costruita ad
arte a scopo didattico)
 Si potrebbero riassorbire i casi particolari in quello generale,
semplificando cosi' la procedura?
 Si', basta inserire un nodo dummy in testa alla lista!
 Il valore del nodo dummy e' ovviamente irrilevante.
testata
dummy
el.1
•••
el.n

 Il nodo dummy e' sempre presente nella lista, anche quando
questa e' vuota.
53
Eliminazione dei casi particolari
struct node {
int
struct node
-5
value;
*next; };
typedef struct node *sortedIntList;
void listInit(sortedIntList *l) {
*l = malloc(sizeof(struct node));
(*l)->value = 0;
// un valore dummy
(*l)->next = NULL;
}
boolean listEmpty(sortedIntList l) {
return(l->next == NULL);
}
54
Eliminazione dei casi particolari
-6
struct node *ordInsert(sortedIntList l,
int newEl) {
// N.B.: l puo' essere passata per valore perche'
// non c'e' mai necessita' di modificare la
// testata
struct node *s = l;
// individua il nodo precedente il nuovo elemento
while (s->next != NULL
&& s->next->value < newEl) {
s = s->next;
}
struct node *t = malloc(sizeof(struct node));
t->value = newEl;
t->next = s->next;
s->next = t;
return (l);
}
55
Lista Doppiamente Linkata
 Le liste i cui elementi sono collegati da un unico riferimento (link) hanno
diversi problemi. Dato un elemento (il riferimento ad un nodo della lista)
 la lista puo' essere scandita solo in una direzione
(e’ vero? Vedi esercizi!)
 non si puo' conoscere l'elemento precedente quello dato (e.g. per
rimuovere l'elemento dato) se non scandendo tutta la lista
 quindi l'eliminazione di un elemento qualunque della lista (pur
possedendone il riferimento) ha complessita' lineare (O(n))
 Questi problemi sono risolti se
 dotiamo ogni elemento della lista di due riferimenti, uno in avanti e
l'altro all'indietro,
 cosi' che la lista possa essere scandita in entrambe le direzioni.
 In questo modo inserzione e rimozione di un elemento in un punto
dato della lista (in particolare all'inizio e alla fine) hanno sempre
complessita' costante (O(1))
56
Lista Doppiamente Linkata
 Struttura di una lista
 circolare,
 doppiamente linkata,
 con nodo dummy di testata.
testata
lLink
dummy
rLink
lLink
el.1
rLink
lLink
el.2
rLink
lLink
el.n
rLink
57
Lista circolare doppiamente linkata con nodo
dummy di testata
 Esercizio: scrivere in C le procedure per:
 L'inserimento di un elemento in testa e in coda alla lista
 La cancellazione di un elemento in testa e in coda alla lista
 L'eliminazione di un elemento qualunque della lista
(possedendone il riferimento, che e' un parametro di
ingresso alla procedura)
58
Liste e Insiemi
 Esercizio:
 Una lista puo' essere utilizzata per rappresentare un insieme.
 Operazioni tipiche su insiemi sono:
 intersezione
 unione
 inserimento di un elemento in un insieme
 rimozione di un elemento (di cui si indica il riferimento) da un
insieme.
 Definire una rappresentazione tramite lista per insiemi di numeri
interi e scrivere delle funzioni C che realizzino queste operazioni.
 Quale e' la complessita' di queste funzioni?
 Come cambiano le cose a seconda del fatto che le liste siano
mantenute ordinate o meno?
59
Insiemi: altra rappresentazione concreta

Esercizio:
Immaginiamo che l'universo su cui costruiamo i nostri insiemi sia
finito e in effetti abbastanza limitato, e.g.
U = { k  N | 0  k  sizeof(unsigned long long)*8-1 }
 Definire una rappresentazione che non si basi su liste per
insiemi di numeri appartenenti a U e scrivere due funzioni C che
realizzino le operazioni di intersezione e unione.
 Definire anche le operazioni di inserimento e eliminazione di un
elemento.
 Quale e' la complessita' di queste funzioni?
60
Ordinamento di liste per straight insertion
 3 procedure basate su diverse semantiche/modalita' implementative
1. Opera per valore:
 non altera la lista in ingresso, ma
 costrusice una nuova lista ordinata contenente gli stessi
elementi della lista originaria.
Si basa sull'utilizzo dell'ADT lista definito in precedenza
(funzioni car(), cons(), …).
2. Opera per valore come la funzione 1, ma opera direttamente
sulla rappresentazione della lista (che e' diversa da quella
utilizzata nella rappresentazione dell'ADT lista utilizzato per la
funzione 1).
3. Non opera per valore, e riutilizza gli stessi elementi della lista di
ingresso per costruire la lista ordinata.
Opera direttamente sulla rappresentazione.
61
Ordinamento di liste per straight insertion: 1a
list insertSort1(list l) {
return(
null(l) ? l
: sSort(cons(car(l), EMPTYLIST),
cdr(l))
);
}
list sSort(list sed, list unSed) {
return(
null(unSed) ? sed
: sSort(sIns(car(unSed),
sed),
cdr(unSed))
);
}
62
Ordinamento di liste per straight insertion: 1b
list sIns(element e, list l) {
return(
null(l) ? cons(e, l)
: e<=car(l) ? cons(e, l)
: cons(car(l),
sIns(e, cdr(l)))
);
}
63
Ordinamento di liste per straight insertion: 2
struct node {
int
struct node
value;
*next; };
typedef struct node *list;
// vedi pag. 51-53: lista con nodo dummy
list insertSort2(list l) {
list scan = l->next;
list newL = malloc(sizeof(struct node));
newL->value = 0; newL->next = NULL;
while (scan!=NULL) {
newL = ordInsert(scan->value, newL);
// vedi pag. 53
scan = scan->next;
}
return(newL);
}
64
Ordinamento di liste per straight insertion: 3a
struct node { come in insertSort2 };
typedef struct node *list;
list insertSort3(list l) {
list scan = l;
list newL = malloc(sizeof(struct node));
newL->value = 0; newL->next = NULL;
while (scan->next!=NULL) {
struct node*temp = scan->next;
newL = ordInsertM(temp, newL);
}
free(l);
return(newL);
}
65
Ordinamento di liste per straight insertion: 3b
list ordInsertM(struct node *el, list l) {
struct node *scan = l;
while (scan->next!=NULL
&& scan->next->value < el->value) {
scan = scan->next;
}
el->next = scan->next;
scan->next = el;
return(l);
}
66