Fondamenti di Informatica II
Ingegneria Informatica (A-I)
Prof. M.T. PAZIENZA
a.a. 2003-2004 – 3° ciclo
Liste
Una lista è una struttura dati ricorsiva (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.
E’ possibile implementare liste anche tramite array, ma ciò
può avvenire solo quando si conoscono esattamente le
dimensioni della lista.
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;
};
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.
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.
Liste
lis-> info
lis
Puntatore alla
(testa di)
lista
Dati
lis->next
Dati
Puntatore al
sucessivo
Dati
0
Puntatore
all’ultimo
elemento
struct rec
{
int info;
rec* next;
};
Tipi di Lista
Lista circolare (l’ultimo puntatore non ha valore NULL,
ma punta al primo nodo)
Lista doppia (può essere visitata nei due sensi ->
presenza di due puntatori per nodo)
Lista doppia circolare (il puntatore all’elemento
successivo dell’ultimo nodo punta al primo elemento
della lista e il puntatore all’elemento precedente del
primo punta all’ultimo elemento della lista)
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
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.
Inserimento in testa
rec* tempp= new rec;
tempp->info = dato;
tempp
dato
lis
tempp
0
dato
tempp->next = lis;
lis
lis = tempp;
tempp
lis
0
dato
0
Estrazione dalla testa
tempp
rec* tempp= lis;
lis
tempp
lis = lis->next;
lis
tempp
tempp->next = NULL;
lis
0
Operazioni su liste
•
•
•
•
Creazione della lista (vuota e successivi inserimenti)
Lettura di una lista
Stampa di una lista
Cancellazione di una lista
• Inserimento in lista
• Estrazione da lista
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(creazione della lista)
non punta a niente in quanto non ci sono elementi.
Es.:
lis NULL
rec* lis=NULL;
Puntatore
alla lista
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
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
Lettura di una lista
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;
Nodo lista
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 iterativa
}
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;
}
Nodo lista
Stampa lista
versione iterativa
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;
}
Nodo lista
Cancellazione lista
versione iterativa
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
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.
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 (allocazione dinamica)
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 tipologia
dell’ inserimento
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
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
Inserimento in testa
Il caso più semplice è costituito dall’ inserimento in testa,
in quanto si dispone di un riferimento esplicito a questa (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;
NB. Funziona anche se la lista è vuota!
Inserimento in testa
tempp
tempp
dato
lis
dato
lis 0
0
tempp->next = lis;
tempp
tempp
dato
lis
0
lis
dato 0
0
lis = tempp;
tempp
lis
tempp
dato
0
lis
dato 0
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;
La lista vuota va gestita come un caso particolare!
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;
Dove è l’errore ??
Ricerca dell’ultimo elemento
La condizione (p->next != NULL) nel caso la lista sia
vuota conduce ad un errore fatale in quanto si sta
dereferenziando un puntatore nullo.
lis
0
lis 0
p 0
p
p->next
p->next = ??
Questo è un tipico errore che si fa nella gestione delle
strutture dinamiche!!!
Ricerca dell’ultimo elemento
La procedura corretta è:
rec* p= lis;
while(p!=NULL && p->next!= NULL) p=p->next;
lis
0
lis 0
p 0
p
p->next
Inserimento in coda
tempp->next = p; (o NULL)
lis
0
lis 0
p 0
p
tempp
dato 0
p->next = tempp;
dato 0
lis = tempp;
lis
lis
p 0
p
tempp
tempp
dato 0
tempp
dato 0
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.
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).
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;}
Ricerca di una posizione specifica
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
0
p
q
lis
p
q 0
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
p
q
Se q==lis allora p non contiene
l’elemento precedente
lis 0
p 0
q 0
10
0
Inserimento ordinato dei valori
Quindi nel caso generale:
tempp-> next = q;
p->next = tempp;
ma se q==lis (inserimento in testa)
lis=tempp
Inserimento ordinato dei valori
tempp
tempp->next=q
lis
7
2
8
10
0
8
10
0
p
q
tempp
p->next =tempp
lis
p
q
7
2
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 in coda
Inserimento in ordine crescente (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
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 inizialmente che la lista non sia già
vuota!
if (lis != NULL)
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
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
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)
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)
q=q->next;}
{p=q;
Casi particolari: l’elemento da eliminare è l’unico della lista.
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 q==lis allora p non contiene
l’elemento precedente
lis
p
q
0
Eliminazione del nodo di coda
tempp
rec* tempp =q;
lis
0
p
q
tempp
p->next =
tempp->next;
oppure
p->next = NULL;
lis
p
q
0
0
Eliminazione del nodo di coda
rec* tempp = q;
tempp
lis
0
p
q
lis = tempp->next;
oppure
lis = NULL;
tempp
lis
p
q
0
0
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
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
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
Inserimento in lista
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
versione ricorsiva
Estrazione da lista
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 ricorsiva