info
, dopo il primo elemento da sinistra avente valore val
:
bool inserisci (elem*& lista, int info, int val) { if (lista == 0) return false; elem* p = lista; // il ciclo prosegue fino a quando: // - la lista termina // - viene trovata una occorrenza while (p != 0 && p->info != val) p = p->next; if (p == 0) // la lista termina return false; // altrimenti e` stata trovato un elemento `val' p->next = new elem (info, p->next); return true; }
La procedura è sempre la medesima: si isola il caso base (lista vuota), nel quale si torna false; in generale si effettua un ciclo, il quale termina se viene trovata una occorrenza (e si inserisce un nuovo elemento e si torna true) o se termina la lista (si torna false).
Leggermente più complessa la funzione per eliminare un elemento in posizione arbitraria, dato il suo valore; come nella funzione precedente, si torna un valore booleano che segnala l'avvenuta eliminazione:
bool elimina (elem*& lista, int n) { // caso base: lista vuota if (lista == 0) return false; // caso base: l'elemento cercato e` il primo if (lista->info == n) { elem* p = lista; lista = lista->next; delete p; } // caso base: lista con un solo elemento // il cui valore NON e` `n' if (lista->next == 0) return false; // due puntatori di scorrimento elem* p = lista; elem* q = lista->next; while (q != 0 && q->info != n) { p = p->next; q = q->next; } if (q == 0) return false; // esiste una occorrenza di `n' p->next = q->next; // si "scavalca" q delete q; // lo si cancella return true; }
In questa funzione i casi base che esaminiamo sono tre; il primo è quello di lista vuota, nel quale si torna semplicemente false. Il secondo caso base è quello di lista il cui primo elemento sia esattamente quello da eliminare, nel cui caso lo si elimina e si torna true. Il terzo e ultimo caso base è di lista con un solo elemento, ove possiamo supporre che tale elemento non sia da eliminare, altrimenti saremmo rientrati nel secondo caso base; basta dunque tornare false. Nel caso generale definiamo due puntatori ausiliari di scorrimento, i quali procedono affiancati, come nel caso dell'eliminazione dell'elemento di coda; trovata l'occorrenza dal puntatore q
, lo si ``scavalca'', cioè si fa in modo che p
punti all'elemento puntato da q
, e si cancella semplicemente q
; si torna infine true. Vediamo un esempio sulle ultime due funzioni presentate:
// ex7_7_9 void main() { elem* lista = 0; for (int i = 8; i > 0; i--) insTesta (lista, i); stampa (lista, 5); inserisci (lista, 0, 7); inserisci (lista, 0, 13); // non ha effetto cout << "\n\n"; stampa (lista, 5); if ( elimina(lista, 5) == true) cout << "\neliminazione di 5 riuscita\n"; if ( elimina(lista, 13) == false) cout << "eliminazione di 13 non riuscita\n"; stampa (lista, 5); }
output:
1 | 2 | 3 | 4 | 5 | |
6 | 7 | 8 |
1 | 2 | 3 | 4 | 5 | |
6 | 7 | 0 | 8 |
1 | 2 | 3 | 4 | 6 | |
7 | 0 | 8 |
Per chiudere la nostra rassegna sulle liste semplici, indichiamo una funzione che copia interamente una lista in un'altra, inizialmente vuota:
void copia (const elem* lista1, elem*& lista2) { const elem* p = lista1; inizializza (lista2); while (p != 0) { insCoda (lista2, p->info); p = p->next; } }
Funzione molto semplice, che sfrutta la nota insCoda
; unica nota è che se la lista2
non è vuota, il suo puntatore viene barbaramente messo a 0
, creando un bel mucchio di garbage; come si potrebbe risolvere il problema? Due possibili strade: effettuare la copia solo se lista2
è vuota; distruggere lista2
nel caso essa non sia vuota. Si provi a mettere in pratica entrambe queste possibilità. Vediamo immediatamente un esempio:
// ex7_7_10 void main() { elem *sorgente, *destinazione; inizializza (sorgente); generaLista (sorgente, 20, 10); stampa (sorgente, 5); copia (sorgente, destinazione); cout << "\n"; stampa (destinazione, 5); }
esempio di output:
5 | 11 | 3 | 5 | 2 | |
2 | 10 | 5 | 20 | 16 |
5 | 11 | 3 | 5 | 2 | |
2 | 10 | 5 | 20 | 16 |
i
-esima;
i
-esimo elemento di una lista