Utilizzare le liste in linguaggio C

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 ipuntatori per accedere a variabili di tipo struct in questo modo:

INDICE

Parte 1: Introduzione.

Parte 2: Fasi, variabili, operatori e software.

Parte 3: Tipi di dato, direttive e primo programma.

Parte 4: Tipi di formato, prinft e scanf.

Parte 5: Istruzioni condizionali e di iterazione.

Parte 6: Funzioni e progetti su più file.

Parte 7: Puntatori e passaggio dei parametri.

Parte 8: Array, stringhe e strutture.

Parte 9: Gestione file: file di testo.

Parte 10: Gestione file: file binari.

Parte 11: Allocazione dinamica della memoria.

Parte 12: Creare ed utilizzare le liste nel C.

Parte 13: Algoritmi di ordinamento di Array.

Parte 14: Esercizi sul linguaggio C.

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 funzioniprimitive 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:

list emptyList(void);

Boolean empty(list);

Piccolo esempio di un programma che utilizza tutte queste funzioni:

main.c

list.h

Nel file list.c qui di seguito sono presenti le funzioni primitive viste prima e inoltre anche queste, che servono al programma:

list.c

Vi lascio adesso da scaricare i file di questo programma; esercitatevi tanto sulle liste che sono veramente molto importanti!!

esercizioliste.zip

Download File

Se volete esercitarvi con degli esercizi, andate qui: Esercizi sulle liste.

Matteo Pumo

Dottore in Ingegneria Informatica.
Contattatemi sui miei Social Network e sul mio Sito personale per collaborazioni, proposte di lavoro e altre informazioni!

Parte 12 – Corso C – Creare ed utilizzare le liste nel C

main.c

list.h

list.c

Post correlati