Le liste sono uno strumento potente e versatile, molto utile ed efficiente per algoritmi di ordinamento (basti pensare al MergeSort). Una lista è una collezione di elementi omogenei, e contrariamente all’ array, occupa in memoria una posizione qualsiasi che può cambiare durante l’utilizzo della lista stessa. La sua dimensione non è decidibile a priori ( l’array è l’opposto, poiché la sua dimensione si decide all’ inizio e non è possibile modificarla) e può variare nel tempo. Con le liste, inoltre, è possibile gestire il collegamento tra un elemento e l’altro mediante l’utilizzo di un puntatore, per mezzo del quale ci si può spostare da un elemento ad un altro. Le liste sono un mix tra due funzioni molto importanti del linguaggio C: le strutture e i puntatori.

Come abbiamo detto prima, la lista può contenere uno o più campi di informazione, che può essere di tipo int, char, float, ecc; mentre deve essere sempre un campo che punta ad un altro elemento della lista, che risulta essere NULL se non ci sono altri elementi, mentre risulta essere una struttura nel caso in cui c’è un qualcosa successivamente.

Adesso vediamo più nel dettaglio come creare una lista, esprimendolo nel linguaggio C:

struct elemento {
 int inf;
struct elemento *pun;
}

Per dichiarare una lista basta scrivere questo semplice comando:

struct elemento *lista

il quale rappresenta un puntatore ad una struttura elemento, ed essendo tale potrebbe essere inizializzata anche come un valore NULL.

Da ricordare che, anche se nella sua rappresentazione, una lista risulta essere sequenziale, in realtà l’allocazione di memoria relativamente agli elementi è libera, cioè ogni volta che devo aggiungere un elemento alla lista, devo allocare la memoria relativa, connetterlo all’ ultimo elemento ed inserirvi l’informazione .

Graficamente una lista può essere rappresentata nel seguente modo:

GESTIONE DI UNA LISTA

Scriviamo un piccolo programma che permetta di memorizzare e stampare un numero determinato di interi. A primo impatto può sembrare abbastanza semplice, ma non lo è affatto; inoltre bisogna fare molta attenzione a non commettere ne errori logici ne sintattici.

Partiamo con l’inclusione delle librerie, in questo caso includiamo solamente stdio.h, per le più comuni operazioni di input/output, e malloc.h per l’allocazione dinamica della memoria; non includeremo nessuna libreria particolare poiché, come detto prima, una lista è composta da elementi preesistenti nel linguaggi C.

#include <stdio.h>
#include <malloc.h>

Successivamente creiamo il tipo elemento, alla base della lista, che contiene un campo intero di nome “a” ed un campo puntatore al tipo elemento di nome “puntatore”:

/* struttura elementi della lista */
struct elemento {
int a;
struct elemento *puntatore;
}

Creiamo i due prototipo delle due funzioni che ci aiuteranno alla soluzione del nostro problema; la prima funzione ha il compito di creare la lista, chiedendo i dati di input all’utente tramite tastiera, che poi verrà restituita dalla funzione stessa; la seconda, invece, restituisce un void e prende in input la lista da stampare.

/* prototipi  funzioni */
struct elemento *crea_lista();
void visualizza_lista(struct elemento *);

Passiamo all’apertura del nostro programma principale dichiarando la funzione int main;  la dichiarazione di una variabile lista di tipo puntatore ad elemento, l’esecuzione della funzione crea_lista(), che  riempirà con dei valori la lista, e l’esecuzione della funzione visualizza_lista() che stamperà a video tutti gli elementi della lista;

int main() {
 struct elemento *lista; // puntatore della lista
lista = crea_lista(); // crea la lista
 visualizza_lista(lista); // stampa la lista
}

Procediamo con la definizione del corpo della funzione crea_lista(), la quale crea due puntatori ad elemento, uno di nome p e l’altro di nome punt; queste due variabili serviranno per scorrere la lista, infatti p è il puntatore al primo elemento della lista, mentre punt è un puntatore ausiliario che permette di scorrere la lista; la variabile i è l’indice del ciclo, mentre n serve a memorizzare il numero degli elementi che si intende inserire.

struct elemento *crea_lista()
{
 struct elemento *p, *puntatore;
 int i, n;

La variabile n viene inserita tramite tastiera dall’utente,

printf(“n Inserire il numero di elementi ..  “);
scanf(“%d”, & n);

Se n vale 0, viene richiesto di creare una lista vuota, quindi si assegna a p il valore null,

if(n==0)
{
p = NULL; // lista vuota

altrimenti si costruisce il primo elemento della lista, chiedendo il suo valore da tastiera:

} else {
/* creazione primo elemento */
p = (struct elemento *)malloc(sizeof(struct elemento));
printf(“nInserisci il primo valore: “);
scanf(“%d”, & p->a);
punt = p;

Nel prossimo articolo parleremo di Input e output su File, se invece ti sei perso lo scorso articolo, si è parlato di Gestione della memoria.

Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata alla Programmazione C.

Alla prossima!