Inhalt |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Datenstrukturen dienen dazu große, unvorhersehbar viele Daten zu speichern und wiederzufinden. Dabei kann man auf eine leichte Speicherbarkeit oder auf eine schnelle Abrufbarkeit Wert legen. Außerdem unterscheiden sich die verschiedenen Lösungen noch durch ihren Speicherbedarf. Insgesamt ist also zu achten auf
Bisher haben wir lediglich das Array kennengelernt. Mit dem Array lässt sich eine vordefinierte Anzahl von Daten einspeichern. Wird diese Anzahl überschritten, so muss das gesamte Array umgespeichert werden. Arrays können nicht nachträglich vergrößert werden. Beim Zugriff muss das gesamte Array durchsucht werden. Die Speicherung ist also schnell, der Zugriff langsam, die Flexibilität ist überhaupt nicht vorhanden. Der Speicherbedarf ist von der festen Obergrenze abhängig.
Mit Threads wird sich ein späteres Kapitel beschäftigen.
Ein Array kann auch beliebige Daten aufnehmen. Dies geschieht dadurch, dass die Objekte, die im Array abgespeichert werden, entweder Instanzen von Klassen oder selbst wieder Arrays sind, und dass das Array als Array vom Typ Object deklariert wird. Alle Klassen stammen in Java von Object ab.
Darüber hinaus gibt es für die eingebauten Datentypen, wie int und double, Wrapper-Klassen, die solche Daten aufnehmen können, wie Integer und Double. Diese Wrapper-Klassen bieten außerdem noch nützliche Zusatzfunktionen. Rechnen kann man mit den so verpackten Daten allerdings direkt nicht mehr. Dazu muss man sie in die elementaren Formate zurück verwandeln. Ab Java 1.5 erledigt dies Java automatisch.
public class Test
{
public static void main (String args[])
{
Object A[] = new Object[6];
// Gib verschiedene Sachen ein:
A[0] = Integer.valueOf(4); // int
A[1] = Double.valueOf(4.5); // double
A[2] = new Test(); // Instanz von Test
int K[] = new int[2];
K[0] = 1;
K[1] = 2;
A[3] = K; // ein Array aus int
A[4] = A; // A selber
A[5] = "Test"; // einen String
// Gib Sie wieder aus:
System.out.println(((Integer) A[0]).intValue() + 2);
System.out.println((Double) A[1]);
System.out.println((Test) A[2]);
System.out.println(((int[]) A[3])[1]);
System.out.println(((Object[]) A[4]).length);
System.out.println((String) A[5]);
}
/**
* Damit lässt sich eine Instanz von Test mit System.out.println() drucken
*/
public String toString ()
{
return "Instanz von Test";
}
}
In diesem Beispiel wird ein Array aus 6 Objekten deklariert, und wir speichern allerhand Verschiedenes in dieses Array ab, und geben es schließlich wieder aus. Man beachte, dass jedesmal das Objekt in den entsprechenden Typ umgewandelt werden muss, wenn man sicher gehen will, dass schon der Compiler weiß, dass es sich nicht einfach um ein Object handelt.
Mit dem Inhalt des Integer wollen wir rechnen. Daher verwenden wir die Methode intValue() von Integer, um den Inhalt zu erhalten. Der Inhalt des Typs Double lässt sich direkt ausgeben, weil Double über eine Methode toString() verfügt. Für unsere Klasse Test haben wir auch dementsprechend vorgesorgt, indem wir dort eine Methode toString geschrieben haben.
A[3] enthält ein (zeigt auf ein) komplettes Array. Die Typumwandlung sieht etwas seltsam aus, funktioniert so aber. Danach kann man das Array wie gewohnt indizieren. Man beachte die Klammern! Die Typumwandlung bezieht sich immer auf den ganzen Ausdruck, vor dem sie steht.
A[4] zeigt gar auf A selber. Dies ist ohne Weiteres möglich. Nachdem wir zu Object[] gewandelt haben, kann die Länge dieses Arrays bestimmt werden
Die Ausgabe dieses Programms ist nun
6 4.5 Instanz von Test 2 6 Test
Macht man übrigens beim Unwandeln des Objektes einen Fehler, indem man zum falschen Datentyp wandelt, so gibt es eine IllegalTypeCastException.
Die Klasse Vector funktioniert wie ein Array, das bei Bedarf wächst. Die Klasse ist in java.util deklariert und muss erst importiert werden.
import java.util.*;
Danach kann man einen Vektor wie folgt deklarieren
Vector v = new Vector();
Der Konstruktor akzeptiert auch eine Minimalgröße, die dafür sorgt, dass der Vector nicht gleich wieder erweitert werden muss. Was kann man nun auf dem Vektor speichern? Natürlich alle Objekte, die ja alle vom Typ Object sind, und auch Arrays. Die Methode addElement(), die zum Speichern dient, akzeptiert demgemäß auch ein Object als Parameter.
Normalerweise verwendet man Vektoren zur Speicherung homogener Daten. Dies ist aber nicht notwendigerweise so, wie das folgende Beispiel zeigt, das Daten verschiedener Typen auf einem Vektor speichert.
import java.util.*;
public class Test
{
static public void main (String args[])
{
Vector v = new Vector();
// Speichere String:
v.addElement("Test");
// Speichere Integer:
v.addElement(Integer.valueOf(2));
// Speichere Double-Array
v.addElement(new double[100]);
// Auslesen:
System.out.println((String) v.elementAt(0));
// druckt: Test
System.out.println((Integer) v.elementAt(1));
// druckt: 2
System.out.println(((double[]) v.elementAt(2)).length);
// druckt: 100
}
}
Diese Art der Vektoren von Objekten ist allerdings unsicher, da ständig eine korrekte Umwandlung in den richtigen Datentyp erforderlich ist, und erzeugt Warnungen. Wir werden weiter unten erfahren, wie man den Datentyp, der tatsächlich im Vektor gespeichert wird, spezifizieren kann.
Es gibt eine Reihe von weiteren Klassen, die Daten enthalten können. Wir führen beispielhaft die in Java implementierte Liste vor. Die Klasse LinkedList, die wir hier verwenden, ist dabei eine spezielle Implementation der allgemeinen Klasse List. Collections findet man im Paket java.util.
import java.util.*;
public class Test
{
static public void main (String args[])
{
// Aufbau der Liste:
LinkedList L = new LinkedList();
for (int i = 1; i <= 10; i++)
L.add(new Integer(i));
// Erster Durchlauf der Liste:
System.out.println("Erster Durchlauf:");
Iterator I = L.iterator();
while (I.hasNext())
{
int i = ((Integer) I.next()).intValue();
System.out.println(i);
if (i == 5)
I.remove(); // Entferne alle 5-er
}
// Zweiter Durchlauf der Liste:
System.out.println("Zweiter Durchlauf:");
I = L.iterator();
while (I.hasNext())
{
int i = ((Integer) I.next()).intValue();
System.out.println(i);
}
}
}
Der obige Code baut eine Liste der Zahlen 1 bis 10 auf, gibt die Liste wieder aus, wobei die 5 entfernt wird, und gibt die Liste ein zweites Mal aus, diesmal natürlich ohne die 5.
Zur Ausgabe verwenden wir einen Iterator, ein Interface, dass man mit der Funktion iterator() bekommt. Er funktioniert ähnlich wie eine Enumeration und hat nur drei Methoden, hasNext(), next() und remove(). Die Bedeutung der ersten beiden Methoden dürfte klar sein. remove() ist eine sichere Art, das gerade abgerufene, aktuelle Element aus der Collection zu entfernen.
Wir werden dieses Beispiel gleich noch modernisieren.
Der Nachteil von Vector und auch der eben
vorgestellten Klasse LinkedList ist, dass der Compiler nicht
sicherstellen kann, dass auch tatsächlich nur Daten vom Typ Integer
in der Liste gespeichert werden.
Dies ändert sich aber mit der Einführung von generischen Klassen. Solche Klassen sind Vorlagen für Klassen, die von einem Datentyp abhängen. Erst wenn die konkrete Instanz der Klasse angelegt wird, wird bestimmt, mit welchem Datentyp die Klasse arbeiten soll.
Als Beispiel verwenden wir die Klasse LinkedList,
die eine solche generische Klasse ist, für den Datentyp Integer.
Dazu wird der Datentyp an den Klassennamen in eckigen Klammern angehängt.
import java.util.*;
public class Test
{
static public void main (String args[])
{
// Aufbau der Liste:
LinkedList<Integer> L = new LinkedList<Integer>();
for (int i = 1; i <= 10; i++)
L.add(Integer.valueOf(i));
// Erster Durchlauf der Liste:
System.out.println("Erster Durchlauf:");
for (Integer I : L)
System.out.println(I.intValue());
L.remove(Integer.valueOf(5));
// Zweiter Durchlauf der Liste:
System.out.println("Zweiter Durchlauf:");
for (Integer I : L)
System.out.println(I.intValue());
}
}
Das sieht deutlich schlanker und sicherer aus.
add() funktioniert nun nur noch mit Objekten vom Typ
Integer.Integer.remove() auf die Liste anwenden. Zum
Vergleich wird equals() verwenden. Diese Methode haben alle
Objekte, und bei Integer werden die Werte verglichen.Übrigens kann man auch Iteratoren als generische Klassen verwenden. In unserem Beispiel sieht das so aus.
Iterator<Integer> I=L.iterator();
Der Iterator liefert dann automatisch Objekte vom Typ Integer und ein Typumwandlung ist nicht mehr notwendig. Damit hat der Compiler die Kontrolle über einen Missbrauch der Liste.
Es ist übrigens auch möglich, eine automatische Typumwandlung von Integer nach int auszunutzen.
for (int i : L) System.out.println(i);
Da die automatische Umwandlung aber ein unklares Konzept ist, rate ich persönlich davon ab. Man könnte versuchen, den Code zum Entfernen der 5-er in die Schleife aufzunehmen.
for (int i : L)
{
System.out.println(i);
if (i==5) L.remove(i); // Entferne alle 5-er
}
Das funktioniert allerdings nicht, weil remove() innerhalb der Schleife für eine Liste nicht erlaubt ist. Andererseits ist der Iterator selbst nicht zugänglich, um seine remove-Methode zu verwenden.
Wir haben damit gelernt, wie man generische Datentypen anwendet. Wie aber schreibt man eigene generische Datentypen?
Um dies zu verstehen, erzeugen wir eine Klasse Speicher, die nur ein Objekt speichern kann.
class Tier
{
String name ()
{
return "Tier";
}
}
class Affe extends Tier
{
String name ()
{
return "Affe";
}
}
class Hund extends Tier
{
String name ()
{
return "Hund";
}
}
class Speicher<Klasse extends Tier>
{
Klasse K;
void put (Klasse k)
{
K = k;
}
Klasse get ()
{
return K;
}
}
public class Test
{
static public void main (String args[])
{
Speicher<Affe> affe = new Speicher<Affe>();
affe.put(new Affe());
System.out.println(affe.get().name());
}
}
Der Name Klasse in der Klasse Speicher steht für eine beliebige Klasse. Allerdings ist spezifiziert, dass diese Klasse in der konkreten Anwendung ein Kind der Klasse Tier sein muss. Wenn nun im Hauptprogramm ein Objekt der Klasse Speicher<Affe> angelegt wird, so wird die Klasse Speicher verwendet, wobei Klasse durch Affe ersetzt wird. Im Prinzip wird also einfach eine Klasse der Form
class Speicher
{
Affe K;
void put (Affe k)
{
K = k;
}
Affe get ()
{
return K;
}
}
erzeugt. Dies ist eigentlich recht einfach zu verstehen.
Allgemeine Klassen wie LinkedList verwenden nicht extends. Die Klassen sehen etwa so aus.
public interface List <Klasse>
{
void add (Klasse x);
Iterator<Klasse> iterator();
}
public interface Iterator <Klasse>
{
Klasse next();
boolean hasNext();
}
Sie sind hier als Interface ausgeführt, was sie in der Realität auch sind. In diesem Fall kann die spezifizierte Klasse ein beliebiges Kind von Object sein.
Was kann man nun tun, wenn man Listen von unbekannten Typen an eine Funktion übergibt, etwa eine Liste von Affen, oder alternativ eine Liste von Hunden? Man verwendet in diesem Fall Wildcards. Die Konstruktion sollte mit dem folgenden Beispiel klar sein.
public class Test
{
static public void print (List<? extends Tier> k)
{
for (Tier e : k)
{
System.out.println(e.name());
}
}
static public void main (String args[])
{
List<Affe> l = new LinkedList<Affe>();
l.add(new Affe());
l.add(new Affe());
print(l);
}
}
Die generische Variante von Vector heißt ArrayList. Diese Klasse funktioniert im Prinzip genauso, ist aber typsicher. Das heißt, schon der Compiler kennt den Typ der enthaltenen Daten. In den Übungen werden wir ein Beispiel dafür konstruieren.
Hashtables sind ein Beispiel für ein fortgeschrittenes und nützliches Konzept. Sie dienen dazu, Daten anhand eines Schlüssels abzuspeichern, unter dem Sie später wieder gefunden werden können. Der Schlüssel kann ein beliebiges Objekt sein, das eine hashCode() Methode hat. Meist jedoch wird einfach ein String verwendet.
Hashtables speichern die Objekte in einem Array unten einem Index, der sich aus dem Hashcode des Schlüssels ergibt. Dabei müssen natürlich eventuelle Kollisionen aufgelöst werden, wofür es verschiedene Strategien gibt. Wie die Hashtables von Java intern funktionieren, kann man zwar im Source-Code von Java studieren, aber im Prinzip ist dies für den Benutzer nicht bekannt.
Hashtables speichern schnell und finden ihre Daten sehr schnell wieder. Darin sind sie Arrays weit überlegen. Sie sind auch sehr flexibel, was die Größe angeht, werden jedoch immer ineffektiver, je voller sie werden, weil immer mehr Kollisionen auftreten.
Folgendes Beispiel illustriert das Abpeichern und Wiederfinden von Objekten in einer Hashtable. Wir verwenden die typsichere Variante, bei der die Datentypen für Schlüssel und Wert angegeben werden muss. Generische Klassen können auch von zwei Datentypen abhängen, die dann beide angegeben werden müssen.
import java.util.*;
public class Test
{
public static void main (String args[])
{
Hashtable<String, String> H = new Hashtable<String, String>();
H.put("eins", "one");
H.put("zwei", "two");
H.put("drei", "three");
System.out.println(H.get("zwei")); // druckt: two
System.out.println(H.get("vier")); // druckt: null
}
}
Falls also ein Schlüssel nicht gefunden wird, liefert get() den Wert null.
Hashtables eignen sich also für Wörterbücher oder Eigenschaftslisten (Properties). Sie sind sowohl beim Zugriff als auch beim Abspeichern sehr effektiv.
Da Java inzwischen schon eine sehr große Anzahl von Datenstrukturen mitbringt, ist es normalerweise nicht nötig, das Rad noch einmal zu erfinden. Wer aber komplexere Strukturen selbst programmieren möchte, muss sich damit auseinandersetzen, wie man Daten im Speicher organisieren kann.
Wir geben hier zum Studium nur das Listing von sortierten Binärbäumen an. Ein Baum besteht aus Knoten, mit je zwei Kindern, die wieder Bäume sind (oder null). Der Knoten hat als Inhalt einen String. Alle Knoten im linken Kindbaum haben einen alphabetisch kleineren String als Inhalt und alle Knoten im rechten Kindbaum einen alphabetisch größeren.
Wir erzeugen einen solchen Baum, und geben die Inhalte sortiert wieder aus.
class StringNode
{
private String S;
protected StringNode Left, Right;
public StringNode(String s)
{
Left = Right = null;
S = s;
}
public void insert (String s) // Fuege s korrekt ein.
{
if (s.compareTo(S) > 0) // dann rechts
{
if (Right == null)
Right = new StringNode(s);
else
Right.insert(s);
} else // sonst links
{
if (Left == null)
Left = new StringNode(s);
else
Left.insert(s);
}
}
public String getString ()
{
return S;
}
public StringNode getLeft ()
{
return Left;
}
public StringNode getRight ()
{
return Right;
}
}
public class Test
{
public static void main (String args[])
{
StringNode tree = null;
for (int i = 0; i < 20; i++) // 20 Zusfallsstrings speichern
{
String s = "Zufallszahl " + Math.random();
if (tree == null)
tree = new StringNode(s);
else
tree.insert(s);
}
print(tree); // Sortiert wieder ausdrucken
}
public static void print (StringNode tree)
// Rekursive Druckfunktion
{
if (tree == null)
return;
print(tree.getLeft());
System.out.println(tree.getString());
print(tree.getRight());
}
}
Einige Anmerkungen
TreeSet, die genau das leistet, was
unsere Bäume können, und mehr.
Will man in Java Funktionen schreiben, die eine variable Anzahl von Argumenten übernehmen können sollen, so musste man früher ein Array verwenden, das diese Argumente enthält. Ab Java 1.5 ist das nicht mehr nötig. Wir schreiben eine Funktion, die beliebig viele Zahlen addiert.
public class Test
{
static public int add (int... I)
{
int sum = 0;
for (int i : I)
sum += i;
return sum;
}
static public void main (String args[])
{
System.out.println(add(4, 5, 3, 5));
}
}
Im Prinzip ist die variable Argumentliste ein Array und damit eine Collection. Man kann also in der Funktion auch tatsächlich auf I[0] etc. zugreifen. Wir haben hier die neue for-Schleife verwendet.
Die variable Argumentliste wird durch die drei Punkte "..." gekennzeichnet. Sie kann nur das letzte Argument der Funktion sein.
Es gibt eine nützliche Funktion, die wir bisher noch nicht besprochen haben, und die ebenfalls mit einer variablen Argumentliste arbeitet. Es ist möglich, mit der Funktion MessageFormat.format() (im Paket java.text) Variablen formatiert in Text einzubetten. Dazu übergibt man zunächst einen Formatstring und dann die Variablen in einer variablen Argumentliste.
Der Formatstring enthält Elemente der Form {variablennummer,formattyp,formatstil}, wobei die letzten beiden Angaben fehlen können. Als Formattyp ist number, date, time oder choice erlaubt. Der Formatstil hängt vom Typ ab. Für Zahlen ist insbesondere die Angabe der Stellen in der Form #.#### interessant. Für int-Zahlen verwendet man einfach integer. Die weiteren komplizierten Formatmöglichkeiten entnehme man der Dokumentation.
import java.text.MessageFormat;
import java.util.Date;
public class Test
{
static public void main (String args[])
{
System.out.println(
MessageFormat.format(
"Heute ist der {0,date}. Pi auf 10 Stellen ist {1,number,#.#########}.",
new Date(), Math.PI));
}
}
Das folgende Programm schreibt den schon beschriebenen Merge Sort für beliebige Comparable um. Interessant ist, dass man den generischen Datentyp Type verwendet, indem man im Header angibt, dass dieser Datentyp ein Comparable erweitert, und zwar eines, das mit Type vergleichen kann. Das Schlüsselwort ist hier extends.
class MergeSorter<Type extends Comparable<Type>>
{
// needed as working space
Type[] work;
public void sort (Type[] array)
{
if (array.length < 2)
return;
// easiest way to create a work area is cloning
work = array.clone();
// call recursive sort
sort(array, 0, array.length - 1);
}
void sort (Type[] array, int start, int end)
{
// System.out.println(start + "-" + end);
// half point, can be equal to start or end.
int half = (start + end) / 2;
if (half - start > 0) // need to sort first half
sort(array, start, half);
if (end - (half + 1) > 0) // need to sort second half
sort(array, half + 1, end);
// merge sorted parts
merge(array, start, half, half + 1, end);
}
void merge (Type[] array, int start1, int end1, int start2, int end2)
{
// aim index to copy into work
int aim = start1;
// remember start index, because we are changing start1
int start = start1;
// Loop breaks if one merge part is exceeded
while (true)
{
if (array[start1].compareTo(array[start2]) < 0)
{
work[aim++] = array[start1++];
if (start1 > end1) // first part is exceeded
{
while (start2 <= end2)
work[aim++] = array[start2++];
break;
}
}
else
{
work[aim++] = array[start2++];
if (start2 > end2) // second part is exceeded
{
while (start1 <= end1)
work[aim++] = array[start1++];
break;
}
}
}
System.arraycopy(work, start, array, start, aim - start);
}
}
public class Test
{
public static void main (String args[]) throws Exception
{
int N = 10000000;
String[] array = new String[N];
for (int i = 0; i < N; i++)
array[i] = "String " + Math.random();
MergeSorter<String> sorter = new MergeSorter<String>();
long time = System.currentTimeMillis();
sorter.sort(array);
// Arrays.sort(array);
System.out.println((System.currentTimeMillis() - time) + " msec");
for (int i = 0; i < N - 1; i++)
if (array[i].compareTo(array[i + 1]) > 0)
throw new Exception("Error in Sort");
}
}
Ein Problem der generischen Klassen in Java ist, dass Arrays vom generischen Typ nicht so einfach erzeugt werden können. Der folgende Weg funktioniert nicht, weil Java generische Klassen in spezieller Weise implementiert.
work = new Type[array.length];
Ein einfacher Ausweg ist, benötigte Arrays im aufrufenden Programm zu erzeugen und im Aufruf des Konstruktors oder einer Funktion zu übergeben. In unserem Fall können wir aber einfach das Argument clonen, da work die gleiche Länge haben soll wie das Array, das wir sortieren.
Eine komplexe Lösung verwendet Reflections. Dazu muss die Klasse bekannt sein, deren Array wir erzeugen wollen. Das ist hier der Fall, da wir ja ein Array dieser Klasse (String) übergeben. Da wir das Ergebnis ungeprüft auf Type[] umwandeln, wird eine Warnung erzeugt, die wir unterdrücken. Der Aufruf sieht einfach folgendermaßen aus.
@SuppressWarnings("unchecked")
public void sort (Type[] array)
{
if (array.length < 2)
return;
// reflection way to generate an array of a generic class
work = (Type[]) java.lang.reflect.Array.newInstance(array[0].getClass(),
array.length);
// call recursive sort
sort(array, 0, array.length - 1);
}
ArrayList
und schreiben Sie ein Beispiel, bei dem Sie 1000 Zufallszahlen in einer
ArrayList speichern, und dann den Mittelwert mit einer for-Schleife
berechnen. Entfernen Sie mit mit einem Iterator alle Werte
kleiner als 0.5, und geben Sie aus, wie viele Werte übrig bleiben.LinkedList mit 1000 Zufallszahlen, eine
leere ArrayList und fügen Sie alle Elemente der LinkedList
der ArrayList mit addAll() hinzu.TreeSet, und schreiben
Sie unser Beispiel für Bäume um, indem Sie diese Klasse verwenden.