Utilizzare le liste in linguaggio C

27 febbraio 2013

Ciao ragazzi, in questa dodicesima parte del corso completo di C che si tiene su questo sito, voglio parlarvi delle liste, un costrutto bellissimo e molto potente del C. E' possibile utilizzare i puntatori per accedere a variabili di tipo struct in questo modo:

typedef struct {
int num1;
int num2;
} Numeri;

Numeri S, *P;
P = &S;

L'operatore " . " ha la precedenza sull'operatore " * ", per cui sono necessarie le parentesi tonde! Ossia bisogna scrivere così:

(*P).num1 = 34;

L'operatore " -> " permette di velocizzare la scrittura di prima:

P -> num1 = 34;

Dopo questa piccola introduzione, passo a dare la definizione di una lista: una lista è un insieme finito di elementi dello stesso tipo, caratterizzata da un elemento in testa (head) e da un elemento in coda che la termina (tail). Dal momento, però, che il tipo lista in C non esiste, bisogna costruirselo da soli, partendo da puntatori e strutture.

Il concetto di lista può essere così disegnato (per avere un'idea generale):

Per dirlo in modo molto basilare e anche sotto alcuni punti di vista sbagliato, voglio farvi capire che ogni elemento della lista è composto da due parti:

Il valore di questo elemento (che sia un intero, un array o una struttura);
Un puntatore all'elemento successivo della lista.

Ovviamente l'ultimo elemento della lista ha un puntatore a NULL.

Vi faccio quindi adesso vedere come si implementa il C il tipo lista:

DEFINIRE LE FUNZIONI PRIMITIVE
Le principali operazioni che si possono compiere su una lista sono:

Inserire un elemento in testa;
Restituire il primo elemento della lista;
Restituisce l'elemento successivo della lista;
Creare una lista vuota.

Per riempire una lista, quindi, dovete creare prima una lista vuota, poi inserite il primo valore e indirizzate quindi il puntatore all'elemento successivo:

Dato che se volessimo utilizzare in ogni programma questa modalità di scrittura a puntatori sarebbe solo uno spreco di tempo e di memoria, è utile crearsi determinate funzioni primitive da utilizzare ogni volta che sono necessarie; queste funzioni, come ho già detto, permettono di eseguire le principali operazioni sulle liste.

Prima bisogna un attimo definire, per comodità, il tipo Element, in modo da rendere ancora più generali le funzioni primitive che adesso andremo a vedere; il tipo Element si definisce in base ovviamente alle necessità, ovvero in base al tipo di dato da usare.

LA FUNZIONE CONS()
La funzione cons() si occupa di inserire un elemento in testa alla lista, ed è così definita:

list cons(Element, list);

LA FUNZIONE HEAD()
La funzione head() restituisce l'elemento in testa alla lista, ed è così definita:

Element head(list);

LA FUNZIONE TAIL()
La funzione tail() restituisce invece la coda della lista, ed è così definita:

list tail(list);

LA FUNZIONE EMPTYLIST() E LA EMPTY()
La funzione emptyList() si occupa di creare una nuova lista vuota, mentre la funzione empty() si occupa di controllare se una lista è vuota o no, e sono così definite: