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

Inserzione in testa e in coda

L'operazione più semplice che si possa effettuare su di una lista è l'inserzione di un elemento in testa, ovvero come primo elemento; si noti che tale operazione in pratica provoca uno shift (trad. ``scorrimento'') della lista verso destra: se inseriamo dei dati sempre in testa, otterremo una lista con i nostri dati inseriti in ordine inverso. Una semplice funzione che effettua l'inserzione in testa di un elemento è la seguente:

void insTesta (elem*& lista, int info) {
  lista = new elem (info, lista);
}
Gli argomenti passati sono la lista alla quale aggiungere un elemento, e il campo informazione di esso; l'inserzione avviene con un solo statement: si assegna al puntatore lista (attenzione: passato per riferimento!) il valore di un nuovo elemento avente l'informazione info e che punta al suo valore. Vediamo cosa succede in realtà nel seguente esempio:

// ex7_7_2.cpp
// si copino in questo punto le definizioni
// della struttura `elem' e della funzione `insTesta'

void main() {
  elem* lista = 0;  // si metta SEMPRE a zero una lista vuota
  insTesta (lista, 2);
  insTesta (lista, 5);
}
Inizialmente creiamo una lista vuota, la quale è costituita da un puntatore a 0; si faccia bene attenzione a mettere sempre a zero una nuova lista, magari utilizzando la seguente banale funzione, da chiamare subito dopo avere definito il puntatore lista:

void inizializza (elem*& lista) {
  lista = 0;
}
Dopo avere inizializzato la lista, chiamiamo per la prima volta la funzione insTesta su di essa, passando l'intero 2 come informazione: prima di tutto viene creato un nuovo elemento, i cui campi vengono immediatamente inizializzati con il valore di info e con il puntatore lista, che vale al momento 0. Tale nuovo elemento avrà un indirizzo, il quale viene tornato dall'operatore new e assegnato a lista, che dunque punta al primo (e per ora unico) elemento. Quando chiamiamo per la seconda volta la funzione insTesta su lista, ripetiamo le medesime operazioni appena elencate, con l'unica eccezione che il puntatore nel neonato elemento è riferito non a 0 ma all'elemento preesistente. Per meglio convincersi del funzionamento di tale meccanismo, si consiglia calorosamente di eseguire qualche prova ``su carta'' di inserimenti su liste vuote e non.

L'inserzione in testa presenta un notevole svantaggio: i dati risultano inseriti in ordine inverso rispetto a quello con il quale li si immette; conviene allora spesso eseguire delle inserzioni in coda, cioè aggiungere ogni nuovo elemento alla fine della lista. Tale procedura è un poco più articolata perché, mentre sappiamo bene dove inizia una lista, non possiamo immaginare dove essa termini se non la scorriamo completamente da sinistra a destra (immaginiamo sempre di avere la testa all'estrema sinistra e la coda all'estrema destra). Ricordiamo che la fine della lista è segnalata dal puntatore next messo a 0:


void insCoda (elem*& lista, int info) {
  // separiamo il caso in cui la lista sia vuota
  // per il quale basta inserire l'elemento in testa
  if (lista == 0) {
    insTesta (lista, info);
    return;
  }
  // puntatore ausiliatio di scorrimento
  elem* p = lista;
  // scorriamo la lista fino a quando l'elemento
  // successivo a `p' e` non nullo
  while (p->next != 0)
    p = p->next;  // passa alla cella successiva
  // quando usciamo dal while, vuol dire che
  // ci troviamo sull'ultimo elemento
  // al quale dobbiamo farne seguire un altro
  // contenente `info'
  p->next = new elem (info, 0);
  // ovviamente l'ultimo elemento deve puntare a 0
}
Non ci si lasci spaventare dalla lunghezza di questa funzione: in realtà essa è molto semplice, e presenta inoltre numerosi commenti. La prima operazione da effettuare è verificare se la lista è vuota: in caso affermativo bisogna operare una strategia a parte, che consiste semplicemente nell'inserire il nostro elemento in testa. Trattare a parte i casi particolari (nessun elemento, un solo elemento) è sempre fondamentale quando si lavora con le liste. Se la lista non è vuota, allora creiamo un puntatore ausiliario, che indichiamo con il nome p, che ci permetterà di scorrere la lista da sinistra a destra; infatti assegnamo al puntatore p il valore di lista, che è l'indirizzo del primo elemento, e lo facciamo ``proseguire'' tramite il comando p = p->next fino a che esso non si trova sull'ultimo elemento della lista, ovvero fino a quando il suo campo next è non-zero. A questo punto basta creare un nuovo elemento che punti a 0, siccome esso diventerà l'elemento terminale della lista, e che abbia il campo dati uguale a info, e assegnare il suo indirizzo all'ex-elemento terminale, cioè p.

ex-2
si scrivano due programmi che creino una lista contenente i seguenti valori: 2, -5, 0, 9; il primo utilizzi l'inserzione in testa, il secondo in coda;
ex-3
si scriva una funzione che inserisca un nuovo elemento in una lista in posizione di secondo elemento; se la lista è vuota si effettui una inserzione in testa, se essa contiene un solo elemento si effettui una inserzione in coda;


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