Show description

Sie ist auf der Elementbeziehung 2 als einzigem Grundbegriff aufgebaut. Dementsprechend könnte man sich einen abstrakten Datentyp Menge gegeben denken durch den Bereich aller Mengen im mathematischen Sinne, zusammen mit einer einzigen, zweistelligen Relation in: x in S ist wahr genau dann, wenn x ein Element der Menge S ist. Das Komprehensionsschema als Operation zur Bildung von Mengen ist als Operation eines abstrakten Datentyps zu allgemein; die Elementbeziehung als einzige zugelassene Operation ist in vielen Fällen nicht ausreichend.

Wir geben eine genauere Formulierung dieses Verfahrens an, ohne daß wir dabei auf eine spezielle Implementation von Stapeln zurückgreifen wollen. Daher nehmen wir an, daß wir einen Stapel als Liste des gewünschten Grundtyps wie folgt vereinbart haben. 5 Lineare Listen 37 Ein solcher Stapel, der nur gleiche Elemente speichert, kann natürlich auch einfach durch einen Zähler modelliert werden, der die Anzahl der Elemente auf dem Stapel angibt. Wir haben dieses Beispiel gewählt, weil man auf ähnliche Art auch das Erkennen und Auswerten arithmetischer Ausdrücke erledigen kann.

Wir haben hier, wie auch im Falle der anderen Listenoperationen, besonders darauf achten müssen, den next-Zeiger des Dummy-Elementes am Listenende auf den vorangehenden Knoten zeigen zu lassen. Das macht es möglich, das Hintereinanderhängen (Verketten) zweier Listen in konstanter Schrittzahl auszuführen. 5 Lineare Listen 31 Um das Einfügen und Entfernen von Listenelementen bei gegebener Position möglichst einfach ausführen zu können, kann man zu jedem Listenelement nicht nur einen Zeiger auf das nächstfolgende, sondern auch auf das jeweils vorangehende Listenelement abspeichern.