stato della memoria prima della eliminazione
Questo esercizio consiste nella scrittura di una funzione che elimina, da una lista di interi, tutti i numeri negativi. Si noti che la eliminazione deve avvenire anche se ci sono elementi negativi all'inizio e alla fine della lista. Di seguito si riportano alcuni possibili file che contengono liste di esempio. Il programma di eliminazione dovrebbe leggere questi file in una lista, stampare la lista, eliminare i negativi e poi stampare di nuovo. Il confronto fra la stampa prima e dopo permette di capire se il programma funziona in modo corretto.
Come al solito, confrontiamo lo stato della memoria prima e dopo l'eliminazione. Usiamo come lista di esempio (2 -9 1 -3 -9). Nel caso in cui si devono eliminare elementi in mezzo a una lista, conviene usare un esempio in cui si siano almeno due elementi consecutivi da eliminare, perchè questo è un caso su cui è facile sbagliare.
stato della memoria prima della eliminazione
stato della memoria dopo la eliminazione
Dal confronto risulta abbastanza evidente che, se un elemento è negativo, allora serve conoscere l'indirizzo della struttura che lo contiene, per poterla deallocare. Questo indirizzo sta scritto nella struttura precedente. Dato che la struttura precedente va modificata (per ``saltare'' la struttura che ha l'elemento negativo) ci serve in effetti l'indirizzo della struttura che precede quella in cui si trova il valore negativo. Facciamo quindi una scansione della lista usando una variabile puntatore s. Non possiamo fare l'eliminazione quando s->val è negativo, dal momento che, in questo modo, s punta alla struttura che contiene il negativo, e non alla struttura precedente. Facciamo invece il controllo su s->next->val. Se questo numero è negativo, l'indirizzo della struttura che lo contiene è s->next.
L'eliminazione avviene mettendo in s->next l'indirizzo della struttura che segue quella che ha un numero negativo dentro. Questa struttura è ovviamente s->next->next. L'istruzione di eliminazione dalla lista è quindi s->next=s->next->next. Dal momento che la struttura va poi deallocata, occorre salvare il suo indirizzo in una variabile r, e poi fare la free una volta che è stata eliminata dalla sequenza di strutture che rappresentano la lista.
Questa è la struttura generale dell'algoritmo: si fa una scansione della lista, eliminando la struttura per la quale s->next->val è negativo. Occorre ora considerare alcuni casi particolari. Quando si fanno operazioni di cancellazione di elementi in mezzo a una lista occorre tenere presente cosa succede quando:
È abbastanza chiaro che la procedura di sopra non funziona se la lista è vuota: infatti, il primo accesso a s->next->val, quando s è NULL, causa un errore. Quindi, il caso di lista vuota va tenuto in considerazione separatamente. In particolare, se la lista è vuota non va ovviamente modificata (intuitivamente, la lista vuota a cui tolgo tutti gli elementi negativi, rimane vuota).
Il caso in cui la lista inizia con un elemento negativo (sia esso l'unico o no) è un altro caso in cui l'algoritmo di sopra non funziona. Infatti, al primo passo si controlla s->next->val, per cui il primo intero s->val non viene controllato affatto. Per eliminare il primo elemento della lista, basta controllare se l->val è negativo. Se lo è, si tratta di eliminare il primo elemento della lista.
Il caso in cui la lista termina con un elemento negativo, d'altra parte, non crea difficoltà: l'algoritmo funziona anche in questo caso.
Passiamo ora al caso in cui si sono più elementi negativi consecutivi. Supponiamo quindi di aver eliminato il primo elemento. Ora s punta alla struttura precedente a quello eliminato. Questa struttura ha un puntatore al successivo, ossia quello che prima seguiva l'elemento ora eliminato. Per poter eliminare anche questo elemento, ci serve che s punti alla struttura precedente. Ma s punta già alla struttura precedente! Quello che occorre quindi fare è controllare di nuovo s->next->val, ed eliminare la struttura successiva se questo valore è negativo. In altre parole, nella lista di esempio, dopo aver eliminato il quarto elemento (-4), ci troviamo nella seguente situazione:
Le linee curve indicano dove abbiamo eliminato delle strutture. Come si vede, subito dopo l'eliminazione della struttura che contiene -3, la struttura successiva a quella puntata da s contiene ancora un elemento da eliminare.
Per chiarire questo fatto, consideriamo l'assunzione che abbiamo fatto nel definire il ciclo: dato che facciamo il controllo su s->next->val, e tutte le strutture vanno controllate, è necessario che s->next assuma l'indirizzo di tutte le strutture che compongono la lista.
Una volta fatta una eliminazione, la struttura che va analizzata è quella che segue quella eliminata. Ma l'indirizzo di questa struttura si trova ora in s->next. Quindi, non è necessario, in questo caso, fare s=s->next, dato che s contiene già l'indirizzo della struttura precedente a quella da analizzare.
Il codice che risulta da queste considerazioni è il seguente:
/* eliminazione elementi negativi */
if(l!=NULL) {
/* eliminazione negativi dal secondo in poi */
if(l->next!=NULL) {
s=l;
while(s->next!=NULL) {
if(s->next->val < 0 ) {
r=s->next;
s->next=s->next->next;
free(r);
}
else
s=s->next;
}
}
/* elimina primo elemento se negativo */
if(l->val<0) {
r=l;
l=l->next;
free(r);
}
}
/* fine eliminazione elementi negativi */
Nel caso in cui la lista è vuota, non si fa nulla. Nel caso in cui la lista ha almeno un elemento, facciamo la scansione. Ogni volta, s punta a una struttura della lista, e analizziamo (controlliamo se il campo val è negativo) la struttura successiva. Dal momento che occorre analizzare tutte le strutture, è necessario portare ogni volta avanti il puntatore; nel caso in cui una struttura viene eliminata, s->next già contiene l'indirizzo di una struttura che ancora va analizzata: in questo caso, il puntatore non va portato avanti.
Il ciclo while elimina dalla lista tutti gli elementi negativi che contiene, ma solo se non si trovano in prima posizione. In altre parole, se il primo elemento della lista è negativo, non viene eliminato. Mettiamo quindi un controllo sul primo elemento della lista.
Concludiamo notando come il controllo sul primo elemento va messo dopo il ciclo. Se infatti lo mettessimo prima, il programma non funzionerebbe sempre: se la lista iniziasse con due elementi negativi, eliminare solo il primo produrrebbe una lista che ha ancora un primo elemento negativo, il quale non verrebbe eliminato dal successivo ciclo while.
In effetti è anche possibile eliminare prima tutti gli eventuali elementi negativi con cui la lista inizia, e poi tutti gli altri. Dato che non si sa con quanti elementi negativi la lista potrebbe iniziare, occorrerebbe un ciclo in cui, a ogni iterazione, si elimina il primo elemento della lista se negativo, e si esce altrimenti.
Riportiamo qui sotto una parte del programma delmezzo.c in cui l'eliminazione degli elementi negativi è realizzata con una funzione. Dal momento che la lista potrebbe iniziare con un elemento negativo (che va quindi cancellato), il puntatore iniziale della lista potrebbe venire alterato dalla funzione, e questa modifica deve essere visibile al programma principale. La lista va quindi passata per indirizzo.
void EliminaNegativi(TipoLista *pl) {
TipoLista s, r;
/* lista vuota: niente da eliminare */
if(*pl==NULL)
return;
/* eliminazione negativi dal secondo in poi */
if((*pl)->next!=NULL) {
s=*pl;
while(s->next!=NULL) {
if(s->next->val < 0 ) {
r=s->next;
s->next=s->next->next;
free(r);
}
else
s=s->next;
}
}
/* elimina primo elemento se negativo */
if((*pl)->val<0) {
r=*pl;
*pl=(*pl)->next;
free(r);
}
}