In questa pagina vediamo cosa succede se una funzione modifica una lista. Consideriamo il seguente programma di esempio sommauno.c che somma 1 a tutti gli elementi di una lista di interi.
La funzione di somma a tutti gli elementi della lista non presenta nessuna difficoltà: si tratta infatti di effettuare una scansione della lista, aggiungendo uno a tutti gli elementi che si incontrano. La cosa interessante del programma sommauno.c è che la lista viene passata per valore invece che per riferimento.
void SommaUno(TipoLista l) {
TipoLista s;
s=l;
while(s!=NULL) {
s->val=s->val+1;
s=s->next;
}
}
A prima vista può sembrare che la funzione non vada bene, se è scritta in questo modo: infatti, il passaggio per valore dovrebbe copiare la lista, e quindi le modifiche fatte dalla funzione dovrebbero avere effetto solo sulla copia locale. invece, il programma funziona perfettamente: il programma principale, alla fine della esecuzione della funzione, vede la lista modificata. Stampando la lista prima e dopo la chiamata di funzione, si vede che effettivamente la lista è stata modificata, e che le modifiche sono visibili dal programma principale: se per esempio si stampa la lista prima e dopo la chiamata di funzione, si vede come la lista dopo la chiamata di funzione è diversa da quella di prima.
Per capire questo comportamento, occorre dare una interpretazione letterale al concetto di ``passaggio di parametro''. La regola del C sulle variabili passate a una funzione è:
quando si passa un valore a una funzione, viene creata una nuova variabile, locale alla funzione, in cui viene copiato questo valore.
Il meccanismo del passaggio dei parametri va interpretato letteralmente. Una variabile di tipo TipoLista è un puntatore, ossia contiene un numero (che rappresenta un indirizzo di memoria). Quando viene chiamata la funzione usando SommaUno(l) quello che succede è che si crea una variabile locale alla funzione, in cui viene copiato il valore passato alla funzione, ossia il numero che sta scritto nella variabile l. Sui puntatori, la regola di sopra si può specializzare come segue (si noti che non è una nuova regola, ma solo un caso particolare di quella di sopra):
quando si passa un puntatore per valore, viene creata una copia locale del solo puntatore: gli oggetti da esso puntati non sono copiati, per cui i due puntatori (quello del programma chiamante e quello locale) contengono lo stesso indirizzo, ossia puntano allo stesso identico oggetto.
Vediamo quindi in che modo evolve la memoria. Supponiamo che la lista l sia costituita dalla sequenza di valori (2 -9 1). Una possibile disposizione in memoria della strutture si trova qui sotto. Usiamo sia la rappresentazione con freccie che quella con numeri.
|
|
|
La funzione SommaUno ha un unico parametro, di tipo TipoLista, ossia un puntatore a struttura. Quando la funzione viene chiamata, si crea una variabile locale di questo tipo, e in essa viene messo il valore che è stato passato. Nell'esempio di sopra, il valore passato è E0032, e questo è quindi il valore che viene messo nella variabile locale della funzione.
Da notare che questo è semplicemente quello che si ottiene applicando due regole note del linguaggio C, ossia:
Proviamo ora a vedere cosa succede traducendo il diagramma di sopra nella notazione con freccie. Tutto quello che serve è considerare che, se un puntatore contiene un numero, allora si mette una freccia con la punta verso l'indirizzo identificato da quel numero.
Lo stesso risultato si ottiene considerando che la funzione contiene una variabile locale l, e che in questa viene messo il valore del parametro passato. Dal momento che sia la variabile locale che il parametro passato sono puntatori, questo equivale alla copia fra puntatori, che nella notazione grafica equivale a mettere nella variabile in cui si copia una freccia con la punta nella stessa locazione della variabile da cui si copia.
Possiamo anche usare l'ultima notazione grafica, quella introdotta appositamente per le liste. La situazione iniziale è la seguente:
Quando si chiama una funzione, si creano tutte le sue variabili locali. In particolare, si crea anche una variabile locale per ognuno dei parametri passati. Nel nostro caso, viene creata una variabile locale l di tipo TipoLista.
Chiamare una funzione equivale a creare una variabile locale l, in cui viene copiato il valore del parametro. Questo equivale a fare una cosa del tipo:
l (locale della funzione) = l (del programma principale)
Come si è già detto, assegnare un puntatore equivale a copiare il numero. Questo equivale a dire che la l della funzione alla fine contiene il numero che stava nella l del programma principale. Dal momento che questo numero è l'indirizzo della prima struttura, la variabile locale l contiene l'indirizzo della prima struttura, che si rappresenta mettendo una freccia da essa alla prima struttura della lista.
Graficamente, assegnare i puntatori equivale a mettere in quello a sinistra di = una freccia con la punta nella stessa posizione del puntatore a destra del simbolo =. Questo è quindi lo stato della memoria quando la funzione inizia.
Il resto della funzione non presenta difficoltà. Consideriamo per esempio il primo passo: si assegna ad s il valore di l, e si esegue il ciclo. Al primo passo si incrementa di uno il valore di s->val, ossia si aumenta di uno il campo val della prima struttura della lista.
Si noti che l'incemento viene fatto sulla struttura puntata da s, che è la stessa puntata da l (sia quella dal main che quella della funzione). Lo stesso incremento viene poi fatto per tutte le altre strutture. Quando la funzione termina, lo stato della memoria è quindi il seguente.
La funzione, a questo punto, termina. Questo equivale a cancellare le variabili locali, ossia la variabile s e la variabile l locale della funzione. Quello che rimane sono la variabile l del programma principale, e le strutture allocate dinamicamente.
Come è fatta la lista prima/dopo la chiamata di funzione? Prima della chiamata la lista è (2 -9 1), come abbiamo assunto all'inizio. Per vedere come è fatta la lista dopo la chiamata, occorre partire da l e vedere le strutture che si incontrano seguendo i puntatori. Dal diagramma di sopra appare abbastanza evidente che il primo elemento è 3, seguito da -8 seguito da 2. La lista dopo la chiamata è quindi (3 -8 2).
Riassumendo, la lista è stata cambiata dalla funzione, anche se la variabile l è stata passata per valore. Questo avviene per i seguenti motivi.
In altre parole, dato che la lista è rappresentata dalle strutture puntate da l, e passare un puntatore equivale a creare una nuova variabile che punta allo stesso oggetto, le modifiche alle strutture puntate sono modifiche alle strutture puntate nel programma principale (questo avviene perchè sono le stesse strutture).
La regola per decidere se passare una lista per valore oppure per indirizzo non dipende dalla possibilità per la funzione di fare modifiche sulla lista. Infatti, la lista può venire modificata anche se viene passata per valore. La regola è invece la seguente:
una lista va passata per indirizzo se il puntatore iniziale viene modificato, e questo modifica deve essere visibile dal programma principale.
Notiamo ancora una volta che questo non è una nuova regola, ma semplicemente quello che si ottiene applicando letteralmente le regole sul passaggio dei parametri in C. Infatti, passare un puntatore equivale a copiare il suo valore. Se il valore del puntatore (ossia l'indirizzo a cui punta) deve venire alterato dalla funzione, allora occorre fare un passaggio per indirizzo. Se invece il puntatore continua ad avere la punta della freccia nello stesso punto, allora il valore del puntatore non viene cambiato, per cui si può fare un passaggio per valore anche se la lista va cambiata.
Una altro caso interessante è quello della aggiunta di un elemento in testa alla lista. In questo caso, il puntatore che rappresenta la lista inizialmente punta alla prima struttura della vecchia lista. Quando si inserisce la nuova struttura, il puntatore contiene l'indirizzo della nuova struttura, che è diverso dall'indirizzo della vecchia.
Nel caso il concetto illustrato sopra non fosse stato chiarito, si suggerisce di leggere il capitolo su memoria e puntatori. Vediamo una serie di esempi. Partiamo da una situazione ovvia: cosa succede se una funzione riceve un puntatore a intero?
void Esempio(int *a) {
*a=12;
}
int main() {
int a=3;
Esempio(&a);
...
Questo cambia il valore di a? Chiaramente sí. Si tratta infatti del passaggio della variabile a per indirizzo. Ora proviamo a passare, invece che un intero, una struttura.
struct abcd{
int cmp;
};
void Esempio(struct abcd *a) {
(*a).cmp=12;
}
int main() {
struct abcd a;
a.cmp=12;
Esempio(a);
...
Non cambia niente: si tratta del passaggio di una struttura per indirizzo, per cui le modifiche fatte nella funzione sono modifiche che vengono fatte direttamente sulla struttura dichiarata nel programma principale.
Una variabile di tipo TipoLista è un puntatore a una struttura. In particolare, la struttura contiene a sua volta un campo puntatore, ma questo, dal punto di vista del linguaggio, è irrilevante. La cosa fondamentale è che passare una lista a una funzione equivale a passare l'indirizzo della prima struttura. Quindi, la funzione opera non su una copia della struttura, ma sulla struttura stessa, nello stesso modo in cui passando l'indirizzo di una variabile intera, la funzione modifica la variabile stessa e non una sua copia.
Volendo riassumere: le liste sono puntatori a struttura, per cui seguono semplicemente le regole dei puntatori, sia per quello che riguarda l'assegnazione che il passaggio dei parametri a funzione. In particolare, il fatto che una varabile di tipo TipoLista rappresenta una sequenza dipende semplicemente dalla interpretazione che diamo alle strutture puntate. In altre parole, per il linguaggio una variabile di tipo lista non è altro che un puntatore: siamo noi che diciamo che rappresenta la lista ottenuta seguendo i vari puntatori.
Per concludere: si faccia attenzione al fatto che il passaggio per valore può dare luogo a modifiche nella lista passata può creare degli errori, nel caso in cui si facciano modifiche alla lista puntata e ci si aspetta che non abbiano effetti sulla lista originaria.