1. Die rekursive Datenstruktur Liste1.5 Das Entwurfsmuster Kompositum

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 1

Bei den Methoden für die Datenstruktur Liste muss die leere Liste im Allgemeinen gesondert behandelt werden. Ebenso erfordert der letzte Knoten mit dem Nachfolger null einen eigenen Fall.

Beispiel 1: int laengeGeben()

Liste Knoten

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 2

Beispiel 2: void hintenEinfuegen(Datenelement dNeu)

Liste Knoten

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 3

Um dies in Modellierung und Implementierung übersichtlicher zu gestalten, hat es sich bewährt,eine eigene Klasse Abschluss zu definieren, die keinen Nachfolger hat und kein Datenelementreferenziert, sondern nur das Ende der Liste verwaltet.

Objektdiagramm für die bisherige Modellierung

Objektdiagramm für die Modellierung mit der Klasse ABSCHLUSS

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 4

Abschluss und Knoten sind Unterklassen einer Klasse Listenelement, welche nur die gemeinsamenMethodennamen auflistet. Aus diesem Grund ist es sinnvoll, Listenelement als abstrakte Klasse zumodellieren.

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 5

Abschluss und Knoten stellen nach außen die selben Methoden zur Verfügung, die sich im Quelltext jedoch unterscheiden können.Dies bezeichnet man als Polymorphismus , ein wesentliches Charakteristikum der Objektorientierung.

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 6

Der dargestellte Teil des Klassendiagramms ist eine Umsetzung eines Entwurfsmuster (Design Pattern).Es trägt den Namen Kompositum (Composite Pattern).Entwurfsmuster spielen in der Softwareentwicklung eine sehr wichtige Rolle.In allgemeiner Form hat das Composite Pattern folgende Struktur:

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 7

Anwendungsbeispiele:

Komponente Kompositum Einzelkomponente

Oberflächenelement Window Button

Verzeichniselement Verzeichnis Datei

Listenelement Knoten Abschluss

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 8

Klassendiagramm:

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 9

Die abstrakte Klasse Listenelement:

Informatik 11 - 1. Die rekursive Datenstruktur Liste – 1.5 Das Entwurfsmuster Kompositum 10

Liste

Beispiel: int laengeGeben()

Knoten

Abschluss

Übung

Verwende als Gerüst das BlueJ-Projektliste_mit_abschlussund führe die notwendigen Änderungen durch.

Einige der nötigen Umformungen sind auf den folgenden Seiten ausführlich erläutert:

11Informatik 11 - 1. Die rekursive Datenstruktur Liste - 1.5 Das Entwurfsmuster Kompositum

12Informatik 11 - 1. Die rekursive Datenstruktur Liste - 1.5 Das Entwurfsmuster Kompositum

Klasse KnotenMethode Knoten hintenEinfuegen(Datenelement dNeu)Die Referenz von Nachfolger wird neu gesetzt durch den rekursiven Aufruf der Methode des Nachfolgers.

Rückgabewert ist die Referenz auf sich selbst.

Klasse AbschlussMethode Knoten hintenEinfuegen(Datenelement dNeu)Erzeugt einen neuen Knoten mit dem Inhalt dNeu und dem bisherigen Abschluss als Nachfolger.

Zurückgegeben wird der neue Knoten, der damit der neue Nachfolger des bisherigen letzten Knotens wird.

Klasse ListeKonstruktor Liste()Eine leere Liste besitzt den Abschluss als Anfang.

Veranschaulichung: Loesungen/.../hinten_einfuegen.pdf

13Informatik 11 - 1. Die rekursive Datenstruktur Liste - 1.5 Das Entwurfsmuster Kompositum

Klasse KnotenMethode Listenelement getNachfolger()return nachfolger

Klasse AbschlussMethode Listenelement getNachfolger()return this

Die Methode in Abschluss muss hier als Rückgabeobjekt this haben. Der Nachfolger vom Abschluss ist somit der Abschluss selbst.Würde man als Rückgabewert hier null setzen, erhält man Fehlermeldungen, wenn man die Liste ganz durchläuft, wie z.B. bei alleInformationenAusgeben() in Liste:

void alleInformationenAusgeben(){Listenelement aktuell = anfang;do{aktuell.informationAusgeben();aktuell = aktuell.getNachfolger(); //dies würde zu aktuell = aktuell.null und dann einer Fehlermeldung führen.

}while (aktuell.getInhalt()!=null);System.out.println();

}

14Informatik 11 - 1. Die rekursive Datenstruktur Liste - 1.5 Das Entwurfsmuster Kompositum

Eine trickreichere Umstrukturierung ist bei den Methoden zur Ausgabe des Inhalts des letzten Knotens notwendig:Bisher konnte man durch die Liste "wandern" und das Ende mit Hilfe der Eigenschaft finden, dass der letzte Knoten keinen Nachfolger hat. Bei der Modellierung mit Abschluss hat aber der letzte Knoten eine Referenz auf den Abschluss, der dann die Aufgabe "Ende geben" übernehmen soll.Der Abschluss benötigt dazu jedoch eine Referenz auf seinen Vorgänger, der ja die gewünschten Daten enthält.Dies realisiert man, indem die Methode getEnde() einen Rückgabewert und einen Übergabeparameter erhält.

Klasse KnotenMethode Datenelement getEnde(Datenelement d)return nachfolger.getEnde(inhalt)

Klasse AbschlussMethode Datenelement getEnde(Datenelement d)return d

In der Klasse Liste ruft man die Methode mit anfang.getEnde(null) auf. Vergleiche dazu auch im Buch S. 38 - 40 (dort heißt die Methode EndeGeben).

Veranschaulichung: getEnde.pdf

15Informatik 11 - 1. Die rekursive Datenstruktur Liste - 1.5 Das Entwurfsmuster Kompositum

Klasse ListeMethode Datenelement endeEntfernen()Bestimme zunächst mithilfe der Methode getEnde den Inhalt d des letzten Knotens.anfang = anfang.endeEntfernen(d)return d

Klasse KnotenMethode Datenelement endeEntfernen(Datenelement d)wenn (inhalt == d)dann

return nachfolgersonst

nachfolger=nachfolger.endeEntfernen(d);return this;

endewenn

Klasse AbschlussMethode Datenelement endeEntfernen(Datenelement d)return thisIn welchem Fall benötigt man den Abschluss?

Veranschaulichung: endeEntfernen.pdf

16Informatik 11 - 1. Die rekursive Datenstruktur Liste - 1.5 Das Entwurfsmuster Kompositum

Klasse ListeMethode void alleInformationenAusgeben()Das aktuelle Listenelement ist zunächst der Anfang.Solange der Inhalt dieses Elements nicht null ist, wird die Methode informationAusgeben() aufgerufen und der Nachfolger als aktuelles Listenelement gespeichert.Die Schleife muss mindestens einmal durchlaufen werden.