Capitolo 18
Strutture di dati avanzate
Figura 1
Un insieme
di stampanti
Figura 2 Classi
e interfacce
per gli insiemi
nella libreria
standard
File SetTest.java
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import javax.swing.JoptionPane;
/**
Programma che illustra il funzionamento di un insieme di stringhe.
L'utente può inserire e rimuovere stringhe.
*/
public class SetTest {
public static void main(String[] args) {
Set names = new HashSet();
boolean done = false;
while (!done) {
String input = JoptionPane.showInputDialog(
"Add name, Cancel when done");
if (input == null) done = true;
else {
names.add(input);
print(names);
} }
done = false;
while (!done) {
String input = JoptionPane.showInputDialog(
"Remove name, Cancel when done");
if (input == null) done = true;
else {
}
System.exit(0);
} /**
Stampa il contenuto di un insieme.
@param s un insieme
*/
private static void print(Set s) {
Iterator iter = s.iterator();
System.out.print("{ ");
while (iter.hasNext()) {
System.out.print(iter.next());
System.out.print(" ");
}
System.out.println("}");
} }
Figura 4 Classi
e interfacce
per le mappe
nella libreria
standard
File MapTest.java
import java.awt.Color;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
Questo programma collauda una mappa che associa nomi a colori.
*/
public class MapTest {
public static void main(String[] args) {
Map favoriteColors = new HashMap();
favoriteColors.put("Juliet", Color.pink);
favoriteColors.put("Romeo", Color.green);
favoriteColors.put("Adam", Color.blue);
favoriteColors.put("Eve", Color.pink);
Stampa i contenuti di una mappa.
@param m una mappa
*/
private static void print(Map m) {
Set keySet = m.keySet();
Iterator iter = keySet.iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object value = m.get(key);
System.out.println(key + "->" + value);
} } }
Figura 5
Una realizzazione molto
semplice di tabella hash
Figura 6
Una tabella hash con liste concatenate per memorizzare elementi aventi lo stesso codice hash
File HashSet.java
import java.util.Iterator;
import java.util.AbstractSet;
/**
Un HashSet memorizza una raccolta non ordinata di oggetti usando una tabella di hash.
*/
public class HashSet extends AbstractSet {
/**
Costruisce una tabella di hash.
@param bucketsLength la lunghezza dell’array buckets
*/
public HashSet(int bucketsLength) {
buckets = new Link[bucketsLength];
size = 0;
/**
Verifica l’appartenenza all’insieme.
@param x un oggetto
@return true se x è un elemento dell’insieme
*/
public boolean contains(Object x) {
int h = x.hashCode();
if (h < 0) h = -h;
h = h % buckets.length;
Link current = buckets[h];
while (current != null) {
if (current.data.equals(x)) return true;
current = current.next;
}
return false;
}
/**
Inserisce un elemento all’insieme.
@param x un oggetto
@return true se x è un oggetto nuovo, false se x era gia' presente nell'insieme
*/
public boolean add(Object x) {
int h = x.hashCode();
if (h < 0) h = -h;
h = h % buckets.length;
Link current = buckets[h];
while (current != null) {
if (current.data.equals(x))
return false; // gia' nell'insieme current = current.next;
Link newLink = new Link();
newLink.data = x;
newLink.next = buckets[h];
buckets[h] = newLink;
size++;
return true;
} /**
Elimina un oggetto dall'insieme.
@param x un oggetto
@return true se x viene eliminato dall’insieme,
false se x non e' presente nell'insieme
*/
public boolean remove(Object x) {
int h = x.hashCode();
if (h < 0) h = -h;
h = h % buckets.length;
Link current = buckets[h];
Link previous = null;
while (current != null) {
if (current.data.equals(x)) {
if (previous == null)
buckets[h] = current.next;
else previous.next = current.next;
size--;
return true;
}
previous = current;
current = current.next;
}
return false;
}
Restituisce il numero di elementi nell'insieme.
@return il numero di elementi
*/
public int size() {
return size;
}
private Link[] buckets;
private int size;
private class Link {
public Object data;
public Link next;
}
private class HashSetIterator implements Iterator {
/**
Costruisce un iteratore per insiemi hash che punta al primo elemento dell'insieme.
*/
public HashSetIterator() {
bucket = 0;
previous = null;
previousBucket = buckets.length;
// imposta bucket all'indice del primo bucket non vuoto
while (bucket < buckets.length
&& buckets[bucket] == null) bucket++;
if (bucket < buckets.length) current = buckets[bucket];
else current = null;
{
Object r = current.data;
if (current.next == null) // avanza al prossimo bucket {
previousBucket = bucket;
bucket++;
while (bucket < buckets.length
&& buckets[bucket] == null) bucket++;
if (bucket < buckets.length) current = buckets[bucket];
else current = null;
}
else // avanza al prossimo elemento in bucket {
previous = current;
current = current.next;
}
}
public void remove() {
if (previous != null)
previous.next = previous.next.next;
else if (previousBucket < buckets.length) buckets[previousBucket] = null;
else
throw new IllegalStateException();
previous = null;
previousBucket = buckets.length;
}
private int bucket;
private Link current;
private int previousBucket;
import java.util.Iterator;
import java.util.Set;
/**
Questo programma collauda la classe insieme realizzata con tabella hash.
*/
public class SetTest {
public static void main(String[] args) {
Set names = new HashSet(101); // 101 e' un numero primo names.add("Sue");
names.add("Harry");
names.add("Nina");
names.add("Susannah");
names.add("Larry");
names.add("Eve");
names.add("Sarah"
names.add("Adam");
names.add("Tony");
names.add("Katherine");
names.add("Juliet");
names.add("Romeo");
names.remove("Romeo");
names.remove("George");
Iterator iter = names.iterator();
while (iter.hasNext())
System.out.println(iter.next());
} }
/**
Una moneta con un valore monetario.
*/
public class Coin {
/**
Costruisce una moneta.
@param aValue il valore monetario della moneta
@param aName il nome della moneta
*/
public Coin(double aValue, String aName) {
value = aValue;
name = aName;
} /**
Restituisce il valore della moneta.
@return il valore
public double getValue() {
return value;
} /**
Restituisce il nome della moneta.
@return il nome
*/
public String getName() {
return name;
}
public boolean equals(Object otherObject) {
if (otherObject == null) return false;
if (getClass() != otherObject.getClass()) return false;
Coin other = (Coin)otherObject;
public int hashCode() {
int h1 = name.hashCode();
int h2 = new Double(value).hashCode();
final int HASH_MULTIPLIER = 29;
int h = HASH_MULTIPLIER * h1 + h2;
return h;
}
public String toString() {
return "Coin[value=" + value + ",name=" + name + "]";
}
private double value;
private String name;
}
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
Un programma per collaudare i codici di hash delle monete.
*/
public class HashCodeTest {
public static void main(String[] args) {
Coin coin1 = new Coin(0.25, "quarter");
Coin coin2 = new Coin(0.25, "quarter");
Coin coin3 = new Coin(0.05, "nickel");
System.out.println("hash code of coin1="
+ coin1.hashCode());
System.out.println("hash code of coin2="
+ coin2.hashCode());
System.out.println("hash code of coin3="
Set coins = new HashSet();
coins.add(coin1);
coins.add(coin2);
coins.add(coin3);
Iterator iter = coins.iterator();
while (iter.hasNext())
System.out.println(iter.next());
} }
Figura 7 Un albero
di ricerca binario
Figura 8
Un albero binario
che non è un albero
di ricerca binario
Figura 9 Un albero di ricerca binario dopo quattro
inserimenti
Figura 10
Un albero
di ricerca
binario
dopo
cinque
inserimenti
File TreeTest.java /**
Questo programma collauda una classe che realizza un albero di ricerca binario.
*/
public class TreeTest {
public static void main(String[] args) {
Tree names = new Tree();
names.insert("Romeo");
names.insert("Juliet");
names.insert("Tom");
names.insert("Dick");
names.insert("Harry");
names.print();
Figura 11
Un albero di ricerca
binario sbilanciato
File Tree.java /**
Questa classe implementa un albero di ricerca binario i cui nodi contengono oggetti che implementano l’interfaccia
Comparable.
*/
public class Tree {
/**
Costruisce un albero vuoto.
*/
public Tree() {
root = null;
} /**
{
Node newNode = new Node();
newNode.data = obj;
newNode.left = null;
newNode.right = null;
if (root == null) root = newNode;
else root.insertNode(newNode);
} /**
Stampa il contenuto dell’albero in successione ordinata.
*/
public void print() {
if (root != null)
root.printNodes();
}
private Node root;
/**
Un nodo di un albero conserva un dato e i riferimenti ai nodi figlio sinistro e figlio destro.
*/
private class Node {
/**
Inserisce un nuovo nodo come discendente di questo nodo.
@param newNode il nodo da inserire
*/
public void insertNode(Node newNode) {
if (newNode.data.compareTo(data) < 0) {
if (left == null) left = newNode;
{
if (right == null) right = newNode;
else right.insertNode(newNode);
} } /**
Stampa questo nodo e tutti i suoi discendenti in successione ordinata.
*/
public void printNodes() {
if (left != null)
left.printNodes();
System.out.println(data);
if (right != null)
right.printNodes();
}
public Comparable data;
public Node left;
public Node right;
}
File TreeSetTest.java
import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
Un programma per collaudare un insieme ad albero.
*/
public class TreeSetTest {
public static void main(String[] args) {
Coin coin1 = new Coin(0.25, "quarter");
Coin coin2 = new Coin(0.25, "quarter");
Coin coin3 = new Coin(0.25, "penny");
Coin coin4 = new Coin(0.25, "nickel");
class CoinComparator implements Comparator {
public int compare(Object firstObject, Object secondObject) {
Coin first = (Coin)firstObject;
Coin second = (Coin)secondObject;
if (first.getValue() < second.getValue()) return –1;
if (first.getValue() == second.getValue()) return 0;
return 1;
} }
Comparator comp = new CoinComparator();
Set coins = new TreeSet(comp);
coins.add(coin1);
coins.add(coin2);
coins.add(coin3);
coins.add(coin4);
Iterator iter = coins.iterator();
while (iter.hasNext())
System.out.println(iter.next());
} }
