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 a lato è un esempio di rappresentazione grafica di una lista.
Struttura di una lista legata (segue)
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 a lato.
Struttura di una lista legata (segue)
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.
Struttura di una lista legata (segue)
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.
Struttura di una lista legata (segue)
Supponiamo di voler costruire la lista a lato;
per implementarla in C++ definiamo il tipo Tnodo:
struct Tnodo {
char nome[10];
Tnodo* next;
}
Struttura di una lista legata (segue)
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.
struct Tnodo {
char nome[10];
Tnodo* next;
}
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.
Struttura di una lista legata (segue)
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;
Implementazione di una lista legata (segue)
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 è di tipo PNodo
info è un intero
next è di tipo PNodo
NULL non punta a niente
struct Tnodo {
int info;
Tnodo *next;
};
typedef Tnodo* Pnodo;
Implementazione di una lista legata (segue)
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 (vedi figura a lato).
Implementazione di una lista legata (segue)
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
Implementazione di una lista legata (segue)
Implementazione di una lista legata (segue)
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.
Implementazione di una lista legata (segue)
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
Implementazione di una lista legata (segue)
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)
Implementazione di una lista legata (segue)
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);
}
}
Implementazione di una lista legata (segue)
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;
}
Implementazione di una lista legata (segue)
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;
}
Implementazione di una lista legata (segue)
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.
Implementazione di una lista legata (segue)
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.
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
Cancellazione di un nodo da una lista L
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 riportata nella figura a lato.
Funzioni
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
