next up previous contents index
Next: Inserzione ed eliminazione in Up: Liste semplici in C++ Previous: Eliminazione in testa e   Indice   Indice analitico

Ricerca e modifica di un elemento

Una lista è costituita di elementi, i quali presumibilmente devono essere acceduti durante l'esecuzione del programma per la lettura o la modifica dei dati in essi contenuti; esistono essenzialmente due metodi per accedere un elemento in una lista semplice: per contenuto e per indice. Accedere per contenuto una cella significa cercare, scorrendo la lista, una cella il cui valore sia uguale ad uno dato. Ad esempio la seguente funzione torna un puntatore alla prima occorrenza (da sinistra) di un elemento avente un determinato valore, passato per argomento alla funzione:

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

occorrenze di 7 trovate: 3

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

ex-2
si scriva un programma che richieda all'utente l'immissione di una lista; si chieda poi all'utente di immettere un numero e si torni un messaggio appropriato che segnali l'esistenza o meno di un elemento nella lista con tale valore;
ex-3
si scriva una funzione che accetti una lista e raddoppi tutti gli elementi pari di essa;
ex-4
si scriva una funzione che accetti una lista e due interi (a, b) e cambi tutti gli elementi con valore a in b;


next up previous contents index
Next: Inserzione ed eliminazione in Up: Liste semplici in C++ Previous: Eliminazione in testa e   Indice   Indice analitico
Claudio Cicconetti
2000-09-06