/* File: piledin.c */ /* Time-stamp: "2002-05-17 00:23:56 calvanes" */ /* Scopo: rappresentazione sequenziale delle pile tramite array dinamico */ #include <stdlib.h> /* Richiede di dichiarare il tipo bool */ /* typedef int bool; */ /* Richiede di dichiarare la dimensione iniziale della pila */ /* #define DimInizialePila 10 */ /* Richiede di dichiarare il tipo degli elementi della pila */ /* typedef int TipoElemPila; */ /* definizione del tipo pila */ struct tipoPila { TipoElemPila *pila; int pos; int dimCorrente; }; typedef struct tipoPila TipoPila; /* implementazione delle operazioni primitive sulle pile */ void InitPila(TipoPila *pp) /* Inizializza la pila *pp, allocando la memoria per il vettore e ponendo a -1 l'indice dell'elemento affiorante. */ { (*pp).pila = malloc(DimInizialePila * sizeof(TipoElemPila)); (*pp).pos = -1; (*pp).dimCorrente = DimInizialePila; } /* InitPila */ bool TestPilaVuota(TipoPila p) /* Restituisce TRUE se la pila p e` vuota, FALSE altrimenti. */ { return (p.pos == -1); } /* TestPilaVuota */ void TopPila(TipoPila p, TipoElemPila *pv) /* Restituisce in *pv l'elemento affiorante della pila, senza modificare la pila. */ { if (TestPilaVuota(p)) printf("ERRORE: PILA VUOTA\n"); else *pv = p.pila[p.pos]; } /* TopPila */ void Push(TipoPila *pp, TipoElemPila v) /* Inserisce l'elemento v in cima alla pila *pp e, se la pila e` piena, aumenta la dimensione della pila. */ { if ((*pp).pos == ((*pp).dimCorrente - 1)) { /* pila piena: raddoppia la dimensione del vettore (*pp).pila */ (*pp).dimCorrente = (*pp).dimCorrente * 2; (*pp).pila = realloc((*pp).pila, (*pp).dimCorrente * sizeof(TipoElemPila)); } /* inserisce l'elemento v in cima alla pila */ (*pp).pos++; (*pp).pila[(*pp).pos] = v; } /* Push */ void Pop(TipoPila *pp, TipoElemPila *pv) /* Elimina l'elemento affiorante della pila p, restituendone il valore in *pv, e se necessario riduce la dimensione della pila. */ { if (TestPilaVuota(*pp)) printf("ERRORE: PILA VUOTA\n"); else { *pv = (*pp).pila[(*pp).pos]; (*pp).pos--; /* se la pila contiene un numero di elementi maggiore di DimInizialePila e inferiore ad un terzo della sua dimensione corrente, viene dimezzata la sua dimensione */ if ((*pp).dimCorrente > DimInizialePila && (*pp).pos < (*pp).dimCorrente/3) { (*pp).dimCorrente = (*pp).dimCorrente / 2; (*pp).pila = realloc((*pp).pila, (*pp).dimCorrente * sizeof(TipoElemPila)); } } } /* Pop */