RAPPRESENTAZIONE DINAMICA oppure RAPPRESENTAZIONE COLLEGATA con Puntatori di una Lista (Pila).

La Struttura di tipo astratto Pila, coincide con quella più generica di Lista (anche se vedremo in seguito esistono anche altri tipo di liste chiamate CODE).
La Pila è una lista di tipo LIFO (Last in first out) oppure detto in modo non convenzionale FILO (First in, last out). Dunque il primo atomo inserito nella Lista sarà l’ultimo ad uscire, che equivale a dire che l’ultimo elemento inserito sarà il primo ad uscire.
Potremmo immaginarci una pila di perline dentro un filo con un nodo all’estremità. Aggiungendo qualche perlina nel nostro filo e volendo sfilare la prima inserita, dovremo obbligatoriamente togliere le ultime perline inserite, per poter sfilare la prima perlina.

In questa nuova rappresentazione, lavoreremo con i puntatori (infatti è una lista Collegata, però sta volta con i puntatori). Poichè avremo allocazioni dinamiche della nostra lista.
A questo proposito un puntatore vuoto che non punta a nulla conterrà il valore NULL.

Definiamo nuovi tipi di dato, con nuove strutture.
Il vantaggio di questa nuova rappresentazione collegata è quello di non dover prefissare un limite alla lunghezza della lista (se non quello della memoria disponibile),
e di dover richiedere uno spazio in memoria direttamente proporzionale a quello della lista.

– Per identificare una lista vuota faremo in modo, senza usare un campo lunghezza = 0, che il primo elemento di tale lista punti a NULL.

typedef int t_atomo; //ci definiamo un nuovo tipo di dato generico t_atomo, lo facciamo a parte così riceverà in ingresso questo tipo di dato che possiamo cambiare in float etc. Senza quindi modificare niente nelle funzioni che implementeremo per lavorare su una lista.

QUESTO NUOVO TIPO DI LISTA è FORMATO DA 2 CAMPI ESSENZIALMENTE, E RICHIAMA RICORSIVAMENTE SE STESSA. QUINDI OTTEREMO UNA LISTA FORMATA DA UN CAMPO INFO (l->info) che è il contenuto dell’elemento, ed un puntatore *prox che punta all’elemento successivo, (che altro non sarà che il campo info della stessa struttura, dichiarato ricorsivamente):

typedef
struct lista  //Dichiarazione ricorsiva di una lista.
{
t_atomo info;  //conterrà l'elemento della lista
struct lista *prox; //punta all'indirizzo di memoria dell'elemento successivo che è a sua volta una struttura uguale a questa.
} t_lista;  //effettivamente questo rappresenta un nodo, ma tramite richiamata ricorsiva diventa una lista.

Tutte le funzioni primitive sulle pile hanno complessità computazionale costante: O(1).

Qua di seguito le funzioni primitive per lavorare con questa struttura dati appena definita:

//Inizializza la lista come vuota:
void inizializza_lista_come_vuota(t_lista *l){
l = NULL; //la lista punterà a NULL. Quindi la lista verrà considerata come vuota.
}
 
//FUNZIONI PRIMITIVE:
 
int null(t_lista *p){ //La funzione Null restituisce 1 se la lista è vuota. Altrimenti restituisce 0
return (p == NULL);
}
 
int car(t_lista *p, t_atomo *x){ //La funzione Car restituisce il primo elemento della lista, lo "restituisce" in questo caso inserendolo in una variabile che passiamo per indirizzo alla funzione, e poi restituisce 0, operazione avvenuta con successo.
 
if (null(p)) //Se la lista è vuota
  return 1; //Operazione non riuscita, la lista è vuota.
  else{ //Altrimenti
  *x = p->info; //Inserisce in x il valore del primo elemento della lista (info appunto).
  return 0; //Operazione avvenuta con successo
  }
 
}
 
//La funzione Cdr elimina il primo elemento dalla lista, rimuovendolo dall'indice in un certo senso.
int cdr(t_lista **p){ //Riceve in ingresso, l'indirizzo in cui è contenuto l'indirizzo che punta alla locazione di memoria del primo elemento.
 
if (null(*p))//se il campo info di questo 2 indirizzo è NULL, restituisce 1, lista vuota.
  return 1; //il puntatore punta a nulla, lista vuota.
else{ //Altrimenti
 
*p = (*p)->prox; //*p che contiene la locazione di memoria del successivo diventa la locazione a cui puntava (ovvero il successivo): (*p)->prox.  Così è come se si eliminasse dall'indice il primo elemento.
 
return 0; //Eliminazione del primo elemento avvenuta con successo.
}
 
}
 
//La funzione Cons inserisce un elemento di tipo t_atomo in una lista. 
int cons(t_lista **p, t_atomo x){ //riceve un doppio puntatore che useremo per estrapolare l'indirizzo di memoria del primo elemento, e riceve l'elemento x da inserire in lista. 
t_lista *temp;
temp = (t_lista *) malloc(sizeof(t_lista)); //alloca in temp un lista di tipo t_lista.
 
if (temp){ //se l'allocazione di memoria avviene con successo
temp->info = x; //inserisce nel campo info di temp il nostro valore X.
temp->prox = *p; //setta come prox. L'indirizzo puntato dal doppio puntatore p. (Quindi l'indirizzo del primo elemento).
*p = temp; //L'indirizzo del primo elemento diventa l'indirizzo conteuto in temp. (non a caso si chiama rappresentazione collegata, poichè sono collegati fra di loro i vari elementi)
return 0; //Operazione avvenuta con successo.
 
}else //Altrimenti
 return 1; //Allocazione della memoria fallita, inserimento fallito.
 
}