Abstract Data Type (adt) pila



Scaricare 111 Kb.
29.12.2017
Dimensione del file111 Kb.

Prof.Ing.S.Cavalieri

L’ADT Pila in Linguaggio C a.a.2009/2010



La Struttura Dati Astratta (ADT) Pila
La pila o stack è una struttura dati astratta in cui l'inserimento e la cancellazione sono consentite solo in una specifica posizione, chiamata cima (top) dello stack. La gestione dello stack è anche chiamata LIFO (Last In First Out), in quanto l'ultimo elemento inserito è il primo ad essere estratto; come detto la posizione dell’ultimo elemento inserito (che potrà essere anche estratto) è chiamata top o cima.

Sia data una pila composta dagli elementi a1, a2, a3, …., an e si supponga che la cima sia rappresentata dalla posizione del primo elemento a1. L'inserimento di un elemento x produce la nuova pila x, a1, a2, a3, …., an. La nuova cima della PILA diviene la posizione di x. La cancellazione della cima ripristina la pila iniziale a1, a2, a3, …., an.



1.Operazioni Primitive sull’ADT Pila


La struttura dati astratta Pila è caratterizzata da alcune operazioni fondamentali. Sia:

  • s una generica pila

  • x un generico elemento dello stesso tipo degli elementi presenti nella pila. Nel seguito il tipo degli elementi contenuti in uno stack verrà chiamato tipobaseStack.

Le seguenti operazioni primitive vengono definite per un ADT Pila:



  • MakeNullStack(s). La funzione inizializza una Pila, restituendo una Pila vuota.

  • EmptyStack(s). La funzione restituisce il valore logico vero se la Pila s è vuota.

  • FullStack(s). La funzione restituisce il valore logico vero se la Pila s è piena.

  • Push(s,x). Questa funzione inserisce l'elemento x nella pila s, nella posizione rappresentata dal top. Se s è la Pila a1, a2,…, an, e se il top è rappresentato dalla posizione dell’elemento a1 della lista, la funzione Push(s,x) restituisce la nuova pila x, a1, a2,…, an.

  • Pop(s). Questa funzione elimina l'elemento della pila che rappresenta la cima. Se s è la Pila a1, a2,…, an e la cima è rappresentata dalla posizione del primo elemento, la funzione Pop(s) restituisce la nuova pila a2, a3,…, an e la nuova cima è rappresentata dalla posizione dell'elemento a2.

  • Top(s). La funzione restituisce l'elemento in cima alla Pila, che rimane inalterata


2.Rappresentazione della Struttura Dati Astratta Pila.


Sono possibili due rappresentazioni della Pila: rappresentazione sequenziale (utilizzando un vettore) e rappresentazione collegata. Quest’ultima rappresentazione può essere realizzata con vettore o con puntatori. Nel seguito verrà considerata solo quella realizzata con puntatori.

2.1.Rappresentazione Sequenziale.


La rappresentazione sequenziale della pila con vettore può essere realizzata come mostrato dalla seguente figura:


Si considera un vettore di N elementi; gli elementi della pila vengono inseriti nel vettore a partire dall’indice 0. Ciascun elemento nuovo verrà inserito nell’elemento del vettore di indice successivo a quello dell’ultimo elemento inserito.

Al fine di poter facilmente individuare l’indice dell’ultimo elemento inserito nella pila, una variabile, chiamata top, indicherà l’indice del vettore contenente l'ultimo elemento inserito. Nella figura top=4, ossia l'ultimo elemento inserito occupa il componente del vettore di indice 4. Quando è necessario inserire un nuovo elemento, top viene incrementata e il nuovo elemento viene posto nella posizione rappresentata da top.

Quando la pila è vuota, viene assunto che top=-1. Quando si deve inserire il primo elemento della pila, top viene incrementato di 1 e l'elemento è messo in posizione data da top, ossia in posizione 0.

Dunque l’algoritmo di inserimento di un elemento in pila è sempre lo stesso: prima si incrementa top e poi si inserisce l’elemento nel vettore in posizione indicata da top. Ovviamente l’inserimento può avvenire fino a quando la variabile top non diviene uguale a N-1; in tal caso la pila è piena.

