Liste Ordinate
Liste Invasive vs Liste non Invasive.
Dato un tipo T che per generalità supponiamo sia una struttura, possiamo creare una lista di oggetti di tipo T in due modi:
- Nel modo “invasivo”, si modifica la dichiarazione del tipo T, ed in particolare si aggiunge alla struttura un puntatore next, che punta all’elemento successivo nella lista, tale campo viene appunto aggiunto, modificando la dichiarazione della struttura originaria. Notiamo che quindi, non abbiamo più un semplice tipo T, ma piuttosto un tipo “membro di lista di T”.
- Nel modo “non invasivo” non viene modificato il tipo T, ma viene creato un nuovo tipo che servirà a rappresentare oggetti “elemento di lista di T”, oltre al tipo T originario.
Esempio, supponiamo di dover rappresentare punti in $$R^2$$, possiamo usare una struttura
[cpp]
// tipo Point2d
typedef struct 2dpoint { double x,y; } Point2d;
// Versione invasiva di una lista di Point2d singolarmente linkata
typedef struct 2dpointl {
double x,y;
struct 2dpointl *next;
} ListPoint2d_invasiva;
// Versione *non invasiva*
typedef struct l {
Point2d point;
struct *l next;
} ListPoint2d_noninvasiva;
[/cpp]
Notiamo che nel secondo caso, non abbiamo bisogno di modificare la struttura Point2d che potrebbe essere stata già usata nel codice e che magari non vogliamo cambiare. Se invece non abbiamo vincoli di questo tipo, possiamo usare la versione invasiva che include il puntatore per realizzare la lista direttamente dentro la definizione di punto (la versione non invasiva è però matematicamente più elegante perche distingue chiaramente tra il tipo punto2d ed il tipo list_of_point2d, che sono ovviamente concetti diversi.).
Per semplicità nel seguito useremo liste invasive, quindi definiremo insieme sia i campi che rappresentano le informazioni sia i puntatori che servono a collegare gli elementi della lista.
Liste Bidirezionali, e Circolari
Dato un elemento p, il campo next di p, indica quale sia l’elemento che segue p nella lista. Notiamo che spesso è utile poter muoversi anche all’indietro, e questo è semplice da realizzare basta includere un altro campo puntatore che possiamo chiamare prev. Esempio:
[cpp]
// lista bidirezionale
typedef struct p {
double x,y;
struct p *prev, *next; //next punta al successivo, prev al precedente;
} LinkedPoint2d;
[/cpp]
Una particolare versione di lista bidirezionale, detta lista circolare può essere molto utile. Tale lista soddisfa i seguenti requisiti: il successore dell’ultimo elemento è il primo elemento della lista, ed il predecessore del primo elemento è l’ultimo. In codice si ha:
[cpp]
// se head punta alla testa della lista
// e tail punta all’ultimo elemento della lista
// la lista è circolare se è vero:
assert(head->prev == tail && tail->next == head);
//
[/cpp]
Costruttori e Distruttori
La gestione delle liste deve essere fatta con un approccio bottom-up, si scrivono quindi delle funzioni elementari per implementare le operazioni di inserimento, cancellazione, ricerca degli elementi, e si usano queste per poter poi manipolare le liste.
Il costruttore di un tipo di dato, è una funziona che costruisce (con la malloc) un elemento e lo inizializza correttamente. Il distruttore invece ha la responsabilità di distruggere l’elemento.
Esempio:
[cpp]
// associazione tra parole e un intero, molto utile, utilizzi:
// wordstat: word e’ una parola e value e’ il conteggio delle occorrenze
// compilatore o interprete: word e’ una variabile intera e value e’ il suo valore.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct item {
char *word;
int value;
struct item *next;
} LinkedWord;
// Costruttore
LinkeWord* new_word(const char* s, int v)
{
LinkedWord *n = malloc(sizeof(LinkedWord)); // creo l’lemento
n->word = malloc(strlen(s)+1); // creo la stringa
strcpy(n->word,s); // metto a posto i campi
n->value = v;
n->next = NULL;
return n;
}
// Distruttore
void delete_word(LinkedWord *p)
{
// prima distruggiamo la stringa poi l’lemento
free(p->word); free(p);
}
void print_word(LinkedWord *p)
{
if (p==NULL) return;
printf("(%s,%d)",p->word,p->value);
}
// uso:
int main(void)
{
LinkedWord *a = new_word("Mario",10);
LinkedWord *b = new_word("Paolo",20);
LinkedWord *c = new_word("Giovanna",30);
// notiamo che non sono ancora collegati, non abbiamo ancora pensato a gestirli come liste
print_word(a); printf("\n");
print_word(b); printf("\n");
print_word(c); printf("\n");
delete_word(a);
delete_word(b);
delete_word(c);
return 0;
}
[/cpp]
Funzioni per Inserimento, Cancellazione, Ricerca di un elemento.
Normalmente le liste vengono utilizzate manipolando un puntatore che rappresenta la testa della lista. La funzione insert può assumere varie forme a seconda dei requisiti che la lista deve soddisfare. In alcuni casi ci possono essere varie funzioni insert, ad esempio per inserire un elemento all’inizio della lista, o per appenderlo, in fondo alla lista, o se ad esempio vogliamo inserire l’elemento in un punto specifico perche la lista deve soddisfare requisiti di ordinamento.
Versione semplice, inseriamo in testa:
[cpp]
LinkedWord* add_head(LinkedWord *testa, const char *string, int v)
{
LinkedWord *n = new_word(string,v);
n->next = testa; // va bene anche se testa == NULL
return n;
}
[/cpp]
Esempio (modificate il programma sopra):
[cpp]
// funzioni precedenti.
void print_list(LinkedWord *testa)
{
for(LinkedWord*l=testa; l!=NULL; l=l->next) {
print_word(l); printf("->");
}
printf("null\n");
}
// uso:
void destroy_list(LinkedWord *testa)
{
LinkedWord*l = testa;
LinkedWord *p;
while (l != NULL) {
// nota bene: leggiamo p->next prima di distruggere
p = l->next;
delete_word(l);
// ok, l diventa p : l = l->next
l = p;
}
}
int main(void)
{
LinkedWord *lista = NULL;
lista = add_head(lista,"Mario",10);
lista = add_head(lista,"Paolo",20);
lista = add_head(lista,"Giovanna",20);
print_list(lista);
destroy_list(lista);
return 0;
}
[/cpp]
Prima di occuparci di una versione generale della insert (o add) vediamo come cercare un elemento e come cancellarlo. Nel caso della find possiamo implementare l’algoritmo in forma iterativa o ricorsiva, cominciamo con la versione ricorsiva, molto semplice.
[cpp]
// find versione ricorsiva
LinkedWord *find_list_rec(const LinkedWord *list, const char *string)
{
if (list == NULL) return NULL;
if ( strcmp(list->word, string) == 0) return list;
else return find_list_rec(list->next,string);
}
// find versione iterativa
LinkedWord *find_list_iter(const LinkedWord *list, const char *string)
{
while (list!=NULL)
if (strcmp(list->word,string)==0)
return list;
else list = list->next;
}
[/cpp]
Notiamo che le due versioni sono comunque semplici, e che la seconda versione può essere facilmente ottenuta dalla prima seguendo uno schema generale chiamato “Trasformazione della ricorsione in coda“.
Tale schema può essere applicato a tutte le funzioni ricorsive che hanno un unica chiamata ricorsiva presente come ultima istruzione della funzione. Tale chiamata, implica evidentemente un esecuzione che riparte dall’inizio del corso della funzione, pertanto può essere sostituita da un while che ingloba tutto il corpo: naturalmente per essere semanticamente equivalenti, si devono gestire in modo corretto i cambiamenti di stato delle variabili: nella chiamata ricorsiva, si passa il resto della lista (l->next), e pertanto nella versione iterativa si aggiornerà list con list=list->next, notiamo che possiamo senza problemi cambiare tale variabile dentro la funzione perche, visto che il passaggio dei parametri è per valore, esso è solo una copia del parametro formale e il suo cambiamento non verrà visto dal chiamante.
Prima di vedere un possibile esempio per la ricerca, vediamo di preoccuparci anche delle cancellazioni che sono in genere una faccenda più delicata, il problema è legato al fatto che in una lista singolarmente linkata noi non possiamo “tornare indietro”, quindi se cerchiamo un elemento muovendo un puntatore fin quando una certa condizione è vera, allora quel puntatore per definizione si fermerà e punterà all’elemento che ci interessa cancellare, ma per farlo dovremmo modificare l’elemento precedente che contiene proprio un suo riferimento.
Soluzione: se si fanno molte cancellazioni, allora conviene usare liste doppiamente linkate, cosi da poter accedere da ogni punto della lista, sia al successivo che al precedente. oppure nel nostro caso, possiamo tenere un puntatore ausiliario che punta sempre all’elemento precedente rispetto a quello che stiamo analizzando, ecco il codice:
[cpp]
LinkedWord *delete_list(LinkedWord *list, const char *s)
{
LinkedWord *cur = list, *p = NULL;
// cerca s tenendo un riferimento all’elemento precedente
while (cur != NULL && strcmp(cur->word,s)!=0) {
p=cur; cur=cur->next;
}
if (cur == NULL)
return list; // siamo alla fine s non e’ nella lista
if (p == NULL) // siamo all’inizio aggiorna la testa
list = list->next;
else
p->next = cur->next; // siamo in mezzo
delete_word(cur); // se cur!=NULL
return list;
}
[/cpp]
Usiamo la funzione sopra:
[cpp]
int main(void)
{
LinkedWord *lista = NULL;
lista = add_head(lista,"Mario",10);
lista = add_head(lista,"Giovanna",40);
lista = add_head(lista,"Paolo",20);
lista = add_head(lista,"Giovanna",30);
print_list(lista);
printf("Search:————–\n");
print_word(find_list_rec(lista,"Paolo")); printf("\n");
// troviamo la prima e la seconda occorrenza
LinkedWord *g = find_list_rec(lista,"Giovanna");
print_word(g); printf("\n");
print_word(find_list_rec(g->next,"Giovanna")); printf("\n");
print_word(find_list_iter(lista,"Mario")); printf("\n");
printf("Delete:—————-\n");
lista = delete_list(lista,""); print_list(lista);
lista = delete_list(lista,"Paolo"); print_list(lista);
lista = delete_list(lista,"Mario"); print_list(lista);
lista = delete_list(lista,"Giovanna"); print_list(lista);
lista = delete_list(lista,"Giovanna"); print_list(lista);
destroy_list(lista);
return 0;
}
[/cpp]
La funzione insert costruita sopra inserisce un elemento solo in testa alla lista, esistono invece due varianti molto importanti, una variante costruisce insert in modo che la lista sia ordinata (su un qualche campo, in modo crescente o decrescente) un altra variante inserisce l’elemento in coda.
Nel caso ad esempio del programma che conta le parole, consideriamo che lo schema del programma principale richiede di cercare una parola e eventualmente aggungerla o modificare il numero di occorrenze, per ogni parola letta, la ricerca quindi deve essere comunque fatta ed è la parte dispendiosa del programma. Potremmo ottimizzare il caso medio se le parole sono tenute ordinate per numero di occorrenze in modo descrescente, il ragionamento è: se una parola è frequente (il numero di occorrenze è alto) allora la probabilità che appaia ancora sarà maggiore rispetto alle altre, quindi se la lista è ordinata in modo decrescente per numero di occorrenze le parole che cerco più spesso saranno nella parte iniziale della lista e saranno trovate con un numero minore di confronti (ci aspettiamo che “Alice” sia prima, nel libro che parla delle sue avventure).
Un esempio di inserimento ordinato è il seguente:
[cpp]
LinkedWord *add_ordered(LinkedWord* list, const char *s, int v)
{
LinkedWord *p = NULL, *l = list;
LinkedWord *n = new_word(s,v);
for (; l!=NULL && l->value >= v; p=l,l=l->next) ;
if (p == NULL) {
n->next = list; return n;
}
p->next = n;
n->next = l;
return list;
}
LinkedWord *add_ordered_rec(LinkedWord *list, const char *s, int v)
{
// caso base cambia la testa
if (list == NULL || v > list->value) {
LinkedWord *n = new_word(s,v);
n->next = list;
return n;
}
// recurse
list->next = add_ordered_rec(list->next,s,v);
return list;
}
[/cpp]
potete provare la funzione sopra, cambiando nel programma precedente add_head con add_ordered. La versione ricorsiva è in questi casi, più elegante e comprensibile.
Se si vuole inserire un elemento in coda, (append) e si gestisce la lista con un puntatore al primo elemento come fatto finora, l’unica soluzione è scorrere la lista fino all’ultimo elemento e poi aggiungere il nuovo elemento. Questo ovviamente costa tanto quanto la lunghezza della lista, quindi, nel caso in cui l’inserimento in coda avviene con alta frequenza, può essere conveniente mantenere oltre al puntatore alla testa, anche un puntatore alla coda, e magari visto che ci siamo anche il numero di elementi presenti nella lista. Esempio:
[cpp]
typedef struct listinfo {
LinkedWord *testa,*coda;
int len;
} ListInfo;
// aggiunge un elemento in coda
void list_append(ListInfo *l, const char* s, int v)
{
LinkedWord *n = new_word(s,v);
if (l->coda == NULL) l->coda = l->testa = n; else l->coda->next = n;
l->len++;
}
int main(void)
{
ListInfo parole = { 0 };
list_append(&parole,"Ciao",10);
print_list(parole.testa);
return 0;
}
[/cpp]
Notate che in quest’ultimo caso, la struttura viene passata per riferimento (usando un puntatore), e viene direttamente cambiata dentro le funzioni che la modificano, queste ultime avranno quindi dominio void.
In questa pagina potete trovare una versione del programma che calcola le statistiche delle occorrenze di parole, che usa delle liste (non ordinate), provate a modificarlo in modo da usare una lista ordinata, come sopra, in senso decrescente rispetto al numero di occorrenze (le parole più frequenti saranno quindi le prime), e verificate se c’è un miglioramento nei tempi di esecuzione.