Claus Schönleber

What the heck are Pointers?

Inhalt

• Es werden Pointer eingeführt.
• Ein einfaches Beispiel führt den Umgang mit Pointern vor.
• Es werden dann einfach verkettete Listen eingeführt.
• Schließlich werden elementare Operationen wie Löschen aus der und Einfügen in die Liste demonstriert.

Pointer in C

Trotzdem sind Pointer notwendig, und viele Probleme lassen sich nur durch Pointer vernünftig lösen.

Deswegen ein Tip vorneweg: Schreiben Sie sich zu Anfang Ihrer Pointer-Karriere sofort - und das ist eine schöne Übung - einige Funktionen, die Ihnen den gekapselten und damit geschützten Umgang mit Pointern gestatten. Dazu gehören: Anhängen an eine Liste, Löschen aus einer Liste, Einfügen in eine Liste, das erste Element einer Liste ermitteln und den Rest der Liste (ohne das erste Element) ermitteln. Damit haben SIe alle Werkzeuge, die Sie benötigen.

Als Vorbild für die letzten beiden Funktionen in dieser Liste gelten "car" und "cdr" aus der Sprache LISP, eine Sprache, die ausschließlich mit Pointern arbeitet, die es dem Programmierer aber völlig abnimmt, sich darum kümmern zu müssen.

Datenstruktur von Variablen

Normale Variablen werden statisch im Speicher abgelegt und über eine Tabelle referenziert. Immer wenn in einem Programmtext auf eine Variable "a" zugegriffen werden soll, wird über die Tabelle ("Symboltabelle") die eigentliche Adresse des gewünschten Wertes ermittelt und dann auf die entsprechende Speicherzelle zugegriffen. In einer Symboltabelle stehen - grob gesagt - der Name der Variablen (damit man sie wiederfindet), die Adresse der Variablen im Speicher (damit man weiß, wo sie ist) und der Typ (damit man weiß, wieviel Platz sie braucht).

Statische Daten haben aber den Nachteil, daß man schon während der Programmierzeit über die Anzahl der zu verarbeitenden Daten Bescheid wissen muß. Es gibt jedoch viele Probleme, die das nicht erlauben. Deswegen gibt es einen speziellen Bereich im Arbeitsspeicher, den Heap (engl.: Haufen), in dem bei Bedarf beliebige Werte abgelegt werden können. Da das während der Laufzeit passiert, kann diesen Werten kein (Variablen-)Name zugewiesen werden; man richtet sich deswegen einen "Merkzettel" ein, einen Wert, der auf die entsprechende Adresse im Heap "zeigt", einen sogenannten Zeiger oder Pointer. Er ersetzt den Variablennamen.

Statt eines Variablennamens nimmt man nun eben den "Pointer", um auf eine Variable zuzugreifen. Dabei ist der Pointer selbst natürlich in einer statischen Variable untergebracht. Über die Verwendung von Pointern wird also schon während der Programmierzeit entschieden!

Solche Daten können nun genausoschnell weggeräumt werden, wie sie angelegt wurden. Manche Sprachen erlauben eine automatische "Heap-Reinigung" (garbage collection), zum Beispiel LISP oder JAVA. In PASCAL oder C/C++ muß der Programmierer das selbst tun; das ist dann ein Quell mannigfaltiger und schwer zu entdeckender Fehler.

Zunächst...

...führen wir einen ersten Pointer ein:

...
int n = 5;   /* "normale int-Variable */
int* ip;     /* Zeiger auf eine int-Variable */

/* 1. Der Zeiger "ip" zeigt auf "n" mit Hilfe des "&"-Operators: */
     ip = &n;

/* 2. n direkt verändern: */
     n = 7;
/* 3. n über den Zeiger "ip" mit Hilfe des Stern-Operators verändern: */
     *ip = 9;
...

Der Operator "&" (Adreßoperator) bewirkt bei einer beliebigen statischen Variablen, daß die Adresse der Variablen "ip" im Speicher ermittelt wird. Solche Adreßwerte können dann einer Zeiger- (oder Pointer-) Variablen zugewiesen werden, oder man kann mit ihnen rechnen (sauberer Programmierstil ist jedoch seit 1958, spätestens aber seit 1968 etwas anderes).

In Schritt 1 wird die Adresse der int-Variablen "n" ermittelt und der Zeigervariablen "ip" zugewiesen. In "ip" steht nun die Speicheradresse, an der die Variable "n" zu finden ist. In "n" selbst steht anfangs der Wert "5". In Schritt 2 wird auf die Variable "n" normal zugegriffen und deren Wert in "7" verändert. In Schritt 3 wird der Inhalt von "ip" ermittelt, dann wird - durch den Stern-Operator veranlaßt - dieser Wert als Referenz interpretiert. Mit anderen Worten: Der Inhalt von "ip" wird nicht als benutzbarer Wert, sondern als Adresse einer Variablen interpretiert. Der Wert "9" wird also nicht der Variablen "ip" zugewiesen, sondern der Variablen, deren Adresse in "ip" steht.

Was hat man nun davon? Nichts. Denn Zeigervariablen sind nichts anderes als ebenfalls statische Variablen, mit denen man auf andere statische Variablen zugreifen kann. Es sieht erstmal flotter aus, aber so ist es kein Gewinn. Natürlich kann man alles, was man "statisch" löst, auch "dynamisch", also mit Zeigern lösen. Aber wozu? Es wird unübersichtlicher und fehleranfälliger. Ok, man kann auf Parties Punkte bei Anfängern machen, gewonnen ist nichts. Interessant und unentbehrlich werden Zeiger erst dann, wenn man sie zusammen mit den im Folgenden besprochenen Mechanismen und Strukturen nutzt. Denn erst dann entfalten sie ihre wahre Stärken.

Wir merken uns: Zeiger sind unentbehrliche Hilfsmittel für dynamische Datenstrukturen. Sie alleine sind für nichts eine Lösung.

Der einfachste dieser Mechanismen ist die...

Einfach verkettete, lineare Liste

Da man mit einem reinen Pointer eigentlich nichts gewinnt - er ist ja selbst eine statische Variable - müssen stets zusätzlich Mechanismen eingesetzt werden, die es erlauben, den Adressraum, der mit dem Pointer verwaltet werden soll, dynamisch während der Laufzeit zu erweitern. Das kann man durch den Einsatz von records (in C: struct) erreichen, denen ein zusätzliches Datenfeld hinzugefügt wird, das einen Zeiger enthält, welcher auf einen weiteren record zeigen kann. Dadurch verknüpft man die einzelenen record einfach dadurch, daß andere record darauf verweisen. Letztendlich muß man sich dann aber durch dieses "Gestrüpp" von Verweisen auf einen Nachbarn hindurchhangeln, um zu einem gesuchten Datensatz zu gelangen. Wie dieses Gestrüpp aufgebaut wird, das entscheidet die gewählte Struktur:

• Linerare, einfach oder mehrfach verkettete Listen
• (Binär-)Bäume
• (n-dimensionale) Netze

Diese Listen sind dynamisch, d.h. im Gegensatz zum "Array", dessen Größe schon vor der Laufzeit des Programms festgelegt werden muß, ist es bei einer verketteten Liste auch während der Laufzeit eines Programms völlig offen, wieviel Elemente sie enthalten darf.

Um das zu erreichen, muß bei Bedarf für ein neu einzugebendes Element im System Platz angefordert werden. Die Verkettung der einzelnen Elemente wird dadurch erreicht, daß man dem letzten Element mitteilt, wo das nächste steht. Das Ganze kann man dann mit einer sequentiellen Datei vergleichen, nur daß die "Datei" nicht auf der Platte, sondern im Arbeitsspeicher (Adressraum der Hardware) steht.

Es interessiert uns momentan noch nicht, welcher Art die Elemente dieser Art von Liste sein dürfen. Zunächst ist interessant, wie der Verkettungsmechanismus funktioniert. Dazu ein paar Momentaufnahmen von einem Programm, das nacheinander insgesamt drei Listenelemente anfordert. Elemente werden links angefügt, bestehende werden nach rechts geschoben.

In Schritt 1 wird ein Element vom System angefordert. Das Element wird durch den Kasten dargestellt. Es enthält die Daten. Der kleine Kasten mit dem Punkt, das ist der Teil, der uns hier interessiert. Denn hier wird gleich die Adresse des nächsten Elements hineingeschrieben, dargestellt durch einen Pfeil.

In Schritt 2 ist das zweite Element angefordert worden. Diesem wurde die Adresse des ersten Elementes beigegeben, damit die Liste verkettet werden kann. So kann man sich nun von Element Nr. 2 nach Element Nr. 1 "hangeln" (nicht umgekehrt!).

Im letzten Schritt ist das dritte Element angefordert und in die schon bestehende Liste eingefügt, sprich angehängt, worden.

Wenn man die fertige Liste betrachtet, dann merkt man zweierlei:

1. Erstens, wo ist der Anfang der Liste? Ohne die Information, wo die Liste beginnt, kann sie ja nicht benutzt werden. Und was bedeutet der Punkt in Datensatz 1 anstelle des Punktes?
2. Zweitens, warum kann die Liste denn nach dem Aufbau nur "von hinten" durchgelesen werden? Die Zeiger gehen doch in die verkehrte Richtung!

Da das "erste" (zuerst angelegte) Element auf kein weiteres zeigt, kann hier keine echte Adresse stehen. Deswegen gibt es auch für diesen "Zeigertyp" ein neutrales Element. Es heißt NULL (manchmal auch NIL) und zeigt auf kein anderes Element. Diese NULL ist sehr deutlich zu unterscheiden von einem Zeiger, der auf einen nicht definierten Speicherbereich zeigt ("wilder Zeiger"). Diese sind strengstens zu vermeiden, denn sie lassen im besten Fall das Programm scheitern, im schlimmsten Fall können - je nach Anwendung - Datenschäden oder physische Schäden entstehen.

Dem System zeigt NULL in diesem Falle an, daß die Kette hier zu Ende ist. Eine Variable vom Typ Zeiger kann auf diesen Wert abgefragt werden. Der "dicke" Punkt in der Ecke des "letzten" Elementes ist der besondere Wert. 

Der "Anfangszeiger" (er heißt oft "first", aber der Name ist natürlich frei wählbar) muß natürlich mit jedem neu angeforderten und anzufügendem Element verändert werden! Da das der Programmierer, also Sie, zu machen haben, sollten Sie sich diesen Schritt genau einprägen!

Zu Punkt zwei: Man kann eine einfach verkettet Liste auch anders organisieren, indem man jeweils zwei Zeiger einrichtet und diese jeweils in die andere Richtung zeigen läßt; das hier ist jedoch die einfachste Form.

Die Einfachheit wird jedoch mit der Eigenschaft bezahlt, daß das zuletzt angefügte Element beim Auslesen der (sequentiellen) Liste als erstes Element wiedergefunden wird. Die Reihenfolge wird umgedreht. Das läßt sich aber kompensieren und kann vernachlässigt werden.

Deklaration von Pointern

Um eine Variable vom Typ Pointer in einem Record zu benutzen, ist "ein wenig" Vorarbeit notwendig. 

• Zunächst muß der Zeigertyp deklariert werden.
• Dann wird der Record eingeführt, von dessen Datenfeldern eines vom gerade eingeführten Zeigertyp ist (hier: next).
• Jetzt können die Variablen eingeführt werden für die entsprechende Anzahl von Zeigern zur Verwaltung der Liste (hier: p,first).

struct mitarblist 
{
	char name[30];
	float gehalt;
	int pnr;
	struct mitarblist* next;
};

mitarblist* p;
mitarblist* first;

Wir haben nun also einen statischen record (hier: C-struct) und zwei statische Variablen "*p" und "*first". Wo um alles in der Welt sind denn nun die dynamischen Strukturen?

[Meditieren Sie kurz darüber!]

Der Trick ist, daß ein (in Worten: 1) record dynamische erzeugt und mit einer statischen Zeigervariablen (z.B. p) eingerichtet und verwaltet werden kann! Nur einer! Alle anderen werden an das Datenfeld "*next" im jeweils neuen record angefügt.

[Meditieren Sie wieder kurz darüber!]

So, nun weiter...

Einsatz von Pointern

Wir müssen vorher nur noch zwei Dinge klären:

1. Wie fordert man einen neuen Record an?
2. Wie greift man auf die Datenfelder der Listenelemente zu?

