allocazione dinamica della memoria - puntatori a strutture - strutture con allocazione dinamica della memoria - stack con allocazione dinamica - coda con allocazione dinamica - la ricorsione - gestione di una lista concatenata

Unità 1 - Unità 2 - Unità 3 - Unità 4 - Unità 5 - Unità 6

Non sempre è nota a priori la dimensione di una struttura e quindi non è possibile utilizzare una struttura sequenziale che richiede la conoscenza di tale dimensione per poter allocare spazio in memoria. In questi casi viene utilizzata la struttura concatenata: si alloca spazio in memoria quando serve e tutto quello che serve, compatibilmente ovviamente con le risorse disponibili, e si collegano gli elementi fra di loro tramite puntatori, in modo che ogni elemento fornisca informazioni su dove trovare in memoria il successivo della lista.

Ora si esamineranno gli strumenti che mette a disposizione il linguaggio C per l’allocazione dinamica della memoria, in seguito si vedranno le funzioni principali per la gestione di una struttura concatenata.

La funzione restituisce il numero di byte che occorrono per conservare un dato del tipo di quello specificato come argomento della funzione. Come argomento della funzione si può specificare un tipo o anche una espressione:

In questo caso la variabile nbyte1 conterrà il numero di byte occorrenti per conservare in memoria un dato di tipo int e nbyte2 il numero di byte occorrenti per conservare in memoria un dato di tipo libro.

Le altre due funzioni specificate di seguito richiedono l’inclusione, nel programma che intende utilizzarle, di un nuovo header. Occorre specificare: #include <stdlib.h>.

La funzione alloca una zona di memoria atta a contenere un dato tipo e restituisce un puntatore a tale zona di memoria. Come argomento la funzione richiede di conoscere il numero di byte da allocare.

Qualora non fosse disponibile la quantità di memoria richiesta, la funzione restituisce nel puntatore il valore NULL (puntatore nullo: costante simbolica definita in stdlib.h utilizzata come valore da attribuire ad un puntatore di fine lista o come inizializzazione di un puntatore).

In 1 è dichiarato un puntatore alla struttura libro.

In 2 si richiede di allocare una zona di memoria tale da contenere una struttura di tipo libro; mediante un casting, il puntatore ritornato viene trasformato in puntatore alla struttura libro.

La funzione rilascia una zona di memoria prima allocata, per esempio, con una chiamata alla funzione malloc. La funzione richiede di conoscere, come parametro, il puntatore alla zona di memoria che si vuol liberare.

È opportuno notare la necessità dell’utilizzo di tale funzione. La memoria centrale è una risorsa limitata e quindi non è opportuno tenere allocata, per elementi che non sono più di nostro interesse, memoria che può essere utilizzata per conservare dati ancora utili per l’elaborazione da svolgere.

La chiamata: free(p1); libera la memoria allocata nell’esempio precedente.

inizio

Ricorre spesso, specie nelle elaborazioni che riguardano strutture dati dinamiche, così come si vedrà in seguito, la necessità di usare puntatori a strutture: per esempio per passare ad una funzione un riferimento ad una struttura.

Tali necessità sono così frequenti che il linguaggio C mette a disposizione uno speciale operatore: l’operatore -> (il trattino seguito dal simbolo di maggiore):

Nella 1 si dichiara la struttura che ha visibilità globale.

La 2 mostra il prototipo di una funzione che prepara un puntatore ad un dato di tipo struct libro.

Nella riga 3 si chiama la funzione leggi passando l’indirizzo di lib1, istanza della struttura libro.

Nelle 4 viene utilizzato l’operatore -> per accedere alle componenti della struttura. Una scrittura alternativa più lunga e, nel caso di strutture, poco usata sarebbe stata:

...

gets((*pl).titolo);

gets((*pl).autore);

...

inizio

Strutture con allocazione dinamica della memoria

Si è già trattato di pile e code implementandole in strutture sequenziali di memoria. È opportuno ricordare, come già fatto osservare a suo tempo, che la struttura sequenziale può andare bene solo a determinate condizioni:

• Se gli elementi della struttura sono pochi e può essere effettuata una previsione sulla quantità degli elementi che troveranno posto nella struttura, ed inoltre se in ogni momento si può prevedere una occupazione media della struttura stessa (si ricordi che la struttura occupa una porzione fissa di memoria e non può essere ampliata: è quindi indispensabile un calcolo abbastanza esatto dello spazio necessario per evitare sprechi ed avere sempre a disposizione posto per inserire elementi nella struttura)
• Se il problema da risolvere prevede l’uso di una sola struttura. Quando sono necessarie più strutture i problemi esposti in precedenza diventano più pressanti

L’allocazione dinamica permette di riservare spazio in memoria solo quando serve e solo quello che serve ed inoltre, l’uso di puntatori permette di operare più velocemente senza spostare fisicamente i dati, per esempio, nel passaggio di parametri. Sono questi due punti importanti nell’ottica di ottimizzazione di risorse: si tenga presente che l’elaboratore trova impiego nel trattamento di grosse masse di dati e quindi la razionalizzazione dello spazio occupato e la velocità di elaborazione sono due punti critici da curare particolarmente.

L’input di un nuovo elemento da inserire in una struttura di dati potrebbe essere svolto, utilizzando l’allocazione dinamica della memoria, secondo lo schema esposto.

L’inclusione specificata in 1 permette di utilizzare le funzioni per l’allocazione dinamica della memoria.

Nella 2 si definisce un puntatore alla struttura libro. In questo modo non si alloca spazio in memoria come sarebbe se fosse stata definita una variabile di tipo libro. Lo spazio, necessario prima di effettuare l’input, viene allocato in 3.

La funzione malloc quando non riesce ad allocare spazio ritorna il valore NULL nel puntatore: tale condizione è testata in 4. Per il modo con il quale il C tratta le condizioni, la 4 poteva più propriamente essere espressa come: if(!buflib).

Nelle 5 vengono effettuati gli input nelle varie componenti della struttura. Si noti l’uso dell’operatore -> per referenziare le singole componenti.

A cominciare da 6 si può usare l’input effettuato per le elaborazioni richieste. Qualora richiesto, per passare l’input effettuato ad una funzione, basta passare il puntatore (si può, per esempio, utilizzare const se si tratta di passaggio per valore).

inizio

Si riportano di seguito le funzioni per la gestione di uno stack solo che, stavolta, gli elementi nello stack sono allocati dinamicamente.

L’inclusione specificata in 1 permette, all’interno del programma, di utilizzare le funzioni per l’allocazione dinamica della memoria.

Nella 2 la dichiarazione di un puntatore alla struttura rec è preceduta dalla dichiarazione di definizione di tipo typedef. Tale dichiarazione permette di utilizzare lpointer allo stesso modo dei tipi definiti dal C, come per esempio il tipo int. lpointer diventa, con questa dichiarazione, un sinonimo di struct rec *, così come libro diventa sinonimo di struct rec. Ciò permette di incrementare la leggibilità delle dichiarazioni, la quale cosa sarà di utilità specie nelle dichiarazioni complesse.

Così come messo in evidenza nelle righe precedenti, nella struttura libro oltre agli attributi visti negli altri esempi, viene dichiarato in 3 un puntatore al prossimo elemento della lista: next è una variabile di tipo lpointer cioè, come evidenziato in 2, un puntatore a libro. Come è possibile notare, la praticità di tale dichiarazione permette di abbreviare e rendere più chiara la natura della variabile next. Tale variabile viene utilizzata per collegare ogni elemento al suo successivo.

La dichiarazione presente in 4 è l’unica che alloca effettivamente spazio in memoria. Viene dichiarata la variabile cima che è di tipo lpointer e che viene inizializzata al valore NULL. Ciò indica che, in questo momento, la struttura è vuota.

