Appunti di informatica sulle Liste e liste di liste

LISTE

Ciascun nodo della lista è una struttura di due campi:

• valore dell’elemento

• un puntatore al nodo successivo della lista (NULL se ultimo elemento)

L’intera sequenza è rappresentata da un puntatore al suo primo elemento (vogliamo

un’unica variabile per accedere a tutti gli elementi della sequenza)NOTA: tale puntatore

non èla sequenza, ma la rappresenta soltanto

Esempio: [3, 8, 5]

Definizione struttura

typedef int TAtomo; int può essere anche uno struct, un float ecc

typedef struct StLista {

TAtomo dato; dato = info

struct StLista * succ; succ = next (puntatore al succ);

} E_lista, *TLista;

funzioni

TAtomo car ( TLista L ); car = stampa il primo elemento

int null (TLista L);

void cons( TLista *PL, TAtomo A ) ; cons = inserisce un valore in prima posizione

int cdr( TLista *PL ); elimina il 1 elemento

• int null( TLista L ) {

return L = = NULL;

}

• TAtomo car( TLista L ) {

return null(L) ? ERR :L->dato;

}

• int cdr( TLista *PL ) {

TLista temp;

if ( null(*PL) ) return 0;

temp = *PL;

*PL = (*PL)->succ;

free(temp);

return 1;

}

• void cons( TLista *PL, TAtomo A ) {

TLista temp;

temp = (TLista) malloc( sizeof(ELista) );

if (temp = = NULL) return temp->dato = A;

temp->succ = *PL;

*PL = temp;

}

LISTE ORDINATE

ES. 3 5 7 8

• inserimento nella lista vuota o inserimento del valore 2 nella lista L equivale ad un

inserimento in testa

• inserimento del valore 6 nella lista L:

1. cerca la posizione dove inserire (è necessario il puntatore all’elemento precedente)

2. alloca la memoria per un nuovo elemento

3. collega il nuovo elemento

DEFINIZIONE

typedef int TAtomo;

typedef struct StLista {

TAtomo dato;

struct StLista * succ;

} ELista, *TLista;

FUNZIONI

void insord(TLista *P, TAtomo T) {

if (null(*P) || (car(*P)>T)) cons(P,T); Inserisce un elemento in ordine

else insord(&((*P)->succ),T)

}

int canc(TLista *P, TAtomo T) {

if (null(*P) || car(*P)>T) return -1; cancella un elemento

if (car(*P) == T) return cdr(P);

return (canc(&((*P)->succ),T));

}

ALTRE FUNZIONI

FACOLTATIVO : liste mediante ARRAY (VETTORI)

Definizione