TIPI DI DATO DATI DINAMICI

I tipi di dato dinamici, sono quei tipi di dato strutturati in cui la dimensione dei dati (cioè il numero delle sottocomponenti) non è definita a priori, anzi, può variare durante l'esecuzione del programma.
Esempi di tipi di dato dinamici sono: gli insiemi, le liste, gli alberi, i grafi, le stringhe la cui lunghezza massima non è fissata a priori, i numeri dove il numero delle cifre non è fissato a priori,...).

Alcuni linguaggi di programmazione offrono delle strutture dati dinamici predefinite (ad esempio, le liste nei linguaggi funzionali come il LISP ed ML), mentre nei linguaggi imperativi, di solito, queste strutture sono realizzate utilizzando i tipi puntatori, i relativi costrutti per l'allocazione dinamica della memoria, ed i tipi record "ricorsivi".
I costrutti necessari sono più o meno gli stessi per ogni linguaggio e sono simili a quelli del C, quindi in questo caso trattiamo direttamente il problema usando subito il C.

ESERCIZIO

ALLOCAZIONE DINAMICA DELLA MEMORIA

Avendo a disposizione i puntatori è possibile durante l'esecuzione di un programma decidere di usare una nuova cella di memoria, che quindi non corrisponde ad alcuna variabile dichiarata nel programma stesso; tale cella potrà solo essere individuata dal suo indirizzo, cioè da un puntatore.
È possibile che una tale richiesta fallisca, poichè non vi sono più celle libere (tutta la memoria è stata utilizzata sia per variabili dichiarate nel programma , sia per quelle allocate dinamicamente).
Quando queste celle allocate dinamicamente non servono più possono essere rilasciate, per essere utilizzate successivamente.

Seguendo la metafora variabile <=> scatola, questi costrutti corrispondono ad avere un certo numero di quelle scatole di cartone smontabili, quelle usate per esempio per i traslocchi, che vengono vendute appiatite.
Quando si abbisogna una nuova scatola, si richiede ad un montatore di montare una nuova scatola e di ritonare un modo per identificarla, cioè un nome di scatola (informaticamente un puntatore).
Potrebbe succedere che non vi siano più scatole da montare, e quindi la richiesta risulta in un fallimento.
Quando una di quese scatole smontabili non serve più è possibile rilasciarla, essa verrà smontata e sarà disponibile per future richieste.

Funzioni C per allocare memoria dinamicamente
void * malloc(size_t size)
malloc è la funzione che alloca della memoria dinamicamente, precisamente quanta indicata dal parametro size, e ritorna un puntatore a quella cella.
Il tipo di questa funzione è void *, cioè puntatore al tipo void, in pratica un puntatore generico.
size_t è il tipo C predefinito per la misura di memoria.

È possibile modificare il tipo di un puntatore generico per mezzo di un'operazione di casting; precisamente se p ha tipo void *, (TYPE *)p ha tipo TYPE *.

Se non è possibile allocare la memoria richiesta, questa funzione ritornerà NULL (il puntatore nullo).

void * calloc(size_t n, size_t size)
calloc allocherà n celle consecutive di memoria di dimensione size e ritornerà un puntatore alla prima di tali celle.
calloc deve essere usata per allocare memoria per gli array (ricordare che in C gli array sono in fondo dei puntatori).
Se non è possibile allocare la memoria richiesta, anche questa funzione ritornerà NULL.

Misura della memoria necessaria per un valore di un tipo
sizeof(TYPE) o sizeof(EXPRESSION) ritornano la misura della memoria necessaria a rappresentare un elemento del tipo o del valore passato come argomento.
Funzione C per rilasciare memoria allocata dinamicamente
void free(void * p)
free è la funzione che rilascia la memoria allocata dinamicamente puntata da p.
Se p è uguale a NULL, non farà niente.

Per usare le operazioni presentate sopra occorre premettere al programma
#include <stdlib.h>; questa è semplicemente il costrutto per richiedere l'uso di una libreria predefinita, che vedremo poi.

RECORD RICORSIVI

Può succedere che vorremmo dichiarare un tipo di dato record ricorsivo, ad esempio 
struct REC { int F1; 
              ...
              int Fn;
              REC Fn+1;
            };
questo non è accettato dal C e dagli altri linguaggi similari (es. Pascal, Ada); mentre se usiamo i puntatori nel seguente modo diventa accettabile 
struct REC { int F1; 
              ...
              int Fn;
              REC * Fn+1;
            };
infatti in questo caso, la componente Fn+1 sara semplicemente un puntatore ad (indirizzo di) una cella che conterrà un valore di tipo REC.

Il C offre una forma abbreviata per descrivere l'accesso ad un campo di un record individato da un puntatore; precisamente: se p ha tipo REC, (*p).Fi può essere scritto semplicemente p ->Fi.

Ricordiamo che comunque "ricorsivo" in informatica significa precisamente induttivo; infatti in questo caso stiamo definendo una struttura dati induttiva: la base è quando F contiene il puntatore NULL, ed il passo induttivo è quando costruiamo un elemento di tipo REC assegnando al suo campo F il puntatore ad un'altro elemento di tipo REC, che avremmo già costruito, e che sarà ovviamente più corto.

ESEMPIO: IL TIPO DI DATO INSIEME DI REALI

Realizziamo gli insiemi come liste di numeri reali ammettendo anche ripetizioni, chiaramente l'ordine degli elementi di tali liste non deve essere rilevante; e realizziamo poi tali liste come un tipo di dato dinamico utilizzando i puntatori.
In questo caso non facciamo assunzioni sul numero di elementi degli insiemi, cioè possiamo trattare insiemi finiti di ogni dimensione. 
#define BOOL int
#define TRUE 1
#define FALSE 0

typedef struct INS *INSIEME;

struct INS { 
            float ELEMENTO;
            INSIEME PROSSIMO;
          } ;
quindi un insieme è un puntatore che punta all'inzio della lista dei suoi elementi.
Il costrutto C typedef introduce un modo compatto per riferirsi al tipo struct INS *, cioè al tipo puntatore al record INS.

Le costanti e le operazioni principali del tipo di dato sono presentate di seguito. 

const INSIEME Vuoto = NULL;
/* l'insieme vuoto*/
          
BOOL Appartiene(float x, INSIEME s)
/* controlla se x appartiene ad s */
{
   BOOL app = FALSE;
   
   while( (s != Vuoto) && (! app) ) 
      if( x == s ->ELEMENTO ) 
          app = TRUE;
      else
          s = s -> PROSSIMO;
  return app;
}

/*altra versione piu' stile C
{   
   while(s != Vuoto) 
      if( x == s ->ELEMENTO ) 
          return TRUE;
      else
          s = s -> PROSSIMO;
  return FALSE;
}

*/

BOOL Contenuto(INSIEME s1, INSIEME s2)
/* controlla se s1 e' contenuto in s2 */
{
    BOOL cont = TRUE;

    while( (s1 != Vuoto) && cont ) 
        if( Appartiene(s1 -> ELEMENTO, s2) ) 
            s1 = s1 -> PROSSIMO;
        else
            cont = FALSE;
    return cont;
} 

INSIEME Singleton (float x)
/* ritorna l'insieme il cui unico elemento e' x */
{ 
    INSIEME s = (INSIEME)malloc(sizeof(struct INS));

    s -> PROSSIMO = Vuoto;
    s -> ELEMENTO = x;
    return s;
}

INSIEME Aggiungi_Elemento(float x, INSIEME s)
/*aggiunge x all'insieme s*/
{
    INSIEME primo;
  
    primo = Singleton(x);
    primo -> PROSSIMO = s;
    return primo;
}

INSIEME Togli_Elemento(float x, INSIEME s)
/*toglie x dall'insieme s, modifica s*/
{  
    if(s == Vuoto)
        return s;
    else if(x == s -> ELEMENTO)
             return Togli_Elemento(x, s -> PROSSIMO);
    else{ s -> PROSSIMO = Togli_Elemento(x, s -> PROSSIMO);
          return s;
        };        
}

INSIEME safeTogli_Elemento(float x, INSIEME s)
/*toglie x dall'insieme s, non modifica s*/
{  
    if(s == Vuoto)
        return s;
    else if(x == s -> ELEMENTO)
             return safeTogli_Elemento(x, s -> PROSSIMO);
    else 
       return Aggiungi_Elemento(s -> ELEMENTO, safeTogli_Elemento(x, s -> PROSSIMO));        
};

INSIEME safeUnione(INSIEME s1, INSIEME s2)
/* non usa s1 ed s2*/
{      
   if(s1 == Vuoto) 
      return Fai_Copia(s2);
   else return Aggiungi_Elemento(s1->ELEMENTO, safeUnione( s1 -> PROSSIMO, s2));
}

INSIEME safeIntersezione(INSIEME s1, INSIEME s2)
/* non usa s1 ed s2*/
{      
   if(s1 == Vuoto) 
      return Vuoto;
   else if(Appartiene(s1 -> ELEMENTO,s2))
        return Aggiungi_Elemento(s1->ELEMENTO, safeIntersezione( s1 -> PROSSIMO, s2));
        else return safeIntersezione( s1 -> PROSSIMO, s2);
        
}
Notare le due versioni della funzione per togliere un elemento, quella sicura e l'altra.
Questo è dovuto all'uso dei puntatori, utilizzando la versione sicura siamo certi che gli argomenti di tipo INSIEME non saranno modificati; quando invece vogliamo proprio modificare tali argomenti si deve usare l'altra versione.
Le versioni sicure di unione ed intersezione non modificano gli argomenti, ma neanche utilizzano le celle di memoria degli argomenti; in questo caso una successiva modica agli argomenti non modificherà la loro unione (intersezione) ritornata da questa funzioni.
Comunque nel caso di strutture dati dinamiche è sempre bene inserire nel tipo di dato una funzione per fare una copia di un dato, come la seguente. 
INSIEME Fai_Copia(INSIEME s)
/*ritorna una copia dell'insieme s*/
{
    INSIEME copia = Vuoto;
  
    while(s != Vuoto){  
        Aggiungi_Elemento(s -> ELEMENTO,copia);
        s = s -> PROSSIMO;
    };
   return copia;
}
ed una per eliminare (disallocare) un dato, come 
void Elimina(INSIEME s)
/* dissalloca s */
{   
   INSIEME aux;
   
   while(s != Vuoto){
       aux = s;
       s = s -> PROSSIMO;
       free(aux); 
       };
}
Le funzioni per leggere e scrivere gli elementi del tipo di dato sono 
INSIEME Leggi_Insieme(void)
{
    char answer = 'S';
    float el;
    INSIEME s = Vuoto;
    
    do{ printf("\nC\'e\' ancora un elemento? (S/N)\n");
        do scanf("%c", &answer);
        while(answer=='\n');
        if(answer=='S'){ printf("Darlo\n");
                         scanf("%f", &el);
                         s = Aggiungi_Elemento(el,s);
                        }
    }
    while(answer == 'S');
    return s;
}

void Stampa_Insieme(INSIEME s)
{   
    printf("{ ");
    while(s != NULL){
       if(! Appartiene(s -> ELEMENTO,s -> PROSSIMO)){
           printf("%f",s -> ELEMENTO);
           if(s -> PROSSIMO != NULL)
               printf(" , ");
       };
       s = s -> PROSSIMO;
    };
    printf(" }");
}

ESERCIZI

  1. Dare delle versioni non safe di unione ed intersezione.
  2. Si consideri la seguente ulteriore definizione di safeTogli_Elemento 
    INSIEME safeTogli_Elemento(float x, INSIEME s)
/*toglie x dall'insieme s, non modifica s*/
{  
    return Togli_Elemento(x, Fai_Copia(S));     
}
    Discutere le differenze con la versione data precedentemente.
  3. Dare una nuova realizzazione del tipo di dato insiemi definendo ogni qual volta è possibile delle funzioni C ricorsive. Per esempio: 
    BOOL Appartiene0(float x, INSIEME s)
/* controlla se x appartiene ad s */
{
   if( s == NULL ) 
      return FALSE;
   else if(x == s -> ELEMENTO)
            return TRUE;
   else return  Appartiene0(x,s -> PROSSIMO);
}
    è la versione ricorsiva di Appartiene.
  4. Dare una nuova realizzazione del tipo di dato insiemi utilizzando a più non posso le peculiarità del C. Per esempio: 
    BOOL Appartiene1(float x, INSIEME s)
/* controlla se x appartiene ad s */
{
   while((s != NULL) &&  x != s ->ELEMENTO ) 
             s = s -> PROSSIMO;
  return s != NULL;
}
    è la versione C-oriented di Appartiene.
  5. Dare una nuova realizzazione del tipo di dato insiemi dove gli insiemi sono realizzati con liste senza ripetizioni.
  6. Dare una nuova realizzazione del tipo di dato insiemi dove gli insiemi sono realizzati con liste senza ripetizioni ed ordinate in modo crescente.
  7. Arrichire il tipo di dato insiemi con le operazioni: differenza, cardinalità e controllo di ugualianza e di differenza.
    Dare sia le versioni safe che quelle unsafe.
  8. Dare i ''cartoni animati'' stile variabili<->scatole e puntatori<->frecce di alcune esecuzioni di alcune funzioni sugli insiemi definite precedentemente.
  9. Scrivere alcuni main per testare (controllare che siano corrette, trovare gli errori che sono stati fatti) le funzioni di una delle implementazione del tipo di dato degli insiemi date precedentemente.

UN'ALTRA IMPLEMENTAZIONE DEL TIPO DI DATO INSIEME DI REALI

Volgiamo dare un'altra implementazione del tipo di dato insieme di numeri reali, nel caso in cui possiamo assumere che la cardinalità degli insiemi considerati sia sempre minore di una certa costante K non troppo grande (ad esempio 100, 1000).
In questo caso possiamo utilizzare gli array ed evitare di usare i puntatori. 
#define MAX_CARD 100

struct INSIEME { 
            float ELEMENTI[MAX_CARD];  
            /*gli elementi dell'insieme sono allocati nelle componenti 
              dell'array ELEMENTI da quella di indice 0 a quella di indice 
              CARD -1
              Si assume che non vi siano ripetizioni. */
            int CARD;  /*cardinalita' dell'insieme, e' anche l'indice della 
            prima componente libera*/
          } ;
          
const  INSIEME Vuoto = { { 0 }, 0 };
/* l'insieme vuoto*/

BOOL Appartiene(float x, INSIEME s)
/* controlla se x appartiene ad s */
{
   BOOL app = FALSE;
   int i;
   
   for(i = 0; i < s.CARD && ! app; i++) 
      if( x == s.ELEMENTI[i] ) 
          app = TRUE;
  return app;
}

void Stampa_Insieme(INSIEME s)
{   
   int i;
   
   printf("{ ");
   for(i = 0; i < s.CARD -1; i++){
       printf("%f",s.ELEMENTI[i]);
                printf(" , ");
       };
    if(s.CARD > 0) printf("%f",s.ELEMENTI[s.CARD-1]);
    printf(" }");
}

BOOL Contenuto(INSIEME s1, INSIEME s2)
/* controlla se s1 e' contenuto in s2 */
{
    BOOL cont = TRUE, i;

    for(i = 0; i < s1.CARD && cont; i++) 
        if( !Appartiene(s1.ELEMENTI[i], s2) ) 
            cont = FALSE;
    return cont;
} 

INSIEME Singleton (float x)
/* ritorna l'insieme il cui unico elemento e' x */
{ 
    INSIEME s = { { x }, 1 };
    return s;
}

INSIEME Aggiungi_Elemento(float x, INSIEME s)
/*aggiunge x all'insieme s*/
{  
    if(!Appartiene(x,s))
        if(s.CARD == MAX_CARD) printf("ERRORE: raggiunta dimensione massima\n");
        else { s.ELEMENTI[s.CARD] = x; 
               s.CARD ++;
             };
    return s;
}

INSIEME Togli_Elemento(float x, INSIEME s)
/*toglie x dall'insieme s*/
{  
    int i;
    
    for(i = 0; i < s.CARD; i++)
        if(s.ELEMENTI[i] == x){
            s.ELEMENTI[i] = s.ELEMENTI[s.CARD-1];
            i = s.CARD = s.CARD-1;
        };   
    return s;  
}

INSIEME Unione(INSIEME s1, INSIEME s2)
{      
    int i;
    
    for(i = 0; i < s1.CARD; i++)
        s2 = Aggiungi_Elemento(s1.ELEMENTI[i], s2);
    return s2;
}

INSIEME Intersezione(INSIEME s1, INSIEME s2)
{      
    int i;
    INSIEME s = Vuoto;
    
    for(i = 0; i < s1.CARD; i++)
        if(Appartiene(s1.ELEMENTI[i],s2))
             s = Aggiungi_Elemento(s1.ELEMENTI[i], s);
    return s;
}

INSIEME Leggi_Insieme(void)
{
    char answer = 'S';
    float el;
    INSIEME s = Vuoto;
    
    do{ printf("\nC\'e\' ancora un elemento? (S/N)\n");
        do scanf("%c", &answer);
        while(answer == '\n');
        if(answer == 'S'){ printf("Darlo\n");
                         scanf("%f", &el);
                         s = Aggiungi_Elemento(el,s);
                        }
    }
    while(answer == 'S');
    return s;
}

ESERCIZI

  1. Discutere le differenze tra la versione che usa i puntatori e l'altra che usa gli array da un punto di vista dell'occupazione della memoria.
  2. Arrichire il tipo di dato insiemi implementato con gli array con le operazioni: , differenza, cardinalità, controllo di uguaglianza e di differenza.
  3. Scrivere alcuni main per testare (controllare che siano corrette, trovare gli errori che sono stati fatti) le funzioni di una delle implementazione del tipo di dato degli insiemi date precedentemente.