Una istanza di classe può contenere, tra le sue variabili, anche un puntatore ad un oggetto della classe stessa. Questo consente di concatenare oggetti di una stessa classe, a formare strutture complesse quali liste o alberi. In particolare, una lista è ottenuta dalla concatenazione di nodi, ciascuno dei quali contiene un puntatore al nodo successivo, nonché un campo dati talvolta chiamato cargo.
Esempio 1: Attraversamento di una lista
Nel codice Processing che segue viene creata una lista di tre nodi concatenati. Quindi tale lista viene visitata per attraversamento e il cargo di ogni nodo viene stampato. Si notino le seguenti cose:
- La classe
Nodeha due tipi di costruttore, uno senza parametri ed uno con parametri. Quest'ultimo consente la creazione con inizializzazione del cargo e del puntatore al nodo successivo. - C'è un metodo
toStringche converte il cargo in una stringa stampabile ogni volta che viene invocata la funzione print sul nodo.
void setup() {
Node node3 = new Node (3, null);
Node node2 = new Node (2, node3);
Node node1 = new Node (1, node2);
printList(node1);
}
void printList (Node list) {
Node node = list;
while (node != null) {
print(node);
node = node.next;
}
println();
}
class Node {
int cargo;
Node next;
Node() {
cargo = 0;
next = null;
}
Node (int cargo, Node next) {
this.cargo = cargo;
this.next = next;
}
String toString() { //rende l'oggetto di classe Node stampabile
return cargo + " ";
}
}
Così come gli array sono il supporto naturale dei cicli
for e delle iterazioni sequenziali, così le liste
sono il supporto naturale della algoritmica ricorsiva. Gli
algoritmi ricorsivi sono definiti induttivamente stabilendo
l'operazione per un elemento base (la base della ricorsione) e
stabilendo come utilizzare il risultato dell'elaborazione
sulla lista privata di tale elemento. Inoltre, bisogna
assicurarsi che l'elaborazione così arrangiata in maniera
"telescopica" raggiunga ad un certo punto una condizione di
terminazione della ricorsione. Ciò non è sempre banale perché
le catene di puntatori degli elementi di una lista potrebbero
presentare dei loop, la cui visita
procederebbe senza fine.
Nell'esempio Esempio 1 si può introdurre
una funzione di stampa dall'ultimo elemento al primo:
void printBackward (Node list) {
if (list == null) return; // terminazione della ricorsione
Node head = list;
Node tail = list.next;
printBackward(tail);
print(head); // base della ricorsione
}
Si può costruire una classe che incorpori l'intera lista e le
operazioni che su di essa si intendono eseguire. Ad esempio,
si può estendere Esempio 1 con
l'introduzione di una classe IntList che supporta
stampe per attraversamento diretto e inverso (ricorsivo). Si
noti l'uso di un doppio metodo printBackward, uno
con e uno senza argomenti, per consentire l'invocazione del
metodo sull'oggetto lista senza necessità di passare un
puntatore alla testa della lista stessa.
IntList lista;
void setup() {
lista = new IntList();
lista.addFirst(3);
lista.addFirst(2);
lista.addFirst(1);
lista.printList();
lista.printBackward();
}
class IntList {
int length;
Node head;
IntList() {
length = 0;
head = null;
}
void addFirst (int i) {
Node node = new Node(i, head);
head = node;
length++;
}
void printList () {
Node node = head;
while (node != null) {
print(node);
node = node.next;
}
println();
}
void printBackward() {
printBackward(head);
println();
}
void printBackward (Node head) {
if (head == null) return; // terminazione della ricorsione
Node tail = head.next;
printBackward(tail);
print(head); // base della ricorsione
}
}
class Node {
int cargo;
Node next;
Node() {
cargo = 0;
next = null;
}
Node (int cargo, Node next) {
this.cargo = cargo;
this.next = next;
}
String toString() { //rende l'oggetto di classe Node stampabile
return cargo + " ";
}
}
double, int, ecc.) e
consentono di creare e manipolare oggetti che contengono
valori primitivi. Ad esempio, la classe wrapper
Integer può essere interrogata in relazione al
più piccolo e più grande valore rappresentabile mediante
Integer.MIN_VALUE e
Integer.MAX_VALUE, rispettivamente. Il valore
numerico di un oggetto della classe Integer si
ottiene con il metodo intValue(). Anche gli array
in Java sono accessibili mediante una classe wrapper. La
classe Arrays, accessibile importando
java.util.*, consente di fare operazioni di test
di uguaglianza, di ricerca, e di ordinamento. Ad esempio, il
semplice codice
import java.util.*;
void setup() {
int[] a = new int[10];
int[] b = new int[10];
for (int i=0; i<10; i++) {
a[i] = i;
b[i] = i;
}
println(Arrays.equals(a,b));
}
Lettura
Si legga il capitolo 14 di How to Think Like a Computer Scientist
