Java: Klasse als Datenstruktur
Willemers Informatik-Ecke
Programme modellieren die Welt. Je nach Zweck des Programms werden bestimmte Aspekte der Objekte dieser Welt nachgebildet. Die Objekte lassen sich modellieren, indem einfache Datentypen zu komplexeren zusammengestellt werden. Um einen Mensch, ein Auto oder ein Datum zu modellieren, wird eine Klasse definiert.

Die Klasse dient der Blaupause zu Objekten. Mein Auto in der Garage ist eine Instanz der Klasse Auto. Das meines Nachbarn ist eine weitere Instanz.

Java baut einen R4

Beispiel:

public class Autoquartett {
    
    static class Auto {
        String marke = "", modell = "";
        int ps = 0, hubraum = 0, baujahr = 0;
        double preis = 0.0, verbrauch = 0.0;
    }
    
    public static void main(String[] args) {
        Auto r4 = new Auto();
        r4.marke = "Renault";
        r4.modell = "R4 GTL";
        r4.ps = 34;
        r4.verbrauch = 6.5;
    }
}
Klassen bekommen unter Java in der Regel eine eigene Datei. Unter Eclipse werden sie über das Menü mit File|New|Class erzeugt.

Man kann innerhalb einer Klasse eine lokale Klasse verwenden. Werden sie aus der Methode main verwendet, müssen sie als static definiert sein.

Kombination von Objekten und Arrays

Arrays können auch Objekte aufnehmen. Um genau zu sein, nehmen sie Referenzen auf Objekte auf.

Das folgende Beispiel stellt den Ausschnitt aus einem Spiel dar. Darin spielt eine Flotte von vier Schiffen eine Rolle, die in einem Spielfeld der Größe 9x7 versteckt werden.

Für die Schiffe wird eine Klasse angelegt. Die Attribute jedes Schiffes besteht aus einer X- und eine Y-Koordinate im Spielfeld, das hier per Zufall festgelegt wird.

public class Schiffe {
    static final int SCHIFFANZAHL = 4;
    static class Schiff {
        int x = 0;
        int y = 0;
    }
    public static void main(String[] args) {
        java.util.Random zufall = new java.util.Random();
        Schiff[] flotte = new Schiff[SCHIFFANZAHL];
        for (int i=0; i<SCHIFFANZAHL; i++) {
            flotte[i] = new Schiff();
            flotte[i].x = zufall.nextInt(9);
            flotte[i].y = zufall.nextInt(7);
            // Doppelte Positionen verhindern...
        }
    }
}
Beachten Sie, dass sowohl für das Array als auch für jedes Schiff ein Befehl new aufgerufen werden muss.

Klassenreferenzen für Methoden

Klassenobjekte können als Parameter an Methoden übergeben und als Rückgabewert zurückgeliefert werden.

Rückgabe einer Referenz

Besonders interessant ist die Rückgabe eines Objekts, weil eine Methode ja nur einen Wert zurückgeben kann. Im Beispiel wird die X- und die Y-Koordinate zurückgegeben. Das ist kein Problem, weil sich beide in einem Objekt der Klasse Koordinate befinden.
static public Koordinate eingabe() {
        Koordinate koord = new Koordinate();
        // Benutzereingabe
        koord.x = x;
        koord.y = y;
        return koord;        
    }
Zunächst wird ein Objekt der Klasse Koordinate erzeugt und dessen Referenz in der lokalen Variable koord gespeichert. Anschließend werden die Werte gefüllt. Mit return wird die Referenz an den Aufrufer zurückgegeben. Das per new erzeugte Objekt stirbt nicht bei Methodenende, sondern erst dann, wenn es keine Referenz mehr darauf gibt.

Referenz als Parameter

Eine Methode kann Klassenobjekte als Parameter entgegen nehmen. Dabei wird die Referenz des Objekts übergeben. Als Beispiel dient die Methode setzeSchiff, die ein Objekt der Klasse Schiff als Parameter entgegennimmt.
    static public void setzeSchiff(Schiff schiff) {
        java.util.Random zufall = new java.util.Random();
        schiff.x = zufall.nextInt(9);
        schiff.y = zufall.nextInt(7);
    }
Der Aufrufer übergibt eine Referenz auf ein Objekt. Diese Referenz wird in die Variable schiff kopiert. Damit verweist die lokale Referenz schiff auf dasselbe Objekt wie die Referenz des Aufrufers. Die Konsequenz ist, dass die Änderungen an dem Objekt, auf das schiff verweist, die Daten des Aufrufers verändert. Darum kann der Aufrufer hier ein Schiff übergeben, das innerhalb der Methode auf eine neue Position gesetzt wird.

Verschachtelte Klassen

