Si risolva il seguente esercizio: data una lista di interi, inserire dopo ogni elemento negativo, la media di tutti i numeri che lo precedono (includere il numero stesso nella media).
L'esercizio consiste ancora in un inserimento di elementi nella lista. Al contrario del caso precedente, l'elemento va inserito dopo quello negativo, per cui per esempio non è mai necessario inserire elementi all'inizio della lista.
Un'altra conseguenza della definizione del problema è che ci basta avere un puntatore che si sposta su tutte le strutture della lista: se la struttura contiene un elemento negativo, è il campo next della struttura stessa che va modificato (al contrario, nel caso di inserimento in lista ordinata era il campo next della struttura precedente quello che andava modificato).
Facciamo quindi una scansione della lista, ossia un ciclo in cui un puntatore s contiene ogni volta l'indirizzo di una diversa struttura della lista. Usiamo inoltre due variabili somma e numero in cui mettiamo rispettivamente la somma e il numero degli elementi incontrati fino a questo momento nella scansione. Ogni volta che la variabile di scansione s punta a una struttura il cui campo val è negativo (ossia s->val), allochiamo una nuova struttura, e il suo indirizzo lo mettiamo in s->next.
La situazione che si viene quindi a creare quando s punta a una struttura con un campo val negativo è la seguente:
Dopo l'inserimento, lo stato della memoria deve essere invece quello che segue:
È quindi chiaro che dobbiamo allocare una nuova struttura, il cui campo val è la media e il cui campo next punta alla locazione in cui puntava prima s->next. Inoltre, s->next deve venire modificato in modo da puntare alla nuova struttura. A questo punto possiamo avanzare il puntatore. Si noti che la media può anche essere negativa. In questo caso, non va scritta nuovamente la media di seguito: infatti, la specifica del problema dice che la media va messa solo dopo agli elementi negativi che si trovavano originariamente nella lista. Per questo motivo, dopo aver inserito il nuovo elemento, portiamo avanti il puntatore: si può verificare facilmente che, in questo modo, quando si inserisce un elemento, alla fine della iterazione del ciclo, il puntatore s è stato portato avanti di due posizioni, ossia punta al successivo elemento della lista originaria.
Il programma medie.c contiene la seguente funzione di aggiunta delle medie.
void InserisciMedie(TipoLista l) {
TipoLista s, t;
int somma, numero;
/* se la lista e' vuota, va lasciata cosi' */
if(l==NULL)
return;
/* inizializza somma parziale e numero elementi
incontrati finora */
somma=0;
numero=0;
/* scansione della lista */
s=l;
while(s!=NULL) {
/* aggiorna somma e numero di elementi trovati */
somma=somma+s->val;
numero++;
/* se l'elemento e' negativo, aggiunge la media
fra questo e il successivo */
if(s->val<0) {
t=s->next;
s->next=malloc(sizeof(struct NodoLista));
s=s->next;
s->val=somma/numero;
s->next=t;
}
/* passa al successivo elemento */
s=s->next;
}
}
Si noti che la funzione va bene anche nel caso di lista vuota (non occorre fare niente), di lista con un solo elemento, e di lista in cui l'elemento finale è negativo. Questo può facilmente venire compreso graficando la evoluzione della memoria.
Per concludere, notiamo che la lista l, anche se viene modificata, è stata passata per valore. Questo si può spiegare con la regola del passaggio di puntatori a funzione:
quando si passa un puntatore per valore, viene creata una copia locale del solo puntatore: gli elementi puntati non vengono copiati.
Dal momento che il puntatore iniziale della lista non viene mai modificato (punta sempre al primo elemento della lista, dal momento che nessun elemento viene mai inserito in testa), passarlo per valore o riferimento è in effetti equivalente. Quello che può succedere è che la prima struttura puntata, o una delle successive, vengono modificate. Dalla regola segue che la funzione lavora con una copia del puntatore, ma gli oggetti puntati sono quelli originali, cieè non sono copie. Quindi, la funzione modifica le strutture originali (non delle copie), ossia le stesse del programma principale.