Un ottimo esempio di strutture dati dinamiche è una semplice libreria per lo stack, una che usi una lista dinamica e che includa funzioni per inizializzare, pulire, inserire ed estrarre.
Il file di intestazione della libreria potrebbe essere questo:
/* Stack Library – Questa libreria contiene le funzioni base per gestire le operazioni su di uno stack di interi (facilmente estendibile) */ typedef int stack_data; extern void stack_init(); /* Inizializza la libreria Chiamare questa funzione prima di chiamare qualsiasi altra funzione. */ extern void stack_clear(); /* Elimina tutti i dati inseriti */ extern int stack_empty(); /* Restituisce 1 se lo stack è vuoto, 0 altrimenti. */ extern void stack_push(stack_data d); /* Inserisce il valore d nello stack */ extern stack_data stack_pop(); /* Restituisce l'elemento al top dello stack estraendolo e rimuovendolo dallo stack. Ritorna un valore non valido se lo stack è vuoto. */
Il codice della libreria è il seguente:
#include "stack.h"
#include <stdio.h>
/* Stack Library - This library offers the
minimal stack operations for a stack of integers */
struct stack_rec
{
stack_data data;
struct stack_rec *next;
};
struct stack_rec *top=NULL;
void stack_init()
/* Inizializza la libreria */
{
top=NULL;
}
void stack_clear()
/* Elimina tutti i dati inseriti */
{
stack_data x;
while (!stack_empty())
x=stack_pop();
}
int stack_empty()
/* Restituisce 1 se lo stack è vuoto, 0 altrimenti. */
{
if (top==NULL)
return(1);
else
return(0);
}
void stack_push(stack_data d)
/* Inserisce il valore d nello stack */
{
struct stack_rec *temp;
temp=
(struct stack_rec *)malloc(sizeof(struct stack_rec));
temp->data=d;
temp->next=top;
top=temp;
}
stack_data stack_pop()
/*Restituisce l'elemento al top dello stack estraendolo e rimuovendolo dallo stack.
Ritorna un valore non valido se lo stack è vuoto. */
{
struct stack_rec *temp;
stack_data d=0;
if (top!=NULL)
{
d=top->data;
temp=top;
top=top->next;
free(temp);
}
return(d);
}
Da notare che questa libreria realizza information hiding. Chi può avere accesso al solo file intestazione non può dire nulla di come lo stack è stato implementato. Si usano array? Si usano puntatori? Si usano files? Non è possibile dirlo.
Da notare che in C si può usare NULL. NULL è definito nella libreria stdio.h, pertanto ricordarsi di includere stdio.h quando si usano i puntatori. NULL è la stessa cosa di zero.
Approfondimenti ed esercizi
Aggiungere le funzioni dup count e add alla libreria dello stack per duplicare l'elemento di testa, restituire il numero di elementi dello stack e per aggiungere due elementi al top dello stack
Scrivere un programma che utilizzi la libreria di cui sopra, utilizzando un makefile (da scrivere anch'esso)
Errori in linguaggio C da evitare
• dimenticare le parentesi prima di referenziare un record.
• Dimenticare di liberare la memoria. Non è sufficiente scrivere top=NULL nella libreria dello stack, perchè questa azione crea blocchi “orfani” che necessitano di essere liberati
• Dimenticare di includere stdio.h quando si usano i puntatori e si utilizza NULL.