Alla funzione push nella 5 viene passato un puntatore alla zona di memoria dove è conservato l’elemento da inserire nella struttura. L’attuale contenuto di cima viene copiato, nella 6, nel puntatore next. Se c’era NULL vorrà dire che questo elemento inserito sarà considerato l’ultimo, se invece puntava ad un elemento E_i, con tale assegnazione E_i diventa il successivo dell’elemento che si sta inserendo. Il puntatore cima, per la 7, da questo momento punterà all’ultimo elemento inserito.

La funzione pop, come definito in 8, ritorna un puntatore all’elemento estratto. Nella 9 viene definita una variabile di tipo lpointer alla quale viene assegnato il valore di cima. Come osservato, nei commenti riguardanti la push, cima punta all’ultimo elemento inserito. Nel caso in cui lo stack fosse vuoto, il valore assegnato sarebbe NULL per l’inizializzazzione della 4. Il programma chiamante deve controllare tale eventualità.

La funzione pop, come specificato in 8, ritorna un puntatore all’elemento estratto dallo stack. Il puntatore ritornato, come osservato precedentemente, assume, come messo in evidenza da 9, il valore di cima: è questo infatti il puntatore all’ultimo elemento inserito. Se lo stack è vuoto il puntatore, per la 4, varrà NULL. L’istruzione presente in 10 testa quest’ultimo caso: se c’era almeno un elemento, cima dovrà puntare al successivo.

Il chiamante dovrà verificare se la pop ritorna un puntatore valido e, finito l’utilizzo dell’elemento estratto, dovrà occuparsi di liberare, con una chiamata alla funzione free, la memoria occupata dall’elemento.

inizio

La logica della gestione di una coda, fatte salve le specificità, è simile alla logica di gestione dello stack: si dovrà tenere conto solo del fatto che qui si devono gestire due puntatori.

Le dichiarazioni presenti in 1 sono formalmente simili a quelle presenti nella gestione dello stack, eccezione fatta per la presenza, in questo caso, di due puntatori invece che uno solo: testa utilizzato per i prelievi, fondo per gli inserimenti.

La funzione aggiungi in 2, si occupa dell’inserimento di un nuovo elemento nella coda. La funzione riceve un puntatore all’elemento da inserire e, per prima cosa (per la 3) considera tale elemento ricevuto come ultimo e quindi registra nel suo puntatore il codice di fine coda. Si occupa poi di modificare il puntatore dell’ultimo elemento che era presente nella coda, ammesso che esista (condizione testata in 4) e quindi di aggiornare fondo al nuovo elemento. Il controllo presente in 5 si occupa di verificare se testa era NULL (non c’erano cioè elementi prima di questo inserito) e, in tal caso fa in modo che tale puntatore conservi l’indirizzo dell’elemento inserito.

La funzione elimina della 6 preleva un elemento dalla coda, restituendo un puntatore allo stesso. Poiché testa punta al primo elemento da prelevare, è il valore di tale puntatore che deve essere restituito (istruzione 7). Se, all’atto del prelievo, c’era almeno un elemento, testa dovrà puntare al prossimo: è di ciò che si occupa il controllo 8. Il controllo presente in 9 si occupa di verificare se l’elemento prelevato era l’ultimo e, in tal caso reinizializza il puntatore fondo.

Così come osservato per la gestione dello stack, il chiamante, finito l’utilizzo dell’elemento estratto dalla coda, dovrà liberare la memoria occupata.

inizio

Il linguaggio C consente l’uso di funzioni ricorsive. Una funzione ricorsiva è una funzione che richiama sé stessa (ricorsione diretta) o richiama una funzione che a sua volta la richiama (ricorsione indiretta). Affinché il procedimento abbia fine è necessario che siano verificate le due seguenti proprietà:

