Traccia della lezione Lez12:

Lucido 2:
Si noti l'operatore di cast nell'allocazione. A rigore, malloc restituisce 
un puntatore "generico" (di tipo void *), dato che viene usata per allocare 
oggetti di qualsiasi tipo. I puntatori generici (void *) sono indirizzi 
puri e l'oggetto puntato è una singola cella. Questo non è grave, dato che 
in realtà i puntatori sono tutti codificati alla stessa maniera e non serve 
conoscere il tipo dell'oggetto puntato finché si considera solo il 
puntatore. Il problema nasce quando si vuole accedere all'oggetto puntato, 
perché non si sa quanto spazio esso occupi. Siccome di solito il risultato 
di malloc viene immediatamente assegnato a un l-value, e questo ha la sua 
dichiarazione di tipo, l'assegnamento fa anche una conversione implicita 
dal puntatore void * restituito da malloc al puntatore del tipo 
dell'l-value. Il cast serve quindi soprattutto a chiarire al lettore che 
cosa si sta facendo.

Ci si può chiedere perché allocare dinamicamente spazio per un oggetto 
puntato, anziché staticamente per una variabile, cioè perché scrivere
int *pi = (int *) malloc(10*sizeof(int));
anziché
int Vi[10];
Il motivo essenziale sta nel fatto che l'allocazione dinamica consente 
di decidere al momento dell'esecuzione quanto spazio allocare, usando 
per la dimensione un'espressione che contiene anche variabili:
int *pi = (int *) malloc(n*sizeof(int));

La memoria allocata con la funziona malloc sta in un'area definita nel suo
complesso come "heap" ("mucchio"), perché è un'area che viene occupata e
liberata in modo libero e non ordinato. Tutte le strutture che abbiamo
visto sinora (statiche), sia quelle del main sia quelle delle funzioni,
stanno in un'area definita "stack" ("pila"), che viene gestita in modo
molto rigoroso, come vedremo in una lezione futura.

Lucido 3:
Le varie strutture dinamiche sono composte da elementi omogenei, 
organizzati in vario modo grazie al meccanismo dei puntatori (si vedano 
i disegni alla lavagna):
- i vettori dinamici usano un solo puntatore al primo elemento: gli altri
  sono contigui e successivi;
- le liste sono formate da elementi composti (struct), ciascuno dei quali 
  contiene un campo puntatore all'elemento successivo;
- gli alberi sono formati da elementi composti (struct), ciascuno dei 
  quali contiene più campi puntatore agli elementi figli (o strutture più 
  sofisticate ancora);
- i grafi sono formati da elementi detti "nodi" (struct), ciascuno dei 
  quali contiene una lista di elementi detti "archi" (struct), che a loro 
  volta possono contenere puntatori agli elementi nodi.


Lucido 4:
La dimensione di un vettore dinamico può essere un'espressione variabile, 
dunque diversa ad ogni singola esecuzione. Per esempio, si può avere un 
vettore di voti degli studenti per un appello, la cui dimensione è pari 
al numero di studenti, diverso ad ogni appello.

Anche per i vettori dinamici, non c'è controllo che l'indice assuma valori 
sensati, cioè che non si vada a leggere o scrivere fuori dal vettore.

Le funzioni malloc e calloc sono quasi equivalenti: allocare una certa 
area oppure un certo numero di sottoaree contigue con la stessa dimensione 
complessiva è uguale. Per chiarezza, si usa la malloc per allocare un 
oggetto singolo, la calloc per i vettori dinamici.

La funzione calloc inoltre azzera l'intero blocco, per cui è più sicura
in caso di bachi. E' un po' meno efficiente, ma accade spesso che si 
voglia assegnare a tutti gli elementi del vettore un valore iniziale pari 
a 0. In tal caso, l'efficienza è la stessa.

Il codice DYNVECT.C illustra un esempio di vettore dinamico: all'utente 
si chiede di indicare via tastiera quanti numeri vuole inserire; il codice 
alloca un vettore della dimensione corretta, chiede all'utente di scrivere
i numeri e li legge, poi li stampa in ordine inverso. 
Sostituendo calloc con malloc, non cambia nulla, apparentemente. Se però 
si commenta il ciclo di lettura, stampando subito il contenuto del vettore
appena allocato, si scopre che calloc lo azzera e malloc no.

Gli esempi del lucido e del codice DYNVECT.C allocano n+1 blocchi, ciascuno
di sizeof(int) celle, producendo vettori con estremi 0 e n compresi.
Se si trattasse di stringhe dinamiche di lunghezza n, cioè vettori dinamici 
di n caratteri, occorrerebbero n celle per i caratteri più una per il 
terminatore, cioè ancora n+1 in tutto.

char *s = (char *) calloc(n+1,sizeof(char));

La differenza con i vettori di interi è che la stringa per convenzione 
parte dall'indice 0, mentre nei vettori abbiamo preferito partire da 1.


Lucido 5:
Se la dimensione dei dati è fissa e immutabile, van bene i vettori statici.
Se varia da un'esecuzione all'altra, ma è nota prima di cominciare a 
leggere i dati (per esempio perché è scritta all'inizio di un file o viene 
fornita dall'utente prima dei dati stessi), van bene i vettori dinamici.
Se la dimensione dei dati non è nota neppure quando si comincia a leggerli, 
una possibile soluzione è allocare una dimensione stimata e poi modificarla 
con la funzione realloc quando ci si accorge che era sbagliata (per difetto 
o per eccesso). 

Qualora la realloc allarghi l'area occupata, bisogna prestare attenzione 
ad eventuali alias, cioè puntatori a celle dell'area stessa, dato che è 
possibile che l'intera struttura venga spostata e copiata altrove,
mentre i puntatori resterebbero indirizzati all'area vecchia.

int *p, *q;
p = (int *) calloc(n+1,sizeof(int));
q = p;
p = (int *) realloc(2*n+1,sizeof(int));
/* Qui non è più possibile dire se p e q coincidono o no! */ 

Nel caso di riduzione, invece, l'area viene ridotta senza spostarsi. 
Le vecchie celle diventano disponibili, per cui potrebbero essere usate 
da allocazioni successive, e quindi conservare o perdere il loro contenuto
in modo imprevedibile.


Lucido 6:
Il puntatore NULL è definito come (void *) 0 in STDDEF.H.
Non occorre includere questa libreria, perché la include STDLIB.H.

L'uso dei puntatori come espressioni logiche è basato sulle regole di 
conversione implicita. Può provocare confusione. Si noti che:
- un puntatore NULL vale FALSO qualunque sia la definizione di NULL 
  (anche se fosse ipoteticamente diversa da 0)
- un puntatore non NULL vale VERO qualunque esso sia (al limite anche se 
  fosse 0)
In pratica tutti i compilatori definiscono NULL come 0, per cui i due 
concetti coincidono.


Lucido 7:
La funzione free è tipicamente odiatissima dagli studenti perché causa 
apparente di blocchi nel programma: si evita di deallocare, e il blocco
svanisce. In realtà, la funzione free non è la causa del blocco, ma solo 
il sintomo di errori compiuti altrove. Purtroppo, è particolarmente 
difficile individuare tali errori, dato che sono stati compiuti accedendo 
ad altri dati, sforando la loro dimensione fino a sovrascrivere in parte
il dato che viene liberato nella free. Quindi, è difficile sapere dove
sta l'errore, che può anche manifestarsi in free diverse (o non 
manifestarsi) a seconda della macchina e del compilatore.

Proprio per questo motivo, è fondamentale deallocare tutto ciò che si è 
allocato: in questo modo, emergono errori che altrimenti potrebbero 
passare sotto silenzio. Si deve essere grati all'ambasciatore che porta 
pena, anziché ignorarlo o sopprimerlo.
I quattro consigli del lucido (deallocare una volta sola, solo oggetti 
allocati dinamicamente, azzerare i puntatori dopo la deallocazione e 
fare attenzione alla riscalatura) vanno in questa direzione.

I puntatori che indicano aree non allocate si chiamano "puntatori 
pendenti" ("dangling pointers"). Si possono produrre per:
- mancata allocazione iniziale
- mancata riallocazione dopo una deallocazione intermedia

Un errore tipico è usare un puntatore come se fosse un vettore senza 
avergli allocato un'area di memoria:

char *s;
strcpy(s,"prova"); // mancata allocazione iniziale (sarebbe stato corretto 
                   // per una stringa statica, come char s[255+1];)

o dopo aver deallocato l'area che gli era stata allocata:

char *s = (char *) calloc(n+1,sizeof(char));
... 
free(s);
...
strcpy(s,"prova"); // mancata riallocazione

Può succedere anche se si hanno puntatori multipli alla stessa area e se 
ne dealloca uno.

char *s1, *s2;
s1 = (char *) calloc(n+1,sizeof(char));
s2 = s1;
... 
free(s1);
... 
strcpy(s2,"prova");

Esistono librerie da includere temporaneamente nel proprio codice, che 
sostituiscono le funzioni malloc e free e una serie di operatori in modo 
da registrare tutte le violazioni compiute durante l'esecuzione del 
programma. In questo modo, rivelano errori che possono essere corretti. 
Ovviamente, rallentano l'esecuzione, ma verranno disinstallate nella 
versione finale.


Lucido 8:
Si noti che le celle, disposte su due dimensioni nel disegno, sono invece 
ovviamente tutte disposte in fila lungo la memoria. Gli m+1 vettori 
(quello dei puntatori e quelli delle righe) sono formati da celle contigue
al loro interno, ma in generale non sono contigui fra loro, e neppure sono 
necessariamente nell'ordine "giusto", cioè per indici crescenti.