Per quanto riguarda l'eliminazione dell'elemento in cima, ciò viene realizzato semplicemente decrementando la variabile top. Ovviamente l’eliminazione può avvenire solo quando la pila non è vuota, ossia top è maggiore o uguale a 0, per quanto detto. Nel caso in cui top sia uguale a 0 (pila con un solo elemento, l’eliminazione dell’elemento avviene decrementando top, che diviene pari a -1, ossia indica la condizione di pila vuota.

La seguente rappresentazione in C verrà adottata per rappresentare l’ADT Pila tramite rappresentazione sequenziale con vettore.

Al fine di rappresentare il tipo di dato di ogni singolo elemento della pila, si definirà il tipo tipobaseStack, come alias del tipo di appartenenza di ciascun elemento della pila. Ad esempio se il tipo di dato di ogni singolo elemento fosse float, l’implementazione del tipo tipobaseStack risulterebbe:
typedef float tipobaseStack;
Visto che alcune funzioni primitive della pila restituiscono un valore booleano, si preferisce definire il tipo boolean implementato dal tipo di dato short, ossia:
typedef short boolean;
Nella rappresentazione in C qui considerata, la pila viene definita da una struttura (struct) costituita da due campi: il vettore che conterrà gli elementi della pila e l'indice top. Tale variabile sarà relativa all’indice dell’ultimo elemento inserito nella pila, come già detto.

L’implementazione della pila in C sarà, dunque:


#define N 10
typedef struct {

tipobaseStack info[N];

int top;

} stack;
dove si è supposto che la pila abbia dimensione 10.


L'unica costante che serve per l'implementazione della pila in C deve indicare la pila vuota. Per tale motivo tale costante verrà chiamata PILAVUOTA. In base alla rappresentazione adottata, il valore di PILAVUOTA è rappresentato da -1 assunto da top. Dunque, la costante PILAVUOTA può essere rappresentata dalla definizione in C:
#define PILAVUOTA -1

Rappresentazioni delle Operazioni Primitive


Le seguenti funzioni implementano le operazioni primitive della Pila.
void MakeNullStack(stack *s) {

s->top=PILAVUOTA;

}
boolean EmptyStack(stack s){

return(s.top==PILAVUOTA);

}
boolean FullStack(stack s){

return(s.top==N-1);

}
void Push(stack *s, tipobaseStack x){

if (!FullStack(*s)) {

s->top++;

s->info[s->top]=x;

}

}
void Pop(stack *s){



if (!EmptyStack(*s))

s->top--;

}
tipobaseStack Top(stack s) {

if (!EmptyStack(s))

return(s.info[s.top]);

}


2.2.Rappresentazione Collegata.


La rappresentazione collegata con puntatori si basa sull'idea di considerare elementi allocati dinamicamente in memoria RAM, ciascuno dei quali è composto da due campi. Un campo memorizza il generico elemento dell’ADT Pila, mentre l'altro campo memorizza l’indirizzo di memoria del successivo elemento.

La rappresentazione collegata della pila con puntatori può essere simile a quella mostrata in figura.

Il puntatore s contiene l’indirizzo dell’ultimo elemento inserito, ossia della cima. Questo elemento a sua volta punta all’elemento inserito al passo precedente e così via. L’elemento (an), inserito per primo, non punta a nessun altro elemento (campo puntatore NULL).

L’inserimento di un nuovo elemento, x, consiste semplicemente nell’allocazione di un nuovo elemento in memoria, che dovrà contenere x e che dovrà puntare all’elemento a1, che rappresentava in precedenza la cima della Pila. La variabile s adesso punterà al nuovo elemento inserito, come visibile dalla seguente figura.




L’eliminazione della cima, analogamente avviene deallocando l’elemento contente la cima della Pila e facendo puntare s all’elemento il cui indirizzo era contentuo nell’elemento di cima, come si evince dalla seguente figura.


Nel caso di una pila vuota, la variabile s dovrà essere uguale a NULL, ad indicare una tale situazione. L’inserimento del primo elemento in Pila, avverrà come detto prima, ossia allocando il nuovo elemento e ponendo s uguale all’indirizzo dell’elemento appena allocato. Tale elemento non punterà a nessun altro, e dunque avrà il valore NULL nel campo relativo all’indirizzo del prossimo elemento. La figura seguente mostra la condizione in cui la Pila è vuota e si inserisce il primo elemento.


Nel seguito, la rappresentazione Pila con puntatori verrà definita nel linguaggio C.

Analogamente a quanto fatto per la rappresentazione sequenziale, anche in tal caso verrà definito il tipo tipobaseStack per rappresentare il tipo di dato di ogni singolo elemento contenuto nella pila. Ad esempio se il tipo di dato di ogni singolo elemento fosse int, l’implementazione di tipobaseStack risulterebbe:


typedef int tipobaseStack;
Verrà, poi, definito il tipo boolean:
typedef short boolean;
Infine la pila verrà implementata definendo un tipo struct nodoStack, che è costituito da campo info che contiene un generico elemento della pila e dal campo next che indica il successivo elemento nella pila. La pila coinciderà con il puntatore all’elemento di tipo struct nodoStack. La sua implementazione è:
typedef struct nodoStack {

tipobaseStack info;

struct nodoStack *next;

} * stack;


L'unica costante necessaria all'implementazione è PILAVUOTA, che indica la pila vuota. In base alla rappresentazione adottata, il valore di PILAVUOTA è rappresentato da NULL assunto dal puntatore al primo elemento della pila. Dunque, la costante PILAVUOTA può essere rappresentata dalla definizione in C:
#define PILAVUOTA NULL

Rappresentazione delle Operazioni Primitive

Le operazioni sulla pila vengono così realizzate:


void MakeNullStack(stack *s) {

*s=PILAVUOTA;

}
boolean FullStack(stack s) {

return(0);

}
boolean EmptyStack(stack s) {

return(s==PILAVUOTA);

}
void Push(stack *s, tipobaseStack x) {

struct nodoStack * temp;

temp=(struct nodoStack *)malloc(sizeof(struct nodoStack));

temp->info=x;

temp->next=*s;

*s=temp;


}
void Pop(stack *s) {

struct nodoStack * temp;


if (!EmptyStack(*s)) {

temp=(*s)->next;

free (*s);

*s=temp;


}

}
tipobaseStack Top(stack s)

{

if (!EmptyStack(s))



return(s->info);

}

3.Esempi di Gestione di Pila.


Il seguente programma si riferisce alla gestione di un ADT pila. Si suppone l’esistenza di un file di nome “Pila.h” contenente l’implementazione della pila (con vettore o con puntatore, come spiegato in precedenza) e la definizione del tipobaseStack.

Come si vede il programma utilizza delle funzioni per leggere ciascun elemento dell’ADT Pila dalla tastiera (LeggiElemento) e visualizzare ciascun elemento dell’ADT Pila sul video (VisualizzaElemento). Queste funzioni sono strettamente legate alla definizione del tipobaseStack, visto che le funzioni di input/output del linguaggio C dipendono dai tipi delle variabili dal leggere/scrivere. Tali funzioni sono dunque definite nel file Pila.h, in dipendenza della codifica del tipobaseStack.


#include
void flush(void);
#include "Pila.h"
stack archivio;
main() {

short s;


tipobaseStack elem;
MakeNullStack(&archivio);

do {


printf("Menu di Operazioni \n");

printf("1-Inserimento \n");

printf("2-Cancellazione \n");

printf("3-Svuota Pila \n");

printf("4-Ispeziona Elemento in Testa \n");

printf("5-Fine \n");

printf("Inserisci la scelta ");

scanf("%d",&s);

flush();
switch(s){

case 1 :

if (!FullStack(archivio)) {

LeggiElemento(&elem);

Push(&archivio,elem);

} else printf("Pila Piena \n");

break;
case 2 :

if (EmptyStack(archivio)) printf("Pila Vuota \n");

else {

Pop(&archivio);



printf("Primo Elemento Estratto \n");

}

break;


case 3 :

while (!EmptyStack(archivio)) Pop(&archivio);

break;
case 4 :

if (EmptyStack(archivio)) printf("Pila Vuota \n");

else VisualizzaElemento(Top(archivio));
}

} while (s<5);

}
void flush(void){

while (getchar()!='\n');

}
Nel caso di Rappresentazione Sequenziale, supponendo che il tipobaseStack sia un float, il file Pila.h è:
#define PILAVUOTA -1

#define N 10


typedef float tipobaseStack;
typedef short boolean;
typedef struct{

tipobaseStack info[N];

int top;

}stack;
void LeggiElemento(tipobaseStack * x){

printf("\nInserisci l'Elemento ");

scanf("%f",x);

flush();

}
void VisualizzaElemento(tipobaseStack x){

printf("\n\nElemento = %f \n\n", x);

}
void MakeNullStack(stack *s){

s->top=PILAVUOTA;

}

boolean EmptyStack(stack s){



return(s.top==PILAVUOTA);

}
boolean FullStack(stack s){

return(s.top==N-1);

}
void Push(stack *s, tipobaseStack x){

if (!FullStack(*s)) {

s->top++;

s->info[s->top]=x;

}

}


void Pop(stack *s){

if (!EmptyStack(*s))

s->top--;

}
tipobaseStack Top(stack s) {

if (!EmptyStack(s))

return(s.info[s.top]);

}

Nel caso di rappresentazione collegata, supponendo che il tipobaseStack sia uno stract contenente i campi: cognome, nome ed età, il file Pila.h è:
#include
#define PILAVUOTA NULL

#define S 15


typedef struct {

char cognome[S], nome[S];

unsigned short eta;

}tipobaseStack;


typedef short boolean;
typedef struct nodoStack {

tipobaseStack info;

struct nodoStack *next;

} *stack;


void LeggiStringa(char s[],unsigned short dim){

unsigned short i;

for (i=0; (s[i]=getchar())!='\n' && i

s[i]='\0';

}
void LeggiElemento(tipobaseStack * x){

printf("\nInserisci l'Elemento ");

printf("\nInserisci il Cognome ");

LeggiStringa(x->cognome, S);

printf("\nInserisci il Nome ");

LeggiStringa(x->nome, S);

printf("\nInserisci l'eta' ");

scanf("%d",&x->eta);

flush();

}
void VisualizzaElemento(tipobaseStack x){

printf("\n\nElemento ");

printf("\nCognome = %s ", x.cognome);

printf("\nNome = %s ", x.nome);

printf("\nEta' = %d \n\n",x.eta);

}

boolean FullStack(stack s){



return(0);

}
void MakeNullStack(stack *s){

*s=PILAVUOTA;

}
boolean EmptyStack(stack s){

return(s==PILAVUOTA);

}

void Push(stack *s, tipobaseStack x) {



struct nodoStack * temp;
temp=(struct nodoStack *)malloc(sizeof(struct nodoStack));

temp->info=x;

temp->next=*s;

*s=temp;


}
void Pop(stack *s) {

struct nodoStack * temp;


if (!EmptyStack(*s)) {

temp=(*s)->next;

free (*s);

*s=temp;


}

}

tipobaseStack Top(stack s){



if (!EmptyStack(s)) return(s->info);

}





elenco: users -> scava -> dispense -> FdINO
FdINO -> 1. Definizione di Albero
users -> La geografia (giochi di tragitti, di percorsi, di territori e confini, cacce al tesoro, idee di distanze, di lunghezze) La psicomotricità
users -> Una possibile sequenza di attività (anche di tipo ludico) su questo tema può essere la seguente, sperimentata in una classe 5
users -> Le indagini più recenti del Ministero dell’Istruzione sui dati della dispersione scolastica arrivano a concludere che la dispe
users -> Lezione 2 L'italiano d'oggi: le varietà funzionali, situazionali e strutturali
users -> Distinguiamo tra dimostrazione ed argomentazione; la prima ha carattere di certezza e di incontrovertibilità è usata nella ri
FdINO -> Struttura dati Coda
FdINO -> La Struttura Dati Astratta (adt) Lista
dispense -> Università degli studi di catania facoltà di Ingegneria
dispense -> Bus di Campo iec 61158: Caratteristiche Principali


Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale