STRUTTURE DATI DINAMICHE

Un linguaggio di programmazione che supporta i puntatori, i tipi record ''ricorsivi'' e l'allocazione dinamica della memoria permette di realizzare delle strutture dati dinamiche, cioè dei tipi di dato strutturati in cui la dimensione dei dati non è definita a priori e può anzi variare durante l'esecuzione del programma (ad esmpio insiemi, liste, alberi, grafi, numeri dove il numero delle cifre non è fissato a priori,...).
I costrutti necessari sono più o meno gli stessi per ogni linguaggio e sono simili a quelli del C, quindi in questo caso trattiamo il problema usando subito il C.

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 è 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, 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.
È 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; deve essere usata 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>.

RECORD RICORSIVI

Può succedere che vorremmo dichiarare un tipo di dato record ricorsivo, ad esempio 
struct REC { int F1; 
              ...
              int Fn;
              REC F;
            };
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 * F;
            };
infatti in questo caso, la componente F sara semplicemente un puntatore ad (indirizzo di) una cella che conterrà un valore di tipo REC.
Ricordandonci che ricorsivo in informatica significa precisamente induttivo, 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 sarà ovviamente più corto.

ESEMPIO: IL TIPO DI DATO INSIEME DI REALI

Realizziamo gli insiemi come liste di numeri reali ammettendo anche ripetizioni, e realizziamo le liste come struttura dati dinamica utilizzando i puntatori. In questo caso non facciamo assunzioni sul numero di elementi degli insiemi, cioè possiamo trattare insiemi finiti di ogni dimensione. 
typedef struct INS *INSIEME;

struct INS { 
            float ELEMENTO;
            INS * PROSSIMO;
          } ;
quindi un insieme è un puntatore che punta all'inzio della lista dei suoi elementi.

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

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

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

    while( (s1 != NULL) && 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 = NULL;
    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 == NULL)
        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 == NULL)
        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 == NULL) 
      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 == NULL) 
      return NULL;
   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 le versioni sicure siamo certi che gli argomenti non sono modificati; quando invece vogliamo proprio modificare gli argomenti si deve usare l'atra versione.
Anche le versioni sicure di unione ed intersezione non modificano ma neanche utilizzano le celle di memoria degli argomenti; in questo caso una successiva modica agli argomenti non modificherà la loro unione (intersezione)
Comunque nel caso di strutture dati dinamiche è 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 = NULL, aux = s, aux2;
  
    while(aux != NULL){  
        aux2 = Singleton(aux -> ELEMENTO);
        aux2 -> PROSSIMO = copia;
        copia = aux2;
        aux = aux -> PROSSIMO;
    };
   return copia;
}
ed una per eliminare (disallocare) un dato, come 
void Elimina(INSIEME s)
/* dissalloca s */
{   
   INSIEME aux;
   
   while(s != NULL){
       aux = s;
       s = s -> PROSSIMO;
       free(aux); 
       };
}
Le funzioni per leggere e scrivere gli elementi del tipo di dato sono 
INSIEME Leggi_S(void)
{
    char answer = 'S';
    float el;
    INSIEME s = NULL;
    
    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
    int 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
    int 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. Arrichire il tipo di dato insiemi con le operazioni: complementare, differenza ed intervallo, quest'ultima dati due numeri interi N ed M ritorna l'insieme { N, N+1, ..., M } se N <= M, l'insieme vuoto altrimenti.
    Dare sia le versioni safe che quelle unsafe.
  7. Dare i ''cartoni animati'' stile variabili<->scatole e puntatori<->frecce di alcune esecuzioni di alcune funzioni sugli insiemi definite precedentemente.
  8. 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 LIBERA -1
              Si assume che non vi siano ripetizioni. */
            int LIBERA;  /*indice della prima casella libera*/
          } ;
          
const  INSIEME Vuoto = { { 0 }, 0 };
/* l'insieme vuoto*/

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

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

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

    for(i = 0; i < s1.LIBERA && 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.LIBERA == MAX_CARD) printf("ERRORE: non c\'e\' piu\' spazio\n");
        else { s.ELEMENTI[s.LIBERA] = x; 
               s.LIBERA ++;
             };
    return s;
}

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

INSIEME Unione(INSIEME s1, INSIEME s2)
{      
    int i;
    
    for(i = 0; i < s1.LIBERA; 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.LIBERA; i++)
        if(Appartiene(s1.ELEMENTI[i],s2))
             s = Aggiungi_Elemento(s1.ELEMENTI[i], s);
    return s;
}

INSIEME Leggi_S(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: complementare, differenza ed intervallo, quest'ultima dati due numeri interi N ed M ritorna l'insieme { N, N+1, ..., M } se N <= M, l'insieme vuoto altrimenti.
  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.