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;
    struct StLista * 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 primo 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

Esempio: 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:
• Cerca la posizione dove inserire (è necessario il puntatore all’elemento precedente)
• Alloca la memoria per un nuovo elemento
• 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); 
          else 
              insord(&((*P)->succ),T)
      

• int canc(TLista *P, TAtomo T) {

          if (null(*P) || car(*P) > T) return -1; 
          if (car(*P) == T) return cdr(P);
          return (canc(&((*P)->succ),T));
      

Altre funzioni

Facoltativo: liste mediante array (vettori)

Definizione

Liste semplici collegate mediante array

Funzioni