Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- listen:verkettet:start [2024/09/18 08:13] – [Probleme des einfachen Ansatzes:] Martin Pabst
+++ listen:verkettet:start [2024/09/27 08:45] (aktuell) – [Problem des ersten Ansatzes:] Martin Pabst
@@ Zeile 10: / Zeile 10: @@
 <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. \\ \\
-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 |}}
-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>
@@ Zeile 70: / Zeile 82: @@
 </HTML>
-==== 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. Dabei weist **rekursiv** (lat. recurrere „zurücklaufen“) darauf hin, dass ein Kunde-Objekt wiederum ein Kunde-Objekt als Nachfolger hat.
-Zwischen den Klassen Warteschlange und Kunde bestehen zwei **Aggregationsbeziehungen**.
-</WRAP>
 ==== Aufgabe 1 ====
-Implementieren Sie die Methode ''getAnzahl()'', die die Anzahl der Kunden in der Warteschlange ausgibt.
+Implementieren Sie die Methode ''getAnzahl()'', die die Anzahl der Kunden in der Warteschlange ausgibt. Nutzen Sie dazu das Prinzip der Rekursion.
+[[.getAnzahl:start|Lösung]]
@@ Zeile 87: / Zeile 95: @@
 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!** \\ \\
 Der Kern des Problems liegt darin, dass der Code zur Modellierung der Daten (Klasse ''Kunde'') und der Code zum Verwalten der Listenstruktur vermischt sind. \\ \\
 **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. Da man bei einer Warteschlange nicht aufs n-te Element zugreifen muss, ist eine verkettete Liste dafür aber insgesamt gut geeignet.
 </WRAP>