next up previous contents index
Next: Approfondimenti. I files d'intestazione Up: Cenni su liste non Previous: Liste circolari   Indice   Indice analitico

Liste bilaterali

Le liste bilaterali sono il modello di lista più utilizzato dai programmatori per le loro strutture dati; infatti esse consentono di scorrere la lista in due sensi, aumentando evidentemente l'efficienza delle operazioni compiute su di essa. Comunque noi mostreremo solamente alcune delle operazioni tipiche sulle liste bilaterali.

// ex7_8_4
#include <iostream.h>

struct elem {
  int   info;
  elem* next;
  elem* prev;
  elem (elem* Next, elem* Prev, int Info) {
    info = Info;
    next = Next;
    prev = Prev;
  }
};

void insTesta (elem*& testa, elem*& coda, int n) {
  if (testa == 0) {
    testa = coda = new elem (0, 0, n);
    return;
  }
  testa = new elem (testa, 0, n);
  elem* secondo = testa->next;
  secondo->prev = testa;
}


void insCoda (elem*& testa, elem*& coda, int n) {
  if (testa == 0) {
    testa = coda = new elem (0, 0, n);
    return;
  }
  elem* p = new elem (0, coda, n);
  coda = coda->next = p;
}

// estrae in testa
bool estraiTesta (elem*& testa, elem*& coda) {
  if (testa == 0)
    return false;
  if (testa == coda) {
    delete testa;
    testa = coda = 0;
    return true;
  }
  elem* p = testa;
  testa = testa->next;
  testa->prev = 0;
  delete p;
  return true;
}

// estrae in coda
bool estraiCoda (elem*& testa, elem*& coda) {
  if (testa == 0)
    return false;
  if (testa == coda) {
    delete testa;
    testa = coda = 0;
    return true;
  }
  elem* p = coda;
  coda = coda->prev;
  coda->next = 0;
  delete p;
  return true;
}

void stampa (const elem* testa) {
  const elem* p = testa;
  int i = 0;
  while (p != 0) {
    i++;
    if (i % 5 == 0)
      cout << p->info << "\n";
    else
      cout << p->info << "\t";
    p = p->next;
  } 
}

// stampa la lista in ordine inverso
void stampaInverso (const elem* coda) {
  const elem* p = coda;
  int i = 0;
  while (p != 0) {
    i++;
    if (i % 5 == 0)
      cout << p->info << "\n";
    else
      cout << p->info << "\t";
    p = p->prev;
  } 
}

void main() {
  elem *testa = 0, *coda = 0;
  int i;
  for (i = 0; i < 5; i++)
    insCoda (testa, coda, i);
  for (i = 5; i < 10; i++)
    insTesta (testa, coda, i);
  stampaInverso (coda);
  cout << "\n";   stampa (testa);
  estraiTesta (testa, coda);
  estraiCoda (testa, coda);
  cout << "\n";   stampa (testa);
}

output:
 4 3 2 1 0
 5 6 7 8 9

 9 8 7 6 5
 0 1 2 3 4

 8 7 6 5 0
 1 2 3    

Si noti che si è dovuto modificare anche la struttura elem, la quale deve presentare in questo caso due puntatori: uno all'elemento precedente (next) e uno al successivo (prev). Nelle liste bilaterali si ha simmetria tra la testa e la coda, per cui possiamo operare sulla lista da sinistra verso destra o viceversa senza perdere efficienza; inoltre, provare per credere, le operazioni di inserzione ed estrazioni in posizioni arbitrarie nella lista sono sensibilmente più veloci e semplici rispetto alle analoghe operazioni sulle liste semplici.

ex-2
si scriva una funzione che restituisca il numero di elementi di una lista bilaterale;
ex-3
si scriva una funzione che permetta l'inserzione di un elemento dopo la prima occorrenza trovata di un certo valore dato in una lista bilaterale;
ex-4
si scriva una funzione che estragga la prima occorrenza (dalla testa) di un elemento dato in una lista bilaterale;
ex-5
si provi a scrivere delle funzioni le quali permettano di gestire una lista bilaterale ordinata, o una lista bilaterale circolare;


next up previous contents index
Next: Approfondimenti. I files d'intestazione Up: Cenni su liste non Previous: Liste circolari   Indice   Indice analitico
Claudio Cicconetti
2000-09-06