Tipo di dato astratto.

Introduzione

Per comprendere il concetto di Tipo di Dato Astratto (Abstract Data Types nel seguito ADT) è utile confrontare ADT con la nozione di procedura (funzione).

• La procedura(funzione) generalizza il concetto di operazione. Oltre alle operazioni elementari definite in un particolare linguaggio, quali addizione e sottrazione, è possibile, definire proprie operazioni ed applicarle a dei dati, che non necessariamente sono dati di tipo elementare, dati cioè definiti dal linguaggio utilizzato. Ad esempio è possibile introdurre attraverso le procedure (funzione) la somma di due vettori, oppure il prodotto tra matrici.

• La procedura (funzione) permette di incapsulare parte di un algoritmo localizzando in una determinata porzione di programma gli apetti che riguardano un determinato comportamente, o determinate operazioni. Ad esempio è possibile localizzare in una procedure tutti gli input, con relativi controlli, di un determinato programma. Il vantaggio considerevole è che noi sappiamo dove si trovano le istruzioni relative ad un determinato aspetto dell'algoritmo, per cui se si devono apportare modifiche, sappiamo dove operare. Se si decide che tutti gli input devono essere numeri positivi, possiamo modificare solo quelle poche linee di codice che riguardano la procedure di input.

Definizione di ADT.

Possiamo pensare ad un ADT come ad un modello matematico con un insieme di operazioni definite sul modello. Ad esempio un insieme di interi, con le operazioni di unione, intersezione, etc.. sono un semplice esempio di ADT.

In un ADT le operazioni possono avere come operando non solo una istanza dell'ADT ma anche altri tipi di operando. Ad esempio nell'ADT "insieme di interi" il risultato di un'operazione può essere una nuova istanza di ADT ma anche un semplice intero.

Le due proprietà viste per le procedure valgono anche per un ADT.

• Gli ADT sono una generalizzazione di dato primitivo (real, integer, etc.), così come la procedure è una generalizzazione di operazione.

• Un ADT incapsula un tipo di dato nel senso che la definizione di dato e tutte le operazioni relative sono localizzate in un determinato segmento di programma. Se si vuole cambiare la definizione di un determinato ADT, modificare o aggiungere operazioni, sappiamo dove guardare, e siamo sicuri che una eventuale modifica non altera il comportamento del programma che lo utilizza. Per un programma un ADT è a tutti gli effetti un dato primitivo.

Esempio.

Per comprendere quanto esposto in precedenza prendiamo in considerazione la data. In alcuni linguaggi di programmazione, soprattutto quelli rivolti a problemi di tipo gestionale, è disponibile un tipo di dato, la data, che permette di gestire le date. Vediamo come è possibile aggiungere al C questo nuovo tipo di dato.

Per gestire una data è necessario poter operare sul giorno, il mese e l'anno. Possiamo allora pensare di avere un nuovo tipo di dato, il tipo Data, con alcune operazioni definite.

• Per creare la data: Data dataCrea(int gg, int mm, int aa);
• Per creare una data nulla: Data dataCreaNulla( void );
• Per ottenere il giorno, il mese o l'anno di una determinata data:
  • int giorno(Data d);
  • int mese(Data d);
  • int anno(Data d);
• Poichè una data potrebbe essere nulla: int isDataNulla(Data d); 0 --> falso 1 --> vero
• Anche se non necessaria possiamo anche pensare di realizzare una funzione che formatta una data per la stampa: char* dataPrint( Data d );

Con queste operazioni primitive è possibile gestire una data. Ad esempio è possibile confrontare due date con una funzione che restituisce un numero negativo se la prima data precede la seconda, 0 se sono uguali, un numero positivo se la prima data segue la seconda.

	int dataCmp(Data d1, Data d2) {
		if(  anno(d1) == anno(d2) )
			if( mese(d1) == mese(d2) ) 
				return giorno(d1) - giorno(d2);
			else
				return mese(d1) - mese(d2);
		else
			return anno(d1) - anno(d2);
	}

Osservazione: abbiamo potuto scrivere la funzione dataCmp conoscendo quali sono le operazioni sulle date, senza sapere come sono state implementate. E' quanto avviene normalmente quando si utilizzano le operazioni predefinite.

Nell'esempio precedente le due funzioni di creazione, dataCrea e dataCreaNulla, si dicono costruttori, mentre le tre funzioni, giorno, mese, anno, si dicono selettori.

