Informatik 12/13 (G9)

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen:
listen:verkettet:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
listen:verkettet:start [2024/09/18 07:52] – [Klassendiagramm] Martin Pabstlisten:verkettet:start [2024/09/27 08:45] (aktuell) – [Problem des ersten Ansatzes:] Martin Pabst
Zeile 10: Zeile 10:
 <WRAP center round info 60%> <WRAP center round info 60%>
 Eine einfach verkettete Liste ist ein Ersatz für das Array um dessen Nachteile (Größenbeschränkung, Speicherplatzverschwendung und Aufwand beim Entnehmen) bei der Umsetzung der Warteschlange zu vermeiden. \\ \\  Eine einfach verkettete Liste ist ein Ersatz für das Array um dessen Nachteile (Größenbeschränkung, Speicherplatzverschwendung und Aufwand beim Entnehmen) bei der Umsetzung der Warteschlange zu vermeiden. \\ \\ 
-Die Idee besteht darin, die Inhaltsobjekte hintereinanderzuhängen, indem jedes Inhaltselement ein Attribut ''nachfolger'' bekommt, das auf das jeweils nächste zeigt. Im Warteschlangen-Objekt wird dann nur noch die Referenz auf das erste Inhaltsobjekt gespeichert:+  * Die Idee besteht darin, die Elemente der Liste hintereinanderzuhängen, indem jedes Element ein Attribut ''nachfolger'' bekommt, das auf das jeweils nächste zeigt.  
 +  * Im Warteschlangen-Objekt wird  
 +    * die Referenz auf das erste Element gespeichert um es auf einfache Art entnehmen zu können und 
 +    * die Referenz auf das letzte Element gespeichert um auf einfache Art weitere anhängen zu können. \\  
 +  * Beim letzten Element der Liste ist einfach ''nachfolger == null'' gesetzt. 
 + 
 +Für die Implementierung einer Warteschlange an einer Supermarktkasse sieht das Objektdiagramm beispielhaft so aus:
 {{ :listen:verkettet:objektdiagramm_einfach_verkettete_liste_einfacher_ansatz_.svg |}} {{ :listen:verkettet:objektdiagramm_einfach_verkettete_liste_einfacher_ansatz_.svg |}}
  
-Beim letzten Inhaltsobjekt der Liste ist einfach ''nachfolger == null'' gesetzt.+</WRAP>
  
 +==== Klassendiagramm ====
 +<WRAP center round info 60%>
 +{{ :listen:verkettet:klassendiagramm_einfach_verkettete_liste_einfacher_ansatz_.svg|}}
 +Es ergibt sich das rechts dargestellte Klassendiagramm. \\ \\ 
 +Die einfach verkettete Liste ist eine **rekursive** Datenstruktur, da ein Kunde-Objekt wiederum ein Kunde-Objekt als Nachfolger hat. \\ 
 +Zwischen den Klassen Warteschlange und Kunde bestehen zwei **Aggregationsbeziehungen**.
 </WRAP> </WRAP>
  
Zeile 71: Zeile 83:
  
  
-<WRAP center round important 60%> +==== Aufgabe 1 ==== 
-**Problem 1: Vermischung von Struktur und Daten** \\  +Implementieren Sie die Methode ''getAnzahl()'', die die Anzahl der Kunden in der Warteschlange ausgibt. Nutzen Sie dazu das Prinzip der Rekursion.
-Bei dieser Implementierung der Warteschlange müssen wir die Klasse ''Inhalt'' anpassen, um die Listenfunktionalität umzusetzen: Sie wird um ein zusätzliches Attribut ''nachfolger'' erweitert und bekommt mehrere Methoden zur Verwaltung der Listenstruktur (''hintenanstellenRekursiv'', ''getAnzahlRekursiv'', ...). Stell' Dir vor, Du programmierst ein Spiel und benötigst eine Liste zur Verwaltung der Spieler, eine zur Verwaltung der Gegner, eine zur Verwaltung der Hindernisse usw. Dies führt dazu, dass Du die Spieler-, Gegner- und Hindernis-Klasse jeweils um das Attribut ''nachfolger'' und die Methoden zur Verwaltung der Listenstruktur erweitern musst: **IMMER WIEDER DERSELBE PROGRAMMCODE!** \\ \\  +
-Der Kern des Problems liegt darin, dass der Code zur Modellierung der Daten (Klasse ''Inhalt'') und der Code zum Verwalten der Listenstruktur vermischt sind. [[datenstrukturen:einfachverklist:trennungstrukturdaten:start|Im nächsten Kapitel erfährst Du, wie Du im Fall der Warteschlange Struktur und Daten trennen kannst.]] \\ \\  +
-**Problem 2: Performance beim Zugriff aufs n-te Element** \\  +
-Will man auf das n-te Element einer verketteten Liste zugreifen, so muss sich das Programm - beginnend beim ersten Element - n-mal "nach vorne hangeln". Das kostet viel Zeit, denn im Mittel sind n/2 Schritte nötig. Dieser Aufwand fällt auch dann an, wenn an hinteren Ende der Liste ein neues Element eingefügt werden soll (siehe später). Letzteres ließe sich natürlich mit wenig Aufwand heilen, indem man im Warteschlangen-Objekt zusätzlich zur Referenz auf das erste Element immer auch die Referenz aufs letzte Element speichert. Da man bei einer Warteschlange nicht aufs n-te Element zugreifen muss, ist eine verkettete Liste dafür also insgesamt gut geeignet. +
-</WRAP>+
  
 +[[.getAnzahl:start|Lösung]]
  
  
