ADT LISTA CON UTILIZZO DI VETTORI.
Gli indirizzi degli elementi contenuti nella lista sono memorizzati in un vettore. La lista è un puntatore ad un record composto da due elementi: il primo è il vettore di indirizzi, il secondo contiene last.
typedef struct {
Elemento elementi[MAXLEN]; /* vettore di puntatori agli elementi della lista */
Posizione last;
} _Lista;
typedef _Lista* Lista;
#define MAXLEN 200
#define Posizione int
#define Elemento void*
Di seguito sono realizzate le operazioni definite in precedenza.
static void fatalError(char* s) {
printf("\nFATAL ERRORR: %s *****\n", s);
exit(1);
}
Lista listaInsert( Lista l, Elemento e, Posizione p ) {
Posizione q;
if(l->last >= MAXLEN) fatalError("listaInsert: Lista piena.");
if((p < 0) || (p > l->last)) fatalError("listaInsert: Posizione errata.");
for(q = l->last; q != p; q--)
l->elementi[q+1] = l->elementi[q];
l->elementi[p] = e;
l->last++;
return l;
}
Elemento listaRetrieve( Posizione p, Lista l) {
if((p < 0) || (p >= l->last)) fatalError("listaRetrieve: Posizione errata.");
return l->elementi[p];
}
Lista listaDelete( Posizione p, Lista l ) {
Posizione q;
if((p < 0) || (p >= l->last)) fatalError("listaDelete: Posizione errata.");
(l->last)--;
for(q = p; q < l->last; q++)
l->elementi[q] = l->elementi[q+1];
return l;
}
Posizione listaNext( Posizione p, Lista l) {
if((p < 0) || (p >= l->last)) fatalError("listaRetrieve: Posizione errata.");
return p+1;
}
Lista listaCrea( void ) {
Lista l = (Lista)malloc(sizeof(_Lista));
l->last = 0;
return l;
}
Posizione listaFirst( Lista l ) {
return 0;
}
Posizione listaEnd( Lista l ) {
return l->last;
}
ADT LISTA DINAMICA.
Ogni elemento della lista è un record composto da due campi puntatore: il primo campo è l'indirizzo del dato, il secondo è l'indirizzo dell'elemento successivo.
#define Elemento void*
struct _nodo {
Elemento e;
struct _nodo* next;
};
typedef struct _nodo* Posizione;
typedef struct _nodo* Lista;
La lista è l'indirizzo del primo elemento.
La lista vuota è la lista che ha come dato NULL. Quando si deve far riferimento ad una posizione si indica sempre la posizione dell'elemento precedete a quello su cui si devono compiere le operazioni. Il primo elemento, che non ha precedenti, lo si indica con il puntatore NULL. Ogni funzione controlla se si deve operare sul primo elemento o sui successivi.
/*
lista.c
*/
#include
#include
#include "lista.h"
Lista listaInsert( Lista l, Elemento e, Posizione p ) {
Posizione x = (Posizione)malloc(sizeof(struct _nodo)); /* creo elemento */
x->e = e; /* inserimento del dato */
if( p == NULL ) { /* inserimento in testa? */
x->next = l; return x; /* modifico il puntatore iniziale l */
}
x->next = p->next; /* altrimenti il successivo di p diventa il nuovo elemento */
p->next = x;
return l;
}
Elemento listaRetrieve( Posizione p, Lista l ){
if( p == NULL )/* in testa? */
return l->e;
return p->next->e;
}
Lista listaDelete( Posizione p, Lista l ){
Posizione x;
if( p == NULL ) { /* in testa? */
x = l;
l = l->next;
} else {
x = p->next;
p->next = p->next->next;
}
free( x );
return l;
}
Posizione listaNext( Posizione p, Lista l ) {
if( p == NULL ) /* in testa? */
return l;
return p->next;
}
Lista listaCrea( void ) {
return NULL;
}
Posizione listaFirst( Lista l ){
return NULL;
}
Posizione listaEnd( Lista l ){
Posizione p;
for(p = l; p != NULL && p->next != NULL; p = p->next)
;
return p;
}
LA realizzazione precedente ha due inconvenienti.
Il primo è che ogni funzione deve chiedersi se si opera con il primo elemento o con i successivi; il primo elemento non ha precedente e quindi in questo caso devo operare direttamente sul puntatore esterno l.
Il secondo è che la funzione listaEnd ha complessità lineare e non costante: il numero di istruzioni che devono essere svolte per ritrovare l'ultimo elemento della lista dipende dalla lunghezza della lista, poichè devo percorrerla tutta.
Questi due inconvenienti possono essere risolti introducendo un elemento fittizio in testa alla lista. Si elimina l'eccezione del primo elemento poichè anche il primo avrà un precedente, che potrà essere utilizzato per memorizzare l'ultimo elemento della lista, rendendo costante anche l'operazione listaEnd.
Le definizioni non cambiano ma cambiano le operazioni. In particolare cambia la creazione, che crea un elemento fittizio e lo inizializza opportunamente.
Lista listaInsert( Lista l, Elemento e, Posizione p ) {
Posizione x = (Posizione)malloc(sizeof(struct _nodo));
x->e = e;
x->next = p->next;
p->next = x;
if( p == l->e ) l->e = x; /* se inserisco in fondo alla lista modifico l'indirizzo ultimo elemento */
return l;
}
Elemento listaRetrieve( Posizione p, Lista l ){
return p->next->e;
}
Lista listaDelete( Posizione p, Lista l ){
Posizione x;
x = p->next;
p->next = p->next->next;
if( x == l->e ) l->e = p; /* se cancello ultimo elemento modifico indirizzo ultimo */
free( x );
return l;
}
Posizione listaNext( Posizione p, Lista l ) {
return p->next;
}
Lista listaCrea( void ) {
Posizione x = (Posizione)malloc(sizeof(struct _nodo));
x->e = x; /* l'indirizzo dell'utimo elemento */
x->next = NULL;
return x;
}
Posizione listaFirst( Lista l ){
return l;
}
Posizione listaEnd( Lista l ){
return l->e;
}
NOTA BENE. Gli esempi mostrati in precedenza che utilizzano ADT sono indipendenti dalle diverse implementazioni dell'ADT lista.
Liste doppiamente concatenate.
Potrebbe essere importante poter percorrere una lista lineare in tutte e due i sensi. Per ogni elemento potrebbe essere necessario determinare sia il precedente che il successivo. Con una lista così pensata diventa possibile utilizzare come puntatore alla cella i-esima l'indirizzo della cella stessa.
L'implementazione che segue si introduce anche un elemento fittizio iniziale, elemento che precede il primo e che segue l'ultimo. Così si evita di dover controllare sempre se l'elemento che si inserisce o si cancella è il primo o l'ultimo. Si eliminano tutte le eccezioni.
Inoltre ricordo la funzione End restituisce la posizione successiva all'ultimo elemento.
La struttura dati da utilizzare nella realizzazione dell'ADT è la seguente:
#define Elemento void*
struct _nodo {
Elemento e;
struct _nodo *next, *pre;
};
typedef struct _nodo* Posizione;
typedef struct _nodo* Lista;
Le operazioni sono realizzate dalle seguenti primitive:
Lista listaCrea( void ) {
Posizione x = (Posizione)malloc(sizeof(struct _nodo));
x->e = NULL;
x->next = x->pre = x;
return x;
}
Lista listaInsert( Lista l, Elemento e, Posizione p ) {
Posizione x = (Posizione)malloc(sizeof(struct _nodo));
x->e = e;
x->next = p;
x->pre = p->pre;
p->pre = x;
x->pre->next = x;
return l;
}
Elemento listaRetrieve( Posizione p, Lista l ){
return p->e;
}
Posizione listaNext( Posizione p, Lista l ) {
return p->next;
}
Posizione listaPre( Posizione p, Lista l ) {
return p->pre;
}
Posizione listaFirst( Lista l ){
return l->next;
}
Posizione listaEnd( Lista l ){
return l;
}
Si lascia come utile esercizio la realizzazione dell'operazione di cancellazione. Si può verificare come i programmi che utilizzano ADT lista lineare operano correttamente anche con ADT lista doppiamente concatenata.
Come utile esercizio realizzare una funzione che stampa la lista in ordine inverso, dall'ultimo elemento al primo. (Si ricorda che la funzione END restituisce l'indirizzo dell'elemento successivo all'ultimo per cui .... ).