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

Liste ordinate

Ordinare una lista è un procedimento alquanto ingrato, per cui è ben più comune creare e gestire delle liste che siano ordinate ad ogni inserimento; per tali liste non esiste la differenza tra coda e testa: inserimento ed estrazione avvengono sempre in maniera tale da non turbare l'ordine della lista.

// ex7_8_1
#include <iostream.h>

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

// inserisce un elemento
void inserisci (elem*& lista, int n) {
  // caso base: lista vuota
  if (lista == 0) {
    lista = new elem (n, 0);
    return;
  }
  // caso base: primo elemento maggiore di `n'
  // inserisce in testa
  if (lista->info > n) {
    lista = new elem (n, lista);
    return;
  }
  // caso base: un solo elemento
  // inserisce in coda
  if (lista->next == 0) {
    lista->next = new elem (n, 0);
    return;
  }
  elem* p = lista;
  elem* q = lista->next;
  while (q != 0 && q->info < n) {
    p = p->next;
    q = q->next;
  }
  // si inserisce il nuovo elemento tra `p' e `q'
  p->next = new elem (n, q);
}

// elimina una ricorrenza dell'elemento `n'
bool elimina (elem*& lista, int n) {
  // caso base: lista vuota
  if (lista == 0)
    return false;
  // caso base: la ricorrenza e` il primo elemento
  // estrazione in testa
  if (lista->info == n) {
    elem* p = lista;
    lista = lista->next;
    delete p;
    return true;
  }
  elem* p = lista;
  elem* q = lista->next;
  while (q != 0 && q->info != n) {
    p = p->next;
    q = q->next;
  }
  if (q == 0)  // occorrenza non trovata
    return false;
  p->next = q->next;
  delete q;
  return true;
}

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

void main() {
  elem* lista = 0;
  inserisci (lista, 4);  inserisci (lista, 1);
  inserisci (lista, 8);  inserisci (lista, 7);
  stampa (lista);
  // il seguente statement non ha effetti: 3 non e` in lista
  elimina (lista, 3);  cout << "\n";  stampa (lista);
  elimina (lista, 1);  cout << "\n";  stampa (lista);
}

output:
 1 4 7 8
 1 4 7 8
 4 7 8  

Le funzioni più interessanti per le liste ordinate sono sicuramente l'inserzione e l'estrazione di un elemento; pur esistendo molte varianti di tali funzioni, i meccanismi sono sempre simili a quelli proposti nel precedente esempio: si estrapolano i casi base dall'algoritmo generale; per quest'ultimo si utilizzano due puntatori di scorrimento che procedono affiancati fino alla fine della lista o al verificarsi di una determinata condizione. Una lista ordinata rende molto più pesanti le operazioni di inserzione ed estrazione, rispetto alle corrispondenti operazioni effettuate in testa sulle liste semplici, ma presenta la preziosa caratteristica di essere in ogni momento ordinata; non mancano modelli reali cui è possibile applicare tale struttura dati.

ex-2
si scriva una funzione che torni la somma aritmetica dei valori degli elementi di una lista ordinata;
ex-3
si modifichi il programma ex7_8_1.cpp in modo tale da avere una lista ordinata in senso decrescente di numeri reali


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