-==== Klassendiagramm ==== 
-<WRAP center round info 60%> 
-Es ergibt sich folgendes Klassendiagramm: 
-{{ :listen:verkettet:klassendiagramm_einfach_verkettete_liste_einfacher_ansatz_.svg |}} 
-Die einfach verkettete Liste ist eine **rekursive** und **zusammengesetzte** Datenstruktur. Dabei weist **rekursiv** (lat. recurrere „zurücklaufen“) darauf hin, dass ein Inhalt-Objekt wiederum ein Inhalt-Objekt als Nachfolger hat. Die Datenstruktur ist zudem aus mehreren Klassen (Warteschlange, Inhalt) zusammengesetzt, zwischen denen eine Aggregationsbeziehung besteht. 
-</WRAP> 
  
-===== Umsetzung in Java ===== +===== Probleme des ersten Ansatzes: ===== 
-Sehen wir uns zunächst nur die Klassen und ihre Attribute an: +<WRAP center round important 60%> 
-<code learnj> +**Problem 1: Vermischung von Struktur und Daten** \\  
-class Inhalt {  +Bei dieser Implementierung der Warteschlange müssen wir die Klasse ''Kunde'' anpassen, um die Listenfunktionalität umzusetzen: Sie wird um ein zusätzliches Attribut ''nachfolger'' erweitert und bekommt unweigerlich auch Methoden zur Verwaltung der Listenstruktur (''getAnzahlRekursiv'', ...). Stellen Sie sich vor, Sie programmieren ein Spiel und benötigen eine Liste zur Verwaltung der Spieler, eine zur Verwaltung der Gegner, eine zur Verwaltung der Hindernisse usw. Dies führt dazu, dass Sie die Spieler-, Gegner- und Hindernis-Klasse jeweils um das Attribut ''nachfolger'' und die Methoden zur Verwaltung der Listenstruktur erweitern müssen: **IMMER WIEDER DERSELBE PROGRAMMCODE!** \\ \\  
-   private String text; +Der Kern des Problems liegt darin, dass der Code zur Modellierung der Daten (Klasse ''Kunde'') und der Code zum Verwalten der Listenstruktur vermischt sind. \\ \\ 
-   private Inhalt nachfolger;+
  
-   public Inhalt(String text) { +**Problem 2: Performance beim Zugriff aufs n-te Element** \\  
-      this.text = text; +Will man auf das n-te Element einer verketteten Liste zugreifen, so muss sich das Programm - beginnend beim ersten Element - n-mal "nach vorne hangeln". Das kostet viel Zeit, denn im Mittel sind n/2 Schritte nötig. Da man bei einer Warteschlange nicht aufs n-te Element zugreifen muss, ist eine verkettete Liste dafür aber insgesamt gut geeignet.
-   }+
  
-   public Inhalt getNachfolger() { +</WRAP>
-      return nachfolger; +
-   } +
- +
-   public void ausgabe() { +
-      println(text); +
-   } +
-   +
-} +
- +
-class Warteschlange { +
-    +
-   private Inhalt erster; +
- +
-   public Warteschlange() { +
-      erster = null; +
-   } +
-    +
-} +
- +
- +
-</code> +
- +
-Die Methode ''erstenEntnehmen'' der Warteschlange kann damit folgendermaßen umgesetzt werden: +
- +
-<code learnj> +
-public Inhalt erstenEntnehmen() { +
-    +
-  Inhalt z = erster; +
-   +
-  if(erster == null) { +
-     return erster; +
-  } +
- +
-  erster = erster.getNachfolger(); +
- +
-  return z; +
- +
-} +
-</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(){...}, [[datenstrukturen:einfachverklist:trennungstrukturdaten:start#hintenanstelleniterativ|beispielhaft implementiert im folgenden Kapitel]]) oder durch **Rekursion** (d.h. dadurch, dass eine Methode sich selbst aufruft) gelöst werden. +
- +
-==== Hintenanstellen: Rekursiv ==== +
-Die rekursive Lösung ist zweigeteilt. Der einfachste Fall (die Liste ist leer) wird direkt in der Klasse Warteschlange behandelt (es wird ''erster = inhalt'' gesetzt). Die "schwierigeren" Fälle werden von der Klasse Inhalt behandelt: Jedes Inhalts-Objekt überprüft, ob es 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**) wird das übergebene Inhalts-Objekt als Nachfolger eingesetzt. \\ \\  +
- +
-**Klasse Warteschlange:** +
-<code learnj> +
-public void hintenAnstellenRekursiv(Inhalt inhalt) { +
-   if(erster == null) { +
-      erster = inhalt; +
-   } else { +
-      erster.hintenAnstellenRekursiv(inhalt); +
-   } +
-} +
-</code> +
- +
-**Klasse Inhalt:** +
-<code learnj> +
-public void hintenAnstellenRekursiv(Inhalt inhalt) { +
-   if(nachfolger == null) { +
-      nachfolger = inhalt; +
-   } else { +
-      nachfolger.hintenAnstellenRekursiv(inhalt); +
-   } +
-} +
-</code> +
- +
-Auch die Ermittlung der Anzahl der enthaltenen Elemente kann sowohl iterativ als auch rekursiv gelöst werden. [[datenstrukturen:einfachverklist:trennungstrukturdaten:start#anzahl_der_enthaltenen_elementeiterativ|Zur iterativen Implementierung siehe das folgende Kapitel]]. +
- +
-==== 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 Inhalts-Objekt nach: +
-=== Klasse Warteschlange: === +
-<code learnj> +
-public int getAnzahlRekursiv() { +
-   if(erster == null) { +
-      return 0; +
-   } else { +
-      return erster.getAnzahlRekursiv(); +
-   } +
-} +
-</code> +
- +
-=== Klasse Inhalt: === +
-<code learnj> +
-/** +
- * Gibt die Anzahl der Elemente "links" von diesem Element +
- * zzgl. 1 zurück; +
- */ +
-public int getAnzahlRekursiv() { +
-   if(nachfolger == null) { +
-      return 1; +
-   } else { +
-      return nachfolger.getAnzahlRekursiv() + 1; +
-   } +
- +
-} +
-</code> +
- +
-===== Gesamtprogramm ===== +
-<HTML> +
- +
-<div class="java-online" style="height: 650px; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'einfachverkettet_0'}"> +
- +
-<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 Inhalt erster; +
- +
-   public Warteschlange() { +
-      erster = null; +
-   } +
-    +
-   public void hintenAnstellenRekursiv(Inhalt inhalt) { +
-      if(erster == null) { +
-         erster = inhalt; +
-      } else { +
-         erster.hintenAnstellenRekursiv(inhalt); +
-      } +
-   } +
- +
-   public Inhalt erstenEntnehmen() { +
-       +
-      Inhalt z = erster; +
- +
-      erster = erster.getNachfolger(); +
- +
-      return z; +
- +
-   } +
- +
-   public int getAnzahlRekursiv() { +
-      if(erster == null) { +
-         return 0; +
-      } else { +
-         return erster.getAnzahlRekursiv(); +
-      } +
-   } +
- +
-} +
-</script> +
- +
-<script type="text/plain" title="Inhalt.java"> +
-class Inhalt {  +
-   private String text; +
-   private Inhalt nachfolger; +
- +
-   public Inhalt(String text) { +
-      this.text = text; +
-   } +
- +
-   /** +
-    * Gibt die Anzahl der Elemente "links" von diesem Element +
-    * zzgl. 1 zurück; +
-    */ +
-   public int getAnzahlRekursiv() { +
-      if(nachfolger == null) { +
-         return 1; +
-      } else { +
-         return nachfolger.getAnzahlRekursiv() + 1; +
-      } +
- +
-   } +
- +
-   public Inhalt getNachfolger() { +
-      return nachfolger; +
-   } +
- +
-   public void hintenAnstellenRekursiv(Inhalt inhalt) { +
-      if(nachfolger == null) { +
-         nachfolger = inhalt; +
-      } else { +
-         nachfolger.hintenAnstellenRekursiv(inhalt); +
-      } +
-   } +
- +
- +
-   public void ausgabe() { +
-      println(text); +
-   } +
-} +
-</script> +
- +
- +
-</div> +
- +
-</HTML>+
  
listen/verkettet/start.1726645959.txt.gz · Zuletzt geändert: 2024/09/18 07:52 von Martin Pabst
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki