Implementazione in C di una pila

La struttura dati pila

La pila è una struttura dati di tipo LIFO per cui l'ultimo elemento inserito è il primo a uscire.

Le operazioni sulla pila sono solo tre:

  • verifica che la pila [non] sia vuota (empty)
  • inserimento di un nuovo elemento (push)
  • restituzione di un elemento e cancellazione dalla pila (pop)

Esempio:

push('c')

c

push('i')

c i

push('a')

c i a

push('o')

c i a o

pop() // ottengo la o

c i a

pop() // ottengo la a

c i

Tempo di esecuzione

Inserimento: ο(1)

Cancellazione: ο(1)

Ricerca: ο(n)

Implementazione

In questa implementazione, la pila è un insieme di nodi, ciascuno dei quali contiene un valore di tipo char e un puntatore al nodo successivo.

// in stack.h
typedef struct stack * Stack;

// in stack.c
struct stack {
char c;
Stack next;
};

Nel file di header è definito un tipo Stack che rappresenta una struct stack *, quindi Stack è un puntatore.

Nel file .c è definita la struttura stack (s minuscola) che contiene il valore del nodo e il puntatore al nodo successivo. Una scrittura alternativa, che non fa uso della definizione del tipo Stack è la seguente:
// in stack.c
struct stack {
char c;
stack * next;
};

init

è stata aggiunta una funzione init() che alloca della memoria e restituisce il puntatore a un nodo vuoto.


Stack init() {
Stack s;
s = (Stack)malloc(sizeof(Stack));
s->next = NULL;
return s;
}

Il cast a Stack presente nella malloc non è strettamente necessario.

empty


int empty(Stack s) {
return s->next == NULL;
}

Dal momento che l'ultimo nodo è vuoto, faccio una verifica sul campo next.

push


void push(Stack *s, char c) {
Stack newStack;
newStack = init();
newStack->c = c;
newStack->next = *s;
*s = newStack;
}

push prende in ingresso il puntatore a uno Stack (quindi un puntatore al puntatore di stack con la s minuscola).

In questo modo quando si usa s si sta utilizzando un indirizzo di memoria, e non un valore. Nella pratica, si agisce sul dato contenuto nell'indirizzo puntato da s; viceversa sarebbe fatta una copia del contenuto di s.

Con puntatore Senza puntatore
push(Stack *s, char c)
è passato un puntatore a s
push(Stack s, char c)
è passato s: in realtà è una "copia" che ha la funzione come scope
Stack newStack;
newStack = init();
newStack->c = c;

Si inizializza un nuovo elemento Stack
Stack newStack;
newStack = init();
newStack->c = c;

Si inizializza un nuovo elemento Stack
newStack->next = *s;
il next contiene un puntatore a s
newStack->next = s;
il next contiene s (una copia del contenuto "originale")
*s = newStack;
l'indirizzo a cui punta s è sostituito dall'indirizzo a cui punta newStack
s = newStack;
s è sostituito dall'indirizzo a cui punta newStack

Al termine di queste operazioni, il contenuto di s nella funzione che utilizza push è cambiato solo nella versione con puntatore; viceversa l'esecuzione di push non ha effetto sulla funzione chiamante nella versione in cui è passato s come valore.

pop

La funzione pop restituisce un char e rimuove l'elemento dalla pila.
char pop(Stack *s) {
char c;
Stack oldS;
oldS = *s;
c = (*s)->c;
*s = (*s)->next;
free(oldS);
return c;
}

Vanno mantenute sia una copia del carattere sia del puntatore, perché dopo aver "spostato" il puntatore a next (*s = (*s)->next;) è necessario prima deallocare lo spazio ormai inutilizzato sia restituire il carattere, che "sopravvive" solo nella copia fatta precedentemente.

Se non si facesse il free dello spazio, questo resterebbe allocato senza che sia puntato da alcun puntatore. Quindi ci sarebbe uno spreco di memoria, crescente a ogni operazione, che si libererebbe solo al termine dell'esecuzione del programma tramite il garbage collector del sistema operativo.

main

main(int argc, char *argv[]) {
Stack s;
char c;
s = init();
push(&s, 'o');
push(&s, 'a');
push(&s, 'i');
push(&s, 'c');
while(!empty(s)) printf("%c", pop(&s));
pop(&s);
getchar();
}

Nel main è necessario passare come parametri non tanto il valore di s, quanto il suo indirizzo di memoria.
L'output di questo esempio sarà "oaic".
Al termine di questo esempio è stato aggiunto un getchar() per comodità.

Ricerca Operativa - 19

OK, 19 non è un voto di cui esattamente vantarsi, e Obama non è più il Presidente degli USA e non elargisce medaglie, MA...

All'inizio del mio percorso di studi avevo preventivato che ci potevano essere due motivi per cui ero giustificato nel sospendere i miei studi per un annetto, e sono alla fine del più piacevole dei due.

In questo contesto, anche solo aver portato a casa un esame - l'unico che ho tentato - mi dà una soddisfazione immensa.

Quindi, Obama: recupera qualche medaglietta dal fondo del cassetto e...