// 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.