Si noti che i vettori delle righe vanno deallocati uno per uno, e che vanno 
deallocati prima del vettore dei puntatori, mentre ovviamente l'allocazione
del vettore dei puntatori precede quella dei vettori delle righe.

Per capire e ricordare meglio la costruzione di una matrice dinamica, 
può essere utile l'istruzione typedef:

typedef int *Row;
typedef Row *Matrix;

Matrix Mat;
int m, n, i, j;

Mat = (Matrix) calloc(m+1,sizeof(Row));
for (i = 1; i <= m; i++)
  Mat[i] = (Row) calloc(n+1,sizeof(int));
  
L'accesso agli elementi funziona come nelle matrici statiche. Infatti, M[i] 
è un puntatore, e quindi può essere usato come nome del vettore a cui
punta, e completato con un indice, quindi M[i][j].

Il codice DYNPRODUCT.C coincide con il codice PRODUCT.C della lezione sui 
vettori statici, ma invita a realizzare le stesse strutture dati come 
matrici dinamiche, da allocare e deallocare esplicitamente.
Il codice compila correttamente, ma eseguito dà errore, perché le matrici
vengono usate senza essere state allocate.

Per esercizio, si realizzino e si usino le funzioni: 
Matrix AllocaMatrice(int n);
void DeallocaMatrice(Matrix Mat, int n);

Si noti che, mentre nel codice con le matrici statiche porre A[1][12] = 0
azzerava automaticamente l'elemento A[2][1], dato che le righe sono 
consecutive, qui questo effetto non si realizza. Sul mio computer si 
ottiene tale effetto ponendo A[1][15] = 0.
Se poi le righe di A vengono allocate in ordine inverso (da n a 1), 
ponendo A[2][15] = 0 si azzera A[1][1] (sempre sul mio computer).

Lucido 9:
Si noti che i singoli elementi di una lista (o albero o grafo) sono 
necessariamente struct perché sono eterogenei: contengono campi (a loro 
volta possibilmente di vario tipo) che raccolgono le informazioni e 
un campo puntatore al elemento successivo. 

L'ultimo elemento della lista non ha successore; per convenzione, si 
adotta come indirizzo il puntatore nullo NULL. Per accedere al primo 
elemento della lista, si usa una variabile aggiuntiva L il cui tipo 
è un puntatore alla struct che fa da tipo per gli elementi della lista.

Si noti che la dichiarazione usata nel lucido impiega il tag di 
struttura anziché l'istruzione typedef.
Il motivo è che questa richiederebbe di scrivere:

typedef struct 
{ 
  ... info; 
  elemento *succ;
} elemento;

Ma la parola "elemento" usata nella definizione del campo succ non è 
ancora stata dichiarata, per cui il compilatore non la può usare. 
Con il tag di struttura, invece, "struct elemento" è già stato definito.

Volendo impiegare comunque typedef, occorre usare il tag di struttura e 
poi ridefinirlo con typedef:

struct _elemento
{ 
  ... info; 
  struct _elemento *succ;
};

typedef struct _elemento elemento;

Si noti la distinzione fra "_elemento" (tag di struttura) e "elemento" 
(nome del tipo). E' un trucco per usare due nomi simili, ma chiaramente 
distinti.

E' anche lecito anticipare la typedef, così da poterla usare dentro 
il tag di struttura per dichiarare il tipo del campo "succ".

typedef struct _elemento elemento;
struct _elemento
{ 
  ... info; 
  elemento *succ;
};


Lucido 10:
L'operatore -> è l'esatto equivalente della combinazione degli operatori 
* e . ma con regole di priorità scambiate rispetto a quelle standard.
Se scriviamo *pn.info, la valutazione segue l'ordine (*(pn.info)) perché
. prevale su *, cioè 
- prima si dovrebbe valutare il campo "info" della struct "pn"
- poi si dovrebbe valutare l'oggetto puntato da pn.info
In realtà, "pn" non e' una struct, ma un indirizzo, e quindi non ha campi;
inoltre il campo "info" non è un puntatore, e quindi non ha senso 
applicargli l'operatore *

Per evitare le parentesi, è stato quindi introdotto l'operatore composto 
-> che sostituisce * e . con la regola di precedenza desiderata.

Lucido 11:
Per capire il codice, conviene disegnare elementi e puntatori e vedere come 
cambiano.

Il codice LISTA.C alloca un elemento di valore 1 e ne stampa il campo info.
Poi lo inserisce nella lista L e stampa il primo elemento della lista 
(ovviamente uguale a 1). Poi alloca un elemento di valore 2, lo inserisce 
nella lista L e stampa il primo elemento della lista, che ora è 2.

Si noti l'uso di typedef per 
- ridurre da "struct _elemento" a "elemento" il nome del tipo degli 
  elementi della lista
- "nascondere" il fatto che la lista L è un puntatore a elemento