Liste pile code

Untitled Cenni teorici In questa esercitazione si è reso necessario utilizzare due strutture dati molto importanti: la pila e la coda. Per implementare queste due classi è però necessario affrontare le liste. Nodi e liste concatenate In informatica si possono dare due definizioni di lista, una sequenziale e una ricorsiva. DEFINIZIONE SEQUENZIALE Una lista è un insieme di elementi in cui ogni elemento, tranne il primo e l'ultimo, hanno un solo predecessore e un solo successore. DEFINIZIONE RICORSIVA Una lista è una lista vuota oppure è una coppia di elementi ( i , l ) dove i è un informazione ed è detta testa della lista, mentre l è a sua volta una lista ed è detta coda della lista. Per implementare una lista viene utilizzata una classe Nodo, che rappresenta ogni nodo della lista. Ogni nodo è caratterizzato da un campo informazione e da un puntatore al nodo successivo della lista. Se il puntatore è null allora significa che la lista è terminata. La classe Nodo è implementata nel seguente modo: public class Nodo { public Object info; public Nodo next; public Nodo(Object o, Nodo n) { info=o; next=n; } } Ciò che segue è una semplice rappresentazione di una lista: Per costruire una lista come quella scritta sopra si può usare il seguente frammento di codice: Nodo a = new Nodo(a1,null); Nodo b = new Nodo(a2,null); Nodo c = new Nodo(a3,null); a.next = b; b.next = c; Per visitare una lista in modo iterativo si può far riferimento al seguente algoritmo: Nodo n = a; // a è il puntatore d'accesso alla lista while (n!=null) { > n = n.next; } Per inserire un elemento in testa basta usare il seguente frammento di codice: n.next = first; // n è il nodo da inserire first = n; // first è il puntatore d'accesso Per inserire un elemento in mezzo o in coda bisogna prima posizionarsi sul nodo precedente tramite un nodo d'appoggio (prec) e poi si può inserire, in questo modo: n.next = prec.next; // n è il nodo da inserire prec.next = n; Per eliminare un elemento in testa basta rifarsi al seguente frammento di codice: first = first.next; Per eliminare un elemento in mezzo o in coda bisogna prima posizionarsi sul nodo precedente tramite un nodo d'appoggio (prec) e poi si può cancellare, in questo modo: prec.next = prec.next.next; Ci sono altri tipi di lista, come la lista doppiamente concatenate o la lista circolare, ma in questa tesina non ne parliamo, quindi passeremo a trattare le pile e le code. Pila Una pila è una successione di elementi in cui tutte le operazioni di inserimento e di cancellazione avvengono dallo stesso estremo detto testa della pila. La pila esegue una disciplina LIFO(Last In First Out). Le pile sono molto utilizzate per controllare le chiamate ai sottoprogrammi. Le pile possono essere implementate in maniera illimitata, attraverso una lista, o in maniera limitata, attraverso un vettore. In questa tesina vedremo solo l'utilizzo di una pila illimitata. Il diagramma UML di una classe Pila è il seguente: Pila - testa: Nodo + Pila() + isEmpty():boole