I puntatori
Da Hacknowledge.
La memoria RAM del calcolatore non è altro che un insieme di locazioni di memoria; per poter localizzare ciascuna locazione, ognuna di esse è identificata da un indirizzo univoco. Questo significa che:
- Per scrivere qualcosa in memoria centrale dobbiamo conoscere l'indirizzo del punto esatto in cui scrivere;
- Se conosciamo l'indirizzo di una data locazione possiamo leggere ciò che è contenuto al suo interno.
Indice |
[modifica] Strutture dinamiche
a differenza delle strutture dati di tipo statico che allocano i dati in "contenitori" prefissati (array, record etc etc), con i puntatori è possibile realizzare delle strutture dati DINAMICHE ottimizzando l'utilizzo della memoria e allo stesso tempo rendendo possibile l'implementazione di algoritmi che ottimizzano anche il tempo di esecuzione dell'elaborazioe dei dati.
I puntatori sono il trampolino di lancio per la programmazione ad oggetti, infatti l'istanza di una classe non è altro che il puntatore ad un'area di memoria disegnata in maniera tale da corrispondere alla struttura della classe.
[modifica] Liste monolanciate
[^start]-->[(DATA)(^next)]-->[(DATA)(^next)]-->[(DATA)(NULL)]
una lista è una struttura dati dinamica che a differenza dell'array non ha uan lunghezza prestabilita, i suoi elementi formano una specie di "trenino" ovvero ognuno ha il collegamento alll'elemento successivo e quindi il puntatore all'elemento successivo.
se l'elemento successivo non esiste (fine della lista) il collegamento conterrà il valore NULL ovvero non punterà a nulla.
questo tipo di lista è utilizzato per gestire le code dinamiche ed è possibile implementare diversi algoritmi, sia sequenziali che ricorsivi.
nelle strutture a Lista è importante mantenere sempre il puntatore(testa) al primo elemento della lista (nell'esempio ^start) se si perde quel riferimento, la lista adrà persa.
supponiamo di essere un elemento che si vuole inserire nella lista.
- se vogliamo inserirci alla fine basterà allocarci da qualsiasi parte sulla ram, quindi modificare il puntatore next dell'ultimo elemento della lista in modo tale che punti a noi.
- se vogliamo inserirci all'inizio invece dobbiamo FARCI UNA COPIA del puntatore di testa se no perdiamo il riferimento alla lista, quindi modificare la testa in modo tale che punti a noi, e noi punteremo all'elemento precedentemente puntato dalla testa.
la lista è monolanciata, quindi è possibile scorrerla in un solo senso, supponiamo ad esempio di fermarci al secondo elemento, e di volerci inserire tra il rpimo e il secondo, non possiamo modificare il puntatore del primo elemento, almeno che non scorriamo di nuovo tutta la lista fino ad arrivare al primo elemento.
per ottimizzare il tutto basterà inserirci dopo il secondo elemento (quindi tra il secondo ed il terzo, che è fattibile senza dover ripercorrere la lista) e quindi invertire il nostro contenuto informativo con quello del secondo elemento.
[modifica] Liste circolari
implementate negli scheduler, le liste circolari non terminano con NULL ma con il puntatore al primo elemento, in qeusto modo è possibile percorrerle costantemente. supponaimoa d esmepio che ogni elemento sia un'operazione da compiere
il processo E scorrererà in sequenza la lista, eseguendo l'operaizone che trova il processo M modificherà invece i collegamenti, ed eventualmente inserirà nuove oeprazioni per modificare il percorso del processo E.
[modifica] Alberi e Grafi
le strutture dati consentono di modellizzare la realtà, a seconda della complessità di un fenomeno fisico, esso può essere rappresentato cons trutture lineari come gli array oppure con strutture dinamiche o ad oggetti.
La Vita non può essere rappresentata con strutture dati lineari come gli array, altrimenti potrebbe essere zippata.. la Vita è sinonimo di Infinito, spazia in ogni dimensione e quindi non può essere modellizzata con una strutture dati e tantomento compressa, poichè ognia spetto,a nche il più piccolo è una parte di Infinito.
Nell'esempio precedente possiamo immaginare il processo E come un treno che si muove ed il processo M come il gestore del percorso che lo dirige.
le strutture ad Albero ed i grafi consentono di rappresentare la realtà ottimizzando ulteriormente laq modellizzaizone.
un grafo è un insieme di nodi da cui dipartono dei grafi è quindi una struttura ricorsiva e può essere immaginata come un albero fatto di nodi e di rami da ogni ramo si collega ad un nodo da cui dipartono altri rami, e così via.
Pensiamo ad esempio ad Internet, Internet è un grafo, gestito da degli algoritmi che lavorano suui grafi, come il famoso algoritmo di Dijkstra.
gli alberi sono un particolare tipo dig rafo in cui due rami non possono puntare allo stesso nodo, e tra questi si distinguono gli alberi bilanciati nei quali da un nodo dipartono solo due rami ed il numero di nodi e sottonodi presenti in una diramazione devono corrispondere a quelli presenti nell'altra diramazione.
Questa struttura dati è particolarmente indicata per la ricerca dicotomica.
[modifica] Puntatori in C
Il C consente di gestire, oltre al contenuto delle variabili stesse, anche i loro indirizzi (ovvero le loro locazioni in memoria) attraverso il meccanismo dei puntatori.
Fino ad oggi abbiamo gestito le variabili all'interno dei blocchi di codice in cui tali variabili erano visibili, quindi non c'è stata la reale necessità di utilizzare l'indirizzo della locazione di memoria in cui i valori di tali variabili erano stati memorizzati. L'uso però a volte diventa indispensabile all'interno delle funzioni (anche nella scanf, come avevo anticipato, si usava implicitamente un puntatore per stabilire l'area fisica di memoria in cui salvare la variabile letta da input).
Un puntatore ha una sintassi simile:
int a=3; // Variabile int *x; // ''Puntatore'' ad una variabile di tipo int x=&a; // Il puntatore ''x'' contiene l'indirizzo della variabile ''a'' *x=4; // In questo modo modifico il contenuto del valore puntato da x, // quindi modifico indirettamente il valore di a
&a identifica l'indirizzo in memoria al quale si trova la variabile a, indirizzo che viene salvato nel puntatore x. Quest'uso dei puntatori dovrebbe farci tornare alla mente la sintassi della scanf:
int a; printf ("Inserisci un valore intero: "); scanf ("%d",&a);
Ora possiamo capire appieno la sintassi della scanf. È una funzione che non fa altro che leggere, in questo caso, un valore intero da tastiera, e salvarlo nell'indirizzo fisico di memoria in cui si trova la variabile a (&a).
Ovviamente, se voglio salvare un valore letto da tastiera in una variabile a cui è già associato un puntatore, non ho bisogno di ricorrere alla scrittura di sopra:
#include <stdio.h> main() { int a; int *x=&a; printf ("Inserisci un valore intero: "); // Salvo il valore immesso direttamente nell'allocazione // di memoria puntata da ''x'', ovvero nella variabile ''a'' scanf ("%d",x); printf ("Valore salvato all'indirizzo: 0x%x: %d\n",x,a); }
ritornerà come output qualcosa del tipo
Valore salvato all'indirizzo: 0xbfc16a24: 4
dove 0xbfc16a24 è, in questo caso, l'indirizzo fisico di memoria (in formato esadecimale) in cui si trova la variabile intera a (e quindi il valore 4, in questo caso). Ricordiamo che sulle macchine a 32 bit (quindi tutte le macchine Intel dal 486 in su, escluse quelle a 64 bit come Itanium e simili) un indirizzo di memoria è sempre grande 32 bit (come in questo caso), quindi in memoria un puntatore occuperà sempre, indipendentemente dalla variabile a cui punta, 32 bit = 4 byte.
[modifica] Passaggio di puntatori alle funzioni
Vediamo ora un'applicazione pratica dell'uso dei puntatori. Abbiamo una classica applicazione che effettua lo scambio di due numeri interi (ovvero, se ho due variabili, a=3 e b=4, voglio ottenere a=4 e b=3). Il modo più immediato di risolvere questo problema è quello di appoggiarsi ad una variabile temporanea:
int a=4; int b=3; int tmp; ..... tmp=a; // tmp=4 a=b; // a=3 b=tmp // b=tmp=4
Vogliamo ora implementare questo codice in una funzione a parte che viene poi richiamata dal nostro programma. Con le nostre conoscenze attuali scriveremo un codice del genere:
#include <stdio.h> // Funzione per lo scambio void swap(int a, int b) { int tmp; tmp=a; a=b; b=tmp; } main() { int a=4; int b=3; printf ("a=%d, b=%d\n",a,b); swap(a,b); printf ("a=%d, b=%d\n",a,b); }
compilandolo avremo una sorpresa inaspettata: i valori sono rimasti immutati. Questo perché alla funzione swap non passiamo le variabili fisicamente, ma passiamo i loro valori. Quando invochiamo una funzione, l'atto della chiamata crea in memoria una nuova area dello stack associata alla funzione appena chiamata. In questo stack vengono copiati i valori degli argomenti passati. La funzione quindi non opera fisicamente sulle variabili passate, ma opera piuttosto su copie di esse. Quando la funzione termina l'area dello stack corrispondente viene distrutta, e con essa anche le copie delle variabili al suo interno, quindi non è possibile tener traccia delle modifiche.
La soluzione è proprio quella di ricorrere ai puntatori, ovvero non passare alla funzione copie delle variabili, ma gli indirizzi fisici in cui esse si trovano, in modo che la funzione agirà direttamente su quegli indirizzi:
#include <stdio.h> // Funzione per lo scambio void swap(int *a, int *b) { int tmp; tmp=*a; // tmp contiene il contenuto della variabile intera puntata da a *a=*b; // a contiene il contenuto della variabile intera puntata da b *b=tmp; // b contiene il contenuto della variabile intera puntata da tmp } main() { int a=4; int b=3; printf ("a=%d, b=%d\n",a,b); // Non passo le variabili alla funzione ma i loro indirizzi in memoria swap(&a,&b); printf ("a=%d, b=%d\n",a,b); }
e ora il nostro codice funziona a dovere.
[modifica] Puntatori e array
Nel paragrafo precedente abbiamo visto gli array come oggetti a sé stanti, diversi da qualsiasi altro tipo di variabile e di dato che abbiamo incontrato. Ai fini del calcolatore però un array viene trattato esattamente alla stregua di un puntatore, un puntatore all'area di memoria dov'è contenuto il primo elemento dell'array stesso. Esempio:
#include <stdio.h> main() { int v[] = {4,2,8,5,2}; // Queste due scritture sono equivalenti printf ("Primo elemento dell'array: %d\n",v[0]); printf ("Primo elemento dell'array: %d\n",*v); }
questo vuol dire che possiamo accedere a qualsiasi elemento dell'array specificando o il suo indice tra parentesi quadre o sommandolo al valore del puntatore al primo elemento:
#include <stdio.h> main() { int v[] = {4,2,8,5,2}; // Queste due scritture sono equivalenti printf ("Secondo elemento dell'array: %d\n",v[1]); printf ("Secondo elemento dell'array: %d\n",*(v+1)); }
questo perché quando viene instanziato un array non viene fatto altro che creare un puntatore ad una certa area della memoria centrale, per poi riservare tanto spazio in memoria quanto specificato dalla dimensione dell'array (nell'esempio di sopra lo spazio di 5 variabili int, una variabile int in genere è grande 4 byte su una macchina a 32 bit quindi vengono riservati 5*4=20 byte a partire dall'indirizzo del primo elemento).
[modifica] Passaggio di array a funzioni
Tale caratteristica si rivela conveniente per molti aspetti. L'aspetto principale consiste nel poter passare un array ad una funzione come se fosse un puntatore. Esempio:
#include <stdio.h> int print_array (int *v, int dim) { int i; for (i=0; i<dim; i++) printf ("Elemento [%d]: %d\n",i,v[i]); } main() { int v[] = { 3,5,2,7,4,2,7 }; print_array(v,7); }
[modifica] Allocazione dinamica della memoria
L'altro enorme vantaggio di quest'ottica da parte del C (ovvero il considerare gli array come semplici puntatori) risiede nel poter allocare dinamicamente dello spazio in memoria. Non sempre sappiamo a priori quanto spazio può servire in memoria per un array usato nel nostro programma. Ad esempio, nel caso in cui si dà la possibilità all'utente di stabilire il numero di elementi da inserire o quando vogliamo salvare dei dati in memoria senza sapere ancora la quantità di dati da salvare (in questo caso dovremmo prima contare il numero di dati da salvare, quindi allocare tanta memoria da poterli mantenere). In questi casi ci viene in aiuto una delle caratteristiche più potenti del C, l'allocazione dinamica della memoria, allocazione che è possibile attraverso la funzione malloc, definita in stdlib.h. La malloc ha una sintassi simile:
al posto di size specificheremo quanta memoria vogliamo allocare per la nostra variabile o il nostro array. Come è possibile vedere il valore di ritorno di questa funzione è void, ovvero ritorna l'indirizzo della zona di memoria allocata in formato 'grezzo'. Per questo motivo è necessario specializzare la funzione attraverso un operatore di cast. Esempio chiarificatore:
#include <stdio.h> #include <stdlib.h> main() { int *v; int i,n; printf ("Quanti elementi vuoi inserire nell'array? "); scanf ("%d",&n); v = (int*) malloc(n*sizeof(int)); for (i=0; i<n; i++) { printf ("Elemento n.%d: ",i+1); scanf ("%d",&v[i]); } for (i=0; i<n; i++) printf ("Elemento n.%d: %d\n",i+1,v[i]); }
La scrittura sizeof(int) ritorna la dimensione di una variabile int sulla macchina in uso, quindi n*sizeof(int) è il numero di byte effettivi da allocare in memoria (ovvero nella malloc diciamo di allocare in memoria n blocchi di dimensione sizeof(int) l'uno che ospiteranno n variabili intere, e salviamo l'indirizzo a cui comincia questa zona di memoria nel puntatore v).
Ciò è possibile anche con array di dimensione superiore a 1 (es. per le matrici):
#include <stdio.h> #include <stdlib.h> main() { int **m; int i,j; int m,n; printf ("Numero di righe della matrice: "); scanf ("%d",&m); printf ("Numero di colonne della matrice: "); scanf ("%d",&n); m = (int**) malloc(m*n*sizeof(int)); // Inizializzo anche tutti i sotto-vettori, ovvero le righe della matrice for (i=0; i<m; i++) m[i] = (int*) malloc(n*sizeof(int)); for (i=0; i<m; i++) for (j=0; j<n; j++) { printf ("Elemento [%d][%d]: ",i+1,j+1); scanf ("%d",&v[i][j]); } for (i=0; i<m; i++) for (j=0; j<n; j++) printf ("Elemento [%d][%d]: %d\n",i+1,j+1,v[i]); }
[modifica] Puntatori a funzioni
Le funzioni a basso livello non sono altro che sequenze di istruzioni binarie piazzate nella memoria centrale, al pari di una qualsiasi variabile. È quindi possibile anche costruire puntatori che puntino a funzioni, in quanto normali aree di memoria. La sintassi è la seguente:
Per richiamare la funzione puntata, basta poi un
Esempio:
#include <stdio.h> void foo() { printf ("Ciao\n"); } main() { void (*ptr)(void) = foo; printf ("foo si trova all'indirizzo 0x%.8x\n",ptr); (*ptr)(); }
o ancora
#include <stdio.h> int foo(int a, int b) { return a+b; } main() { int a=2,b=3; int (*ptr)(int, int) = foo; printf ("foo si trova all'indirizzo 0x%.8x\n",ptr); printf ("%d+%d=%d\n",a,b,(*ptr)(a,b)); }
[modifica] Funzioni di callback
La conseguenza immediata dei puntatori a funzione sono le funzioni di callback. Ovvero, nulla mi impedisce, a questo punto, di passare come parametro di una funzione un puntatore a funzione, e la funzione richiamata può richiamare la funzione passata come argomento. Esempio:
#include <stdio.h> void print () { printf ("Ciao\n"); } int foo(void (*f)(void)) { f(); } main() { foo(print); }
