Qualunque tipo di programma, semplice o complesso, poggia le sue basi su un insieme di dati di un certo tipo (tali tipi possono essere anche più d'uno) organizzati secondo le proprie esigenze. L'insieme organizzato e tipizzato di dati prende nome di struttura dati. Facciamo un paragone con un esempio preso della vita quotidiana. Pensiamo ad una libreria, quest'ultimo altro non è che un grande contenitore diviso in ripiani ognuno dei quali può contenere un numero finito di libri. Se ci serve altro spazio possiamo comprare un'altra libreria. Un libro a sua volta può essere visto come un insieme di pagine contenenti a loro volta testo. Schematicamente abbiamo una simile situazione:

Dalla figura si evince che la macro entità Libreria è composta da 4 sotto-tipi di dati ognuno dei quali con un proprio tipo. Una simile organizzazione forma la struttura dati "Libreria".
In questa lezione esamineremo alcune strutture dati molto comuni ed anche molto utili in quanto l'organizzazione dei dati della quasi totalità dei programmi può essere riconducibile ad esse. Tali strutture dati sono: Lista, Lista bi-direzionale, Pila ed Albero.

Allocazione dinamica della Memoria
Prima di passare in rassegna le strutture dati sopra menzionate, bisogna prima sapere come è possibile "chiedere al sistema operativo di darci altra memoria". Questa azione è chiamata in gergo Allocazione Dinamica, all'opposto c'è il rilascio della memoria che si chiama Deallocazione. Pensiamo all'esempio della libreria. Come facciamo a sapere quante librerie ci serviranno per tutta la vita (in programmazione è la vita del programma)? Non potremmo mai saperlo! Quando ne abbiamo bisogno andiamo al negozio e ne compriamo un'altra (chiediamo altra memoria per il programma al S.O.). Ma il negoziante avrà sempre una libreria della grandezza richiesta (ci sarà nel computer una quantità di memoria sufficiente a soddisfare la nostra richiesta)? Non è detto! In casi simili dobbiamo gestire questa condizione di ERRORE.
La memoria libera presente nel calcolatore viene chiamata Heap.
Il modo di allocare e deallocare memoria in C e C++ è diverso. Il C fa uso di funzioni di libreria mentre il C++ ha degli operatori che fanno parte direttamente nel linguaggio. Il motivo di una simile differenza sta nel fatto che il C++ deve poter allocare memoria anche per gli Oggetti e ricordiamo che un oggetto è composto da dati e funzioni e quindi deve essere trattato in un certo modo.
Esaminiamo prima l'allocazione dinamica in C. Il prototipo della funzione di allocazione è:

void *malloc(unsigned size);

Semplice no? La funzione prende in ingrasso un intero senza segno che rappresenta il numero di byte da allocare e restituisce un puntatore alla memoria allocata. Il puntatore restituito non ha tipo, ma come vedremo tra breve può essere convertito in un puntatore standard.
Per deallocare la memoria che non è più necessaria si utilizza invece la seguente funzione:

void free(void *block);

ovvero una funzione che prende in ingresso un puntatore e che non restituisce nulla.
Esempio completo in C:

#include <stdio.h>
#include <string.h>
#include <alloc.h>

#include <process.h>
 
int main(void)
{
    char *str;
    /* allocate memory for string */
    if((str = (char *) malloc(10)) == NULL)
    {
        printf("Not enough memory to allocate buffer\n");
        exit(1); /* terminate program if out of memory */
    }
    
     /* copy "Hello" into string */
    strcpy(str, "Hello");
    
    /* display string */
    printf("String is %s\n", str);

    
    /* free memory */
    free(str);
    return 0;
}

Esaminiamo le parti che più ci interessano:

• Conversione del puntatore void: Ciò che a noi serve è un puntatore a carattere, la conversione del puntatore tornato dalla malloc viene fatta in questo modo: (char *) malloc(10). Questo tipo di conversione si chiama Conversione Cast a run-time ed è una delle capacità del C/C++ che li rende dei potenti linguaggi di programmazione.
• Deallocazione: free(str); esaminando il prototipo delle funzione è necessaria una conversione cast. Siccome un puntatore void è più generale un (char *), la conversione viene fatta automaticamente dal compilatore.
• Puntatore nullo: un particolare valore che può assumere un puntatore è il valore nullo indicato con NULL. Tale valore deve essere controllato in modo da sapere se il contenuto della variabile puntatore è valido.

Passiamo al C++. L'operatore di allocazione è il new, mentre quello di deallocazione è il delete o delete[].

Puntatore = new tipo(num_byte);
delete[] Puntatore; oppure delete Puntatore;

Il precedente programma convertito in C++ diventa:

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <process.h>

int main()
{
    char *str; //allocate memory for string
    if((str = new char(10)) == NULL)
    {
        cout << "Not enough memory to allocate buffer\n" << endl;
        exit(1); //terminate program if out of memory
    }
    
    //copy "Hello" into string
    strcpy(str, "Hello");
    
    //display string
    cout << "String is " << str << endl;
    
    //free memory
    delete[] str;
    return 0;
}

Visto che il C++ include il C, in un programma C++ è possibile usare il sistema di allocazione-deallocazione del C. E' importante però rispettare la seguente regola: un puntatore allocato con l'operatore new deve essere deallocato con l'operatore delete, mentre un puntatore allocato con la funzione malloc deve essere deallocato con la funzione free.

Liste
Iniziamo la descrizione delle strutture dati complesse più comuni con le liste. Queste ultime non sono altro che una concatenazione logica di una struttura, struct, di base. La rappresentazione schematica di una struttura dati a Lista è la seguente:

Prima di andare avanti bisogna dare una avvertenza. Attenzione a non cancellare il Puntatore Principale. Se ciò accade, tutta la struttura dati andrà persa! Anzi, rimarrà anche allocata inutilmente memoria nel sistema!
La lista è governata dalla seguente regola: Un elemento della lista viene aggiunto sempre alla fine. Ovviamente secondo le proprie esigenze sarà possibile modificare la struttura e comportamento. Ad esempio una ottimizzazione nella velocità di inserimento potrebbe essere quella di mantenere un altro puntatore ausiliario che punta all'ultimo elemento della lista.
L'importante è però definire la struttura e le sue regole di utilizzo e rispettarle sempre nel programma onde evitare errori logici.
Vediamo come si realizza in C/C++ la definizione della struttura dati lista:

struct TLista;

struct TLista
{
    int dato1;
    int dato2;
    TLista *next;
};

TLista *Lista; //Il puntatore principale della lista

Esaminiamo il codice. La prima riga definisce l'esistenza di una struct chiamata TLista. Siccome la definizione di una lista è ricorsiva ovvero all'interno della struttura c'è una variabile puntatore dello stesso tipo della lista, la prima riga indica al compilatore di mantenere traccia del nome TLista e la sua definizione sarà esplicitata in seguito.
Subito dopo segue la struct che definisce il contenitore dei dati mantenuti da una lista. Nel record è possibile inserire qualunque tipo di dato standard o complesso definito prima della struct in esame. Notare la presenza del puntatore *Lista di tipo TLista. Questo puntatore è la variabile che lega logicamente uno dopo l'altro i vari record della lista.
Scriviamo adesso il codice C++ utile alla gestione della lista, nello specifico: inserimento di un elemento alla fine della lista, stampa del contenuto della lista e cancellazione totale della lista:

#include <iostream.h>
#include <conio.h>

struct TLista;

struct TLista
{
    int dato1;
    int dato2;
    TLista *next;
};
 
TLista *Lista;

void AggiungiElem(TLista *L, int d1, int d2);
void StampaLista(TLista *L);
void CancellaLista(TLista *L);

int main(int argc, char* argv[])
{
    Lista = NULL;
    Lista = new TLista;
    Lista->dato1 = 0;
    Lista->dato2 = 0;
    Lista->next = NULL;
    AggiungiElem(Lista,1,10);
    AggiungiElem(Lista,2,20);
    AggiungiElem(Lista,3,30);
    AggiungiElem(Lista,4,40);
    AggiungiElem(Lista,5,50);
    StampaLista(Lista);
    CancellaLista(Lista);
    getch();
    return 0;
}

void AggiungiElem(TLista *L, int d1, int d2)
{
    TLista *temp, *ultimo;
    
    temp = L;
    //esploro la lista fino alla fine.
    while(temp!=NULL)
    {
        ultimo = temp;
        temp = temp->next;
    }
    temp = new TLista;
    temp->dato1 = d1;
    temp->dato2 = d2;
    temp->next = NULL;
    ultimo->next = temp;
}

void StampaLista(TLista *L)
{
    TLista *temp;
    
    temp = L;
    while(temp!=NULL)
    {
        cout << "(" << temp->dato1 << ", " << temp->dato2 << ")";
        temp = temp->next;
    }
}

void CancellaLista(TLista *L)
{
    TLista *temp;
    
    temp = L;
    while(L!=NULL)
    {
        temp = L->next;
        delete L;
        L = temp;
    }
}

La funzione AggiungiElem(), aggiunge appunto un elemento alla lista. L'elemento è costituito da 2 numeri interi. Il ciclo while non fa altro che esplorare la lista fino alla fine e mantenere un puntatore che al termine del ciclo punterà all'ultimo elemento della lista, alloca la memoria per un nuovo record e lo collega alla lista, precisamente all'ultimo.
La funzione StampaLista(), tramite il ciclo while, scorre l'intera lista e per ogni record stampa tra parentesi tonde i due campi del record.
L'ultima funzione, CancellaLista(), è simile alla precedente. Il ciclo while scorre tutta la lista e mantiene un puntatore ausiliario che al momento della cancellazione del record punta al record successivo nella lista.

Lista Bidirezionale
La precedente struttura dati ha un problema: la scansione può essere fatta solo in un senso. Volendo creare una struttura dati lista che può essere esplorata in entrambi i sensi, è necessario apportare solo una piccola modifica, visibile schematicamente nella figura seguente:

Come si può vedere, è sufficiente aggiungere un altro puntatore di tipo "lista" che punta all'elemento logicamente precedente a quello in cui ci si trova.
L'esempio del precedente paragrafo può essere trasformato in lista bidirezionale apportando pochissime modifiche:

#include <iostream.h>
#include <conio.h>

struct TLista;

struct TLista
{
    int dato1;
    int dato2;
    TLista *next;
    TLista *prev;
};

TLista *Lista;

void AggiungiElem(TLista *L, int d1, int d2);
void StampaLista(TLista *L);
void CancellaLista(TLista *L);
 
int main(int argc, char* argv[])
{
    Lista = NULL;
    Lista = new TLista;
    Lista->dato1 = 0;
    Lista->dato2 = 0;
    Lista->next = NULL;
    Lista->prev = NULL;
 AggiungiElem(Lista,1,10);
    AggiungiElem(Lista,2,20);
    AggiungiElem(Lista,3,30);
    AggiungiElem(Lista,4,40);
    AggiungiElem(Lista,5,50);
    StampaLista(Lista);
    CancellaLista(Lista);
    getch();
    return 0;
}

void AggiungiElem(TLista *L, int d1, int d2)
{
    TLista *temp, *ultimo;
    
    temp = L;
    //esploro la lista fino alla fine.
    while(temp!=NULL)
    {
        ultimo = temp;
        temp = temp->next;
    }
    temp = new TLista;
    temp->dato1 = d1;
    temp->dato2 = d2;
    temp->next = NULL;
    temp->prev = ultimo;
    ultimo->next = temp;
}

void StampaLista(TLista *L)
{
    TLista *temp;
    
    temp = L;
    while(temp!=NULL)
    {
        cout << "(" << temp->dato1 << ", " << temp->dato2 << ")";
        temp = temp->next;
    }
}

void CancellaLista(TLista *L)
{
    TLista *temp;

    temp = L;
    while(L!=NULL)
    {
        temp = L->next;
        delete L;
        L = temp;
    }
}

Le modifiche fatte sono:

• Aggiunta del puntatore TLista *prev; nella definizione della struttura TLista.
• Aggiunta della riga Lista->prev = NULL; nel main per l'inizializzazione del primo record.
• Aggiunta della riga temp->prev = ultimo; nella funzione AggiungiElem(). Questa riga è quella che realizza la connessione logica tra i record consecutivi della lista.

Tutto il resto rimane inalterato.

Pila
Quando si è discusso sulla lista mono-direzionale, si è detto che gli elementi devono essere aggiunti sempre alla fine della lista. Ma se vogliamo invece inserirli all'inizio?? Ebbene, nessuno ci vieta di inserirli all'inizio, in questo modo però stiamo creando un'altra struttura dati! Più precisamente stiamo creando una struttura dati a Pila, nella quale gli elementi (i record) sono inseriti sempre "in testa". Questa organizzazione dei dati è anche detta LIFO dall'acronimo inglese Last In, First Out ovvero il primo ad essere inserito sarà l'ultimo ad essere tolto. Lo schema logico di una simile struttura dati è identico in ogni sua parte a quello dalla lista mono-direzionale, quindi non lo ripetiamo. Ciò che invece cambiano sono le operazioni di gestione. Fondamentalmente le operazioni possibili sono 2 ma nessuno vieta di aggiungerne altre di aiuto. Le operazioni principali si chiamano PUSH e POP. La prima inserisce un record in testa alla struttura dati mentre la seconda cancella la testa della pila restituendo come valore di output il contenuto della dell'elemento cancellato.
Riportiamo come di consueto un listato di esempio con l'aggiunta delle funzioni ausiliarie EMPTY che controlla se la pila è vuota e CLEAR_STACK che svuota tutta la pila liberando anche la memoria:

#include <iostream.h>
#include <conio.h>

#define DIMBUF 50

struct PILA;

struct PILA
{
    char strdir[DIMBUF];
    struct PILA *next;
} *Pila;

void PUSH(char *s);
void POP(char *s);
bool EMPTY(void);
void CLEAR_STACK(void);

int main(int argc, char* argv[])
{
    char msg[DIMBUF];
    
    PUSH("uno");
    PUSH("DUE");
    PUSH("tre");
    PUSH("QUATTRO");
    PUSH("--- fine ---");
    
    while(!EMPTY())
    {
        POP(msg);
        cout << msg << endl;
    }
    
    CLEAR_STACK();
    getch();
    return 0;
}

void PUSH(char *s)
{
    struct PILA *t = new PILA;
    
    if(t==NULL) return;
    else
    {
        strcpy(t->strdir,s);
        t->next = Pila;
        Pila = t;
    }
}

void POP(char *s)
{
    struct PILA *t;
    
    if(Pila!=NULL)
    {
        strcpy(s,Pila->strdir);
        t = Pila;
        Pila = Pila->next;
        delete t;
    }
}

bool EMPTY(void)
{
    if(Pila==NULL) return true;
    return false;
}

void CLEAR_STACK(void)
{
    char *buf=new char[DIMBUF];
    while(!EMPTY()) POP(buf);
}

Struttura dati ad Albero

L'ultima struttura dati che esamineremo prende il nome di struttura dati ad Albero in quanto la sua schematizzazione assomiglia ad un albero capovolto o ancora meglio ad un albero genealogico. Proprio sulla base di quest'ultima analogia, quando si parla di struttura dati ad albero, si usano i termini padre, figlio, ecc…, per i record che terminano la struttura si usa il termine foglia e in generale, un qualunque record della struttura viene indicato come Nodo. Il primo nodo della struttura prende il nome di Radice. Lo schema logico si presenta così:

Un albero che ha solo 2 figli si chiama Albero Binario, uno con 3 figli Albero ternario,…, uno con n figli si chiama Albero n-ario.
Pensate un attimo, ma non vi sembra di aver gia visto da qualche parte nel vostro computer una organizzazione simile? Di esempi ce ne sono tanti, ma quello più evidente è l'organizzazione dei file e cartelle del sistema operativo nel quale i nodi sono le singole cartelle e le foglie i file veri e propri (documenti, immagini,…). Altri esempi di impiego massiccio di queste strutture sono i database nei quali le righe delle tabelle sono organizzate ad albero ordinato per una maggiore velocità di ricerca rispetto ad una organizzazione sequenziale ordinata. Sugli alberi è stata fatta molta ricerca e sono nati tanti libri. Per lo scopo di queste dispense è sufficiente sapere come sono organizzati gli alberi, come si inserisce e cancella un nodo e come si può testare la presenza di un cero elemento nell'albero supponendo che sia ordinato.
Di seguito riportiamo il codice di un possibile esempio di utilizzo della struttura ad albero binario detto di ricerca in quanto è governato dalla seguente regola: dato un nodo contenente il valore X, il figlio sinistro contiene un dato minore di X mentre il figlio destro contiene un dato maggiore di X.

#include <iostream.h>
#include <conio.h>

struct TAlbero;

struct TAlbero
{
    int dato;
    TAlbero *Padre;
    TAlbero *FiglioDS;
    TAlbero *FiglioSN;
};
 
TAlbero *Albero;

void InOrder(TAlbero *A);
void PreOrder(TAlbero *A);
void PostOrder(TAlbero *A);
void TreeInsert(TAlbero *A, int v);
TAlbero *Minimo(TAlbero *A);
TAlbero *Successore(TAlbero *A);
TAlbero *DeleteNode(TAlbero *A, int key);
TAlbero *TreeSearch(TAlbero *A, int v);

int main(int argc, char* argv[])
{
    Albero=NULL;
    TreeInsert(Albero,5); TreeInsert(Albero,1);
    TreeInsert(Albero,10); TreeInsert(Albero,3);
    TreeInsert(Albero,6); TreeInsert(Albero,4);
    TreeInsert(Albero,0); TreeInsert(Albero,7);
    TreeInsert(Albero,2); TreeInsert(Albero,8);
    
    cout << "Radice: " << Albero->dato << endl;
    cout << "InOrder: "; 
    InOrder(Albero);
    cout<<endl;
    cout << "PreOrder: ";
    PreOrder(Albero);
    cout<<endl;
    cout << "PostOrder: ";
    PostOrder(Albero);
    getch();
    return 0;
}

void InOrder(TAlbero *A)  //Detto anche Ordine Simmetrico
{
    if(A!=NULL)
    {
        InOrder(A->FiglioSN);
        cout << A->dato << " ";
        InOrder(A->FiglioDS);
    }
}

void PreOrder(TAlbero *A) //Detto anche Ordine Anticipato
{
    if(A!=NULL)
    {
        cout << A->dato << " ";
        PreOrder (A->FiglioSN);
        PreOrder (A->FiglioDS);
    }
}

void PostOrder(TAlbero *A) //Detto anche Ordine Differito
{
    if(A!=NULL)
    {
        PostOrder (A->FiglioSN);
        PostOrder (A->FiglioDS);
        cout << A->dato << " ";
    }
}

void TreeInsert(TAlbero *A, int val)
{
    TAlbero *x, *y, *z;
    
    z = new TAlbero;
    z->FiglioSN = NULL;
    z->FiglioDS = NULL;
    z->Padre = NULL;
    z->dato = val;
    y = NULL;
    x = A;
    
    while(x!=NULL)
    {
        y = x;
        if(z->dato<x->dato) x = x->FiglioSN;
        else x = x->FiglioDS;
    }
    z->Padre = y;
    if(y==NULL) Albero = z;
    else
        if(z->dato<y->dato) y->FiglioSN = z;
        else y->FiglioDS = z;
}

TAlbero *Minimo(TAlbero *A)
{
    TAlbero *x;
    x = A;
    while(x->FiglioSN!=NULL) x = x->FiglioSN;
    return x;
}

TAlbero *Successore(TAlbero *A)
{
    TAlbero *x,*y;
    
    x = A;
    if(x->FiglioDS!=NULL) return Minimo(x->FiglioDS);
    else
    {
        y = x->Padre;
        while(y!=NULL && x==y->FiglioDS)
        {
            x = y;
            y = y->Padre;
        }
    }
    return y; 
}

TAlbero *DeleteNode(TAlbero *A, TAlbero *z)
{
    TAlbero *x,*y;
    if(z->FiglioSN==NULL || z->FiglioDS==NULL) y = z; else y = Successore(z);
    if(z->FiglioSN!=NULL) x = y->FiglioSN; else x = y->FiglioDS;
    if(x!=NULL) x->Padre = y->Padre;
    if(y->Padre==NULL) Albero = x;
    else
        if(y==(y->Padre)->FiglioSN) (y->Padre)->FiglioSN = x;
        else (y->Padre)->FiglioDS = x;
    if(y!=z) z->dato = y->dato;
    return y;
}

TAlbero *TreeSearch(TAlbero *A, int v)
{
    TAlbero *temp;
    
    temp = A;
    while(temp!=NULL && v!=temp->dato)
    {
        if(v<temp->dato) temp = temp->FiglioSN;
        else temp = temp->FiglioDS;
    }
    return temp; 
}

Iniziamo la spiegazione delle funzioni. Supponiamo di avere in memoria una albero come in figura:

• InOrder(): La funzione richiama ricorsivamente se stessa sul figlio sinistro del nodo attuale. Quando il nodo passato è nullo la ricorsione termina, si torna all'ultima funzione chiamante, si stampa il contenuto del nodo e comincia la ricorsione sul figlio destro. Questo processo ricorsivo termina quando si raggiunge l'ultima foglia figlia destra di un certo nodo. Il risultato stampato da questa funzione è: 10, 20, 30, 35, 40, 50, 70, 90, 80, 99.
• PreOrder(): La funzione stampa prima il contenuto del nodo e inizia il processo ricorsivo sul figlio sinistro e poi su quello destro. Il risultato stampato da questa funzione è: 50, 30, 20, 10, 40, 35, 70, 80, 90, 99.
• PostOrder(): La funzione inizia il processo ricorsivo sul figlio sinistro, poi su quello destro ed infine stampa il contenuto del nodo. Il risultato stampato da questa funzione è: 10, 20, 35, 40, 30, 90, 99, 80, 70.
• Minimo(): Ritorna il nodo che contiene il dato più piccolo ovvero, in base alla regola che governa un albero binario di ricerca, ritorna la foglia più a sinistra seguendo il disegno precedente (10).

Per esercizio provare a descrivere il comportamento delle altre funzioni.

Puntatore a Funzione
Concludiamo questa lezione con la descrizione di un particolare tipo di puntatori che non tutti i linguaggi possiedono: i puntatori a funzione. Così come abbiamo un puntatore ad intero, carattere, … così è possibile avere un puntatore il cui contenuto sarà l'indirizzo di memoria nel quale una certa funzione inizia. Per coloro i quali dopo questo corso vorranno imparare a programmare per Windows® senza utilizzare il framework VCL o MFC si troveranno subito a dover utilizzare almeno un puntatore a funzione. Senza addentrarci negli aspetti della programmazione base di Windows, diciamo soltanto che il sistema operativo utilizzerà questo puntatore in modo da poter richiamare il gestore dei messaggi che Windows manda all'applicazione.
La sintassi di dichiarazione di un puntatore a funzione è la seguente:

tipo_restituito (*nome_funz)(parametri);

dove parametri è un elenco di parametri di input della funzione dichiarato come di consueto. Vediamo un esempio:

...

double (*f1)(double x1);
double (*f2)(double x2,double x3);

...

cout << "2 elevato alla 32= " << pow(2,32) << endl;
f2 = pow;
cout << "2 elevato alla 32= " << f1(2,32) << endl;

...

cout << "Coseno di 0.321 radianti= " << cos(0.321) << endl;
f1 = cos;
cout << "Coseno di 0.321 radianti= " << f1(0.321) << endl;

...