Dynamische Strukturen

Willemers Informatik-Ecke

Diese Seite basiert auf Inhalten aus meinem Buch "Einstieg in C++", seinerzeit erschienen im Verlag Galileo Computing. Das Buch ist inzwischen vergriffen.


Das Nachfolgebuch heißt C++. Der Einstieg und ist bei Wrox im Verlag Wiley-VCH erschienen.

Die Inhalte dieser Website unterliegen meinem Urheberrecht und dürfen trotz inhaltlicher Überschneidungen mit dem Buch dank der freundlichen Genehmigung des Verlags Wiley-VCH hier erscheinen.

Normalerweise legen Sie beim Erstellen des Programms die Variablen fest, die im Programm verwendet werden. Dazu müssen Sie bereits vor dem Erstellen des Programms festlegen, welche Daten sie brauchen. Nehmen wir an, Sie wollen in Ihrem Programm eine Einkaufsliste führen. Dazu können Sie ein Array von Einkaufslisteneinträgen anlegen. Aber wieviele Einträge sollen es maximal werden? Egal welchen Wert Sie wählen: Er ist zu klein, wenn Sie der Kaufrausch packt und zu groß, wenn Sie nur noch einmal schnell Eier und Speck für ein improvisiertes Mittagessen brauchen. Für solche Fälle bietet C++ die Möglichkeit, während des Programmlaufs Speicher anzufordern, der dann über Zeiger zugegriffen wird.

Anlegen und Freigeben von Speicher

new

Der Befehl new fordert neuen Speicher an. Um ihn zugreifen zu können, liefert new einen Zeiger darauf zurück. Damit new weiß, wie viel Speicher angefordert werden soll, folgt dem Befehl der gewünschte Datentyp.

float *floatZeiger = new float;

Anfordern

Dieser Speicher wird aus dem Arbeitsspeicher des Programms genommen, dem so genannten Heap. Die einzige Verbindung, die das Programm zu dem Speicher hat, ist der Zeiger. Das Programm ist für diesen Speicher verantwortlich. Das bedeutet, dass der Speicher so lange über einen Zeiger erreichbar sein muss, wie er gebraucht wird, und dass er nach Gebrauch durch den Befehl delete wieder frei gegeben werden muss.

Initialisierung

Der neu angeforderte Speicher kann gleich initialisiert werden. Dazu wird der Initialisierungswert in Klammern hinter dem Typ angegeben.

int *intZeiger = new int(2);  // Initialisierung
Die Variable, auf die intZeiger zeigt, wird gleich nach ihrer Erzeugung mit dem Wert 2 belegt.

Speicherlecks

Der angeforderte Speicher muss irgendwann wieder freigegeben werden. Insbesondere, wenn über den Zeiger neuen Speicher angefordert wird, bevor der alte freigegeben wurde, irren Speicherreste durch den Hauptspeicher, auf die nicht mehr zugegriffen werden kann. Da dies durchaus mit einem Auto vergleichbar ist, das Öl verliert, spricht man von einem Speicherleck (memory leak). Wie beim Ölverlust scheint der Speicherverlust in gewissen Maßen nicht tragisch und macht sich vielleicht höchstens an einem geringen Geschwindigkeitsverlust bemerkbar. Kritisch wird es erst, wenn der verbleibende Speicherrest unter ein gewisses Niveau sinkt. Dann kommt es zu dramatischen Geschwindigkeitseinbrüchen oder gar zum Programmabsturz. Aus diesem Grund sollten Sie darauf achten, dass jeder angeforderte Speicher auch wieder freigegeben wird. Dazu dient der Befehl delete. Dem Befehl folgt der Zeiger, der auf den freizugebenden Speicher weist:

delete floatZeiger;

Freigabe

Der Zeiger muss nicht der sein, mit dem der Speicher angefordert wurde. Er muss lediglich auf den richtigen Speicher zeigen und vom gleichen Typ sein. Nach der Speicherfreigabe durch delete empfiehlt es sich, die Zeigervariable auf 0 zu setzen. Damit wird verhindert, dass an einer anderen Stelle versehentlich eine weitere Freigabe erfolgt. delete erkennt, wenn die Zeigervariable 0 ist, und versucht dann erst gar nicht, dessen Speicher freizugeben. Fast noch wichtiger ist aber, dass eine weitere Verwendung dieses Zeigers zum Auslesen oder Beschreiben des Speichers sofort zu einem Fehler führt und damit auffindbar wird. Nach der Freigabe weist der Zeiger schließlich auf einen Speicherbereich, der nicht mehr gültig ist. Es kann sein, dass der Speicher später wieder vergeben wird. Wird der Zeiger nicht auf 0 gesetzt und arbeitet das Programm wieder mit diesem ungültigen Zeiger, wird Speicher verwendet, der vielleicht von anderen Programmteilen angefordert wurde. Da das Programm aber weiterläuft, als wäre alles in Ordnung, würde dieser Fehler nie gefunden.

Zur Laufzeit erzeugte Arrays

Mit Hilfe des Befehls new können auch Arrays dynamisch angefordert werden. Das Besondere daran ist, dass Sie die Größe des Arrays als Parameter angeben. In einigen Fällen kann das Programm erst nach dem Start wissen, wie groß das Array sein muss. Durch dynamisches Anfordern wird genau der Speicherplatz verwendet, der gebraucht wird.

new

Um ein Array während der Laufzeit zu erzeugen, wird dem Operator new in rechteckigen Klammern hinter dem Typ mitgeteilt, wie viele Elemente angefordert werden sollen. Der Zeiger, dem der neue Speicher zugeordnet wird, kann anschließend, auf Grund der Kompatibilität zwischen Zeiger und Array, genauso behandelt werden wie ein Array.

delete[]

Wurde mit new ein Array angefordert, muss dessen Freigabe mit dem Array-Aufruf delete[] erfolgen. Obwohl ein normaler Aufruf von delete von den meisten Compilern nicht bemängelt wird, ist das Ergebnis undefiniert.

int *Lotto = 0;      // Zeiger definieren und sichern
Lotto = new int [6]; // Array mit sechs Elementen erzeugen
for (i=0; i<6; i++)  // Array durchlaufen
{
     Lotto[i] = rand() % 49 + 1; // Lottozahl erzeugen
}
delete[] Lotto;      // Freigabe des Speichers
Lotto = 0;           // Zeiger sichern

Verkettete Listen

Wenn Sie mehrere Elemente eines Typs brauchen, werden Sie automatisch an ein Array denken. Wenn es aber vor der ersten Speicheranforderung schwer möglich ist, die maximale Anzahl der Elemente abzuschätzen, sind verkettete Listen eine gute Lösung. Wird ein neues Datenelement benötigt, wird es erzeugt und in die Liste eingefügt. Benötigen Sie ein Element nicht mehr, wird es gelöscht. Wie viele Elemente in der Liste sind, ist nur durch den verfügbaren Speicher beschränkt. Der Zugriff auf die Elemente an einer bestimmten Positionsnummer ist allerdings aufwändiger als in einem Array.

Daten und Zeiger

Die Basis einer verketteten Liste ist eine Struktur, die einerseits die eigentlichen Daten und andererseits einen Zeiger enthält, um auf das nächste Element der Liste zu verweisen.

struct TListenKnoten
{
    int data;
    TListenKnoten *next;
};

next

Etwas verblüffend ist die Verwendung des Typs TListenKnoten innerhalb der Deklaration des Typs TListenKnoten. Dem Compiler muss an dieser Stelle das genaue Aussehen des Typs TListenKnoten noch nicht bekannt sein, da hier lediglich ein Zeiger darauf definiert wird. Ein Zeiger ist aber immer gleich groß, ganz gleich, auf was er zeigt. Für den flüchtigen Beobachter ist es vielleicht irritierend, dass in der Struktur ein Zeiger ist, der scheinbar auf sich selbst zeigt. Wie aber schon der Name next andeutet, verweist der Zeiger nicht auf den eigenen Verbund, sondern auf den nächsten, der allerdings vom gleichen Typ sein wird. Eine verkettete Liste sieht also etwa so aus, wie es in Abbildung (abblinlist) schematisch dargestellt ist.

Im Buch erscheint an dieser Stelle die Abbildung einer verketteten Liste (abblinlist).

Anker

Die Variable Anker ist ein Zeiger auf den Typ TListenKnoten und bildet die Basis für den Zugriff auf die verkettete Liste vom Programm aus. Über den Anker erreicht man den ersten Listenknoten. Dort enthält das Element next den Verweis auf den nächsten Listenknoten. So kann sich das Programm durch die Liste hangeln, bis next einmal 0 ist. Damit wird das Ende der Liste angezeigt. Ist die gesamte Liste leer, muss die Variable Anker 0 enthalten.

Neues Element

Ein neuer Listenknoten wird durch Aufruf von new erzeugt. Dabei muss darauf geachtet werden, dass der Zeiger next gleich korrekt gesetzt wird. Wenn Sie nicht sofort den Nachfolger einhängen können, setzen Sie den Zeiger auf 0.

#include <iostream>
using namespace std;

struct TListenKnoten
{
    int data;            // simuliert die Daten
    TListenKnoten *next; // Verknüpfung zum Nachfolger
};

TListenKnoten *Anker = 0; // Anfang der Liste

int main()
{
    int Inhalt;
    TListenKnoten *node, *old;
    // Fülle die Liste mit Zahlen, bis 0 eingegeben wird
    do
    {
        cout << "Zahl eingeben (0 für Ende)" << endl;
        cin >> Inhalt;
        if (Inhalt)
        {
            // Neues Element für die Liste erzeugen:
            TListenKnoten *node = new TListenKnoten;
            node->data = Inhalt;  // Besetze die Daten
            node->next = Anker; // Hänge die bisherige Liste an
            Anker = node;       // Setze den Anfangspunkt hierher
        }
    } while (Inhalt);
    // Gebe die Liste in umgekehrter Reihenfolge aus
    // und lösche dabei die ausgegebenen Elemente
    while (Anker)    // ungleich 0! Die Liste ist nicht leer!
    {
        cout << Anker->data << endl;
        old = Anker;         // Sichere zum späteren Löschen
        Anker = Anker->next; // Ziehe nächstes Element nach vorn
        delete old;          // Lösche das ausgelesene Element
    }
}

Mit verketteten Listen lassen sich flexibelste Lösungen für die Ablage von Daten erzeugen. Sie können Daten an einem Ende der Liste einhängen und am anderen Ende entfernen. Damit ergibt sich ein Puffer. Wenn Sie das letzte Element einer Liste auf das erste zeigen lassen, ergibt sich eine Ringstruktur.


Informatik-Ecke Einstieg in C++ (C) Copyright 2005 Arnold Willemer