next up previous contents index
Next: Ricerca e modifica di Up: Liste semplici in C++ Previous: Stampa di una lista   Indice   Indice analitico

Eliminazione in testa e in coda

La lista è una struttura fortemente dinamica: in ogni momento deve essere possibile aggiungere o togliere elementi; abbiamo visto la prima di queste due operazioni, è giunto il momento di studiare anche la seconda. L'eliminazione di un elemento, cioè la deallocazione della memoria da esso occupata nello heap, può avvenire, come l'inserzione, in testa o in coda. Nel primo caso la funzione è molto semplice:

void eliminaTesta (elem*& lista) {
  if (lista != 0) {
    // puntatore temporaneo all'elemento da eliminare
    elem* p = lista;
    // la lista e` costituita ora dagli elementi
    // dal secondo all'ultimo
    lista = lista->next;
    // possiamo deallocare la memoria del primo elemento
    delete p;
  }
}

Prima di procedere all'eliminazione dell'elemento di testa, bisogna accertarsi che la lista sia vuota; in caso affermativo è sufficiente uscire dalla funzione. Altrimenti, si definisce un puntatore al primo elemento della lista, si sposta il puntatore lista al suo elemento successivo (nota: potrebbe anche andare a 0, nel caso la lista sia costituita da un solo elemento), si rimuove l'elemento puntato da p.

Come nel caso dell'inserzione, l'eliminazione dell'ultimo elemento di una lista è un'operazione un poco più complessa rispetto all'eliminazione in testa; infatti bisogna, con una procedura simile a quella per l'inserzione, cercare l'ultimo elemento scorrendo tutta la lista da sinistra a destra.


void eliminaCoda (elem*& lista) {
  // se la lista e` vuota la si lascia inalterata
  if (lista == 0)
    return;
  
  // se la lista e` costituita da un solo elemento
  // lo si elimina direttamente
  if (lista->next == 0) {
    delete lista;
    lista = 0;
    return;
  }
  
  // puntatori ausiliari che scorrono la lista da sx a dx
  // separati l'un l'altro da un solo elemento
  elem* p = lista;
  elem* q = lista->next;
  while (q->next != 0) {
    p = p->next;
    q = q->next;
  }
  // `q' ora e` l'ultimo elemento della lista
  // mentre `p' e` il penultimo
  p->next = 0;  // chiude la lista
  delete q;
}

La differenza fondamentale tra l'inserzione e l'eliminazione in coda è che, mentre nel primo caso basta un solo puntatore di scorrimento, nel secondo ce ne vogliono due; essi partono dai primi due elementi della lista, nel caso essa non sia vuota o costituita da un solo elemento, e la scorrono affiancati. Quando il campo next del puntatore più avanzato è arrivato a fine corsa, basta eliminare l'ultimo elemento e fare in modo che il penultimo punti a 0; l'utilizzo di due puntatori è molto comune nelle liste semplici, avendo esse un solo verso di percorrimento. Si consiglia di provare ad eseguire il programma seguente ``a mano'':


// ex7_7_5
void main() {
  elem* lista; inizializza (lista);
  generaLista (lista, 20, 5);
  stampa (lista, 5);
  eliminaTesta (lista);
  stampa (lista, 5);
  for (int i = 0; i < 4; i++) {
    eliminaCoda (lista);
    cout << "\n";
    stampa (lista, 5);
  }
}

esempio di output:
 9 13 15 16 7
 13 15 16 7  
 13 15 16    
 13 15      
 13        

ex-2
si scriva un programma che generi una lista di 20 elementi, la stampi, elimini cinque elementi in testa e cinque in coda e la ristampi;
ex-3
si scriva una funzione che distrugga tutti gli elementi di una lista;
ex-4
si scriva una funzione che elimini un elemento in testa ed uno in coda in una lista, facendo molta attenzione ai casi particolari;


next up previous contents index
Next: Ricerca e modifica di Up: Liste semplici in C++ Previous: Stampa di una lista   Indice   Indice analitico
Claudio Cicconetti
2000-09-06