Ein Objekt kann andere Objekte enthalten. So kann ein Auto ein Datum als Erstzulassung haben. Dieses Datum besteht seinerseits aus Tag, Monat und Jahr.
    static class Datum {
        int tag=0, monat=0, jahr=0;
    }
    static class Auto {
        String marke = "", modell = "";
        int ps = 0, hubraum = 0, baujahr = 0;
        double preis = 0.0, verbrauch = 0.0;
        Datum erstzulassung = new Datum();
    }
Das Attribut erstzulassung ist eine Referenz mit allen Konsequenzen. Vor allem muss die Variable initialisiert werden. Das kann wie oben zu sehen, direkt in der Klasse erfolgen.

Selbstreferenz: Rekursive Datentypen

Wenn eine Klasse eine Referenz auf sich selbst besitzt, verweist dies in der Regel auf ein anderes Objekt derselben Klasse. Auf diese Weise lässt sich eine verkettete Liste bauen.

Im folgenden Beispiel ist es eine Liste, die als Daten einen String mit einem Namen enthält. Das Hauptprogramm füllt diese Liste aus einem Array, das mit Namen vorbesetzt ist.

Der Anfang der Liste, den man auch als Anker bezeichnet, ist über die Variable liste greifbar. Ist liste==null, gibt es kein Element. Ansonsten greift man über liste.next auf das nächste Element zu. Damit man den Anfang der Liste nicht verliert, verwendet man üblicherweise eine weitere Referenz zum Laufen durch die Liste. Diese Variable heißt im Listing lauf.

public class MeineListe {

    static class Liste {
        String name;
        Liste next = null;
    }
    public static void main(String[] args) {
        Liste liste = null;
        String[] clowns = { "August", "Arnold", "Willemer" };
        for (String clown : clowns) {
            Liste alt = liste;
            liste = new Liste();
            liste.name = clown;
            liste.next = alt;
        }
        Liste lauf = liste;
        while (lauf!=null) {
            System.out.println(lauf.name);
            lauf = lauf.next;
        }
    }
}
Der Vorteil einer verketteten Liste gegenüber einem Array ist die Möglichkeit, die Liste bei Bedarf dynamisch zu verlängern. Auch das Einfügen oder Löschen von Elementen in der Mitte ist bei einer verketteten Liste wesentlich effizienter als bei einem Array.

Dagegen ist der direkte Zugriff auf das Element an der x-ten Position im Array deutlich schneller, weil man sich in einer verketteten Liste von Element zu Element durchhangeln muss.

Bäume haben mindestens zwei Selbstreferenzen

Wenn eine Klasse zwei Referenzen auf die eigene Klasse besitzt, liegt der Verdacht nahe, dass es sich um einen Baum handelt. Eine typische Anwendung eines solchen Baums ist das sortierte Ablegen von Daten.

Sie kennen vieleicht das Kinderspiel, in dem sich ein Kind eine Zahl ausdenkt, die das andere Kind raten muss. Als Hilfestellung verrät das erste Kind, ob die gedachte Zahl größer oder kleiner als die geratene Zahl ist. Besonders effizient findet das ratende Kind die Zahl, indem es den Zahlenraum halbiert. So kann es nach 10 Versuchen eine Zahl zwischen 1 und 1000 finden.

Beim Baum legt man die Werte gleich entsprechend ab. Hier die Definition der Klasse:

static class Baum {
        int wert = 0;
        Baum kleiner = null;
        Baum groesser = null;
    }

Auslesen eines Sortierbaums

Es ist schwierig, einen kompletten Baum sortiert mit Schleifen auszugeben. Solange es ein kleineres Element gibt, verzweigen Sie immer zum kleineren Ast ab. Ist die unterste Variable ausgegeben, müssen Sie eine Stufe zurück, dort den größeren Ast nehmen und dann wieder möglichst tief über den kleineren Ast hinunter ... Das wollen Sie nicht programmieren!

Stattdessen verwenden Sie eine knackig kurze Rekursion. Sie tut genau das oben beschriebene und das auf wenigen Zeilen.

static void ausgeben(Baum baum) {
    if (baum != null) {
        ausgeben(baum.kleiner);
        System.out.print(" " + baum.wert);
        ausgeben(baum.groesser);
    }
}

Einfügen in Sortierbaum

Etwas mehr Aufwand müssen Sie beim Einfügen in den Sortierbaum treiben. Aber auch hier ist die Lösung rekursiv. Die Vorraussetzung für das Funktionieren der Methode einsortieren ist, dass die Variable baum ungleich null ist.
static void einsortieren(Baum baum, int zahl) {
    if (baum.wert > zahl) {
        if (baum.kleiner != null) {
            einsortieren(baum.kleiner, zahl);
        } else {
            baum.kleiner = new Baum();
            baum.kleiner.wert = zahl;
        }
    } else {
        if (baum.groesser != null) {
            einsortieren(baum.groesser, zahl);
        } else {
            baum.groesser = new Baum();
            baum.groesser.wert = zahl;
        }
    }
}