• Home
• Differenzierung 8
• Differenzierung 9
• Einführungsphase
• Qualifikationsphase 1
• Qualifikationsphase 2
• Wettbewerbe

• Komponenten und Klassen
• Unified Modelling Language (UML)
• Erzeugen von Klassen durch Vererbung
• Kennt-Beziehung
• Listenstrukturen
• Das Sortierproblem
• Baumstrukturen
• Speicherbarkeit von Objekten

Listenstrukturen

Listenstrukturen sind im Unterricht bereits mehrfach vorgekommen.
1. Die einzelnen Notizen im Programm Notizzettel wurden in der Komponentenliste (TComponentList) des Formulars gespeichert.
2. Die Namen der Notizzettel wurden in einem Listenfeld (TListBox) aufgeführt (Eigenschaft Items).
3. Der Bildschirm (TScreen) enthielt eine Liste aller Fenster (Eigenschaft Forms).

Wichtige Operationen auf Listen

Ein Vergleich der wichtigsten Methoden dieser Objekte zeigt auch die wesentlichen Merkmale einer solchen Listenstruktur auf:

• Eine Liste ist eine Auflistung, eine Hintereinanderschaltung (= Sequenz) von Objekten (= Listenelemente).
• Jede Liste ist endlich, kann aber beliebig viele Elemente enthalten. Die Elemente sind durchnummeriert: Es gibt ein erstes, ein letztes, ein n-tes Listenelement.
• Der Zugriff erfolgt kontrolliert auf ein aktuelles, besonders ausgezeichnetes Element über spezielle Eigenschaften (Items, Forms) oder Methoden.

Array und Liste

Die Informatik nutzt zwei verschiedene grundlegende Strukturen, um Elemente linear im Speicher zu verwalten.
Das Array:
Die Datenstruktur Array speichert eine bestimmte Anzahl von gleichartigen bzw. gleich großen
Elementen, die im Speicher in einem Block ab einer bestimmten Speicheradresse hintereinander abgelegt werden. Die Größe eines Arrays wird beim Erzeugen des Arrayobjektes festgelegt. Ein Array besitzt deshalb in der Regel eine statische Struktur. Da die Daten fortlaufend in einem bestimmten Speicherbereich abgelegt werden, kann jedem Element eine Zahl (ein Index) zugewiesen werden. Mit diesem Index kann man gezielt (direkt)auf ein Element zugreifen.

Die Liste:
Die Datenstruktur Liste speichert eine variable Anzahl von Elementen. Im Speicher können die Elemente irgendwo stehen. Ihre Speicheradresse ist individuell, d.h. die Adresse des nachfolgenden Elementes lässt sich nicht aus der Adresse des vorhergehenden Elementes bestimmen. Deshalb sind die einzelnen Elemente miteinander über Referenzen miteinander verkettet. Die Größe einer Liste ist variabel. Zur Laufzeit kann eine Liste beliebig viele Elemente aufnehmen. Eine Liste hat eine dynamische Struktur. Auf die einzelnen Elemente kann man nur sequentiell zugreifen; ausgehend vom ersten Element muss man allen Referenzen folgen, um das gewünschte Element zu erreichen. Der Vorteil einer Liste gegenüber einem Array ist, dass das Einfügen und Löschen von Elementen an jedem Punkt in der Liste in konstanter Zeit möglich ist. Dies liegt daran, dass nur Verweise neu gesetzt werden und nicht - wie bei Arrays - alle nachfolgenden Elemente verschoben werden müssen. Die Liste verbraucht jedoch mehr Speicher, da die Verweise auf andere Listenelemente gespeichert werden.

Vergleich von Speichern, Löschen und Zugriff

Speichern:
Elemente können sortiert oder nicht sortiert abgelegt werden. Arrays oder Listen können sowohl sortiert als auch nicht sortiert sein. Um ein Element in ein Array einzufügen, benötigt man einen freien Speicherplatz. Auf die erste freie Adresse erfolgt der Eintrag des Elementes. Beim sortierten Einfügen müssen alle nachfolgenden Elemente im Speicher um eine Adresse verschoben werden. Muss das neue Element auf den ersten Platz gesetzt werden, müssen alle anderen Elemente verschoben werden. Im Durchschnitt muss bei einem sortierten Einfügen die Hälfte aller Elemente verschoben werden. Beim Einfügen eines Elements in eine Liste müssen immer Referenzen
geändert werden, weil das Element eingehängt wird. Sortiertes Einfügen ist jedoch bei einer Liste weniger aufwändig als bei einem Array. Wie beim Array muss zuerst die richtige Position gefunden werden. Doch dann werden nur Referenzen geändert, weil das Element in die Kette eingebunden wird. Kein Element wird verschoben.

Löschen:
Beim Löschen eines Elements wird ein Platz im Array frei. So entstehen freie Adressplätze. Werden dann Elemente neu eingefügt, muss man das Array sequentiell durchgehen, um einen freien Platz zu finden. Alternativ kann man nach jedem Löschen alle nachfolgenden Elemente um eine Position nach vorne verschieben. In der Liste muss das gewünschte Element sequentiell gesucht werden. Das zu gesuchte Element wird ausgekettet, und es werden nur Referenzen geändert. Kein Element muss verschoben werden

Zugriff:
Der Zugriff im Array erfolgt direkt mit dem Index auf ein Element. Die Adresse im Speicher
wird mittels des Indexes berechnet. Zugreifen auf eine Liste erfolgt immer sequentiell. Das bedeutet, dass man die Liste von Anfang an bis zum gesuchten Element durchgehen muss. Im Durchschnitt
muss die Hälfte der Elemente angesehen werden.

Vergleich Liste und Array:

Eigenschaft	Array	Liste
Größenänderung	nicht möglich	problemlos möglich
Einfügen / Löschen	langsam	schnell
Zugruff auf n-tes Element	schnell	langsam
binäre Suche	möglich	nicht möglich
Typ des Elementes	muss gleich sein	kann unterschiedlich sein

TLinList, TStack, und TQueue

EducETH stellt Unterrichtsmaterialien zu verschiedenen Fächern und Themen zu Verfügung. Der folgende Link (Lineare Liste) führt zu einer Einführung zum Thema "Lineare Listen".

Die lineare Liste (TLinList)

Vokabel

Das Programm Vokabel verwaltet eine Liste fremdsprachiger Vokabeln mit ihrer deutschen Bedeutung.

Das Bild zeigt das Programm in seiner Endfassung. Die Listbox dient zur Kontrolle des Listeninhalts. Sie ist für den eigentlichen Programmablauf nicht nötig. In einer ersten Fassung (Version 1) soll durch Anklicken des Buttons "Neue Vokabelliste" eine Liste mit einem Grundwortschatz erzeugt werden. Mit Hilfe der Navigationsfelder soll in der Liste geblättert werden. Anschließend wird diese Version erweiter um die Methoden anhängen und einfügen. Die Version 3 kann dann Vokabeln suchen und löschen. Sortieren kommt in der Version 4 hinzu, Version 5 kann dann Daten speichern und laden. Sortieren, speichern und laden werden über das Hauptprogramm realisiert.

Die Klasse TLinArray

Die Klasse TLinArray verwaltet die fremdsprachige Vokabel mit ihrer deutschen Bedeutung. Ein interner Positionszeiger markiert die aktuelle Position im Array. Innerhalb des Arrays kann geblättert werden, es können Vokabeln gelöscht, eingefügt oder angehängt werden.

TLinList = class
private
first: Integer;
last: Integer;
current: Integer;
counter: Integer;
vok: array [1..100,1..2] of string;
public
constructor create;virtual;
//Positionsangaben

//Navigation
procedure next; virtual;
procedure toFirst; virtual;
procedure toLast; virtual;
procedure previous;virtual;
//Listenoperationen
procedure getObject(var vokabel,deutsch:string); virtual;
procedure setObject; virtual;
procedure append(vokabel,deutsch:string); virtual;
procedure remove(vokabel,deutsch:string); virtual;
procedure insertBefore(vokabel,deutsch:string); virtual;
procedure insertBehind(pObject: TObject);virtual;
end;

Download für Lazarus

mListA mit der Klasse TLinArray
mDialog (wird ab Version 2 benötigt)
Vokabel Version Array

 

Die Klasse TLinList

Objekte der Klasse TLinList verwalten beliebige Objekte nach einem Listenprinzip. Ein interner Positionszeiger wird durch die Listenstruktur bewegt, seine Position markiert ein aktuelles Objekt. Die Lage des Positionszeigers kann abgefragt, verändert und die Objektinhalte an den Positionen können gelesen oder verändert werden. Die Klasse TLinList stellt Methoden in folgender Syntax zur Verfügung:

constructor create;
function isEmpty: boolean;
procedure next;
procedure toFirst;
procedure toLast;
procedure previous;
procedure append(pObject: TObject);
procedure insertBefore(pObject: TObject);
procedure insertBehind(pObject: TObject);
function getObject: TObject;
procedure setObject(pObject: TObject);
procedure remove;
destructor destroy; override;

Dokumentation der Methoden der Klasse TLinList

Konstruktor	create:
Nachher	Eine leere Liste ist angelegt. Der interne Positionszeiger steht nil.
Anfrage	isEmpty: boolean
Nachher	Die Anfrage liefert den Wert true, wenn die Liste keine Elemente enthält, sonst liefert sie den Wert false.
Auftrag	next
Nachher	Der Positionszeiger ist um eine Position in Richtung Listenende weitergerückt. Das jeweils nachfolgende Listenelement wird zum aktuellen Element. Stand der Positionszeiger auf dem letzten Listenelement, hat er sich nicht verändert.
Auftrag	previous
Nachher	Der Positionszeiger ist um eine Position in Richtung Listenanfang weitergerückt. Das jeweils vorhergehende Listenelement wird zum aktuellen Element. Stand der Positionszeiger auf dem ersten Listenelement, hat er sich nicht verändert.
Auftrag	toFirst
Nachher	Der Positionszeiger steht auf dem ersten Listenelement. Falls die Liste leer ist, hat er den Wert nil.
Auftrag	toLast
Nachher	Der Positionszeiger steht auf dem letzten Listenelement. Falls die Liste leer ist, hat er den Wert nil.
Anfrage	getObject: TObject
Nachher	Die Anfrage liefert den Wert des aktuellen Listenelements bzw. nil, wenn die Liste keine Elemente enthält.
Auftrag	setObject (pObject: TObject)
Vorher	Die Liste ist nicht leer.
Nachher	Der Wert des Listenelements an der aktuellen Position ist durch pObject ersetzt.
Auftrag	remove
Vorher	Der Positionszeiger hat nicht den Wert nil.
Nachher	Das aktuelle Listenelement ist gelöscht. Der Positionszeiger steht auf dem Element hinter dem gelöschten Element, bzw. auf dem letzen Element, wenn das gelöschte Element das letzte Listenelement war. Das Inhaltsobjekt des gelöschten Listenelements existiert weiterhin.
Destruktor	destroy
	Die Liste existiert nicht mehr

Die Elemente der linearen Liste werden vom Objekt TLinList selbst hergestellt und verwaltet. Dazu besitzt TLinList das Objekt TElement. Dieses Element besteht aus zwei Komponenten: einer Inhaltskomponente und einer Zeigerkomponente. Die Inhaltskomponente nimmt den vom Programm übergebenen Wert auf. Da sie vom Typ TObject ist, kann jedes beliebige Objekt in der Liste gespeichert werden. Die Zeigerkomponente weist auf das nächste in der Liste vorhandene Element. Jedes neu hergestellte Element erhält automatisch eine Adresse. Diese Adresse wird in dem vorherigen Element gespeichert. Damit auf den Inhalt und die Adresse eines Elementes zugegriffen werden kann, benötigt TLinList entsprechende Funktionen und Prozeduren. Die Typ-Deklaration für TElement sieht wie folgt aus:

TElement = class(TObject)
private
content: TObject;
nextElement: TElement;
constructor create(pObject: TObject);
procedure setContent(pObject: TObject);
procedure setNext(pNext: TElement);
function getContent: TObject;
function getNext: TElement;
destructor destroy;override;
end;

Wie oben schon erwähnt wurde, besitzt TLinList einen Zeiger, der auf ein Element der Liste verweist. Des weiteren benötigt TLinList zwei weitere Zeiger: einen, der auf das erste Element der Liste, und einen, der auf das letzte Element zeigt. Das erste Element kann dann auf das zweite Element zeigen, das zweite auf das dritte usw. TLinList benöigt also drei Variablen vom Typ TElement, die genau dieses können: pFirst, pLast und pCurrent. Die komplette Typ-Deklaration für TLinList sieht dann wie folgt aus:

TLinList = class(TObject)
private
pFirst, pLast, pCurrent: TElement;
public
//Konstruktoren/Destruktoren
constructor create; virtual;
destructor destroy; override;
//Positionsangaben
function isEmpty: boolean; virtual;
//Navigation
procedure next; virtual;
procedure toFirst; virtual;
procedure toLast; virtual;
procedure previous;virtual;
//Listenoperationen
function getObject: TObject; virtual;
procedure setObject(pObject: TObject); virtual;
procedure append(pObject: TObject); virtual;
procedure remove; virtual;
procedure insertBefore(pObject: TObject);virtual;
procedure insertBehind(pObject: TObject);virtual;
end;

Download für Delphi:

mListe mit den Klassen TElement und TLinList
mDialog (wird ab Version 2 benötigt)
Vokabel Version 1
Vokabel Version 2
Vokabel Version 3
Vokabel Version 4

Download für Lazarus:

mListe mit den Klassen TElement und TLinList
mDialog (wird ab Version 2 benötigt)
Vokabel Version 1
Vokabel Version 2
Vokabel Version 3
Vokabel Version 4

 

Die doppelt verkettete Liste (TDoubleList)

Im Gegensatz zur einfach-verketteten Liste hat jedes Element sowohl einen Zeiger auf das nachfolgende als auch auf das vorhergehende Element. Der Vorgänger-Zeiger des ersten und der Nachfolger-Zeiger des letzten Elementes zeigen auf den Wert nil. Diese besonderen Elemente dienen zum Auffinden des Anfangs und des Endes einer doppelt verketteten Liste. Der zusätzliche Zeiger erfordert einen höheren Speicherbedarf. Die Listen lassen sich jedoch schneller durchsuchen, Elemente sind schneller einzufügen und zu löschen. Mit den entsprechenden Algorithmen sind diese Listen auch schneller so sortieren.

Die Klasse TElement muss für den zweiten Zeiger ergänzt werden:

TElement = class(TObject)
private
content: TObject;
nextElement: TElement;
constructor create(pObject: TObject);
procedure setContent(pObject: TObject);
procedure setNext(pNext: TElement);
procedure setPrevious(pNext: TElement);
function getContent: TObject;
function getNext: TElement;
function getPrevious:TElement;
end;

Die Listenstruktur TLinList bleibt erhalten. Einige Prozeduren müssen jedoch angepasst werden.

Download für Delphi:

mDoppelt mit den Klassen TElement und TDoubleList

Download für Lazarus:

mDoppelt mit den Klassen TElement und TDoubleList

 

Der Ring (TCircle)

Der Ring ist ein Spezialfall der linearen Liste. Das letzte Element verweist auf das erste Element. Somit gibt es keine Anfangs- und Endelemente, sondern lediglich ein aktuelles Element. Ansonsten erfolgt der Datenzugriff genau wie bei der linearen Liste. Die Anzahl der vorhandenen Elemente lässt sich bei  dieser Version ermitteln.

TCircle = class(TObject)
private
pCurrent: TElement;
public
//Konstruktoren/Destruktoren
constructor create; virtual;
destructor destroy; override;
//Positionsangaben
function isEmpty: boolean; virtual;
function anzahl:integer;virtual;
//Navigation
procedure next; virtual;
procedure previous;virtual;
//Listenoperationen
function getObject: TObject; virtual;
procedure setObject(pObject: TObject); virtual;
procedure remove; virtual;
procedure insertBefore(pObject: TObject);virtual;
procedure insertBehind(pObject: TObject);virtual;
end;

Download für Delphi:

mRing mit den Klassen TElement und TCircle

Download für Lazarus:

mRing mit den Klassen TElement und TCircle

 

Der Stapel (TStack)

Keller, Stapel oder Stack: drei Bezeichnungen für den selben Sachverhalt. Den Begriff Stapel kennt man vom Kartenspiel. Man kann die oberste Karte nehmen oder eine Karte auf den Stapel legen. Überträgt man dieses Verfahren auf die Liste, dann kann das erste Listenelement gelöscht werden oder es kann ein neues Element vorne eingefügt werden. Ferner muss man wie beim Kartenspiel die gezogene Karte bzw. das erste Listenelement auswerten. Des weiteren muss man testen können, ob die Liste leer ist. In der Informatik spricht man daher auch von einer LiFo-Struktur (Last in, first out).

Eine Klasse TStack muss also einen neuen Stapel erzeugen können (TStack.Create), einen Stapel löschen können (TStack.Destroy), eine neues Element anfügen können (TStack.Push(pObject)), das oberste Element lesen können (TStackl.Top), das oberste ELement löschen können (TStack.Pop) und testen können, ob der Stapel leer ist (TStack.IsEmpty).  Es ergibt sich folgende Klassendefinition:

TStack = class (TObject)
public
constructor create;
destructor Destroy; override;
procedure Push (pObject:TObject);
procedure Pop;
function Top: TObject;
function IsEmpty: Boolean;

Rangieren

 

Taschenrechner

Download für Delphi

Rangieren
Taschenrechner
mStapel mit den Klassen TElement und TStack

Download für Lazarus

Rangieren
Taschenrechner
mStapel mit den Klassen TElement und TStack

 

Die Schlange (TQueue)

Schlange, Queue oder FiFo (First in, first out): Bei dieser Listenstruktur werden Elemente hinten angehängt und vorne weggenommen. Eine Klasse TQueue muss also eine neue Schlange erzeugen können (TQueue.Create), ein neues Element anfügen können (TQueue.Enqueue), das erste Element lesen können (TQueue.Front), das erste Element löschen können (TQueue.Dequeue) und testen können, ob die Schlange leer ist (TSchlange.IsEmpty). Es ergibt sich folgende Klassendefinition:

TQueue = class (TObject)
public
constructor create;
destructor Destroy; override;
procedure Enqueue (pObject:TObject);
procedure Dequeue;
function Front: TObject;
function IsEmpty: Boolean;

Die Waschstraße

Der Supermarkt

Download für Delphi

Waschstraße
Supermarkt
mSchlange mit den Klassen TElement und TQueue

Download für Lazarus

Waschstraße
Supermarkt
mSchlange mit den Klassen TElement und TQueue