Struttura di una lista legata
Una lista legata è una variabile strutturata in cui ogni
elemento mantiene l’indirizzo (mediante un puntatore)
dell’elemento successivo.
Ogni elemento della struttura viene detto nodo.
Tutti i nodi della struttura sono implementati come variabili
dinamiche.
La figura seguente è un esempio di rappresentazione
grafica di una lista.
p4 è il puntatore nullo:
non punta a niente
Pk
giallo
p1
bleu
p2
rosso
p3
nero
p4
p4 è il puntatore nullo:
non punta a niente
Pk
giallo
p1
bleu
p2
rosso
p3
nero
p4
In questo esempio Pk è il puntatore alla lista, ogni nodo della lista è
composto da un dato e da un puntatore al nodo successivo: (giallo, p1)
(bleu, p2) (rosso, p3) (nero, p4). La stessa situazione può essere
descritta con la tabella seguente:
TIPO
CONTENUTO
OSSERVAZIONI
INDIRIZZO
0x0064fdf0
Nodo
giallo
p1= 0x0064fe0f
p1 = indirizzo prossimo nodo
0x0064fe0f
Nodo
bleu
p2= 0x0064fe07
p2= indirizzo prossimo nodo
0x0064fe07
Nodo
rosso
p3= 0x0064fff0
p3=indirizzo prossimo nodo
0x0064fff0
Nodo
Nero
P4=0 o NULL
p4= fine della lista
Una lista lineare legata è una collezione di oggetti (gli
elementi della lista o nodi) definiti dinamicamente, uniti
insieme da puntatori. Ogni singola variabile puntatore è
costituita da almeno due campi: il primo contiene
l’informazione,
il
secondo
l’indirizzo
dell’elemento
successivo.
Nodo: è una variabile dinamica che costituisce l’elemento
della lista legata.
Pk
giallo
p1
bleu
p2
rosso
p3
nero
p4
Dalla definizione emerge chiaramente che per gestire una
lista è sufficiente conoscere il puntatore al suo primo
elemento.
Il nodo è una variabile strutturata di tipo struct in cui uno dei
campi è formato da un puntatore al prossimo nodo:
chiameremo campo next tale campo, mentre gli altri dati
della struct li indicheremo come campo dati (esso conterrà
le informazioni specifiche).
In questo modo tutti i nodi sono collegati insieme per
formare il dato strutturato denominato lista.
Pk
giallo
p1
bleu
p2
rosso
p3
nero
p4
Supponiamo di voler costruire la lista sottostante;
per implementarla in C++ definiamo il tipo Tnodo:
struct Tnodo
{
char nome[10];
Tnodo* next;
}
.
Pk
giallo
p1
bleu
p2
rosso
p3
nero
p4
Una tipica lista inizia con una variabile puntatore al nodo e
termina con il puntatore nullo. Nell’esempio in figura Pk
punta al primo nodo posto all’inizio della lista; per accedere
a tale nodo basta dereferenziare pk .
(*pk).nome contiene il nome di 10 caratteri della struttura
Tnodo
(*pk).next contiene l’indirizzo del nodo successivo.
La struttura Tnodo, in questo esempio, è
costituita da un array di 10 caratteri e da un
puntatore next al prossimo nodo; è
opportuno notare come il puntatore punta
ad un tipo che viene definito in quello stesso
momento.
struct Tnodo
{
char nome[10];
Tnodo* next;
}
Pk
anna
p1
ugo
p2
ciro
p3
dario
p4
In luogo della scrittura precedente si utilizza la seguente in
cui non appare il simbolo * di derenfereziazione:
pk->nome
pk->next
Il simbolo -> viene detto operatore freccia: esso si applica al
puntatore della struttura e non alla variabile che denota la
struttura.
Implementazione di una lista legata
Una lista può essere paragonata ad un insieme, i cui
elementi sono i nodi della lista (o, meglio, il campo
informazione del nodo). Le prime operazioni da introdurre in
un insieme sono: inserimento, cancellazione, ricerca.
Come primo passo introduciamo un semplice esempio di
nodo a cui fare riferimento. A questo scopo, per
semplificare,
riteniamo
opportuno
prendere
come
informazione base del nodo un numero intero; avremo
quindi
struct Tnodo {
int
info;
Tnodo
*next;
};
typedef Tnodo* Pnodo;
Con typedef Tnodo* Pnodo abbiamo definito un nuovo tipo, Pnodo, che
rappresenta un puntatore a Tnodo.
Il nodo della lista legata lineare è costituito da un campo info, in questo
caso un intero, e da un campo next che contiene un puntatore alla
struttura Tnodo. Vogliamo creare un nodo nella memoria heap con
queste caratteristiche.
Temp
info
next
NULL
Temp
è di tipo PNodo
è un intero
è di tipo PNodo
non punta a niente
info next
NULL
struct Tnodo {
int info;
Tnodo
*next;
};
typedef Tnodo* Pnodo;
Scriviamo una procedura CreaNodo che ha in input l’informazione info e che
restituisce il puntatore Temp del nodo creato:
void CreaNodo(int info1, Pnodo& Temp)
{
Temp= new Tnodo;
Temp->info=info1;
Temp->next=NULL;
}
Se la lista è vuota inseriamo il nodo appena creato come primo elemento;
per ottenere tale risultato poniamo L = Temp, dove L è ovviamente di tipo
Pnodo.
L
Temp
8
next
NULL
Pnodo L,Temp;
L=NULL;
int info1;……………………
info1=8;
CreaNodo(info1, Temp)
if (L==NULL) L=Temp;
Se la lista non è vuota, ma contiene già qualche elemento,
possiamo decidere se inserire il nuovo nodo in testa o in
coda.
Volendo inserire il nuovo nodo in testa, cioè all’inizio della
lista, potremmo porre ancora L =Temp; in questo caso, però,
perderemmo il contenuto di L.
I passi da fare sono allora:
conservare il valore di L in Temp->next e successivamente
porre L=Temp
Lista di partenza
L
8
3
11
NULL
Nuovo nodo
NULL
6
Temp
Temp
L
Nuova lista
6
L
8
3
11
NULL
Pnodo Insert (int info1, Pnodo L) {
//E’una funzione che inserisce l'elemento in testa alla lista
Pnodo Temp;
CreaNodo(info1, Temp);
Temp->next=L;
return Temp;
}
Scriviamo ora una procedura che, assegnato un nodo con
puntatore Temp ed una lista L, inserisce il nodo Temp in
coda alla lista L.
Osserviamo che
se la lista è vuota allora è sufficiente creare il nodo con
puntatore L;
se la lista non è vuota dobbiamo scorrerla tutta fin quando il
puntatore corrente raggiunge NULL.
Attenzione che nel momento in cui viene raggiunta la fine
della lista si perde il legame con la lista stessa in quanto
non si conosce il puntatore al nodo precedente.
La freccia verso il basso rappresenta un puntatore a NULL; se
conserviamo il puntatore precedente (PREC) ed il valore del puntatore
corrente (CURR) è NULL, allora per mantenere la lista linkata dobbiamo
porre:
PREC->next=Temp
Lista di partenza
L
8
3
11
NULL
Nuovo nodo
L
8
Nuova lista
NULL
6
Temp
3
11
PREC
6
CURR
NULL
La procedura che inserisce un nodo in coda ha la seguente intestazione
void InsertCoda(int info1,Pnodo &L );
con la seguente descrizione
if L==NULL
Creanodo(info1,L)
else
scorri tutta la lista finché non
raggiungi la fine, conservando sia il
nodo precedente (PREC) che quello
corrente (CURR);quando hai raggiunto
la fine esegui
CreaNodo(info1,PREC->next)
La parte evidenziata in corsivo rappresenta un ciclo che ha questa
struttura:
inizializzazione: curr=L e prec=NULL;
condizione del ciclo: while (curr != NULL)
corpo del ciclo: prec=curr e curr=curr->next
In definitiva si ha
void InsertCoda(int info1,Pnodo &L)
{
Pnodo prec, curr;
if (L==NULL)
CreaNodo(info1, L);
else {
curr=L; prec=NULL;
while (curr!=NULL) {
prec=curr;
curr=curr->next;
}
CreaNodo(info1, prec->next);
}
}
Introduciamo ora la funzione Insert che permette di
aggiungere un elemento all’interno della lista dopo un
preassegnato nodo individuato dal suo puntatore.
Supponiamo di dover inserire il nodo nella lista L dopo il
nodo avente come puntatore P. tra gli elementi 8 ed 3, e che
il puntatore del nodo con item 8 è L. A questo scopo basta
porre
Temp->next = P->next
e P->next = Temp
Pnodo Insert (int info1, Pnodo P, Pnodo &L) {
/*Inserisce l'elemento all’interno della lista
dopo il nodo puntato da P */
Pnodo Temp;
CreaNodo(info1, Temp);
Temp->next=P->next;
P->next=Temp;
return L;
}
Pnodo Insert (int info1, Pnodo P, Pnodo &L) {
/*Inserisce l'elemento all’interno della lista
dopo il nodo puntato da P */
Pnodo Temp;
CreaNodo(info1, Temp);
Temp->next=P->next;
P->next=Temp;
return L;
}
P
Lista di partenza
Nuovo nodo
L
8
Nuova lista
L
8
3
6
Temp
3
next
next
11
NULL
NULL
next
6
11
NULL
Scriviamo ora una funzione inserisciNodoMezzo nel caso in cui
si deve aggiungere un elemento all’interno della lista dopo una
determinata chiave.
Dovremo prima cercare la chiave se esiste, e quindi inserire il
nodo come prima.
void inserisciNodoMezzo( int info1,Pnodo &L)
{// inserisce un nuovo nodo in mezzo alla lista
int inf;
Pnodo prec, curr, Temp;
cout<<"Dammi valore nodo ";
cin>>inf;cout<<endl;
if (L==NULL)
creaNodo(info1, L); // caso lista vuota
else
{
curr=L; prec=NULL;
while ((curr->info!=info1)&&(curr->next!=NULL)
{ prec=curr;
// cerco la chiave
curr=curr->next; }
if (curr->next!=NULL) // chiave trovata nel mezzo
{ creaNodo(inf, Temp);
Temp->next=curr->next;
curr->next=Temp; }
if ((curr->info==info1)&&(curr->next==NULL))
{ creaNodo(inf, Temp); // chiave trovata alla fine
curr->next=Temp; }
}
}
Utilizziamo due puntatori:
curr e prec che individuano il
puntatore di scorrimento
della lista L (curr) e il
puntatore dell’elemento
immediatamente precedente
(prec).
Se e quando curr->info è
uguale all’info dopo del quale
vogliamo porre il nuovo
nodo, allora operiamo come
nel caso di inserimento noto
il puntatore che ora sarà curr.
Analizziamo ora la cancellazione di un nodo da una lista L.
Per poter cancellare un nodo contenente un dato valore dobbiamo:
•
•
cercare il nodo all’interno della lista
cancellare il nodo con delete mantenendo il legame dentro la lista.
La procedura CancellaNodo, scritta in modo ricorsivo, ha la seguente
struttura
void CancellaNodo(Pnodo &L, int info1)
if (L!=NULL)
if (L->info=info1)
cancella mantenendo il legame nella lista
else
richiama la funzione col nodo successivo
Per poter eseguire il punto 2 è necessario
• conservare il puntatore L in un’altra variabile Temp
• porre L=L->next
• cancellare la memoria a cui punta Temp
Tenendo presente queste osservazioni possiamo scrivere la procedura
CancellaNodo come segue.
void CancellaNodo(Pnodo &L, int info1)
{
Pnodo Temp;
if (L!=NULL)
{
if (L->item==info1) {
Temp=L;
L=L->next;
delete Temp;
}
else
CancellaNodo(L->next, info1);
}
}
// PROTOTIPI
void costruisciLista(Pnodo &);
void stampaLista(Pnodo L)
void stampaLista(Pnodo );
{ while (L!=NULL){
void creaNodo (int, Pnodo&);
cout<<" "<<L->info;
Pnodo inserisciNodoTesta (int,Pnodo );
L=L->next;}
void inserisciNodoCoda (int,Pnodo &);
}
void inserisciNodoMezzo (int,Pnodo &);
void cancellaNodo (int,Pnodo &);
void costruisciLista(Pnodo &L)
{Pnodo nodo;
int item;
string NomeIn, NomeOut;
ifstream filista;
Pnodo inserisciNodoTesta
ofstream outlista;
( int info1,Pnodo L)
NomeIn="L5.txt";
{// inserisce un nuovo nodo
filista.open(NomeIn.c_str());
in testa alla lista
if (!filista)
Pnodo Temp;
{ cerr<<"Non si puo' aprire il file"<<endl;
creaNodo(info1, Temp);
system("pause"); }
Temp->next=L;
filista>>item;
return Temp;
creaNodo(item,L);
}
while (!filista.eof())
{ filista>>item;
inserisciNodoCoda(item,L);
}
}
void inserisciNodoCoda ( int info1,Pnodo &L)
{// inserisce un nuovo nodo in coda alla lista
Pnodo prec, curr;
if (L==NULL)
creaNodo(info1, L);
else {
curr=L; prec=NULL;
while (curr!=NULL) {
prec=curr;
curr=curr->next;
}
creaNodo(info1, prec->next);
}
}
void inserisciNodoMezzo( int info1,Pnodo &L)
{// inserisce un nuovo nodo in mezzo alla lista
int inf;
Pnodo prec, curr, Temp;
cout<<"Dammi valore nodo ";
cin>>inf;cout<<endl;
if (L==NULL)
creaNodo(info1, L);
else {
curr=L; prec=NULL;
while ((curr->info!=info1)&&(curr->next!=NULL))
{prec=curr;
curr=curr->next;
}
if (curr->next!=NULL)
{ creaNodo(inf, Temp);
Temp->next=curr->next;
curr->next=Temp;
}
if ((curr->info==info1)&&(curr->next==NULL))
{ creaNodo(inf, Temp);
curr->next=Temp;
}
}}
Una procedura iterativa è invece la seguente
void CancellaNodo(Pnodo &L, int info1)
{
Pnodo prec=NULL;
if ((L->next!=NULL)&(L->info!=info1))
{prec=L;
L=L->next;}
if (L->next!=NULL){
prec->next=L->next;
delete L;
}
else
cout<<“ nodo non trovato “<<endl;
}
}
Nell’allegato liste.cpp è riportato un codice per il trattamento
delle liste legate con le seguenti funzioni:
void costruisciLista(Pnodo &); //costruisce una lista a partire da un file testo
void stampaLista(Pnodo ); //stampa una lista
void creaNodo (int, Pnodo&); //crea un nodo
Pnodo inserisciNodoTesta (int,Pnodo &); // inserisci un nodo in testa
void inserisciNodoCoda (int,Pnodo &); // inserisci un nodo in coda Pnodo
void inserisciNodoMezzo (int,Pnodo &); // inserisci un nodo nel mezzo
void cancellaNodo (int,Pnodo &); // cancella un nodo
void cercaItem(int ,Pnodo ,Pnodo &); // cerca un nodo con una data info
bool listaVuota(Pnodo); // verifica se una lista è vuota
int cercaPosizione(int, Pnodo); // cerca la posizione lungo la lista di un dato nodo
int contaNodi(Pnodo); // conta quanti nodi ha la lista