Programmieren mit C++

Verkettete Listen werden beim Programmieren oft benötigt. Diese Art der Datenhaltung bietet sich an, wenn die maximale Anzahl der Elemente, die verwaltet werden soll, nicht im voraus festgelegt werden kann, ein sequentieller Zugriff von der Geschwindigkeit her tragbar ist und die Anzahl der Elemente stark schwankt.

Es gibt viele verschiedene Arten von verketteten Listen. Die Listen können bezüglich eines Kriteriums geordnet oder ungeordnet sein. Sie können das Einfügen an einem Ende, an beiden Enden oder an jeder beliebigen Stelle unterstützen. Diese unterschiedlichen Verhaltensweisen des Einfügens bestehen selbstverständlich auch bezüglich des Löschens. Listen können in einer oder in beiden Richtungen durchlaufen werden. Sie können gleichartige oder unterschiedliche Datentypen aufnehmen. Bei unterschiedlichen Datentypen treten Probleme auf, wenn die Liste gemäß einem Ordnungskriterium sortiert ist.

Wie können unterschiedliche Datentypen sortiert werden? Die Listen können nur Objekte verwalten, die von einer Basisklasse abgeleitet sind. In diesem Fall gibt es bezüglich der Ordnung keine Probleme, wenn eine Vergleichsfunktion in der Basisklasse implementiert ist und diese für alle abgeleiteten Klassen Anwendung finden kann.

Listenarten

Seit der Einführung von Templates in C++ kann eine Listenklasse unabhängig von den zu verwaltenden Datentypen programmiert werden. Die Objekte, die verwaltet werden sollen, müssen aber zumindest diejenigen Memberfunktionen unterstützen, die in der Template-Implementierung benötigt werden. So einfach diese Forderung auch erscheinen mag, in der Praxis ist die Realisierung doch oftmals komplizierter.

Templates

Eine Listenklasse, die sortiertes Einfügen von Strings erlaubt, benötigt eine Vergleichsfunktion für Strings. Diese Funktion ist in einer guten Stringklasse vorhanden. Verwenden Sie diese Listenklasse mit Zeigern auf Strings, so ist auch eine Vergleichsfunktion für die Zeiger auf die Strings vorhanden. Diese ist im Standardsprachvorrat von C++ enthalten. Der Compiler vergleicht die beiden Zeiger auf die Stringobjekte. Allerdings ist die Sortierung jetzt anders, als der Benutzer der Liste sich dies vorstellt. Der Benutzer wollte, daß die Strings sortiert in der Liste vorhanden sind. Die wirkliche Sortierordnung ist aber die Speicheradresse der Objekte.

Sortierung

C++ bietet aber keine sprachlichen Möglichkeiten, diese Ungereimtheiten auszuschließen. So kann der Implementierer einer Klasse nur hoffen, daß der Anwender sie so benutzt, wie er es sich vorgestellt hat. Daß das Klassendesign nicht trivial ist, zeigt allein schon die Tatsache, daß nach 10 Jahren C++ bisher nur eine IO-Streamklasse, eine Klasse für komplexe Zahlen und eine fast abgeschlossene String-Klassenbibliothek existieren. Bei allen anderen Klassen herrscht noch der Konkurrenzkampf der Anbieter. Wie immer zu Lasten des Anwenders, der seine Programme nicht portabel gestalten kann. Zum jetzigen Zeitpunkt ist eine Klassenbibliothek für viele Compiler und Plattformen auch nur eingeschränkt machbar. Noch nicht alle Compiler haben die nötigen Sprachelemente implementiert:

• Templates
• Exceptions

Klassendesign

Sicher ist eine Listenklasse auch ohne diese Sprachelemente implementierbar. Aber erst mit Templates ist die Implementierung sinnvoll. Viele Hersteller, die Listenklassen ohne Templates implementiert haben, änderten ihre Bibliotheken auf Templates ab, seit diese verfügbar sind. Der Benutzer dieser Klassen muß bei einer Umstellung auch am eigenen Programm Änderungen vornehmen, sofern der Hersteller die Versionen ohne Templates nicht mehr unterstützt.

Mehrere Compiler und Plattformen

Wieso sind erst Listenklassen mit Templates sinnvoll? Mit Templates ist eine Typprüfung durch den Compiler möglich. Früher war das nur möglich, wenn die Objekte, die in den Listen verwaltet wurden, von einer gemeinsamen Basisklasse abgeleitet waren. In der Regel benötigt man aber eine Liste, um eine Art von Datenstrukturen zu verwalten. Ein primitives Telefonbuch ist eine alphabetisch sortierte Liste von Datensätzen, die zum Beispiel aus

• Name
• Telefonnummer

Templates

bestehen. Für diese Datensätze definiert man eine Struktur. Jetzt benötigt man eine Liste für Datensätze dieses Typs. Mit Templates ist man schnell am Ziel. Die Liste in ihrer Grundform ist als Template-Klasse bereits vorhanden. Die Instanzbildung für eine Liste mit Telefonbuch-Datensätzen übernimmt der Compiler. Außer einer Deklaration dieser Liste braucht der Anwender bezüglich der Liste nichts zu programmieren.

Instanzbildung

Exceptions sind zwar nicht im gleichen Maße notwendig wie Templates, sie gestalten die Listenklasse aber anwenderfreundlicher. Beim Programmieren mit Listen treten Fehlersituationen auf, auf die das Anwenderprogramm reagieren muß. Die Listenklasse muß dem Anwenderprogramm diese Unregelmäßigkeiten mitteilen. Ohne Exceptions geht dies mit Hilfe von Fehlerstati der betreffenden Funktionen. Die Konsequenz ist, daß die Funktion kein anderes Ergebnis zurückgeben kann. Durch diese Einschränkung kann die Schnittstelle der Funktionen nicht so gestaltet werden, wie es für ein leicht lesbares Programmieren notwendig ist.

Exceptions

Die Template-Klasse für einfach verkettete Listen liegt in zwei Versionen vor. Eine Version enthält die Datenelemente selbst, die zweite Version enthält nur Zeiger auf die Datenelemente. Listen mit Zeigern auf die Datenelemente sind notwendig, wenn auf ein und denselben Datenbestand mehrere „Ansichten“ oder Teilmengen gebildet werden sollen, bei denen sich Änderungen an einem Element auf alle Teilmengen auswirken. Die Liste, die Zeiger auf die Datenelemente enthält, kann die Datenelemente optional mit delete löschen, wenn der Listeneintrag gelöscht wird.

Die beiden Listenklassen heißen

• WertEinfacheListe
• ReferenzEinfacheListe

Die Namen sind vielleicht nicht besonders schön, drücken aber aus, was die Klasse beinhaltet. Die erste Klasse enthält die Datenobjekte selbst, die zweite Klasse hingegen nur Zeiger auf die Datenobjekte.

Zwei Versionen

In der Headerdatei CONT.H sind allgemein benötigte Definitionen sowie Typ- und Klassendeklarationen für Containerklassen enthalten.

Headerdatei

Der Typ LISTINDEX ist long. Alle Listenpositionen sind vom Typ LISTINDEX. 2147483647 Listenelemente können somit theoretisch aufgenommen werden. 2 Milliarden ist wirklich nur ein theoretischer Wert, da der Arbeitsspeicher in der Regel hierfür nicht genügt. Wäre LISTINDEX vom Typ int, könnten in einer 16-Bit-Betriebssystemumgebung 32767 Elemente in der Liste untergebracht werden. Diese Anzahl kann unter Umständen als Einschränkung empfunden werden. Außerdem sollte man in diesem Fall den Datentyp short wählen, da sonst in 16- und in 32-Bit-Umgebungen unterschiedlich viele Listenelemente vorhanden sein dürfen.

Datentyp LISTENINDEX

