Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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.

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.

La funzione push

In particolare la funzione push deve prevedere i seguenti passi fondamentali:

  • Dichiarazione un puntatore p di tipo elem
  • Allocazione memoria per un elemento puntato da p
  • Puntare al dato di input
    • p -> d = dato di input
  • Aggiornare il puntatore
    • p ->next = stk -> top
  • Aggiornare il puntatore alla testa dello stack
    • stk -> top = p
  • Aggiornare il numero di elementi presenti nello stack
    • stk -> cnt++
Push in una pila.

Push in una pila.


La funzione pop

In particolare la funzione pop deve prevedere i seguenti passi fondamentali:

  • Dichiarazione un puntatore p di tipo elem
  • Allocazione memoria per un elemento puntato da p
  • Estrarre il dato dalla testa ed aggiornare opportunamente i puntatori:
    • d = stk -> top -> d
    • p = stk -> top
    • stk->top=stk->top->next
  • Aggiornare il numero di elementi presenti nello stack
    • stk -> cnt–
  • Liberare la memoria a cui punta p
Pop in una pila.

Pop in una pila.


Linguaggio C – stack.h

Header file

In questa parte di codice scritto in Linguaggio C si descrive come puo’ essere sviluppato un header file dal nome stack.h per la gestione di uno stack.

Codice_C_1

Codice_C_1


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.

Esercitazione

La pila

In questa parte di codice scritto in Linguaggio C si descrive un programma di tipo main che richiama diversi moduli per la gestione di una pila.

Codice_C_2

Codice_C_2

Codice_C_3

Codice_C_3


Esercitazione

La pila: funzioni principali

Descriviamo alcuni dettagli di tipo realizzativo.

s puntatore alla struttura definita TipoStack costituita da:

  1. array puntatore all’array di elementi.
  2. maxElem variabile che contiene il numero degli elementi dell’array puntato da array.
  3. itop variabile che contiene l’indice corrente della pila.

Inoltre:

s->array indirizzo dell’array di elementi ovvero nome dell’array di elementi.
s->itop indice corrente della pila.
s->array[s->itop] valore dell’elemento dell’array s->array di indice s->itop.

Codice_C_4

Codice_C_4


Esercitazione

La pila: funzioni principali

  • La funzione void push(TipoStack *s, tipoElemento data), inserisce un elemento nella pila.
  • La funzione tipoElemento pop(TipoStack *s) estrae un elemento dalla pila.
  • La funzione tipoElemento top(TipoStack *s), ritorna il primo elemento della pila.
Codice_C_5

Codice_C_5


Esercitazione

La pila: funzioni principali

  • La funzione int size(TipoStack *s), ritorna la lunghezza della pila.
  • La funzione void destroy(TipoStack *s), distrugge la la memoria allocata per la pila.
  • La funzione void deleteElement(TipoStack *s, tipoElemento data), elimina un elemento della pila medinante la definizione delle operazioni ammesse per una pila: inserimento e prelievo dei dati solo dalla cima (top) della struttura.
Codice_C_6

Codice_C_6


Esercitazione

La pila: funzioni principali

  • La funzione void display(TipoStack *s), visualizza gli elementi della pila.
  • La funzione int isEmpty(TipoStack *s) segnala se la pila è vuota.
  • La funzione int isFull(TipoStack *s) segnala se la pila è piena.
Codice_C_7

Codice_C_7


I materiali di supporto della lezione

Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition.Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238--243.

salvatore-cuomo-4608-19-esercizi.zip

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion