Datenstrukturen Modul 2

mit Delphi / Lazarus Schlange, Stapel und Menge

MOTIVATION

An einer besonders günstigen Tankstelle mit mehreren Zufahrten kommt es immer zu langen
Schlangen und der Frage, wer als nächster da war und wer als nächster tanken darf.

Der Pächter hat sich nun folgendes überlegt. Ein neu heranfahrendes Auto wird über das
Nummernschild gescannt und auf einer digitalen Schautafel in die Warteschlange eingereiht.
Oben steht immer das Nummernschild des Wagens, der als nächster dran ist.

Modelliere ein Klassendiagramm zur Umsetzung und nimm nur die Methoden auf, die für diese
Aufgabe dringend notwendig sind.

ÜBERSICHT

1.) Warteschlange (Queue --> FIFO-Prinzip)

Eine andere Art von Datenstruktur sind Queues (Warteschlangen).

Als Modell einer Queue kann man sich eine Warteschlange vorstellen. An einem Ende werden
neue Elemente hineingeschoben, am anderen Ende werden sie wieder entnommen.

Die Operationen einer Queue (Element hineinschieben und Element herausholen) werden put
und get genannt (oder queue und dequeue). Die Elemente stehen in der gleichen Reihenfolge,
in der sie eingefügt wurden. Eine Queue wird deshalb auch "First In, First Out"-Datenstruktur
("FIFO"-Datenstruktur) genannt.

2.) Stapel (Stack --> LIFO-Prinzip)

Das Modell eines Stacks LIFO-Prinzip ist ein Stoß von Elementen, ganz ähnlich einem Stapel
von Blättern auf einem Schreibtisch oder aufgetürmten Konferenzstühlen. Der Stack arbeitet
nach dem LIFO Prinzip: Last In, First Out.
Das Element, das zuletzt auf den Stack gelegt wurde, wird zuerst wieder vom Stack entfernt.

1
 Datenstrukturen Modul 2
mit Delphi / Lazarus Schlange, Stapel und Menge

Stacks werden sehr häufig in der Programmierung zur Realisierung von bestimmten Funktionen
eingesetzt. Die wichtigsten Operationen auf einen Stack sind push und pop.

Push bedeutet, ein Element auf einen Stack zu legen.

Pop bedeutet, das oberste Element von einem Stack zu entfernen.

3.) Mengen
Im Gegensatz zu Listen, Queues und Stacks haben Mengen

 keine bestimmte Ordnung,

 kein Gedächtnis und
 enthalten keine Elemente doppelt.

Das Modell einer Menge ist eine

beliebige Sammlung von Elementen.

Methoden der Datenstruktur Menge

 enthalten Liefert true, wenn ein Element in der Menge enthalten ist, sonst false.
 einfügen Ist das Element noch nicht in der Menge enthalten, wird es hinzugefügt.
 löschen Ist das Element in der Menge enthalten, wird es gelöscht.
 ausgeben Alle Elemente der Menge werden ausgegeben.

TRAINIEREN
Aufgabe 1
Hier siehst du ein Klassenmodell einer Warteschlange.

TForm TSchlange
Liste: TSchlange 1 1 next: TElement TElement
index: TElement
Wartender: String
next: TElement
procedure put (s : String)
function get : String

Implementiere es und programmiere die Methoden.

2
 Datenstrukturen Modul 2
mit Delphi / Lazarus Schlange, Stapel und Menge

Aufgabe 2
Browserfenster (Zurück-Button)

Entwirf ein Programm, das Internet-Adressen (String-Variablen) auf einen Stack legen und das
oberste Elemente wieder entfernen kann.
a) Modelliere dazu das Klassendiagramm.
b) Skizziere die beiden Operationen push und pop anhand eines Objektdiagramms.
c) Implementiere das Programm.

ANWENDEN

Aufgabe 1
Es soll eine Anwendung (als neues Programm) geschrieben werden, die einen Text darauf
untersucht, ob Klammern richtig geschlossen sind. Es sind die drei Klammerarten () [] {} erlaubt,
außerdem sollen verschachtelte Klammerausdrücke möglich sein.

BEISPIELE
(1) a+2*[(1+5) : 3]  
(2) 3+x*(4+y*(z-5) 
(3) [(3+2]) 
(4) „Am Anfang wurde das Universum erschaffen. Das machte viele Leute sehr wütend und wurde allenthalben als
Schritt in die falsche Richtung angesehen.“ – [aus: Das Restaurant am Ende des Universums, 1980, ISBN 3-
453-14698-0]
(Original engl.: “In the beginning the Universe was created. This has made a lot of people very angry and been
widely regarded as a bad move.”)  

a) Erkläre zunächst, warum die Beispiele 1 und 4 korrekt und die beiden anderen falsch sind.
b) Implementiere das Programm, übernimm dabei die obige Datenstruktur “Stapel“ ohne
Veränderung. Die Eingabe ist eine String-Variable. Für String-Variablen gelten folgende
Operationen:

s : String;

laenge := length(s); // liefert die Länge der Zeichenkette

a = s[i]; // liefert das i-te Zeichen in der Zeichenkette

3
 Datenstrukturen Modul 2
mit Delphi / Lazarus Schlange, Stapel und Menge

VERNETZEN

Aufgabe 1
Jede moderne Programmiersprache stellt automatisch Datenstrukturen für Stapel, Liste und
Schlange zur Verfügung. Lazarus kennt u.a.: TStringList.

http://lazarus-ccr.sourceforge.net/docs/rtl/classes/tstringlist.html

a) Liste alle Methoden (Funktionen / Prozeduren) der Datenstruktur TStringList auf, die für eine
Benutzung der Datenstruktur wichtig sein könnten.
b) Schreibe ein Testprogramm für eine Liste, das TStringList benutzt.

Aufgabe 2
Ein Internetbrowser speichert zur statistischen Auswertung die Wörter aller Suchanfragen in
einer Wortmenge. Die Häufigkeit einer Suchanfrage spielt dabei keine Rolle.
Modelliere mithilfe der Datenstruktur TStringList ein Programm, das über die Datenstruktur
„Menge“ die Suchanfragen verwaltet.

Aufgabe 3
Angenommen, Lazarus würde die erfundene Datenstruktur TList, mit den angegebenen
Operationen zur Verfügung stellen:

 procedure add (s : String); // fügt das Element s am Ende der Liste ein
 function take (i : integer): String; // gibt das i-te Element zurück, ohne es zu löschen
 procedure delete (i : integer); // entfernt das i-te Element aus der Liste
 function count : integer; // gibt die Größe der Liste an.

a) Auf der Basis von TList soll ein Stack (LIFO-Prinzip) implementiert werden. Erstelle ein
Klassendiagramm und schreibe den Lazarus-Code für push und pop auf.
b) Entwickle den Programmcode für die Funktion enthalten, die zurück liefert, ob ein
übergebenes Element im Stack enthalten ist.