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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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