FONDAMENTI DI INFORMATICA II
Ingegneria Gestionale
a.a. 2001-2002 - 4° Ciclo
Liste
1
Liste
Una lista è una struttura dati (formata da elementi dello
stesso tipo e collegati insieme) la cui lunghezza può
variare dinamicamente.
I suoi elementi sono variabili dinamiche che vengono
creati e/ o distrutti a tempo di esecuzione producendo
una struttura dati che cresce o diminuisce a seconda
delle esigenze del programma in esecuzione.
2
Liste
Ogni elemento di una lista è definito come una
struttura costituita da uno o più campi dati e da un
campo puntatore contenente l’indirizzo dell’elemento
successivo.
struct elem
{ int info;
elem * succ ;
} ;
3
Liste
Ogni lista è definita da una variabile puntatore che
punta al primo elemento della lista.
Nel caso di assenza di elementi (lista vuota) tale
variabile puntatore assume valore NULL.
In una lista il campo puntatore dell’ultimo elemento
assume sempre valore NULL.
4
Liste
lis
lis->info lis->next
Dati
Puntatore
alla lista
Dati
Puntatore al
successivo
struct rec
{
int info;
rec *next;
};
Dati
0
Ultimo
elemento
5
Liste
Allocazione dinamica di liste
L’allocazione dinamica della memoria si presta
alla gestione di liste di oggetti , quando il loro numero
non é definito a priori.
Queste liste possono aumentare e diminuire di
dimensioni dinamicamente in base al flusso del
programma, e quindi devono essere gestite in un modo
più efficiente dell’allocazione di memoria permanente
sotto forma di array
6
Liste
Inserimento in testa:
rec *tempp= new rec;
tempp->info= dato;
tempp
dato
lis
tempp
0
dato
tempp->next= lis;
lis
tempp
0
dato
lis= tempp;
lis
0
7
Liste
Estrazione dalla testa:
rec *tempp= lis;
tempp
lis
0
tempp
lis= lis->next;
lis
0
tempp
tempp->next= NULL;
lis
0
0
8
Liste
Strutture concatenate:
Una struttura é detta concatenata quando é costituita,
oltre che dai suoi normali membri , anche da uno o più
membri aggiuntivi, dichiarati come puntatori alla
struttura stessa.
struct rec
{int info;
rec* next;
};
La definizione di una struttura concatenata é di solito
accompagnata da un certo numero di funzioni , che hanno
il compito di gestirla , cioè eseguire le operazioni di
inserimento , di eliminazione e di ricerca di oggetti.
9
Liste
Liste concatenate:
Una lista concatenata (linked list) é un insieme di
oggetti, caratterizzati dal fatto di essere istanze di una
struttura concatenata .
In ogni oggetto , i membri puntatori alla struttura
contengono l’ indirizzo di altri oggetti della lista ,
creando così un “legame” fra gli oggetti e rendendo la
stessa lista “percorribile”, anche se gli oggetti non sono
allocati consecutivamente in memoria.
Se la struttura possiede un solo membro puntatore a
se stessa, la lista é detta single-linked , se ne possiede
due, é detta double-linked.
10
Liste
Operazioni su liste:
• Creazione della lista (vuota)
• Inserimento in lista
• Inserimento in testa
• Inserimento in coda
• Inserimento in una posizione specifica
• Eliminazione di un nodo dalla lista
• Estrazione da lista
• Lettura di una lista
• Stampa di una lista
• Cancellazione di una lista
11
Liste
Creazione della lista:
Per creare una lista, basta definirla, ovvero è sufficiente
creare il modo di riferirsi ad essa. L’unica cosa che esiste
sempre della lista è la sua testa (o radice) ossia il
puntatore al suo primo elemento.
Questa è l’unica componente allocata staticamente ed è
inizializzata a NULL poiché all’inizio non punta a niente
in quanto non ci sono elementi.
Puntatore
Es.:
alla lista
lis
NULL
rec* lis= NULL ;
lista
12
Liste
Creazione di un nuovo nodo:
La creazione di un nuovo nodo (in qualunque fase
dell’esistenza di una lista) avviene creando una nuova
istanza della struttura tramite allocazione dinamica,
utilizzando di solito un puntatore d’appoggio ( tempp )
Es.:
rec* tempp = new rec;
tempp
info
next
13
Liste
Assegnazione di valori ai campi dati:
L’assegnazione di valori ai campi dati si ottiene
dereferenziando il puntatore al nodo e accedendo ai
singoli dati, ovvero utilizzando direttamente
l’operatore ->
Es.:
tempp-> info= 7;
tempp
7
info
next
14
Liste
Inserimento in lista:
Le operazioni di inserimento di un elemento (ed
analogamente quelle di cancellazione) possono
avvenire secondo diverse modalità, (ovvero in diverse
posizioni della lista) assumendo di volta in volta
caratteristiche specifiche.
15
Liste
Inserimento di un nuovo elemento:
In ogni caso l’inserimento di un nuovo elemento nella
lista prevede sempre i seguenti passi:
1) Creazione di un nuovo nodo
2) Assegnazione di valori ai campi dati
3) Collegamento del nuovo elemento alla lista
esistente
• aggiornamento del campo puntatore del nodo
• aggiornamento dei puntatori della lista
Queste due ultime operazioni caratterizzeranno la
16
tipologia dell’inserimento
Liste
Inserimento in testa:
Le operazioni di collegamento per l’inserimento in
testa, utilizzano il riferimento esplicito alla testa di
lista (il puntatore alla lista lis).
• Il campo next del nuovo nodo punterà allo stesso
valore di lis
• lis punterà al nuovo nodo
tempp-> next= lis;
lis= tempp;
Valido anche per l’inserimento iniziale ( la lista è
vuota)
17
Liste
Inserimento in testa:
Tempp
dato
Tempp
lis
tempp
0
tempp->next= lis;
dato
lis
0
lis
dato
0
Tempp
lis
dato
0
dato
0
0
lis= tempp;
tempp
lis
dato
Tempp
0
lis
18
Liste
Inserimento in coda:
L’inserimento in coda è più complesso, in quanto non
abbiamo un puntatore esplicito all’ultimo elemento,
ma dobbiamo prima scorrere la lista per cercarlo.
Supponiamo di averlo trovato e che sia il puntatore p:
Il campo next del nuovo nodo punterà a NULL (in
quanto è l’ultimo)
Il campo next dell’ex ultimo nodo punterà al
nuovo nodo.
Es.:
tempp-> next= NULL;
p-> next= tempp;
19
Liste
Ricerca dell’ultimo elemento:
Per cercare l’ultimo elemento, possiamo scorrere la
lista tramite un puntatore ausiliario p , inizializzato a
lis.
Es:
rec* p= lis;
while (p-> next != NULL) p= p->next;
Questa ricerca non può però applicarsi a liste vuote!
20
Liste
Ricerca dell’ultimo elemento:
La condizione ( p-> next != NULL ) nel caso la
lista sia vuota conduce ad un errore fatale in quanto p
ha il valore NULL e quindi non consente l’accesso ad
alcuna struttura.
lis
0
p
p-> next
lis
0
p
0
p-> next= ??
Questo è un tipico errore che si fa nella gestione delle
strutture dinamiche!!!
21
Liste
Ricerca dell’ultimo elemento:
La procedura corretta è:
rec* p= lis;
while (p!= NULL && p-> next !=NULL) p= p->next;
lis
0
p
lis
0
p
0
p-> next
22
Inserimento in coda:
Liste
tempp->next= p; (o NULL)
lis
0
p
tempp
dato
0
p->next= tempp;
p-> next
lis
0
p
0
tempp
lis
p
p
dato
0
0
dato
0
lis= tempp;
lis
tempp
dato
tempp
0
23
Liste
Inserimento in una posizione specifica:
L’inserimento in una posizione specifica richiede
preventivamente l’individuazione di tale posizione
all’interno della lista e dipende dalla condizione che si
vuole verificare, per cui dobbiamo prima scorrere la
lista per determinarla.
Vediamo ad esempio come comportarsi per inserire i
valori in ordine crescente.
24
Liste
Inserimento ordinato dei valori:
Nel caso di inserimento in ordine crescente, la lista
risultante deve rimanere in ogni momento ordinata.
Pertanto, all’inserimento di un nuovo valore, si dovrà
scorrere la lista fino alla posizione corretta per
l’inserimento (fin quando cioè il campo info dei nodi
esistenti risulta minore del dato da inserire).
25
Liste
Ricerca di un elemento qualsiasi:
La condizione più sicura da utilizzare in una ricerca è
riferirsi direttamente al puntatore all’elemento nella
condizione di scorrimento. In tal modo però si
sorpassa l’elemento cercato.
Per questo nella ricerca della posizione di inserimento si
usano di solito due puntatori, p e q, che puntano
rispettivamente all’elemento precedente e al successivo.
Es:
rec* q= lis; rec* p= lis;
while (q != NULL && q-> info < tempp-> dato)
{p= q; q= q-> next;}
26
Liste
Ricerca di un elemento qualsiasi:
rec* q= lis; rec* p= lis;
while (q != NULL && q-> info < tempp-> dato)
{p= q; q= q-> next;}
tempp
7
lis
2
8
10 0
2
5
6
p
q
lis
0
p
q
0
27
Liste
Casi particolari:
rec* q= lis; rec* p= lis;
while (q != NULL && q-> info < tempp-> dato)
{p= q; q= q-> next;}
tempp
7
lis
8
9
10 0
p
q
Se all’uscita del while si ha q= =lis, allora p non è il
puntatore all’elemento precedente.
28
Liste
Inserimento ordinato dei valori:
Quindi nel caso generale:
tempp-> next = q;
p-> next = tempp;
ma se q== lis (inserimento in testa)
lis= tempp
29
Liste
Inserimento ordinato dei valori:
tempp->next= q;
tempp
7
lis
2
8
10 0
8
10 0
p
q
p->next= tempp;
tempp
7
lis
2
p
q
30
Liste
Eliminazione di un nodo dalla lista:
L’eliminazione di un nodo dalla lista prevede:
• Ricerca del nodo da eliminare (se necessaria)
• Salvataggio del nodo in una variabile ausiliaria (per
passo 4)
•Scollegamento del nodo dalla lista (aggiornamento dei
puntatori della lista)
• Distruzione del nodo (deallocazione della memoria)
In ogni caso, bisogna verificare che la lista non sia già
vuota!
If (lis != NULL) ….
31
Liste
Ricerca del nodo da eliminare:
Dipende dalle esigenze del programma.
Come per l’inserimento, il caso più semplice è
costituito dall’eliminazione del nodo di testa, in
quanto esiste il puntatore lis a questo elemento.
Negli altri casi, si procede come per l’inserimento
32
Liste
Scollegamento del nodo dalla lista:
Individuato il nodo, bisogna evitare che la sua
rimozione spezzi la lista.
lis
0
lis
0
lis
0
In generale, è necessario aggiornare il puntatore
next dell’elemento precedente.
33
Liste
Eliminazione del nodo di testa:
Bisogna aggiornare il puntatore alla testa lis che
dovrà puntare al nodo successivo a quello da
eliminare.
rec* tempp= lis; (salvataggio nodo da
eliminare)
lis = tempp-> next; (aggiornamento lista)
delete tempp; (distruzione nodo)
34
Liste
Eliminazione del nodo di coda:
Bisogna aggiornare il campo next relativo al penultimo
nodo, che ora diventa l’ultimo (e quindi assume valore
NULL).
Per la ricerca dell’ultimo elemento si usano due
puntatori p e q , che puntano rispettivamente al
penultimo e all’ultimo elemento.
La condizione sarà:
rec* q= lis; rec* p= lis;
while (q != NULL && q-> next != NULL)
{p= q;q= q-> next;}
Casi particolari: l’elemento da eliminare è l’unico della
lista.
35
Liste
Eliminazione del nodo di coda:
rec* q= lis; rec* p= lis;
while (q != NULL && q-> next != NULL)
{p= q;q= q-> next;}
lis
0
p
q
Se all’uscita del while si ha q=
=lis, allora p non è il puntatore
all’elemento precedente.
lis
0
p
q
36
Liste
Eliminazione del nodo di coda:
tempp
lis
rec *tempp= q;
0
p
q
tempp
p->next= tempp->next;
oppure:
p->next= NULL;
lis
0
0
p
q
37
Liste
Eliminazione del nodo di coda:
tempp
lis
rec* tempp= q;
0
p
q
Lis= tempp->next;
oppure
lis= NULL;
tempp
lis
0
0
p
q
38
Liste
Lettura di una lista da tastiera
rec* LeggiListaR() {
int val; cin >> val;
if (val == 0) return NULL;
else {
rec* l = new rec;
l-> info = val;
l-> next = LeggiListaR();
return l;
}
}
Lettura lista
Versione ricorsiva
rec* LeggiListaI( ) {
int val; cin >> val;
if (val == 0) return NULL;
else {
rec* l = new rec;
l-> info = val;
rec* ll = l; cin >> val;
while (val != 0) {
ll-> next = new rec;
ll = ll-> next;
ll-> info = val; cin >>
val;
}
ll-> next = NULL;
return l;
}
}
Lettura lista
Versione 39
iterativa
Liste
Stampa di una lista
void StampaListaR( rec* l)
{
if (l == NULL) cout <<
endl;
else {
cout << l-> info << ’ ’;
StampaListaR( l-> next);
}
}
Stampa lista
Versione ricorsiva
void StampaListaI( rec* l)
{
while (l != NULL) {
cout << l-> info << ’ ’;
l = l-> next;
}
cout << endl;
}
Stampa lista
Versione iterativa
40
Liste
Cancellazione di una lista
void CancellaListaR( rec*& l)
{
if (l != NULL) {
CancellaListaR( l-> next);
delete l;
l = NULL;
}
}
Cancellazione Lista
Versione ricorsiva
void CancellaListaI( rec*&
l)
{
while (l != NULL) {
rec* ll = l;
l = l-> next;
delete ll;
}
l = NULL;
}
Cancellazione lista
Versione iterativa
41
Liste
Esempio
#include <iostream. h>
struct rec {
int info;
rec* next;
};
void main()
{
rec* lis;
lis = LeggiListaR();
StampaListaR( lis);
CancellaListaR( lis);
lis = LeggiListaI();
StampaListaI( lis);
CancellaListaI( lis);
}
Programma chiamante
42
Liste
Inserimento in lista
void instesta( rec*& lis,
int a)
{
rec* p = new rec;
p-> info = a;
p-> next = lis;
lis = p;
}
Inserimento in testa
void insfondo( rec*& lis, int a)
{
rec* p = lis;
for (rec* q = p; q != NULL; q = q->
next)
p = q;
q = new rec;
q-> info = a;
q-> next = NULL;
if (p != NULL)
p-> next = q;
else
lis = q;
}
Inserimento in43 coda
Liste
Inserimento in ordine crescente (campo info)
void inscresc( rec*& lis, int a)
{
rec* p = lis;
for (rec* q = p; q != NULL && q-> info < a; q = q-> next)
p = q;
rec* r = new rec;
r-> info = a;
r-> next = q;
if (q != lis)
p-> next = r;
else
lis = r;
}
Inserimento in ordine crescente
44
Liste
Estrazione da lista
BOOL esttesta( rec*& lis, int& a)
{
rec* p = lis;
if (lis != NULL) {
a = lis-> info;
lis = lis-> next;
delete p;
return T;
}
return F;
}
Estrazione dalla testa
45
Liste
Estrazione da lista
BOOL estfondo( rec*& lis, int& a)
{
rec* p = lis;
if (lis != NULL) {
for (rec* q = p; q-> next != NULL; q = q-> next)
p = q;
a = q-> info;
if (q == lis)
lis = NULL;
else
p-> next = NULL;
delete q;
return T;
}
return F;
}
Estrazione dal fondo
46
Liste
Estrazione da lista
BOOLEAN togli( rec*& lis, int a)
{
rec* p = lis;
for (rec* q = p; q != NULL && q-> info != a; q = q-> next)
p = q;
if (q != NULL) {
if (q == lis)
lis = p-> next;
p-> next = q-> next;
delete q;
return T;
}
return F;
}
Estrazione di un elemento specifico
47
Liste
Inserimenti in versione ricorsiva
void insfondoR( rec*& lis, int a)
{
if (lis != NULL)
insfondoR( lis-> next, a);
else {
rec* p = new rec;
p-> info = a;
p-> next = NULL;
lis= p
}
}
Inserimento in fondo
Versione ricorsiva
void inscrescR( rec*& lis, int
a)
{
if (lis != NULL && lis-> info
< a)
inscrescR( lis-> next, a);
else {
rec* p = new rec;
p-> info = a;
p-> next = lis;
lis= p
}
}
Inserimento in ordine
48
Versione ricorsiva
Liste
Estrazioni in versione ricorsiva
BOOL estfondoR( rec*& lis, int& a)
{
if (lis != NULL) {
if (lis-> next != NULL)
return estfondoR( lis-> next, a);
else {
a= lis-> info;
delete lis;
lis = NULL;
return T;
}
}
else return F;
}
Estrazione dal fondo
Versione ricorsiva
BOOL togliR( rec*& lis, int a)
{
if (lis != NULL) {
if (lis-> info != a)
return togliR( lis-> next,
a);
else {
rec* p = lis;
lis = lis-> next;
delete p;
return T;
}
}
else return F;
} Estrazione di un elemento
specifico - Versione
49
ricorsiva