Die Klasse xListeKeinElement ist von der Klasse xmsg abgeleitet. xmsg ist die Exception-Basisklasse und ist recht einfach gehalten. Sie enthält einen String, der die Fehlerursache bezeichnet. Beim Auslösen der Ausnahme wird dem Objekt der Fehlertext im Konstruktor übergeben. Mit der Memberfunktion why erhält man den String zurück und kann ihn ausgeben um den Anwender über den Fehler zu informieren. Die dem ANSI-Komitee zur Normung vorliegende Klasse arbeitet mit der Klasse String. Die auf der Diskette vorhandene Version arbeitet mit Zeichenketten. Die Schnittstelle ist identisch, wenn man berücksichtigt, daß die String-Klasse eine Konvertierung in Zeiger auf Zeichenketten und umgekehrt vornimmt. Wenn der zur Verfügung stehende Compiler die xmsg Klasse unterstützt, so sollte diese Klasse weggelassen werden und diejenige des Compilers Verwendung finden.

Klasse xListeKeinElement

Die Klasse xListeKeinElement ist um die Listenposition erweitert. Diese Position enthält die Stelle, an der der Fehler aufgetreten ist, der zur Ausnahme führte. Dem Konstruktor der Klasse muß neben dem Fehlertext für die xmsg-Basisklasse auch die Listenposition übergeben werden. Mit der Memberfunktion position erhält man beim Bearbeiten der Ausnahme die Stelle, an der der Fehler auftrat. Selbstverständlich ist diese Position vom Datentyp LISTINDEX. Der Fehlertext, der von der Klasse xListeKeinElement geliefert wird, ist in der Headerdatei definiert.

Listenposition

Die Klasse WELLISTENELEMENT beinhaltet die Daten und einen Zeiger auf den Nachfolger. Die beiden Datenelemente sind public definiert. Diese Klasse wird nur innerhalb der Klasse WertEinfacheListe verwendet. Dadurch kann der sinnlose Overhead vermieden werden, der beim funktionalen Abkapseln dieser Klasse entsteht. Auch diese Klasse ist eine Template-Klasse, da die Daten, die in der Liste verwaltet werden, von der Instanzbildung abhängig sind.

Klasse WELLISTENELEMENT

Die Klasse WertEinfacheListe ist die eigentliche Template-Listenklasse, die die Daten komplett enthält. Sie enthält als private Elemente die Zeiger auf das erste und das letzte Listenelement. Der Zeiger auf das erste Listenelement wird benötigt, um auf den Beginn der Liste zugreifen zu können. Da es sich um einfach verkettete Listen handelt, gehen alle Aktivitäten vom Listenbeginn aus. Der Zeiger auf das letzte Listenelement ist aus Effizienzgründen vorhanden. Beim Anfügen an die Liste kann das komplette Durchwandern der Liste, um das letzte Element zu suchen, mit diesem Zeiger verhindert werden. Die Anzahl aller in der Liste vorhanden Elemente ist auch aus Effizienzgründen vorhanden. Sie könnte auch durch das Zählen aller Listenelemente gefunden werden, was aber nicht sehr effizient für die Laufzeit ist. Da die Liste auch einen Iterator hat, ist diese Klasse als friend-Klasse deklariert. Die friend-Klasse hat Zugriff auf die privaten Elemente der Klasse.

Klasse WertEinfacheListe

Die Iteratorklasse ist vorhanden, um die Liste durchlaufen zu können. Sie stellt Funktionen für das Fortschreiten innerhalb der Liste zur Verfügung. Zu einer Liste können mehrere Iteratoren gleichzeitig deklariert werden, die unabhängig voneinander an unterschiedlichen Positionen operieren können. Wäre der Iterator Element der Klasse, so wäre dies nicht möglich, da immer nur eine aktuelle Position existieren könnte. Die Listenklasse ist für das Einfügen und Löschen (Verwalten) der Listenelemente zuständig, die Iteratorklasse für das geordnete Fortschreiten innerhalb der Listenelemente.

Iteratorklasse

Die Klasse besitzt einen Konstruktor ohne Parameter und einen Kopierkonstruktor. Der Destruktor löscht die komplette Liste. Als Operatoren sind vorhanden:

• Zuweisung
• Arrayindizierung

Memberfunktionen

