14.11 Der ADT Lineare Liste
Verschiedene Definitionen des ADT Lineare Liste
Während der ADT Stack oder Queue oder auch Dictionary eindeutig definiert sind, existiert für den ADT Lineare Liste keine solche eindeutige Definition. Schaut man in der Literatur oder im Internet, so findet man für diesen ADT zum Teil völlig verschiedene Beschreibungen. Machen wir doch einfach mal eine Bestandsaufnahme.Fundstelle 1:
Der ADT Lineare ListeInit(): Erzeugt eine leere Liste. Rechts_anfuegen(x): Das neue Element x wird am Ende der Liste angefügt. Links_anfuegen(x): Das neue Element x wird am Anfang der Liste angefügt. Loeschen(): Entfernt das erste Element aus der Liste, auf das der Cursor weist. Leer(): Prüft, ob die Liste leer ist Vor(): Rückt den Cursor um eine Position nach rechts. Nach_vorne(): Setzt den Cursor auf das erste Element. Quelle: |
Fundstelle 2:
Der ADT Lineare ListeCreate(): Erzeugt eine leere Liste. Empty(): Prüft, ob die Liste leer ist EndPos(): Liefert TRUE, wenn der Positionszeiger auf das letzte Element zeigt. Top(): Liefert den Wert des Elementes, auf das der Positionszeiger zeigt. PostPos(): Setzt den Positionszeiger um eine Stelle nach rechts. PrePos(): Setzt den Positionszeiger um eine Stelle nach links. Reset(): Setzt den Positionszeiger auf das erste Element. Insert(x): Fügt das Element x vor der momentanen Position ein und stellt den Positionszeiger auf das neue Element. Delete(): Löscht das Element an der aktuellen Position und setzt den Positionszeiger auf den Nachfolger dieses Elementes. Search(x): Setzt den Positionszeiger auf das gesuchte Element und liefert TRUE zurück, falls das Element gefunden wurde. Quelle: |
Fundstelle 3:
Der ADT Lineare ListeCreate(): Erzeugt eine leere Liste. IstLeer(): Prüft, ob die Liste leer ist AmAnfang(): Prüft, ob sich der Cursor vor dem ersten Element befindet. AmEnde(): Prüft, ob sich der Cursor hinter dem letzten Element befindet. GibElemente(): Liefert die Anzahl der Listenelemente. GibPosition(): Liefert die Position des Cursors Vor(): Setzt den Cursor um eine Stelle nach rechts. Zurueck(): Setzt den Cursor um eine Stelle nach links. Gehe(p): Setzt den Cursor auf Position p Loesche(): Löscht das Cursor-Element und behält die Position bei. FuegeEin(x): Fügt an der Cursor-Position ein neues Element ein. LiesDaten(): Liefert den Wert des aktuellen Elementes. SchreibDaten(x): Ersetzt das aktuelle Element durch das Element x Vorhanden(x): Liefert TRUE, falls das Element x in der Liste vorhanden ist. Destroy(): Vernichtet die Liste komplett. Quelle: |
Fundstelle 4:
Der ADT Lineare ListeInit(): Erzeugt eine leere Liste. Einfuegen(x): Fügt das Element x am Ende oder am Anfang der Liste ein. Vorhanden(x): Gibt TRUE zurück, wenn das Element x in der Liste vorhanden ist. Entfernen(x): Entfernt das Element x aus der Liste. Ausgeben(): Gibt alle Listenelemente in der vorhandenen Reihenfolge aus. Quelle: |
Fundstelle 5:
Der ADT Lineare ListeInit(): Erzeugt eine leere Liste. Kopf(): Gibt den Listenkopf zurück. Rest(): Gibt die Restliste zurück. Einfuegen(x): Anhängen eines neuen Elementes vorn an die Liste. Laenge(): Gibt die Zahl der Elemente zurück Maplist(): Eine als Parameter übergebene Funktion wird auf jedes Element einer Liste angewendet; die Ergebnisse werden als neue Liste zurückgegeben. Quelle: |
Fundstelle 6:
Der ADT Lineare ListeInit(): Erzeugt eine leere Liste. Einfuegen(x,p): Füge Element x an Position p ein. Entferne(p): Entferne das Element, welches sich an Position p befindet. Entferne(x): Entferne das Element x, falls es in der Liste vorkommt. Lies(p): Liefere den Wert des Elementes an Position p zurück. Position(x): Suche das Element x und liefere seine Position zurück. |
Fundstelle 7:
Der ADT Lineare ListeErzeugen(): Erzeugt eine leere Liste. Einfuegen(x,p): Füge Element x an Position p ein. Entfernen(p): Entferne das Element, welches sich an Position p befindet. Suchen(x): Liefert die Position des Elementes x in der Liste zurück. Zugriff(p): Liefert den Wert des Elementes an der Position p zurück. Quelle: |
So, wir haben jetzt sieben verschiedene Fundstellen ausgewertet, und jetzt kommt die erste Aufgabe für Sie:
Übung 15.4 (100 Punkte)Geben Sie die Operationen des ADT Lineare Liste an! |
Gut, Sie sehen an der Punktzahl der Aufgabe, dass sie unmöglich zu lösen ist, daher vergessen wir die Aufgabe auch schnell wieder. Offensichtlich gibt es in der Fachliteratur bzw. im Internet keinen Konsens darüber, was man unter einer Linearen Liste zu verstehen hat. Schauen wir also in die Richtlinien des Landes NRW. Hier wird eine Lineare Liste mit den Operationen vor und zurück erwähnt, und das deutet darauf hin, dass die Autoren der Richtlinien eine Liste im Sinn hatten, die so ähnlich funktioniert wie ein urtümlicher Cassettenrecorder. Daher scheint die Definition der Fundstelle 3 noch am sinnvollsten zu sein. Man kann ja die Operationen etwas zusammenkürzen. Heraus kommt dann folgende Definition des ADT Lineare Liste, die auch Grundlage für die Übung 15.4 sein soll:
Der ADT Lineare ListeInit(): Erzeugt eine leere Liste. Leer(): Gibt TRUE zurück, wenn die Liste leer ist AmAnfang(): Gibt TRUE zurück, wen sich der Cursor am Listenanfang befindet. AmEnde(): Gibt TRUE zurück, wen sich der Cursor am Listenende befindet.. Laenge(): Liefert die Anzahl der Listenelemente. Position(): Liefert die Position des Cursors Vor(): Setzt den Cursor um eine Stelle nach rechts. Zurueck(): Setzt den Cursor um eine Stelle nach links. Gehe(p): Setzt den Cursor auf Position p Loesche(): Löscht das Element, auf das der Cursor gerade zeigt. Danach zeigt der Cursor auf das bisherige Folgeelement. FuegeEin(x): Fügt an der Cursor-Position ein neues Element ein. Anschließend zeigt der Cursor auf das neue Element. GibWert(): Liefert den Wert des aktuellen Elementes. Vorhanden(x): Liefert TRUE, falls das Element x in der Liste vorhanden ist. Quelle (modifiziert durch Helmich): |
Ergänzung August 2006
Inzwischen hat die Landesregierung NRW einen "Werkzeugkasten" mit recht netten Klassendefinitionen herausgebracht, die stark verbindlichen Charakter haben. Natürlich enthält auch dieser Werkzeugkasten eine Listen-Klasse. Die Abiturienten unter Ihnen sollten sich also auf jeden Fall diese Klassen-Definition "List" von Herrn Rüttgers ansehen.
Für Abiturienten NRW 2007/2008
zurück zu Folge 15 - Abstrakte Datentypen
Diese HTML-Seite wurde erstellt von Ulrich Helmich am 15. April 2006.