Die erste Frage ist sehr einfach zu beantworten. Man benötigt einfach eine neue Adresse im Speicher (Adressraum der Hardware), und die wird mit einer Standardprozedur ermittelt:

p = (mitarblist*) malloc (sizeof(mitarblist*));

"malloc" fordert genau soviel Speicherplatz an, wie eine Instanz eines records vom Typ "mitarblist" benötigt. Danach wird noch der Typ des Speicherplatzes auf "mitarblist" gesetzt (gecastet).

Mit dieser Standardprozedur wird im System Platz für einen neuen Record angefordert. Die Adresse, an der dieses neue Listenelement beginnt, wird dem Pointer "p" zugewiesen. Er zeigt ab sofort auf den neuen Record.  Es gibt eine bessere, neuere Funktion dafür: "new", der vor allem in C++ und Java verwendet wird. C ist da manchmal etwas veraltet in der Technik...

Um dabei den Anschluß an die Liste nicht zu verlieren, muß der Anfangszeiger natürlich diesen neuen Wert erhalten. Der bisherige Wert des Anfangszeigers muß aber vorher der Zeigervariablen des neuen Records zugewiesen werden, damit das neue Element mit der Liste verbunden wird.

Üblicherweise werden, wenn man keine spezielleren Bezeichnungen benötigt, der Listen- und Arbeitszeiger "p" und der Anfangszeiger "first" genannt. Natürlich kann man auch der Problematik angepaßte Namen verwenden, aber für Übungszwecke empfehle ich diese Nomenklatur.

Zur Antwort auf die zweite Frage: Wie man gleich im Beispiel sehen wird, gibt es keine extra Variable, die den Record repräsentieren würde. Das ist auch überflüssig, denn wir wissen ja, wo der Record im Speicher steht, nämlich ab der Adresse, die in "p" steht. Dadurch brauchen wir keinen Variablennamen. Also sprechen wir die Datenfelder durch die Zeigervariable (fast) wie gewohnt an. Der Unterschied ist nur, daß man dem System mitteilen muß, daß man nicht ein Datenfeld des Pointers haben möchte, sondern ein Datenfeld des Records, auf das der Pointer zeigt! Das geschieht dann folgendermaßen:

*p.feldname

(*p).feldname

p->feldname

Wenden wir das bisher Gesagte im Beispiel an:

(Im Beispiel lassen wir das Gehalt und die Personalnummer der Einfachheit halber weg und verarbeiten nur den Namen.)

#include <stdio.h>

main ()
{
     struct mitarblist 
     {
         char name[30];
         struct mitarblist* next;
     };

     struct mitarblist* p;       /* Arbeitszeiger, Index für die Liste */
     struct mitarblist* first;   /* Kopf der Liste */
     char n[30];
     int index;

     /* ERZEUGEN */
     /* Das später letzte Element der Liste zeigt auf */
     /* keinen weiteren Datensatz. */
         first = NULL;

     for (index = 0; index <= 9; index++)
     {
         /* Pointerelemente einlesen */
              printf ("%i -> ",index);
              scanf ("%s",n);
         /* Anfordern eines neuen Records */
              p = (struct mitarblist*) malloc (sizeof(struct mitarblist*));

         /* Zuweisen des Recorddatenfeldes */
              strcpy (p->name,n);

         /* Der neue Record bekommt die Adresse des */
         /* letzten Records, die ja in "first" noch */
         /* steht. */
                   p->next = first;

         /* Aktualisieren des Anfangszeigers */
                   first = p; 

}
	
/* LESEN */
/* Vorbereitung der Ausgabe: Zeiger "p" wird auf */
/* das "erste" Element der Liste gesetzt */
      p = first;
      while (p != NULL) 
      {
          /* Pointerelemente ausgeben */
               printf ("%s \n",p->name);
          /* Setzen des Zeigers auf den nächsten Record */
                   p = p->next; 

      }
}

Generierung der Liste: Dabei ist die Form der Schleife unwichtig. Hier ist es eine FOR-Schleife. Auch die Eingabeform ist unwichtig. Genausogut könnte man die Eingabe auch aus einer Datei vornehmen.

Ausgabe der Liste: Für die Ausgabe bzw. für das lineare Durchsuchen sind also wesentlich weniger Schritte notwendig. Wichtig ist die Bedingung in der WHILE-Schleife, die das Ende der Liste über den Wert NIL ermittelt.

