elem* trova (elem* lista, int n) { // se la lista e` vuota viene tornato un puntatore nullo if (lista == 0) return 0; elem* p = lista; // procede fino a che: // - finisce la lista // - viene trovata una occorrenza while (p != 0 && p->info != n) p = p->next; return p; }
Si faccia bene attenzione: per la prima volta la funzione non è void, bensì torna un puntatore alla struttura elem
; utilizzando tale puntatore possiamo modificare a piacimento il dato il cui indirizzo viene tornato. Vediamo un esempio, nel quale creeremo una lista con numeri da 1 a 10, la stamperemo, cercheremo tramite trova
l'elemento 7
e lo metteremo a -7
:
// ex7_7_6 void main() { elem* lista; inizializza (lista); for (int i = 10; i > 0; i--) insTesta (lista, i); stampa (lista, 5); elem* p = trova (lista, 7); p->info = -7; stampa (lista, 5); }
output:
1 | 2 | 3 | 4 | 5 | |
6 | 7 | 8 | 9 | 10 | |
1 | 2 | 3 | 4 | 5 | |
6 | -7 | 8 | 9 | 10 |
In questo caso, avendo costruito la lista ad hoc, eravamo sicuri che trova
avrebbe trovato un elemento; tuttavia in generale non possiamo dare per scontato il successo di tale funzione, la quale in caso di fallimento torna un puntatore nullo. Vediamo il seguente esempio in cui, sfruttando la trova
, stampiamo tutte le occorrenze di un certo elemento:
// ex7_7_7 void main() { elem* lista; inizializza (lista); generaLista (lista, 10, 20); stampa (lista, 5); elem* p; elem* listaParziale = lista; int i = 0; // contatore delle occorrenze while ((p = trova(listaParziale, 7)) != 0) { i++; listaParziale = p->next; } cout << "occorrenze di 7 trovate: " << i; }
esempio di output:
2 | 8 | 10 | 7 | 3 | |
4 | 3 | 4 | 4 | 10 | |
7 | 8 | 5 | 9 | 1 | |
6 | 7 | 1 | 1 | 1 |
In questo esempio sfruttiamo il fatto che un puntatore ad un elemento di una lista costituisce una sottolista di essa; possiamo allora effettuare la ricerca in sottoliste sempre minori, le quali partono dall'elemento successivo all'occorrenza trovata fino alla fine della lista.
Oltre alla ricerca per valore di un elemento, possiamo cercare un elemento in base al suo indice, ovvero al numero di elementi che lo separano dalla testa; tale modalità di accesso degli elementi, simile a quella degli array, è comunque poco usata: se abbiamo bisogno di accedere in maniera diretta dei dati, conviene sempre creare un array piuttosto che una lista. Comunque una funzione che ci restituisce un puntatore all'i
-esimo elemento di una lista è il seguente:
elem* trovaIndice (elem* lista, int i) { if (lista == 0) return 0; elem* p = lista; for (int j = 0; (j < i) && (p != 0); j++) p = p->next; return p; }
L'algoritmo è molto semplice: si prende un puntatore di scorrimento e si procede nella lista fino a quando non si verifica una delle due seguenti condizioni: tocchiamo l'i
-esimo argomento, arriviamo alla fine della lista. Anche questa funzione, come la precedente, torna un puntatore nullo nel caso di elemento non trovato, il che avviene solo se l'indice supera il numero di elementi della lista. Vediamo un esempio:
// ex7_7_8 void main() { elem* lista = 0; generaLista (lista, 20, 10); stampa (lista, 5); elem* p = trovaIndice (lista, 0); p->info = 0; p = trovaIndice (lista, 6); p->info = 0; cout << "\n"; stampa (lista,5 ); }
esempio di output:
9 | 13 | 6 | 8 | 19 | |
15 | 7 | 6 | 11 | 20 | |
0 | 13 | 6 | 8 | 19 | |
15 | 0 | 6 | 11 | 20 |
a
, b
) e cambi tutti gli elementi con valore a
in b
;