Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- listen:trennungstrukturdaten:start [2024/09/19 07:15] – Martin Pabst
+++ listen:trennungstrukturdaten:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== 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 |}}
-===== Umsetzung in Java =====
-=== Die Klasse Inhalt ===
-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 {
-    private Knoten erster;
-}
-public class Knoten {
-    private Knoten nachfolger;
-    private Inhalt inhalt;
-    public Knoten(Inhalt inhalt){
-       this.inhalt = inhalt;
-    }
-}
-</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>
-Schwieriger gestaltet sich das Einfügen des letzten Knotens, da das Warteschlangen-Objekt ja nur die Referenz auf den ersten Knoten speichert und man sich von diesem ausgehend zum letzten Knoten "durchhangeln" muss. Dies kann man entweder durch eine **Iteration** (d.h. unter Nutzung einer Wiederholung, z.B. for(){...}) oder durch **Rekursion** (d.h. dadurch, dass eine Methode sich selbst aufruft) gelöst werden.
-==== Hintenanstellen: Iterativ ====
-Die iterative Lösung "bewegt" sich durch die Warteschlange/Liste, bis ein Knoten ohne Nachfolger (d.h. die o.g. Methode hat den Rückgabewert ''null'') gefunden wird:
-<code learnj>
-public void hintenAnstellenIterativ(Inhalt inhalt) {
-    if(erster == null) {
-        erster = new Knoten(inhalt);
-    } else {
-        Knoten aktuellerKnoten = erster;
-        while(aktuellerKnoten.getNachfolger() != null) {
-            aktuellerKnoten = aktuellerKnoten.getNachfolger();
-        }
-        aktuellerKnoten.setNachfolger(new Knoten(inhalt));
-    }
-}
-</code>
-==== Hintenanstellen: Rekursiv ====
-Die rekursive Lösung ist zweigeteilt. Der einfachste Fall (die Liste ist leer) wird direkt in der Klasse Warteschlange behandelt (es wird ein neuer Knoten erzeugt und als erster Knoten eingesetzt). Die "schwierigeren" Fälle werden von der Klasse Knoten behandelt: Jeder Knoten überprüft, ob er einen Nachfolger hat. Im positiven Fall wird das einzufügende Element an diesen übergeben (durch Aufruf derselben Methode – daher wird diese Lösungsstrategie als rekursiv bezeichnet). Anderenfalls (genannt **Abbruchbedingung**) erzeugt der Knoten selbst einen neuen Knoten mit dem übergebenen Inhaltselement und setzt diesen als neuen Nachfolger ein. \\ \\
-**Klasse Warteschlange:**
-<code learnj>
-public void hintenAnstellenRekursiv(Inhalt inhalt) {
-    if(erster == null) {
-        erster = new Knoten(inhalt);
-    } else {
-        erster.hintenAnstellenRekursiv(inhalt);
-    }
-}
-</code>
-**Klasse Knoten:**
-<code learnj>
-public void hintenAnstellenRekursiv(Inhalt inhalt) {
-    if(nachfolger == null) {
-        nachfolger = new Knoten(inhalt);
-    } else {
-        nachfolger.hintenAnstellenRekursiv(inhalt);
-    }
-}
-</code>
-Auch 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(erster == null) {
-      return 0;
-   }
-   int anzahl = 1;
-   Knoten aktuellerKnoten = erster;
-   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>
-public int getAnzahlRekursiv() {
-   if(nachfolger == null) {
-      return 1;
-   }
-   return nachfolger.getAnzahlRekursiv() + 1;
-}
-</code>
-==== Sequenzdiagramm am Beispiel einer Warteschlange mit drei Knoten: ====
-{{ :datenstrukturen:einfachverklist:trennungstrukturdaten:pasted:20221010-112128.png?500 }}
-===== Gesamtprogramm =====
-<HTML>
-<div class="java-online" style="height: 650px; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'einfachverkettet1'}">
-<script type="text/plain" title="Hauptprogramm.java">
-Warteschlange w = new Warteschlange();
-w.hintenAnstellenRekursiv(new Inhalt("Inhalt 1"));
-w.hintenAnstellenRekursiv(new Inhalt("Inhalt 2"));
-w.hintenAnstellenRekursiv(new Inhalt("Inhalt 3"));
-println("Anzahl der Elemente: " + w.getAnzahlRekursiv());
-Inhalt inhalt = w.erstenEntnehmen();
-inhalt.ausgabe();
-inhalt = w.erstenEntnehmen();
-inhalt.ausgabe();
-</script>
-<script type="text/plain" title="Warteschlange.java">
-class Warteschlange {
-   private Knoten erster;
-   public void hintenAnstellenIterativ(Inhalt i) {
-      if(erster == null) {
-         erster = new Knoten(i);
-      } else {
-         Knoten aktuellerKnoten = erster;
-         while(aktuellerKnoten.getNachfolger() != null) {
-            aktuellerKnoten = aktuellerKnoten.getNachfolger();
-         }
-         aktuellerKnoten.setNachfolger(new Knoten(i));
-      }
-   }
-   public void hintenAnstellenRekursiv(Inhalt i) {
-      if(erster == null) {
-         erster = new Knoten(i);
-      } else {
-         erster.hintenAnstellenRekursiv(i);
-      }
-   }
-   public int getAnzahlIterativ() {
-      if(erster == null) {
-         return 0;
-      }
-      int anzahl = 1;
-      Knoten aktuellerKnoten = erster;
-      while(aktuellerKnoten.getNachfolger() != null) {
-         aktuellerKnoten = aktuellerKnoten.getNachfolger();
-         anzahl++;
-      }
-      return anzahl;
-   }
-   public int getAnzahlRekursiv() {
-      if(erster == null) {
-         return 0;
-      }
-      return erster.getAnzahlRekursiv();
-   }
-   public Inhalt erstenEntnehmen() {
-      if(erster == null) {
-         return null;
-      }
-      Inhalt inhalt = erster.getInhalt();
-      erster = erster.getNachfolger();
-      return inhalt;
-   }
-}
-</script>
-<script type="text/plain" title="Knoten.java">
-class Knoten {
-   private Knoten nachfolger;
-   private Inhalt inhalt;
-   public Knoten(Inhalt inhalt) {
-      this.inhalt = inhalt;
-   }
-   public Inhalt getInhalt() {
-      return inhalt;
-   }
-   public Knoten getNachfolger() {
-      return nachfolger;
-   }
-   public void setNachfolger(Knoten nachfolger) {
-      this.nachfolger = nachfolger;
-   }
-   public void hintenAnstellenRekursiv(Inhalt i) {
-      if(nachfolger == null) {
-         nachfolger = new Knoten(i);
-      } else {
-         nachfolger.hintenAnstellenRekursiv(i);
-      }
-   }
-   public int getAnzahlRekursiv() {
-      if(nachfolger == null) {
-         return 1;
-      }
-      return nachfolger.getAnzahlRekursiv() + 1;
-   }
-}
-</script>
-<script type="text/plain" title="Inhalt.java">
-// Dies ist nur eine beispielhafte Inhalt-Klasse. Ihre Attribute und Methoden sind nicht relevant
-// für das Funktionieren der einfach-verketteten Liste, d.h. Struktur und Inhalt sind sauber getrennt!
-class Inhalt {
-   private String text;
-   public Inhalt(String text) {
-      this.text = text;
-   }
-   public void ausgabe() {
-      println(text);
-   }
-}
-</script>
-</div>
-</HTML>
-<WRAP center round todo 60%>
-**Aufgabe 1:** \\ \\
-Erweitere 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:** \\ \\
-Erweitere die Klasse Warteschlange um eine Methode ''letztesElementLoeschen()'', die das letzte Element der Warteschlange löscht. \\ \\
-[[.letztesLoeschenLoesung:start|Lösung]]
-</WRAP>