Salvatore Cuomo » 19.Strutture dati di tipo astratto

Introduzione

Definizione

un ADT (Abstract Data Type) è un modello (formale) che generalizza ed estende i tipi di dato primitivi e le operazioni definite su di essi;

Un ADT (es. contatore) è connotato da:

• lo stato dell’ADT (es. conteggio);
• i metodi che definiscono le operazioni ammesse sul dato astratto (modifica e/o accesso allo stato) (es. crea, elimina, azzera, incrementa, decrementa).

consente pertanto di estendere l’insieme dei tipi di dato predefiniti del linguaggio.

Esempio 1

La pila

Una pila (detta anche stack) è un ADT in cui l’accesso ai dati è realizzato con strategia LIFO (Last In First Out): l’operazione di estrazione restituisce l’elemento più recentemente inserito.

I metodi sono:

• init, crea e inizializza un’istanza vuota dell’ADT;
• push, inserisce un elemento;
• pop, estrae l’elemento più recentemente inserito;
• empty, restituisce vero se la pila è vuota, viceversa falso;
• destroy, elimina l’istanza dell’ADT.

Esempio 1 cont

Rappresentazione grafica di una pila.

Esempio 2

La coda

una coda è un ADT in cui l’accesso ai dati è realizzato con strategia FIFO (First In First Out): l’operazione di estrazione restituisce l’elemento presente da più tempo.

I metodi sono:

• init, crea e inizializza un’istanza vuota dell’ADT;
• enqueue, inserisce un elemento;
• dequeue, estrae l’elemento presente da più tempo;
• empty, restituisce vero se la coda è vuota, viceversa falso;
• destroy, elimina l’istanza dell’ADT.

Dichiarazione di uno stack

È possibile realizzare uno stack utilizzando una lista concatenata. Si può definire un nuovo tipo di dato

elem come:

struct elem{


data            d;
struct elem     *next;


};
typedef struct elem elem;

È possibile definire lo stack mediante una dichiarazione del tipo:

struct stack {


int   cnt;
elem *top;


};
typedef struct stack stack;

Dichiarazione di uno stack

Le funzioni da implementare sono:

• void initialize(stack *stk);

utilizzata per inizializzare lo stack.

• void push(data d, stack *stk);

utilizzata per inserire all’interno dello stack.

• void pop(data *d, stack *stk);

utilizzata per estrarre dallo stack.

• boolean empty(const stack *stk);

Per verificare quando lo stack è vuoto.

Esercizi sulla Pila

Problema

Sviluppare in linguaggio C un programma per una gestione di una Pila ( Stack ) basata su array, che implementi si seguenti i principali metodi:

• Aggiungi un elemento ( Push )
• Preleva un elemento ( Pop )
• Mostra l’elemento in cima alla Pila ( top )
• Mostra il numero di elementi nella Pila ( size )
• Verifica se la Pila e’ vuota ( isEmpty )
• Verifica se la Pila e’ piena ( isFull )

Esercizi sulla Pila

Osservazione

La Pila e’ un insieme ordinato di elementi. L’ ordine degli elementi nella pila e’ determinato dalle operazioni di inserimento e prelievo.

L’inserimento ed il prelievo avvengono ad una estremita’ dell’insieme detta cima della pila.

Esempi di applicazione della struttura Pila si trovano:

* nella gestione dell’indirizzo della prossima istruzione nelle chiamate ( eventualmente nidificate ) a sottoprogrammi.
* nella verifica dell’accoppiamento delle parentesi aperte e chiuse in una espressione.