Il costruttore è quella funzione che permette di creare ed eventualmente inizializzare una variabile, il selettore è quella funzione che estrae un dato-parziale dalla variabile.

Esempio.

1. Costruire una funzione che coverte un giorno del mese in giorno dell'anno.

   Per risolvere il problema abbiamo bisogno di una funzione annoBisestile che avuto in ingresso un anno restituisce 1 se bisestile, 0 altrimenti.

   	int annoBisestile( int aa ) {
   		return aa % 4 == 0 && aa % 100 != 0 || aa % 400 == 0;
   	}
   	
   

   	int giornoDiAnno( Data d) {
   		char tab_giorni[2][13] = {
   			{0, 31,28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
   			{0, 31,29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
   		};
   		int giorni = giorno(d);
   		int i;
   
   		for(i = 1; i < mese(d); i++)
   			giorni += tab_giorni[annoBisestile(anno(d))][i];
   		
   		return giorni;
   	}
   
   

2. Costruire la funzione giorniTraDueDate, che avuto in ingresso due date restituisce il numero di giorni tra le due.

   	int giorniTraDueDate( Data d1, Data d2 ) {
   		int aa_min, aa_max, giorni_min, giorni_max;
   		int giorni = 0, i;
   
   		if( datacmp( d1, d2 ) < 0 ) { 	
   			aa_min = anno(d1); giorni_min = giornoAnno(d1);
   			aa_max = anno(d2); giorni_max = giornoAnno(d2);
   		} else { 
   			aa_min = anno(d2); giorni_min = giornoAnno(d2);
   			aa_max = anno(d1); giorni_max = giornoAnno(d1);
   		}
   
   		for(i = aa_min; i < aa_max; i++)
   			giorni += 365 + annoBisestile(i);
   		giorni = giorni - giorni_min + giorni_max;
   		return giorni;
   	}
   
   

	Data d2, d1 = dataCrea(18, 1, 1957);

	d2 = dataCrea(giorno(d1), mese(d1), anno(d1));

Data dataCreaCopia( Data d );

d2 = dataCreaCopia( d1 );

Chiarezza sui termini.

Che differenza c'è tra type (data types), struttura dati (data structures) e adt?

1. In un linguaggio di programmazione data type è l'insieme di valori che una determinata variabile può assumere. Ad esempio una variabile di tipo boolean può assumere due valori, vero e falso. I tipi elementari (basic data type) variano da linguaggio a linguaggio. In Pascal abbiamo integer, real, char e boolean. Anche le regole per costruire dati strutturati a partire dai tipi elementari variano da linguaggio a linguaggio.
2. Un ADT è un modello matematico con un insieme di operazioni definite su di esso.
3. Come abbiamo visto in precedenza si possono descrivere algoritmi utilizzando ADT, ma per scrivere il programma definitivo in un linguaggio di programmazione, è necessario rappresentare l'ADT in termini di data types e operazioni che il linguaggio mette a disposizione.
4. Per rappresentare un adt in un linguaggio di programmazione si utilizzano le strutture dati (data structures) che sono un insieme di variabili, anche di tipo differente, connesse tra loro in vario modo. La cella è l'elemento elementare di una struttura. Possiamo pensare alla cella come ad una scatola capace di contenere un valore di tipo elementare o composto. Le strutture dati sono create per attribuire un nome ad un insieme di celle che così vengono interpretate come una "cosa sola". Il più semplice aggregato di celle in Pascal, così come in C, è l'ARRAY, il vettore. Un altro aggregato di celle, dato strutturato, messo a disposizione del Pascal è il record, in C si chiama struct.

Realizzazione

Riprendiamo l'ADT data visto in precedenza. Per passare alla realizzazione del programma vero e proprio è necessario trasformare il tipo data in una struttura, utilizzando il linguaggio di programmazione che si ha a disposizione. Vediamo come si potrebbe fare in C.

Poichè la data deve contenere tre informazioni, il giorno, il mese e l'anno, possiamo pensare di utilizzare un vettore di interi. Allora la data sarà:

typedef int* Data;

La data nulla sarà un puntatore NULLO.

Le operazioni viste in precedenza devono diventare operazioni elementari su un vettore di interi. Vediamo prima i costruttori:

static int annoBisestile( int aa ) {
		return aa % 4 == 0 && aa % 100 != 0 || aa % 400 == 0;
}

	Data dataCrea( int g, int m, int a ) {
		char tab_giorni[13] = {0, 31,28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
		Data d;
		int giorni = (m == 2) annoBisestile(a):0;

		if( a < 0 ) return NULL;
		if( m < 1 || m > 12 ) return NULL;
		giorni += tab_giorni[m];
		if( g < 1 || g > giorni ) return NULL;
		
		d = calloc(3, sizeof(int));
		d[0] = g;
		d[1] = m;
		d[2] = a;
		return d;
	}

	Data dataCreaNulla( void ) {
		return NULL;
	}

	Data dataCreaCopia( Data d ) {
		Data d1 = calloc(3, sizeof(int));
		int i;
		for(i=0; i<3; i++) d1[i] = d[i];
		return d1;
	}

	int giorno( Data d ) {
		return d[0];
	}

	int mese( Data d ) {
		return d[1];
	}

	int anno( Data d ) {
		return d[2];
	}

	int isDataNulla( Data d ) {
		return d == NULL;
	}

	char* dataPrint( Data d )  {
		char *p, buffer = malloc(20);

		sprint( buffer, "%d-%d-%d", giorno(d), mese(d), anno(d) );
		return buffer;
	}

Un utile esercizio è il seguente: modificare la funzione dataPrint passando in ingresso anche un formato e prevedendo formati diversi di stampa della data.

Nuove realizzazioni.

Non esiste un solo modo per la realizzazione dell'ADT data. Altre possibili realizzazioni sono le seguenti:

1. typedef char* Data;

   In questo caso Data è un vettore di caratteri, 8, due per il giorno, due per il mese e quattro per l'anno. Realizzare le operazioni primitive.

2. typedef unsigned long* Data;

   In questo caso Data è un puntatore ad un intero senza segno. Per memorizzare una data sono necessari 5 bit per il giorno, 4 bit per il mese 11 bit per l'anno, se consideriamo al massimo sino al 2000. In tutto 5 + 4 + 11. Un campo long ha 32 bit. Operando sui bit si può memorizzare la data.

3. typedef unsigned long* Data;

   La data può essere memorizzata in un unsigned long come numero di giorni ha partire dall'anno 0 o da un anno successivo.

Osservazione.

typedef unsigned long * Data;

static int annoBisestile( int aa ) {
		return aa % 4 == 0 && aa % 100 != 0 || aa % 400 == 0;
}

Data dataCreaNulla( void ) {  /* rimane identico  */
	return NULL;
}

Data dataCrea( int g, int m, int a ) {
	char tab_giorni[13] = {0, 31,28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	Data d;
	int giorni = (m == 2) ? annoBisestile(a):0;

	if( a < 0 ) return NULL;
	if( m < 1 || m > 12 ) return NULL;
	giorni += tab_giorni[m]; 
	if( g < 1 || g > giorni ) return NULL;
	
	d = malloc(sizeof(unsigned long));
	*d = (a << 9) | (m << 5) | g;
	return d;
}

int giorno( Data d ) {
	return *d & 0x1F;
}

int mese( Data d ) {
	return (*d >> 5) & 0xF;
}

int anno( Data d ) {
	return *d >> 9;
}

ADT grande intero

Realizziamo un ADT grandeIntero che permette di utilizzare interi che superano la capacità dei long int.

Le operazioni necessarie sono quelle definite sugli interi. In particolare oltre alla somma, prodotto, sottrazione e divisione sarà necessario una funzione per creare l'intero inizializzandolo a zero, una funzione che genera il successivo, una funzione per assegnare. Come costruttori:

	Gint gintCrea( void ); 		crea un Gint inizializzandolo a zero
	Gint gintCreaN( int x ); 	crea un Gint inizializzandolo a x;
	Gint gintCreaGn( Gint n ); 	crea un Gint inizializzandolo ad n;
	Gint gintCreaS( char* s ); 	crea un Gint inizializzandolo ad s;

	Gint gintSuccessivo( Gint n );
	Gint gintSomma( Gint x, Gint y );
	Gint gintSottrai( Gint x, Gint y );
	Gint gintProdotto( Gint x, Gint y );

	int gintIsZero( Gint x );
	int gintCmp( Gint x, Gint y );

Con queste operazioni è possibile la realizzazione del fattoriale di un Gint.	
	
	Gint fattoriale( Gint i ) {
		Gint r = gintCreaN( 1 ), uno = gintCreaN( 1 ), s = gintCreaGn( i );

		while( !isZero( s ) ) {
			r = gintProdotto( r, s );
			s = gintSottrai( s, uno );
		}
		return r;
	}


Altra possibile realizzazione di fattoriale è in termini ricorsivi, utilizzando la seguente definizione:

	fattoriale(n) = 1 se n = zero
	altrimenti fattoriale(n) = n * fattoriale(n-1)

	Gint fattoriale( Gint n ) {
		if( gintIsZero( n ) ) return gintCreaN( 1 );
		return gintProdotto( n, fattoriale(  gintSottrai( n, gintCreaN( 1 ) )));
	}

Come si può vedere una volta dichiarate le operazioni sull'ADT Gint si possono realizzare algoritmi che le utilizzano. Una possibile realizzazione dell'ADT Gint è la seguente:

un Gint (grande int) è un vettore di unsigned char. Il vettore verrà gestito come una sequenza di bit in complemento a due. Il bit del segno è il bit 0. Le celle sono 16 ed il peso maggiore è quello della cella 0. Le funzioni che implementano le operazioni elementari sono così definite:

/************************************************/
/* Gint.h									*/
/* Libreria grandi interi. Un grande intero è	*/
/* un vettore di caratteri. Viene utilizzata    */
/* una rappresentazione in complemento a due.   */
/************************************************/

#define SIZE 16								/* dimensione del vettore  	*/
#define BASE sizeof( unsigned char ) * 8	/* numero bit per cella		*/

typedef unsigned char Cifra;
typedef Cifra* Gint;

Gint gintCrea( void );			/* crea Gint inizializzandolo a zero  				*/
Gint gintCreaGn( Gint );		/* crea Gint inizializzandolo al valore in ingresso */
Gint gintCreaN( int );			/* crea Gint inizializzandolo al valore in ingresso */
Gint gintCreaS( char* );		/* crea Gint inizializzandolo al valore in ingresso */

void gintZero( Gint );			/* azzera Gint in ingresso							*/
Gint gintSuccessivo( Gint );	/* restituisce Gint successivo						*/
Gint gintComplemento( Gint );	/* restituisce il complemento a due					*/
Gint gintAssegna( Gint, Gint);	/* assegnazione										*/
int gintIsZero( Gint );			/* è = zero?										*/
int gintCmp( Gint, Gint );		/* confronto										*/
Gint gintSomma( Gint, Gint );
Gint gintSottrai( Gint, Gint );
Gint gintProdotto( Gint, Gint );
void gintStampa( Gint );

La loro implementazione è la seguente:

/************************************************/
/* Gint.c									*/
/* Libreria grandi interi. Un grande intero è	*/
/* un vettore di caratteri. Viene utilizzata    */
/* una rappresentazione in complemento a due.   */
/************************************************/

#include "Gint.h"

static unsigned valuebit( Cifra x, int p )
{
        return (x >> p) & ~(~0 << 1);
}

static void modibit( Cifra* x, int p )
{
        Cifra y = 1;
 
        y = (y << p);
        *x = *x ^ y;
}

static Cifra modi( Cifra* v )
{
        int i;

        for(i=0; (i < BASE) && valuebit(*v, i); i++)
                modibit(v,i);
        if( i == BASE ) return 1;
        modibit(v,i);
        return 0;
}

Gint gintCrea( void ) {
	Gint i = (Gint)malloc(SIZE*sizeof(Cifra));
	int k;

        for(k=0; k= 0); k--)
                rip = modi( &ni[k] );
        return ni;
}

Gint gintComplemento( Gint i ) {
        Gint g = gintCreaGn( i );
        int k, j = 0;

        for( k = 0; k < SIZE; k++)
                g[k] = ~g[k];
        return( gintSuccessivo( g ) );
}

Gint gintCreaN( int x ) {
	Gint i = gintCrea(), k;
	int meno = x < 0;
	if( meno ) x = -x;
	for( ; x>0; x--) {
		k = i;
		i = gintSuccessivo( i );
		free( k );
	}
	if( meno ) return gintComplemento( i );
	return i;
}

Gint gintCreaS( char* s ) {

	/***************************************************************/
	/*    da realizzare !!!!!!!!!!!!!!!!!!!!!                      */
	/***************************************************************/
	
}

Gint gintAssegna( Gint d, Gint s )
{
        int k;
 
        for(k = 0; k < SIZE; k++)
                d[k] = s[k];
	return d;
}

Gint gintSomma( Gint i1, Gint i2 )
{
   	int rip = 0, k = SIZE-1, j = 0;
   	Gint r = gintCrea();
 

   	while( k >= 0 ) {
        	if(( valuebit( i1[k], j) == 1 ) && ( valuebit( i2[k], j ) == 1 ) ) {
        		if( rip == 1 )
modibit( &r[k], j );
            		rip = 1;
         	}
else  if(( valuebit( i1[k], j) == 0 ) && ( valuebit( i2[k], j ) == 0 ) ) {
                                if( rip == 1 )
modibit( &r[k], j );
                  				rip = 0;
                		}
else	if( rip == 0 )
modibit( &r[k], j );
                if( ++j == BASE ) {
                        j = 0; k--;
                }
	}
        return r;
}

Gint gintSottrai( Gint i1, Gint i2 )
{
        return( gintSomma(i1, gintComplemento(i2)));
}

void gintStampa( Gint i )
{
   /* stampa il contenuto delle singole celle in esadecimale!!!*/
        int k;
 
        for(k=0; k< SIZE; k++)
                if( i[k] != 0 ) return 0;
        return 1;
}

static void perdue( Gint i )
{
        int k, rip=0;
 
        for(k=SIZE-1; k>=0; k--) {
		int r=valuebit( i[k], BASE-1 );
                i[k]=( i[k] << 1);
                if( rip ) modibit( &i[k], 0 );
                rip=r;
        }
}
 
Gint gintProdotto( Gint i1, Gint i2 )
{
	Gint r = gintCrea();
	int i, k;
	
	for( i=0; (i=0; k-- ) {
	        	perdue( r );
	        	if( valuebit(i2[i], k) ) r = gintSomma( r, i1 );
		}
	return r;
}

Un utile esercizio è il seguente: scrivere due funzioni di supporto, str2gint e gint2str, che convertono rispettivamente una stringa contenente un numero nel corrispondente Gint e un Gint nella corrispondente stringa. Realizzare quindi gintCreaS che avuto in ingresso una stringa contenente un numero restituisce il corrispondente Gint, e la funzione gintStampa che stampa il Gint in ingresso utilizzando la base 10.

ADT razionale

Realizzare adt numeri razionali, rappresentati sotto forma di frazione.

Un ADT razionale deve mettere a disposizione le seguenti operazioni:

• Creazione del razionale: Razio razioCrea( int numeratore, int denominatore )
• Due selettori:
  • int razioNum( Razio r )
  • int razioDen( Razio r )

	Razio razioSomma( Razio x, Razio Y ) {
		return razioCrea( razioNum(x)*razioDen(y) + razioDen(x)*razioNum(y), 
							razioDen(x)*razioDen(y) );
	}

	Razio razioSottrai( Razio x, Razio y ) {
		return razioCrea( razioNum(x)*razioDen(y) - razioDen(x)*razioNum(y),
							razioDen(x)*razioDen(y) );

	Razio razioMoltiplica( Razio x, Razio y ) {
		return razioCrea( razioNum(x)*razioNum(y), razioDen(x)*razioDen(y) );
	}

	Razio razioDividi( Razio x, Razio y ) {
		return razioCrea( razioNum(x)*razioDen(y), razioDen(x)*razioNum(y) );

	void razioPrint( Razio x ) {
		printf( "%d/%d ", razioNum(x), razioDen(x) );
	}

	int razioUguale( Razio x, Razio y ) {
		return razioNum(x)*razioDen(y) == razioNum(y)*razioDen(x);
	}

	typedef struct {
			int num, den;
	} _Razio
	
	typede _Razio* Razio;
	
	
Per il costruttore:

	static int abs( int x ) {
		return (x >= 0)? x: -x;
	}

	static int mcd( int x, int y ) {
		int a;
		
		do {
			x = x / y;
			a = x; x = y; y = a;
		} while( y > 0 );
		return x;
	}

	Razio razioCrea(int n, int d) {
		Razio x=(Razio)malloc(sizeof(_Razio));
		int cd;
		
		if( d == 0 ) return NULL;
		if( n == 0 ) { x->num = n; x->den = d; }
		else {
			cd = mcd( abs(num), abs(den) );
			if( den < 0 ) { n = -n; d = -d }
			x->num = n / cd;
			x->den = n / cd;
		}
		return x;
	}

Per i selettori:

	int razioNum( Razio x ) {
		return x->num;
	}
	
	int razioDen( Razio x ) {
		return x->den;
	}