Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Trennung von Struktur und Daten ======
<WRAP center round info 80%> 
Im [[listen:verkettet:start|vorhergehenden Kapitel ]] haben Sie eine Warteschlangen-Implementierung kennengelernt, bei der der Code zur Verwaltung der Listenstruktur mit dem Code zur Verwaltung der Daten vermischt war. Wir werden jetzt Struktur und Daten sauber trennen, so dass der Code zur Verwaltung der Listenstruktur besser wiederverwendbar wird. \\ \\ 

Die Lösungsidee besteht darin, jedes Datenobjekt in ein Objekt einer **neuen Klasse ''Knoten''** zu "verpacken", das neben dem Verweis auf das Datenobjekt auch einen Verweis auf denjenigen Knoten enthält, der den Verweis auf den Nachfolger des aktuellen Inhaltsobjekts beinhaltet. **"Einfach verkettet"** ist diese Liste übrigens insofern, als die Knoten keinen Verweis auf ihre Vorgänger-Knoten beinhalten (das wäre dann eine "doppelt verkettete Liste"). \\ \\
</WRAP>

==== Beispielhaftes Objektdiagramm ====
{{ :listen:trennungstrukturdaten:objektdiagramm_einfach_verkettete_liste_trennung_struktur_-_daten_.svg?500 |}}
==== Klassendiagramm ====
{{ :listen:trennungstrukturdaten:klassendiagramm_einfach_verkettete_liste_trennung_struktur_-_daten_.svg |}} 