Mit dem Zuweisungsoperator kann eine Liste einer anderen zugewiesen werden. Kopierkonstruktor und Zuweisungsoperator müssen bei einer Klasse vorhanden sein, die Referenzen auf andere Objekte enthält, wie dies bei der Liste der Fall ist. Der Compiler erzeugt den Kopierkonstruktor und die Zuweisung automatisch, falls diese Memberfunktionen nicht definiert sind. Da aber auch die Zeiger einfach kopiert werden, zeigen sie auf die Elemente der Ursprungsliste, was aber der Anwender sicher nicht von der Klasse erwartet.

Zuweisung

Der Arrayindex Operator ist zweimal vorhanden. Einmal liefert er als Ergebnis das Element, das andere Mal eine Referenz auf das gewünschte Element. Somit ist der Arrayindex-Operator sowohl auf der rechten als auch auf der linken Seite des Zuweisungsoperators einsetzbar.

liste[5] = 7;
wert = liste[5];

Der Compiler wählt die richtige Funktion aus. Beim oberen Statement muß er eine Referenz auf das Objekt liefern, beim unteren Statement das Objekt selbst.

Arrayindizierung

anhaengen hängt ein neues Listenelement an die Liste an.

Memberfunktion anhaengen

anzahl existiert in zwei verschiedenen Versionen. Es handelt sich also um eine überladene Funktion. Die erste Version (ohne Parameter) gibt die Anzahl der gesamten Listenelemente zurück. Die Funktion ist inline. Durch das Element AnzahlElemente der Klasse, das die Gesamtanzahl der Listenelemente beinhaltet, genügt es, diesen Wert zurückzugeben. Die zweite Version mit dem Template-Parameter gibt die Anzahl der Elemente zurück, die identisch mit dem übergebenen ist. Die Identität wird durch die Memberfunktion == der Template-Klasse festgestellt.

Memberfunktion anzahl

einfuegen fügt ein Listenelement an einer bestimmten Position in der Liste ein. Das erste Element der Liste ist das Element mit der Nummer 0. Wollen Sie mit dieser Funktion ein Element am Beginn der Liste einfügen, so brauchen Sie nur den zweiten Parameter wegzulassen, da dieser Defaultparameter mit 0 vorbelegt ist.

Memberfunktion einfuegen

Die Funktionloesche existiert in drei Varianten. Ohne Angabe von Parametern wird die gesamte Liste gelöscht. Mit einem Template-Parameter werden alle Elemente gelöscht, die dieser Vorlage entsprechen. Bei dieser Variante ist ein zweiter Parameter (dummy) vorhanden. Dieser Parameter wird benötigt, wenn die Liste für den Datentyp long instanziert wird. Die dritte Variante löscht ein Listenelement an einer bestimmten Position innerhalb der Liste. Sie benötigt einen Parameter vom Typ LISTINDEX. LISTINDEX entspricht dem Datentyp long. Wäre bei der vorherigen Funktion der dummy-Parameter nicht vorhanden, könnte der Compiler die beiden Funktionen nicht unterscheiden. Diese Vorgehensweise hat allerdings den Nachteil, daß die Löschfunktion, die gemäß einer Vorlage löscht, mit einem unnützen zweiten Parameter aufgerufen werden muß. Auch ein Defaultparameter hilft hier nicht. Dann könnte man zwar die Funktion so aufrufen, wie es sinnvoll erscheint, nur mit dem Parameter vorlage. Aber der Compiler kann die beiden Funktionen wiederum nicht unterscheiden.

Memberfunktion loesche

Die letzte Memberfunktion position gibt die Position innerhalb der Liste zurück, die ein Objekt, das dem übergebenen entspricht, innehat.

Memberfunktion position

Der Kopierkonstruktor legt eine identische Liste an. Hierzu bedient er sich eines Iterators für die Klasse WertEinfacheListe. Der Iterator durchläuft die komplette Liste, die als Parameter übergeben wird. Die Memberfunktion daten des Iterators liefert die Daten des aktuellen Elements. Die Memberfunktion anhaengen fügt die Daten an die Liste an. Nach dem kompletten Durchlauf der Quelliste liegt ein Duplikat dieser Liste vor.

Kopierkonstruktor

Der Zuweisungsoperator ist ähnlich dem Kopierkonstruktor. Auch er erstellt eine komplette Kopie der Originalliste. Vorher muß er allerdings die möglicherweise bereits vorhandene Liste löschen. Beim Kopierkonstruktor kann diese Gegebenheit nicht der Fall sein. Die aktuelle Liste ist beim Kopierkonstruktor nicht vorhanden. Um Zuweisungen wie z. B.

