Programmieren Teil 10 – Strukturierte Datentypen 2

Dann sieht das zugehörige Speicherbild so aus (die Variablenzugehörigkeiten sind wieder entsprechend in Var1 und Var2 angegeben):

Nun habe ich am Anfang des Artikels erwähnt, dass es bei der Komposition von strukturierten Datentypen zu Problemen kommen kann. Konkret geht es um die folgende Situation; nehmen wir eine Struktur Human an, die den Namen eines Menschen festhält, sowie die Eltern dieses Menschen (mit char* werden Zeichenketten beschrieben – die Details dahinter sollen an dieser Stelle nicht weiter interessieren, können aber theoretisch aus den Informationen der Artikel 7 und 8 hergeleitet werden)

struct Human
{
  char* name;
  Human mother;
  Human father;
};

Soweit sieht das ja eigentlich ganz logisch aus; das Problem ist nur, dass es so nicht machbar ist. Versucht man, diesen Code zu kompilieren, wird der Compiler unweigerlich Fehlermeldungen bringen, die leider nicht unbedingt auf das eigentliche Problem hinweisen; der Visual-Studio-Compiler von Microsoft wird etwa wenig aussagekräftig melden:

error C2460: 'Human::mother': Verwendet gerade definiertes 'Human'

Das Problem hier liegt natürlich in der Art des Speicherlayouts. Wie weiter oben beschrieben, benötigt eine Variable eines strukturierten Datentyps so viele Speicherzellen, wie die einzelnen Bestandteile des Datentyps benötigen. Für die Human-Struktur wäre das also einmal eine Speicherzelle für den Verweis auf den Namen (char* name) und der benötigte Speicher für die Mutter und den Vater. Die Mutter ist wieder ein Human, die wiederum eine Speicherzelle für den Namen und entsprechenden Speicher für deren Eltern benötigt; für die Eltern der Mutter (und natürlich des Vaters) gilt wieder das gleiche, und so weiter. Wir haben es also mit dem Problem einer unendlichen Rekursion zu tun: der benötigte Speicher wäre in unserem Beispiel unendlich groß, weil jeder Mensch einen Namen und zwei Eltern hätte.

Was uns fehlt, ist die Möglichkeit, einem Menschen nicht zwei Eltern zu geben (das widerspricht jetzt zwar auf den ersten Blick der Realität, aber biologisch gesehen ist das sogar korrekt: wenn wir weit genug in die Vergangenheit gehen, werden wir ein Wesen finden, welches keine zwei Eltern hatte). Um das zu verwirklichen, müssen wir die Datenstuktur für den Human etwas anders aufbauen, da momentan immer zwei Eltern gefordert sind.

Wünschenswert wäre eine Möglichkeit, die Eltern wahlweise zu definieren oder – wenn sie nicht vorhanden sind – undefiniert zu lassen. Mit einer “normalen” Variablendeklaration lässt sich das nicht erreichen, da gewöhnliche Variablen nicht in dem Sinne undefiniert sein können; ihnen kann zwar einfach kein Wert zugewiesen werden – der für sie theoretisch benötigte Speicher muss aber dennoch immer reserviert werden. Das Stichwort zur Lösung ist aber genau die Reservierung von Speicher: wie wir uns erinnern, ging es im Kapitel über den Heap schon einmal genau darum. Das Mittel der Wahl sind dann auch die bereits in diesem Artikel erwähnten Adressverweise, sprich: die Pointer.

Wir erinnern uns: eine Variable kann als ein Pointer deklariert werden, indem vor den Variablennamen ein * geschrieben wird; Pointer-Variablen verweisen nicht auf konkrete Werte, sondern auf eine Adresse, unter welcher der gesuchte Wert im Speicher zu finden ist. Zudem hat eine Pointer-Variable eine feste Größe und benötigt zur Speicherung immer genau 4 Byte, also eine Speicherzelle (auf 64-Bit-Systemen entsprechend 8 Byte).

Möchten wir nun, dass eine Variable auf keine Adresse verweist, so weisen wir ihr einen speziellen Wert zu, nämlich die 0. An dieser Adresse werden während des Programmablaufs niemals relevante Daten stehen, weswegen sie zur Markierung von derartigen Leerverweisen benutzt wird; man spricht dementsprechend auch von Null-Pointern.