1. Debbono esistere dei parametri (valori base) per cui la funzione non richiami sé stessa
2. Ogni volta che la funzione richiama sé stessa i parametri devono essere più vicini ai valori base

L’uso di tali funzioni è di utilità per la codifica di algoritmi che sono definiti ricorsivamente. Un esempio classico di algoritmo ricorsivo è quello che definisce il fattoriale di un numero.

Il fattoriale del numero n intero positivo (cioè n!) è definito:

• uguale a n*(n-1)! se n ¹ 0

• uguale a 1 se n = 0

In altri termini è vera la seguente uguaglianza: n! = n*(n-1)*(n-2)*..2*1. La prima definizione data è di tipo ricorsivo: il fattoriale di un numero viene calcolato come prodotto del numero stesso per il fattoriale del numero che lo precede. Affinché il procedimento sia finito si assume in pratica la posizione: 0! = 1.

Nella 1 viene definito il prototipo della funzione che calcola il fattoriale, funzione chiamata dal main nella riga 2. A tale funzione è passato per valore il numero di cui si vuole calcolare il fattoriale.

La struttura condizionale che inizia da 3, come si nota chiaramente, non fa altro che esprimere utilizzando le caratteristiche del linguaggio di programmazione, la definizione di fattoriale. La funzione chiama sé stessa (nella 4) passando come parametro il valore, decrementato di una unità, del parametro ricevuto e in questo modo ci si approssima, come richiesto dalle proprietà espresse precedentemente, al valore 0 (valore base). Tale ultimo valore, in dipendenza della verità della condizione espressa in 3, blocca il processo ricorsivo. La funzione calcFatt poteva, facendo riferimento alla seconda definizione data, essere scritta utilizzando una struttura ciclica:

Nella prima versione di calcFatt il ciclo è in pratica sostituito dalla chiamata ricorsiva; l’algoritmo risulta più leggibile, più vicino al nostro modo di concepire la risoluzione del problema.

La ricorsione può essere utilizzata per scrivere qualsiasi funzione che utilizzi assegnazioni, istruzioni if-else e while. A titolo di esempio si propone il programma per il calcolo della somma di una serie di numeri, terminanti con il valore nullo, scritto utilizzando una funzione ricorsiva al posto di una struttura ciclica:

Anche in questo caso, nella definizione della funzione, esiste un valore base (questo==0) e la funzione, richiamando sé stessa si approssima a tale valore (se si immaginano tutti gli input in una coda di attesa, ogni volta che se ne preleva uno con la funzione scanf, ci si avvicina alla fine della coda).

L’uso della funzione ricorsiva in questo caso rende più evidente l’algoritmo utilizzato. La struttura che comincia dalla riga 1 si può infatti interpretare:

inizio

Gestione di una lista concatenata

La lista concatenata è la struttura ideale da utilizzare quando si debbano rappresentare insiemi di dati in cui le operazioni di inserimento e cancellazione siano prioritarie. Tali operazioni, come si vedrà, vengono permesse in maniera estremamente agevole dalla struttura.

Nel caso di una lista non c’è una allocazione preventiva della struttura: si definiscono le strutture di cui si ha bisogno, la memoria verrà allocata quando serve, quando cioè si tratterà di conservare gli elementi.

Le dichiarazioni presenti sono simili a quelle utilizzate nell’implementazione di uno stack: anche in questo caso si deve collegare ogni elemento con il suo successivo.

La dichiarazione presente in 1 è l’unica che alloca effettivamente spazio in memoria. Viene dichiarata la variabile entryp che è di tipo lpointer e che viene inizializzata al valore NULL. Questa rappresenta il puntatore al primo elemento della lista (entry point); i successivi elementi della lista saranno raggiungibili attraverso i puntatori contenuti in ogni nodo.

Definita la struttura concatenata, ci si occuperà delle operazioni fondamentali sulle liste. La prima operazione esaminata riguarda l’attraversamento di una lista: l’esame cioè di tutti i nodi presenti nella lista. Nel programma scritto di seguito vengono riportate solo le istruzioni riguardanti l’elaborazione richiesta; per la definizione della struttura si fa riferimento a quanto scritto in precedenza.

