Programmare in C – Un Esempio pratico: il linked stack

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.

Scarica subito una copia gratis

Scrivi un commento

Seguici anche sul tuo Social Network preferito!

Send this to a friend