Strutture Dati Astratte
Algoritmi e Strutture Dati
Molti algoritmi fanno usostrutture dati:
I persfruttare i serviziche queste mettono a disposizione;
I perriversare su di esse la complessit`adi alcune operazioni (senza doversi interessare della loro implementazione);
I per gestire dati secondo determinate politiche.
Inoltre, lestesse strutture dati possono essereutilizzate da pi`u algoritmi:
Esempio: La struttura codapu`o essere utilizzata per:
I gestire le richieste ad una stampante (coda di stampa);
I regolare l’esecuzione di pi`u processi (coda di priorit`a);
I memorizzare la frontiera in unavisita in ampiezza di un grafo;
Strutture Dati e Astrazione
Astrazione dei dati: Separazione del concetto “dato” dalla sua rappresentazione.
“Un’astrazione deve denotare le caratteristiche essenziali di un oggetto contraddistinguendolo da tutti gli altri oggetti e fornendo,
in tal modo, dei confini concettuali ben precisi relativamente alla prospettiva dell’osservatore”(Grady Booch).
Strutture Dati Astratte (ADT): strutture dati definite a prescindere dalla loro implementazione.
Opacit`a dei dati: ogni programma pu`o accedere alla struttura esclusivamentetramite i servizi (concetto diinterfaccia).
L’ADT pila di interi
Esempio: Vogliamo definire una pila di interi:
typedef struct STACK { ... }* Stack;
Qualiservizivogliamo dal tipoStack?
I Stack init( void ); inizializza una nuova pila;
I void push( Stack, int ); inserisce un intero nella pila;
I int pop( Stack ); toglie l’ultimo intero inserito e lo resituisce;
I int isEmpty( STACK * );dice se la pila `e vuota;
Tali servizi identificano l’interfaccia della struttura.
Vediamo una possibile soluzione: quella in C.
Strutture Dati Astratte
...in C
L’interfaccia `e un filestack.h. Serve definire un tipo Stack.
/* stack.h */
typedef struct STACK { int *store;
int top;
}* Stack;
Stack init( void );
void push( Stack, int );
int pop( Stack );
int isEmpty( Stack );
Non `e un ADT!! Non si implementano le funzioni, ok, ma si suppone cheSTACK sia implementato come un vettore!
Come risolvo il problema della rappresentazione del tipo STACK?
Dichiaro un tipo “puntatore all’etichettastruct STACK”.
/* stack.h */
typedef struct STACK* Stack;
Stack init( void );
void push( Stack, int );
int pop( Stack );
int isEmpty( Stack );
Posso definire la strutturaSTACKnel file di implementazione!
Ora siamo di fronte ad un ADT.
L’ADTStack pu`o essere implementato tramite vettore nel file di implementazione:
/* stack.c */
#include <stdio.h>
#include <stdlib.h>
#include ‘‘stack.h’’
#define MAX DIM 100
struct STACK { int store[MAX DIM]; int top; };
Stack init( void ) { ... }
void push( Stack s, int i ) {...}
int pop( Stack s ) { ... } int isEmpty( Stack s ) { ... }
Posso definire la strutturaSTACKnel file di implementazione!
Ora siamo di fronte ad un ADT.
Esempio di ADT per sorting
Nell’esempio visto a laboratorio, vediamo unaADT,Item, per memorizzare oggetti generici su cui fare sorting.
Servizi diItem:
I crea un nuovoItem (in modo casuale, per i test);
I dati dueItem, dimmi l’ordine (ordinamento totale);
I dato unItem, scrivilo sullo schermo;
In questo modo, possiamo riscrivere tutti gli algoritmi che ordinano vettori (diItem) astraendo da quali oggetti questi Item
rappresentano e da quale ordinamento sia definito su questi oggetti.
