// 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.
ex7_8_1.cpp
in modo tale da avere una lista ordinata in senso decrescente di numeri reali