next up previous contents index
Next: Cenni su liste non Up: Liste semplici in C++ Previous: Ricerca e modifica di   Indice   Indice analitico

Inserzione ed eliminazione in punti arbitrari di una lista

Inserire o eliminare un elemento che non sia in posizione iniziale o finale, è di solito una operazione non semplice, in quanto bisogna prima di tutto identificare l'elemento sul quale operare; essendo le liste strutture dati non indicizzate, l'identificazione di un elemento all'interno di esse è non ovvia. Una strada possibile è quella di inserire un elemento dopo l'occorrenza di un'altro di essi; ad esempio la seguente funzione inserisce un nuovo elemento, avente valore 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  

eliminazione di 5 riuscita
eliminazione di 13 non riuscita
 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

ex-2
si scriva un programma che crei una lista contenente i primi 10 numeri pari; si elimini 8, 10, 12; si copi tale lista in un'altra e si stampi quest'ultima;
ex-3
si scriva una funzione che elimini tutti gli elementi aventi un certo valore;
ex-4
si scriva una funzione che inserisca un elemento in posizione i-esima;
ex-5
si scriva una funzione che elimini l'i-esimo elemento di una lista


next up previous contents index
Next: Cenni su liste non Up: Liste semplici in C++ Previous: Ricerca e modifica di   Indice   Indice analitico
Claudio Cicconetti
2000-09-06