Schwierig wird das Ganze, wenn ein Datensatz aus der Liste entfernt oder eingefügt werden soll. 

Formulieren wir ein Programm, welches sich an dem gerade besprochenen Beispiel orientiert und wahlweise einen Datensatz löscht oder einfügt: 

#include <stdio.h>

main ()
{	
   struct mitarblist 
   {
       char name[30];
       struct mitarblist* next;
   };

   struct mitarblist* p;        /* Arbeistindex */
   struct mitarblist* first;    /* Kopf der Liste */
   struct mitarblist* insert;   /* Einfügeposition */
   struct mitarblist* last;     /* Vorgänger von p */

   char answer;
   int position,i;

   /* Auswahlmenue mit Eingabe */
       printf ("(1) Einfügen, (2) Löschen: ");
       scanf ("%c",&answer);
       do
       {
           printf ("Position, an der eingefügt/gelöscht werden soll:");
           scanf ("%d",&position);
       }
       while ((position >=0) && (position <= 9));

   /* Grundinitialisierung der Liste */
       p = first;
       i = 1;

   /* Ermitteln der Position für die gewünschte Manipulation */
   /* Zeiger "last" enthält stets die vorletzte Position */
       while ((p != NULL) && (i < position))
       {
           last = p;
           p = p->next;
           i++;
       }
   /* Verzweigung Löschen oder Einfügen? */
       switch (answer)
       {
           case 1 : {
                      insert = (struct mitarblist*) 
                                         malloc (sizeof(struct mitarblist));
                      insert->next = p->next;
                      p->next = insert; 
                      break;
                    }
           case 2 : {
                      last->next = p->next; 
                      break;
                    }
       }
 
   /* Ausgabe, wie schon gewohnt */
       p = first;

       while (p != NULL)
       {
           printf ("%s",p->name);
           p = p->next;
       }
}

Einfügen

Dabei müssen folgende Schritte ausgeführt werden:

1.
Anfordern eines neuen Records mittels "malloc"

insert = (struct mitarblist*) malloc (sizeof(struct mitarblist));

2.
Dem Verkettungszeiger des neuen Records wird der Verkettungszeiger des Records zugewiesen, auf den der Record (Nr. 2 im Beispiel) verwies, hinter den derneue eingefügt werden soll.

insert->next = p->next;

3.
Zum Schluß muß der Verkettungszeiger des Records, hinter den der neue eingefügt werden soll, noch auf den neuen gesetzt werden.

p->next = insert;

Löschen:

Folgende Schritte sind hier nötig:

1. Zunächst muß beim Durchhangeln ein zusätzlicher Zeiger mitgeführt werden, der immer auf den zuletzt betrachteten Record zeigt ("last").

last = p;
p = p->next;

2. Dann muß der Verkettungszeiger des vor dem zu löschenden Records auf den Nachfolger des zu löschenden Records gesetzt werden.

   last->next = p->next;

Verwaltung des "Heap"

Doch dafür kurz ein (vereinfachtes) Wort über die Zeigerverwaltung. Die Datensätze, auf die die Zeiger verweisen, werden in einem gesonderten Speicherbereich, genannt "Heap", abgelegt. Man kann ihn sich ungefähr so vorstellen:
 

Datensatz 1

Datensatz 2

Datensatz 3

...

Datensatz n

[Heapgrenze]

[freier Platz]
...
...

Wenn man jetzt einen Datensatz aus der verketteten Liste herausnimmt, dann will man auch dessen Speicherplatz wieder als frei kennzeichnen, d.h. für die Prozedur "malloc" wieder zur Verfügung stellen.

free

free (<zeigervariable>)

Nach 

free (p)

                ...     
                case 2 : {
                           last->next = p->next; 
                           free (p);
                           break;
                         } ...

Das Problem der "Heaplöcher" löst man in moderneren Programmiersprachen durch eine sogenannte "garbage collection".  Das ist ein Prozeß, der unabhängig vom EInfluß des Programmierers oder Anwenders von Zeit zu Zeit anspringt und derartige Löcher durch Umordnen des Heaps beseitigt. Beispiel dafür sind LISP oder Java.