Costruzione con aggiunte successive

Il metodo di costruzione delle liste basato sull'uso di sequenze di tipo *(*(*l).next).next).next, è inattuabile in caso di liste appena più lunghe di tre elementi. Abbiamo visto come si possano costruire le liste partendo dal fondo. Vediamo ora un altro metodo, che è completamente equivalente.

Questo metodo è basato sulla ripetizione della aggiunta di un elemento in testa alla lista. Per prima cosa, possiamo realizzare una funzione che aggiunge un elemento in testa a una lista:

void InserisciTestaLista(TipoLista *pl, int e) {
  TipoLista t;

  t=malloc(sizeof(struct NodoLista));
  (*t).val=e;
  (*t).next=*pl;

  *pl=t;
}

Questa procedura fa esattamente quello che faceva il frammento di codice che inseriva in testa. L'unico punto a cui bisogna fare attenzione è il fatto che, dal momento che il valore della variabile puntatore l viene modificato, va passato per riferimento. Questo punto potrebbe creare qualche difficoltà. In realtà è molto semplice: consideriamo la chiamata con la lista (2 -9 1) e il nuovo elemento -5 (vedi figure nella pagina precedente). Quando la procedura viene chiamata, per esempio con InserisciTestaLista(&l, -5), il valore di l è l'indirizzo della struttura che contiene 2, mentre alla fine dell'esecuzione deve essere l'indirizzo della struttura che contiene -5. Quindi, il valore di l viene modificato. Inoltre, questo cambiamento deve essere visibile nel programma chiamante (se cosí non fosse, il programma chiamante continuerebbe a vedere la lista (2 -9 1) anche dopo la esecuzione della funzione). Quindi, la variabile l, dato che il suo valore viene modificato e la modifica deve essere visibile al chiamante, va passata per indirizzo.

La seconda cosa da notare è che la funzione va bene anche nel caso in cui la lista di partenza è vuota. Se eseguiamo InserisciTestaLista(&l, 12) e la variabile l vale NULL, quello che si ottiene è che l viene modificato in modo da puntare a una struttura che contiene 12 e NULL, cosa che si può verificare graficamente. Questa è esattamente la lista (12), che è quello che ci si aspetta aggiungendo 12 in testa alla lista vuota ().

Possiamo ora passare alla costruzione della lista. Supponiamo di voler creare la lista (90 32 -22). Potremmo procedere in questo modo: partiamo dalla lista vuota, e a questa aggiungiamo -22 in testa. Come si è detto, si ottiene la lista (-22). Se si aggiunge anche 32, sempre in testa a questa nuova lista, si ottiene (32 -22). Se aggiungo anche 90 ottengo esattamente la lista che serviva, ossia (90 32 -22).

Detto in un altro modo, se aggiungo una sequenza di elementi in ordine, ottengo che gli elementi si trovano nella lista in ordine inverso rispetto all'ordine in cui sono stati inseriti: se inserisco prima -22, poi 32 e alla fine 90, quello che ottengo è la lista in cui questi elementi si trovano in ordine inverso, ossia (90 32 -22).

Il seguente programma costruzione.c costruisce la lista (13 -5 2 -9 1) partendo dalla lista vuota e inserendo gli elementi in testa, cominciando dall'ultimo (prima 1, poi -9, poi 2, ecc).

/*
  Costruzione di una lista dal fondo.
*/

#include<stdlib.h>

struct NodoLista {
  int val;
  struct NodoLista *next;
};

typedef struct NodoLista *TipoLista;


/*
  stampa di una lista di lunghezza generica
*/

void StampaLista(TipoLista l) {
  TipoLista s;

  s=l;
  while(s!=NULL) {
    printf("%d ", (*s).val);
    s=(*s).next;
  }

  printf("\n");
}


/*
  aggiunta di un elemento in testa alla lista
*/

void InserisciTestaLista(TipoLista *pl, int e) {
  TipoLista t;

  t=malloc(sizeof(struct NodoLista));
  (*t).val=e;
  (*t).next=*pl;

  *pl=t;
}


/*
  main
*/

int main() {
  TipoLista l;

                /* creazione della lista (13 -5 2 -9 1) */

  l=NULL;	/* lista vuota */
  InserisciTestaLista(&l, 1);
  InserisciTestaLista(&l, -9);
  InserisciTestaLista(&l, 2);
  InserisciTestaLista(&l, -5);
  InserisciTestaLista(&l, 13);

  
                /* stampa la lista */

  StampaLista(l);

  return 0;
}