liste1 = list1;

gerecht zu werden, ist die Abfrage vorhanden, ob die Liste sich selbst zugewiesen werden soll. In diesem Fall unternimmt die Memberfunktion keine Aktivitäten. Diese Funktion dauert je nach Größe der Liste einige Zeit. Damit aber bei einer Zuweisung an sich selbst nicht unnütz Zeit verschwendet wird, ist diese Abprüfung vorhanden. Die Funktion gibt eine Referenz auf sich selbst zurück, womit Statements der nachfolgenden Art möglich sind.

liste1 = liste2 = liste3;

Operator =

Die beiden Arrayindexfunktionen sind bis auf die Deklaration identisch. Sie sind zwar leicht unterschiedlich programmiert, die Statements sind aber identisch. Die unterschiedliche Schreibweise soll die unterschiedliche Rückgabe verdeutlichen. Wohlgemerkt, die beiden Schreibweisen sind in der Tat identisch, den Unterschied erledigt der Compiler, indem er einmal eine Referenz und einmal die Daten selbst zurückgibt. Die Funktion löst bei einem ungültigen Listenindex eine Ausnahme mit einem xListeKeinElement-Objekt aus.

Operator []

anhaengen hängt ein Element am Ende der Liste an. Durch den Zeiger pEnde, der auf das letzte Element der Liste zeigt, ist dieser Vorgang relativ einfach zu erledigen. Vor allem wird die Zeit hierdurch nicht abhängig von der Listenlänge.

Memberfunktion anhaengen

Die Rückgabe der Anzahl aller Listenelemente, die einer Vorlage entsprechen, ist aufwendig. Dieses Problem ist nur durch einen kompletten Durchlauf der Liste zu lösen. Benötigen Sie diese Funktion sehr oft, so ist zu überlegen, ob die Daten nicht mit einer anderen Containerklasse verwaltet werden sollten, die die Suche nach bestimmten Elementen effizienter durchführen kann. Das Erkennen der Gleichheit des Elements der Liste und der Vorlage erledigt der Operator ==, der von der Template-Klasse bereitgestellt werden muß.

Anzahl der Listenelemente

Auch das Einfügen eines Listenelements an einer bestimmten Position ist eine aufwendige Angelegenheit, zumal wenn die Liste länger und die Einfügeposition nahe am Listenende ist. Auch hier hilft nur ein Durchwandern vom Beginn der Liste bis zum gewünschten Punkt. Diese Funktion kann eine Ausnahme auslösen, wenn die Listenposition nicht vorhanden ist.

Einfügen eines Listenelements

Das Löschen der gesamten Liste muß mittels eines Durchlaufs durch alle Listenelemente bewerkstelligt werden.

Löschen der gesamten Liste

Diese zweite Löschfunktion löscht nur Elemente, die einer Vorlage entsprechen. Es werden alle Elemente gelöscht, die identisch mit der Vorlage sind. Der dummy-Parameter ist notwendig, um diese und die folgende überlagerte Funktion für den Compiler unterscheidbar zu machen, wenn eine Listeninstanz für den Datentyp long gebildet wird.

Löschen bestimmter Elemente

Die letzte Löschfunktion löscht ein Listenelement an einer bestimmten Position. In diesem Fall muß die Liste nur bis zu der angegebenen Position durchlaufen werden. Ist die als Parameter übergebene Position nicht vorhanden, so löst die Funktion eine xListeKeinElement-Ausnahme aus.

Löschen an vorgegebener Position

position gibt den Listenindex eines Elements zurück, das anhand des als Vorlage übergebenen Parameters gesucht wird. Auch für diesen Vergleich der Objekte dient der Operator == den die Template-Klasse implementiert haben muß.

Memberfunktion position

Dies waren alle Funktionen der Listenklasse. Die nächste Klasse ist die Iteratorklasse WertEinfacheListeIterator. Der Namen dieser Klasse ist lang, dafür sind aber Verwechslungen nahezu ausgeschlossen.

Die Klasse verfügt über einen Zeiger auf die Liste, die aktuelle Position innerhalb der Liste, an der sich der Iterator gerade befindet, und ein Flag, ob der Iterator gültig ist. Der Iterator kann nicht bereits bei der Deklaration gültig sein. Nach der Befehlssequenz

WertEinfacheListe     liste;
WertEinfacheListeIterator  iterator(liste);

könnte man im Konstruktor das Element pElement, das auf das erste Element der Liste zeigt nicht initialisieren. Der Startzeiger der Liste ist zu diesem Augenblick NULL. Dieser Startzeiger würde aber in das Element pElement übernommen. Beim ersten Zugriff auf ein Element der Liste käme das böse Erwachen. Aus diesem Grund muß die Verbindung mit der Liste beim ersten Zugriff hergestellt werden.

Neben dem Konstruktor und dem Destruktor existieren Operatorfunktionen für das Fortschreiten zum nächsten Listenelement oder das Fortschreiten um eine Anzahl Listenelemente. Der Operator () gibt einen Zeiger auf die Daten an der aktuellen Stelle der Liste zurück. Die überladenen Funktionen daten können entweder rechts oder links des Zuweisungsoperators stehen. Sie liefern die Daten oder eine Referenz der Daten an der aktuellen Stelle zurück.

Die Funktion naechsterEintrag stellt die aktuelle Position auf das nächste Listenelement, das identisch mit dem als Parameter übergebenen ist. Die Memberfunktion gibt die aktuelle Listenposition zurück. Die Funktion ruecksetzen setzt den Iterator an den Listenbeginn zurück. Die meisten Funktionen der Klasse WertEinfacheListeIterator sind inline definiert, da sie relativ wenige Aktionen durchführen.

Iteratorklasse WertEinfacheListe

Der Konstruktor übernimmt die Initialisierung der Elemente außer dem Zeiger auf das erste Listenelement, der möglicherweise noch nicht gültig ist.

Konstruktor

Der Operator ++ bewegt den Iterator zum nächsten Listenelement.

Operator ++

Der Operator += bewegt den Iterator um die Anzahl Elemente in der Liste weiter.

Operator +=

Die Operatorfunktion () gibt einen Zeiger auf die Daten an der aktuellen Stelle zurück.

Operator ()

Die Memberfunktion naechsterEintrag sucht das nächste Element der Liste, das gleich dem übergebenen ist. Alle Memberfunktionen prüfen zuerst, ob der Iterator gültig ist. Ist dies nicht der Fall, so wird der Zeiger auf das erste Listenelement übernommen, der aktuelle Index auf das erste Element der Liste gesetzt und der Iterator als gültig markiert.

Memberfunktion naechsterEintrag

Die Klasse ReferenzEinfacheListe ist ähnlich der Klasse WertEinfacheListe. Bei dieser Listenart werden allerdings Zeiger auf die eigentlichen Daten in der Liste verwaltet.

Template-Klasse ReferenzEinfacheListe

Die Klasse RELLISTENELEMENT unterscheidet sich nur darin von der Klasse WELLISTENELEMENT, daß das Datum ein Zeiger auf die Daten darstellt. Bei der Klasse WELLISTENELEMENT sind die Daten direkt in der Klasse enthalten.

Die komplette Klassendefinition der Klasse ReferenzEinfacheListe ist sehr ähnlich der Klasse WertEinfacheListe. Bei der Klasse ReferenzEinfacheListe ist nur ein Operator [] notwendig, da der Operator, der einen Zeiger auf das Datum zurückgibt, sowohl auf der linken als auch auf der rechten Seite des Zuweisungsoperators verwendet werden kann. Bei den Memberfunktionen dieser Klasse werden Zeiger auf die Daten übergeben, die in der Liste verwaltet werden sollen. Die Implementierung ist an diese Gegebenheiten angepaßt.

Klasse RELLISTENELEMENT

Auch die Iteratorklasse ist angepaßt. Sie heißt ReferenzEinfacheListeIterator. Auch hier werden Zeiger auf die Daten statt der Daten selbst übergeben.

Iteratorklasse