Liste dinamiche in C

LISTE DINAMICHE



  1. Introduzione alle liste dinamiche

  2. Gli elementi delle liste dinamiche

  3. Utilizzare una lista dinamica

  4. Creare un nuovo elemento

  5. Verificare se una lista è vuota

  6. Inserire un elemento in coda alla lista

  7. Inserimento di un elemento all'inizio delle liste dinamiche

  8. Ricerca di un elemento

Introduzione:
Per memorizzare e lavorare su un gruppo di elementi dello stesso tipo spesso si ricorre agli array. Gli array hanno però dei limiti che in certe situazioni rendono scomodo, svantaggioso o addirittura impossibile il loro utilizzo. Il maggiore di questi limiti è che gli array hanno una dimensione fissa: questo implica uno spreco di memoria e risorse se l'array non è completamente riempito e l'impossibilità di usare più elementi di quanti se ne erano previsti. Un altro svantaggio notevole è la scarsa flessibilità, si pensi ad esempio a come è difficile ordinare un array. Per queste e altre ragioni spesso quando si devono gestire un numero non prevedibile di elementi uguali tra di loro si ricorre ad una allocazione dinamica della memoria. Un modo usato e relativamente semplice per fare questo sono le liste dinamiche, che si possono pensare come una serie di elementi concatenati tra di loro.

Torna su


Gli elementi delle liste dinamiche:
Ogni elemento di una lista dinamica deve essere strutturato in modo da permettere due operazioni essenziali:

  • Memorizzare le informazioni o variabili necessarie

  • Permettere il concatenamento tra gli elementi

Per fare ciò l'elemento deve essere una struttura che abbia dei campi in cui memorizzare le variabili e un campo di tipo puntatore alla stessa struttura che si sta definendo, per legare ogni elemento all'eventuale successivo. Vediamo ad esempio come dove essere definito un elemento di una lista dinamica di interi:

typedef struct struttura{ int info; struct struttura* next; }elemento_lista;

Torna su

Utilizzare una lista dinamica:
La prima cosa da fare per utilizzare una lista dinamica è creare una variabile tramite la quale si possa raggiungere la lista. Questa variabile deve essere di tipo puntatore all'elemento che si è definito per la struttura. Una buona norma è assicurarsi che questa variabile punti a NULL fintanto che la lista dinamica non contiene elementi.

elemento_lista* testa;
testa=NULL;

Alla variabile testa si farà riferimento ogni volta che sarà necessario eseguire operazioni sulla lista dinamica.

Torna su

Creare un nuovo elemento:
Per creare un nuovo elemento, senza per il momento preoccuparsi di inserirlo in alcun modo nella lista, bisogna ricorrere alla funzioni per l'allocazione dinamica della memoria malloc, disponibile includendo la libreria stdlib.h. Questa funzione restituisce un puntatore che punta alla variabile appena allocata.

elemento_lista* nuovo;
nuovo=(elemento_lista*)malloc(sizeof(elemento_lista));

La funzione accetta un unico parametro che è la lunghezza in byte della variabile per cui alloca memoria, calcolabile con la funzione del C sizeof(). L'epressione "(elemento_lista*)" è invece un cast, che trasforma il valore di uscita della malloc nel tipo che desideriamo.

Torna su

Verificare se una lista è vuota:

Controllare se in una lista dinamica ci sono elementi o se questa è ancora vuota è molto utile per implementare funzioni più complesse per l'inserimento, la ricerca o la rimozione di elementi. Sebbene questa operazione richieda un solo controllo a volte può essere utile per creare ordine definire una funzione che svolga questo compito; eccone un esempio:

int lista_vuota(elemento_lista* lista) { if(lista==NULL) return 1; else return 0; }

La funzione lista_vuota ritorna 1 se la lista è vuota, 0 in caso contrario, in modo che il valore ritornato possa essere usata in controlli come if o while.

... if(lista_vuota(testa)) printf("La lista è vuota\n"); ...

Torna su

Inserire un elemento in coda alla lista
Un elemento nuovo in una lista può essere inserito in diverse posizioni. Vediamo ora come inserirlo in fondo alla lista, ovvero come ultimo elemento.

elemento_lista* ins_coda(elemento_lista* lista, int num) { elemento_lista* nuovo; elemento_lista* punt; nuovo=(elemento_lista*)malloc(sizeof(elemento_lista)); nuovo->info=num; nuovo->next=NULL; if(lista_vuota(lista)) { lista=nuovo; } else { punt=lista; while(punt->next!=NULL) punt=punt->next; punt->next=nuovo; } return lista; }

Torna su

Inserimento di un elemento all'inizio delle liste dinamiche:

A volte invece occorre inserire un elemento all'inizio di una lista dinamica, prima degli altri elementi. Ecco come si può fare:

elemento_lista* ins_testa(elemento_lista* lista, int n) { elemento_lista* nuovo; nuovo=(elemento_lista*)malloc(sizeof(elemento_lista)); nuovo->num=n; nuovo->prox=lista; lista=nuovo; return lista; }

Torna su

Ricerca di un elemento:

Questa funzione cerca se nella lista è presente un elemento che abbia come campo informazioni un certo valore; restituisce 1 se lo trova, 0 in caso contratio.

int cerca(elemento_lista* lista, int num) { elemento_lista* punt; if(lista_vuota(lista))//definita qui return 0; else{ punt=lista;