Nella 1 viene dichiarato il prototipo della funzione che si occuperà di esaminare un nodo della lista: tale funzione riceverà il puntatore al nodo da esaminare.

La funzione verrà chiamata, come in 2, passandogli inizialmente l’entry point in modo da puntare al primo elemento.

L’esame degli elementi della lista è effettuato con una funzione ricorsiva: se il puntatore passato (vedi 3) è un puntatore valido, elabora l’elemento e richiama la funzione passando il puntatore contenuto nel nodo esaminato (il puntatore al prossimo nodo). A cominciare da 4 si elabora l’elemento (quello raggiungibile per mezzo del puntatore p1); nel caso specificato in questa sede, l’elaborazione è una visualizzazione delle informazioni contenute nel nodo stesso.

La funzione getchar specificata in 5 legge un carattere dalla tastiera. In questa applicazione viene svuotato il buffer della tastiera (riga precedente la 5) e si aspetta (per mezzo del ciclo presente in 5) il carattere newline. In pratica si blocca il programma permettendo di leggere gli output: il programma proseguirà in seguito alla digitazione del tasto <Invio> .

Nella 6 viene chiamata ricorsivamente esamina passandogli come parametro il puntatore al prossimo nodo della lista.

La lista concatenata è un insieme ordinato di elementi: la successione logica degli elementi è quella data dai puntatori. Nel frammento di programma successivo ci si occuperà dell’inserimento di un nuovo libro nella lista in modo che i libri siano ordinati per titolo.

L’inserimento di un nuovo elemento, così come la cancellazione di un elemento esistente, sono operazioni che avvengono in modo agevole perché vengono effettuate mediante l’uso dei puntatori. Sono operazioni molto veloci sia perché per mantenere l’ordine non è necessario inserire fisicamente l’elemento nel posto che gli compete (si sottolinea che, a differenza dell’array, l’ordine logico non coincide con l’ordine fisico), sia perché si opera mediante i puntatori con le locazioni di memoria interessate alle operazioni.

Prima di passare ad esaminare le funzioni che effettuano l’inserimento di un nodo in una lista, è bene chiarire l’algoritmo utilizzato al fine di una più agevole comprensione delle funzioni stesse e dei parametri utilizzati.

Il programma si occuperà per prima cosa di trovare il posto giusto dove inserire il nodo (si ricorda che i libri devono essere registrati in ordine alfabetico per titolo).

Tenendo conto che ogni elemento della lista contiene oltre ai dati del libro registrato, il puntatore al prossimo elemento, e che è proprio questo che occorre modificare affinché punti all’elemento da inserire, occorre conoscere l’indirizzo di memoria del puntatore da modificare affinché possa avvenire tale modifica. Non si tratta infatti, in questo caso, di accedere all’elemento successivo per cui basta solo la conoscenza del valore del puntatore, bensì di modificare tale valore affinché punti ad un nuovo elemento.

Trovato il puntatore da modificare l’inserimento dell’elemento viene effettuato in maniera agevole.

Nelle 1, al solito, sono riportati i prototipi delle funzioni utilizzate: la inserisci si occupa dell’inserimento effettivo mentre le altre funzioni si occupano di predisporre le condizioni affinché tale inserimento possa aver luogo.

In 2 viene allocato, tramite la funzione malloc, lo spazio necessario per contenere un elemento di tipo libro. La funzione restituisce un puntatore alla memoria allocata, è necessario quindi verificare se tale puntatore punta effettivamente ad una zona di memoria valida (il puntatore deve cioè contenere un valore diverso da NULL). Se tale condizione è verificata vengono acquisiste le informazioni da conservare e si passa, nella 3, il valore contenuto nel puntatore alla funzione aggiungi che si occuperà dell’inserimento.