<WRAP center round tip 60%>
Beim Zeichnen der Klassen- und Objektdiagramme orientieren wir uns an der [[https://www.omg.org/spec/UML/2.5.1/About-UML|UML-Specification]]. Sie definiert folgende Symbole für die **Beziehungen zwischen Klassen**:
  * {{:listen:trennungstrukturdaten:aggregation.png?150|}} **Aggregation** (//aggregation//): Ein Objekt der Klasse A **enthält** Objekt(e) der Klasse B. \\ \\
  * {{:listen:trennungstrukturdaten:composite.png?150|}} **Komposition** (//composition//): Ein Objekt der Klasse A **besteht aus** Objekt(en) der Klasse B. \\ \\
  * {{:listen:trennungstrukturdaten:association.png?150|}} **Assoziation** (//association//): Objekte der Klasse A stehen auf irgendeine Art in Beziehung zu Objekten der Klasse B. Ein Verb/Nomen über der Linie zusammen mit einem Pfeil oder > bezeichnet die Beziehung näher. \\ \\
  * {{:listen:trennungstrukturdaten:inheritance.png?150|}} **Vererbung** (//inheritance//): A ist Unterklasse von B. \\ \\

[[https://www.visual-paradigm.com/guide/uml-unified-modeling-language/uml-aggregation-vs-composition/|Hier eine schöne, anschauliche Erklärung zur Unterscheidung der Beziehungsarten]].

Bei Aggregation, Komposition und Assoziation ist es oft hilfreich, die **Kardinalität** der Beziehung durch Zahlenangaben wie ''0, 1'' oder ''*'' ("0 bis unendlich") anzugeben. \\ \\ 

**Vorgehen in Prüfungen (auch Abitur):** \\ 
Der Lehrplan unterscheidet die Fälle Aggregation, Komposition und Assoziation bisher nicht in der Symbolik, auch in den Musterlösungen zum Abitur wird in allen drei Fällen nur die Symbolik der Assoziation (Linie mit Verb/Nomen dran und Pfeil für die Leserichtung) verwendet. Entsprechend dürfen auch Sie in schriftlichen Prüfungen verfahren. \\ 
**Das Symbol für Vererbung (Dreieckpfeil) wird aber sehr wohl verwendet.**
</WRAP>

===== Umsetzung in Java =====
=== Die Klasse Kunde ===
Die Klasse ''Kunde'' muss für die Speicherung in der Warteschlange überhaupt nicht mehr angepasst werden:
<code learnj>
class Kunde {
   String name;
 
   Kunde(String name) {
      this.name = name;
   }
}
</code>

Sehen wir uns bei den Klassen ''Warteschlange'' und ''Knoten'' zunächst nur ihre Attribute an:
<code learnj>
public class Warteschlange {
   Knoten anfang;
   Knoten ende;
}

public class Knoten {
   Knoten nachfolger;
   Kunde daten;

   Knoten(Kunde kunde) {
      this.daten = kunde;
   }
}
</code>

Die Klasse ''Warteschlange'' übernimmt in dieser Konstellation die "Kommunikation" mit dem Nutzer der Warteschlange. Der **Nutzer ruft weder Methoden der Klasse Knoten direkt auf noch "weiß" er von deren Existenz**. \\ \\ 
Die Warteschlange setzt damit das Prinzip der **Trennung von Struktur und Inhalt** um, d.h. bei der Verwendung der Struktur (hier: Warteschlange bzw. Liste) sind keinerlei Änderungen an der Klasse ''Kunde'' notwendig.

Damit die Warteschlange auf die Knoten geeignet zugreifen kann, benötigt die Klasse ''Knoten'' Methoden zum Holen und Setzen der Nachfolger-Referenz (sog. **Getter**- und **Setter**-Methoden):
<code learnj>
   Knoten getNachfolger() {
      return nachfolger;
   }

   void setNachfolger(Knoten nachfolger) {
      this.nachfolger = nachfolger;
   }

   Kunde getDaten() {
      return daten;
   }
</code>

Die Methode ''erstenEntnehmen'' der Warteschlange kann damit folgendermaßen umgesetzt werden:

<code learnj>
   Kunde erstenEntnehmen() {
      Knoten erster = anfang;
      anfang = erster.getNachfolger();
      return erster.getDaten();
   }
</code>

Kaum schwerer ist das Anfügen neuer Knoten am Ende der Warteschlange:
<code learnj>
   void hintenAnstellen(Kunde kunde) {
      if(anfang == null) {
         anfang = new Knoten(kunde);
         ende = anfang;
         return;
      }

      Knoten neuerKnoten = new Knoten(kunde);
      ende.setNachfolger(neuerKnoten);
      ende = neuerKnoten;

   }
</code>


Die Ermittlung der Anzahl der enthaltenen Elemente kann sowohl iterativ als auch rekursiv gelöst werden:

==== Anzahl der enthaltenen Elemente: iterativ ====
**Klasse Warteschlange:**
<code learnj>
public int getAnzahlIterativ() {
   if(anfang == null) {
      return 0;
   }
   
   int anzahl = 1;
   Knoten aktuellerKnoten = anfang;
   while(aktuellerKnoten.getNachfolger() != null) {
      aktuellerKnoten = aktuellerKnoten.getNachfolger();
      anzahl++;
   }

   return anzahl;
}
</code>

==== Anzahl der enthaltenen Elemente: rekursiv ====
Hier kümmert sich die Methode ''getAnzahlRekursiv'' der Klasse ''Warteschlange'' selbst wieder nur um den trivialen Fall (''erster == null'', also Anzahl == 0) und "fragt" im nichttrivialen Fall beim ersten Knoten nach:
**Klasse Warteschlange:**
<code learnj>
   int getAnzahlRekursiv() {
      if(anfang == null) return 0;
      return anfang.getAnzahlRekursiv();
   }
</code>

** Klasse Knoten:**
<code learnj>
   int getAnzahlRekursiv() {
      if(nachfolger == null) return 1;
      return nachfolger.getAnzahlRekursiv() + 1;
   }
</code>

==== Sequenzdiagramm am Beispiel einer Warteschlange mit drei Knoten: ====
{{ :listen:trennungstrukturdaten:sequenzdiagramm_getanzahlrekursiv.svg |}}
===== Gesamtprogramm =====
<HTML>

<div class="java-online" style="height: 650px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'einfachverkettet2'}">

<script type="text/plain" title="Hauptprogramm.java">
Warteschlange s = new Warteschlange();
s.hintenAnstellen(new Kunde("Max"));
s.hintenAnstellen(new Kunde("Tina"));
s.hintenAnstellen(new Kunde("Silke"));
s.hintenAnstellen(new Kunde("Tim"));

println(s.hatKunde("Silke"));
println(s.hatKunde("Tom"));


class Warteschlange {
   Knoten anfang;
   Knoten ende;

   void hintenAnstellen(Kunde kunde) {
      if(anfang == null) {
         anfang = new Knoten(kunde);
         ende = anfang;
         return;
      }

      Knoten neuerKnoten = new Knoten(kunde);
      ende.setNachfolger(neuerKnoten);
      ende = neuerKnoten;

   }

   Kunde erstenEntnehmen() {
      Knoten erster = anfang;
      anfang = erster.getNachfolger();
      return erster.getDaten();
   }

   int getAnzahlIterativ() {
      if(anfang == null) {
         return 0;
      }
 
      int anzahl = 1;
      Knoten aktuellerKnoten = anfang;
      while (aktuellerKnoten.getNachfolger() != null) {
         aktuellerKnoten = aktuellerKnoten.getNachfolger();
         anzahl++;
      }
 
      return anzahl;
   }


   int getAnzahlRekursiv() {
      if(anfang == null) return 0;
      return anfang.getAnzahl();
   }

   Kunde gibDenNtenKunden(int n) {
      if(n == 0) return anfang.getDaten();
      return anfang.gibDenNtenKunden(n);
   }

   boolean hatKunde(String name) {
      if(anfang == null) return false;
      return anfang.hatKunde(name);
   }

}

class Knoten {
   Knoten nachfolger;
   Kunde daten;

   Knoten(Kunde kunde) {
      this.daten = kunde;
   }

   boolean hatKunde(String name) {
      if(daten.name == name) return true;
      if(nachfolger == null) return false;
      return nachfolger.hatKunde(name);
   }

   int getAnzahl() {
      if(nachfolger == null) return 1;
      return nachfolger.getAnzahl() + 1;
   }

   Knoten getNachfolger() {
      return nachfolger;
   }

   void setNachfolger(Knoten nachfolger) {
      this.nachfolger = nachfolger;
   }

   Kunde getDaten() {
      return daten;
   }

   Kunde gibDenNtenKunden(int n) {
      if(n == 1) return daten;
      if(nachfolger != null) {
         return nachfolger.gibDenNtenKunden(n - 1);
      }

      // Fehler: n ist zu groß!
      return null;
   }
}

class Kunde {
   String name;
 
   Kunde(String name) {
      this.name = name;
   }
}</script>

</div>

</HTML>

<WRAP center round todo 60%>
**Aufgabe 1:** \\ \\ 
Erweitern Sie die Klasse Warteschlange um eine Methode ''gibDenNtenWertZurück(int n)'', die den Inhalt des n-ten Elements der Warteschlange zurückgibt. \\ \\ 
[[.ntesElementLoesung:start|Lösung]] \\ \\ 
**Aufgabe 2:** \\ \\ 
Erweitern Sie die Klasse Warteschlange um eine Methode ''letztesElementLoeschen()'', die das letzte Element der Warteschlange löscht. \\ \\ 
[[.letztesLoeschenLoesung:start|Lösung]] \\ \\ 
**Aufgabe 3:** \\ \\ 
Erweitern Sie die Klasse Warteschlange um eine Methode ''hatKunde(String name)'', die genau dann ''true'' zurückgibt, wenn sich gerade eine Kundin/ein Kunde mit dem angegebenen Namen in der Warteschlange befindet. \\ \\ 
[[.hatKunde:start|Lösung]]
</WRAP>