next up previous contents index
Next: Liste bilaterali Up: Cenni su liste non Previous: Liste semplici con puntatore   Indice   Indice analitico

Liste circolari

Una lista circolare è una lista semplice senza un puntatore in testa; semplicemente ogni elemento è collegato al suo successivo, senza un inizio né una fine, come se gli elementi fossero posti su di una circonferenza. Per accedere la lista si usa di solito un indicatore, il quale è libero di muoversi da un elemento ad un altro; vediamo una possibile implementazione di una lista circolare:

// ex7_8_3
#include <iostream.h>

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

// inserisce un elemento
void inserisce (elem*& ind, int n) {
  // caso base: lista vuota
  if (ind == 0) {
    ind = new elem (n, 0);
    ind->next = ind;
    return;
  }
  ind->next = new elem (n, ind->next);
}

// sposta l'indicatore in avanti
void avanza (elem*& ind) {
  ind = ind->next;
}

// stampa la lista
void stampa (const elem* ind) {
  if (ind == 0)
    return;
  const elem* p = ind;
  while (p->next != ind) {
    cout << p->info << "\t";
    p = p->next;
  }
  cout << p->info << "\n";
}

void main() {
  elem* ind = 0;
  for (int i = 0; i < 5; i++)
    inserisce (ind, i);
  stampa (ind);
  avanza (ind);  stampa (ind);
  avanza (ind);  stampa (ind);
}

output:
 0 4 3 2 1
 4 3 2 1 0
 3 2 1 0 4

Le liste circolari sono relativamente difficili sia da programmare che da utilizzare, in quanto mancano i soliti punti fissi costituiti da testa e coda; in realtà, se si escludono gli scopi puramente didattici, non sono molto usate nel mondo della programmazione.

ex-2
si scriva una funzione che raddoppi tutti gli elementi di una lista circolare;
ex-3
si scriva una funzione che torni il numero di occorrenze di un certo elemento in un una lista circolare;


next up previous contents index
Next: Liste bilaterali Up: Cenni su liste non Previous: Liste semplici con puntatore   Indice   Indice analitico
Claudio Cicconetti
2000-09-06