La funzione aggiungi dichiara nella 4 la variabile ppos come puntatore a lpointer, praticamente un puntatore a puntatore. È in questi casi che la typedef fornisce i suoi maggiori vantaggi: senza il suo uso si sarebbe dovuto scrivere struct rec **ppos; con un notevole sforzo mentale per cercare di fissare le idee sul senso di puntatori e puntatori di puntatori. Con la definizione di tipo la 4 si può leggere: si dichiara ppos come un puntatore al tipo lpointer. Come osservato prima si tratta di cercare il puntatore il cui valore dovrà essere modificato, è necessario passare alle funzioni un puntatore alla variabile il cui contenuto dovrà essere modificato.

La funzione cerca si occupa di ritornare, così come evidenziato in 1, un puntatore al dato da modificare (che è un puntatore). A tale funzione viene passato, come specificato in 5, l’entry point e il titolo da confrontare per trovare la giusta posizione di inserimento. Alla funzione inserisci, chiamata successivamente in 6, si passa il puntatore al dato da modificare ritornato da cerca e il puntatore all’elemento da inserire.

La funzione cerca verifica, in 8, se il titolo del libro puntato è alfabeticamente successivo al titolo del libro che si sta inserendo, o, in 7, se la lista è terminata. Laddove una di queste condizioni è verificata la funzione ritorna l’indirizzo del puntatore poiché è questo il dato da modificare e quindi occorre conoscere il suo indirizzo. Se nessuna delle condizioni descritte prima è verificata, la funzione chiama ricorsivamente sé stessa (9) passando ad esaminare il prossimo elemento della lista.

La funzione inserisci si occupa dell’inserimento effettivo dell’elemento nella struttura concatenata. La funzione riceve, come evidenziato in 10, il puntatore all’indirizzo da modificare e il puntatore all’elemento da inserire. Il puntatore al punto di inserimento dovrà contenere l’indirizzo del nuovo elemento (12), ma prima il vecchio contenuto del punto di inserimento dovrà essere assegnato al puntatore del nuovo elemento (11). È opportuno fare notare che un errore nell’assegnazione dei valori ai puntatori, per esempio scambiare di posto la 11 e la 12, comporta la perdita di fatto degli elementi successivi della lista: ogni elemento contiene informazioni per rintracciare il prossimo, basta modificare in maniera erronea un puntatore perché tutti gli elementi da quel punto in poi, scompaiano, anzi non sono mai esistiti (non è possibile rintracciarli in alcun modo).

L’algoritmo per l’eliminazione di un nodo dalla lista è simile a quello dell’inserimento.

Si cerca l’indirizzo dell’elemento da cancellare, si modifica tale indirizzo con il contenuto del puntatore dell’elemento da cancellare (in modo che tale indirizzo non punti più all’elemento che si deve eliminare, ma al prossimo della lista) e si rende libera, per eventuali altri usi, l’area di memoria prima occupata dall’elemento cancellato.

In 1 viene acquisito il titolo del libro da eliminare e passato, in 2, come parametro alla funzione che si occuperà di cercare il puntatore all’elemento da cancellare. Se tale puntatore contiene un valore valido (test effettuato a cominciare da 3), si passa come parametro (in 4) alla funzione elimina che procederà alla cancellazione dell’elemento dalla lista.

La funzione cerca è la stessa funzione esaminata nell’inserimento: cambia solo il confronto da effettuare (espresso in questo caso dalla 5). In questo caso si tratta di trovare la coincidenza del titolo conservato nel nodo con il titolo da cancellare.

L’eliminazione dell’elemento prevede in 6 la conservazione temporanea del puntatore al fine di recuperare l’area di memoria con la chiamata alla free della 8. La cancellazione dell’elemento è effettuata in 7: nella sequenza dei puntatori si salta l’elemento da non considerare aggiornando in tal modo la sequenza logica degli elementi.

Inizio