Dynamische Speicherverwaltung

  • Wozu braucht man dynamische Speicherverwaltung?
  • Den benötigten Speicher herausfinden
  • Speicher anfordern und freigeben
  • Zugriff auf den angeforderten Speicher
  • Ziel erreicht
  • Mit der Standard-C-Lib ins Ziel

Wozu braucht man dynamische Speicherverwaltung?

Bisher haben wir die Spielregeln geübt. Mit dieser Lektion kommen wir endlich in die Lage, damit zu spielen. Denn worum geht es beim Programmieren? Es geht darum Daten zu verarbeiten, und zwar Daten, die wir vorher nicht kennen. Wir werden uns hier damit beschäftigen, zwei Strings miteinander zu einem einzigen String zu verbinden. Eine Aufgabe, die immer wieder vorkommt, wenn man Beispielsweise einen Vornamen und den zugehörigen Nachnamen zu einem Text zusammenfügen möchte.

Hierbei bekommen wir zunächst ein Problem: Beim Start des Programms wissen wir noch nicht wie lang Vorname und Nachname sein werden. Wir müssten also ein Array verwenden, von dem wir hoffen, dass es lang genug ist. Das ist ein übliches, wie auch kritisches Vorgehen. Die Größe des Arrays ist im Quelltext festgelegt und kann nicht verändert werden. Die Größe ist statisch. Wenn man davon ausgeht, dass niemand einen Namen mit mehr als 100 Buchstaben hat, dann funktioniert das Programm vermutlich für alle Personen, die Du kennst. Wenn das Programm aber von anderen verwendet wird, dann wird es garantiert jemanden geben, der einen entsprechend langen Namen hat.

Also lösen wir das Problem anders: Wir finden zunächst heraus, wie lang Vorname und Nachname sind und fordern dann dynamisch Speicher an:

Den benötigten Speicher herausfinden

Wenn wir zwei Strings miteinander verbinden wollen, so brauchen wir die Länge der beiden Strings. Wir wissen, dass C-Strings nichts anderes als Arrays sind und dass wir Arrays als Pointer betrachten können. Mit einem Zeiger können wir die Adresse des ersten Zeichens übergeben und nun schauen, wie weit wir gehen müsst, bis wir das Nullbyte finden, also am Ende des C-Strings angekommen sind.

#include <stdio.h>
 
int strLength( char * str )
{
  int length = 0;
 
  while( str[ length ] )
    length = length + 1;
 
  return length;  
}
 
int main( void )
{
  char vorname[]  = "Hans";
  char nachname[] = "Mustermann";  
 
  int length = strLength( vorname )
             + 1                     // Leerzeichen
             + strLength( nachname )
             + 1;                    // Nullbyte   
 
  printf( "%d Bytes werden benötigt\n", length );
 
  return 0;
}

Nach der Ausführung erhalten wir:

16 Bytes werden benötigt

Um aus „Hans“ und „Mustermann“ den String „Hans Mustermann“ zu machen, benötigen wir also 16 Byte. Das Nullbyte dürfen wir hierbei nicht vergessen!

Speicher anfordern und freigeben

Nachdem wir nun wissen, wieviel Speicher wir benötigen, müssen wir das Betriebssystem bitten, uns diesen Speicher zur Verfügung zu stellen. Wie printf() gehören die dafür verwendeten Funktionen malloc() und free() zur grundsätzlich mitgelieferten C-Standard-Bibliothek.

malloc() übergibt man die benötigte Größe in Bytes und man erhält einen Zeiger auf den bereitgestellten Speicher. Falls malloc() einen Nullzeiger zurückgibt, kann das Betriebssystem keinen Speicher in der gewünschten Größe zur Verfügung stellen.

Damit Speicher der nicht mehr benötigt wird an anderer Stelle wieder verwendet werden darf, muss man ihn erst wieder freigeben. Hierfür übergibt man der Funktion free() den Zeiger, den man zuvor von malloc() erhalten hat. Man darf zwar den Nullzeiger, aber nicht bereits einmal freigegebenen Speicher ein zweites Mal freigeben.

printf() wird in der Headerdatei stdio.h deklariert, für die Funktionen malloc() und free() benötigen wir zusätzlich die stdlib.h

#include <stdio.h>
#include <stdlib.h>
 
int strLength( char * str ); // siehe oben
 
int main( void )
{
  char vorname[]  = "Hans";
  char nachname[] = "Mustermann";  
 
  int length = strLength( vorname )
             + 1                     // Leerzeichen
             + strLength( nachname )
             + 1;                    // Nullbyte   
 
  printf( "%d Bytes werden benötigt\n", length );
 
  char * name = malloc( length );
 
  if( name )
  { 
    // hier kann mit dem Speicher gearbeitet werden
 
    free( name );  
  }
 
  return 0;
}

Die Zeile

  char * name = malloc( length );

fordert den Speicher an und ist gültiges C. Reine C-Compiler gibt es heute kaum noch, die meisten C-Compiler sind in Wirklichkeit C++-Compiler. Der gcc-Compiler akzeptiert den Quellcode, der C++ Compiler g++ liefert folgende Meldung:

malloc.c: In function ‘int main()’:
malloc.c:26: error: invalid conversion from ‘void*’ to ‘char*’

sollte Dein Compiler meckern, ersetze bitte die Zeile wie folgt:

  char * name = (char *) malloc( length );

Auch das ist gültiges C, was hier genau passiert, nennt sich „Casting“ und ist bei einem C++ Compiler erforderlich. Was Casting ist wird in einer späteren Lektion erklärt.

Zugriff auf den angeforderten Speicher

Wir haben in der vorherigen Lektion über Zeiger gelernt, dass man mit ihnen genauso arbeiten kann, wie mit Arrays. Wir können nun eine Funktion schreiben, die einen String kopiert.

Das mache ich jetzt einfach mal, lies sie Dir gut durch und bemühe Dich sie nachzuvollziehen:

#include <stdio.h>
#include <stdlib.h>
 
int copyString( char * from, char * to, int maxLength )
{
  int copiedChars = 0;
 
  while( maxLength )
  {
    to[ copiedChars ] = from[ copiedChars ];
 
    if( !to[ copiedChars ] )
      break;
 
    copiedChars = copiedChars + 1;
    maxLength   = maxLength   - 1;
  }
 
  return copiedChars;
}
 
int strLength( char * str )
{
  int length = 0;
 
  while( str[ length ] )
    length = length + 1;
 
  return length;  
}
 
int main( void )
{
  char vorname[]  = "Hans";
  char nachname[] = "Mustermann";  
 
  int length = strLength( vorname )
             + 1                     // Leerzeichen
             + strLength( nachname )
             + 1;                    // Nullbyte   
 
  printf( "%d Bytes werden benötigt\n", length );
 
  char * text = malloc( length );
 
  // #0 - Vorname kopieren an &text[0]
  int position = copyString( vorname, text, length );
 
  // #1 - Leerzeichen hinter vorname einfügen 
  text[ position ] = ' ';
  position = position + 1;
 
  // #2 - Nachname kopieren hinter ' ' (&text[position])
  copyString( nachname, &text[ position ], length - position );
 
  printf( "Der zusammengesetzte Name: '%s'\n", text );
 
  free( text );
 
  return 0;
}

Schauen wir uns an, was passiert. Bei Kommentar #0 haben wir den Vornamen kopiert. Das Array sieht also wie folgt aus, wie zuvor markiere ich mit einem '@', wenn niemand weiß, was dort steht, da diese Zeichen nie initialisiert wurden.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
H a n s '\0' @ @ @ @ @ @ @ @ @ @ @ @

Die Funktion hat 4 Buchstaben kopiert und gibt entsprechend 4 zurück, die in der Variablen position gespeichert. Anschließend wird an position das Nullbyte mit dem Leerzeichen überschrieben:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
H a n s ' ' @ @ @ @ @ @ @ @ @ @ @ @

Anschließend wird position um eins erhöht.

Schließlich wird mit der Zeile

copyString( nachname, &text[ position ], length - position );

nun nachname an die Adresse kopiert, die der Indexposition angibt, also 5 (das 5. Zeichen hinter dem Beginn des Arrays text, also hinter das Leerzeichen):

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
H a n s ' ' M u s t e r m a n n '\0' @

Die 16 Bytes, die wir alloziert haben verlaufen vom 0. bis zum 15. Byte und das 16. Byte ist von uns nicht berührt worden - das ist wichtig, denn wir dürfen dieses Byte weder lesen noch schreiben!

Ziel erreicht

Damit haben wir das Ziel erreicht: Es ist ein String konstruiert worden, der aus Vor- und Nachnamen besteht und durch ein Leerzeichen voneinander getrennt ist. Wenn Du dieses Programm nachvollziehen kannst, dann ist das ein wichtiger Schritt zur Programmierung, denn dieses Programm ist das erste, das aus zwei Daten ein neues Datum konstruiert. Wir haben erstmals Informationsverarbeitung betrieben. :-)

Mit der Standard-C-Lib ins Ziel

Wir haben hier alles von Hand geschrieben. Es ist wichtig, dass Funktionen wie strLength und copyString von Dir selbst geschrieben werden können und deswegen ist es wichtig, dass Du diese Funktionen nachvollziehen kannst.

Aber später wird es nicht mehr darum gehen solche Funktionen nachzuvollziehen, sondern sie einfach zu benutzen. Und da solche Funktionen regelmäßig verwendet werden, werden sie in der C-Standard-Library mitgeliefert, die hier auf proggen.org auch auf Deutsch mit Beispielprogrammen beschrieben ist. Schau Dich also ruhig mal um, welche Aufgaben Dir die Standard-Lib später abnehmen kann.

Um C wirklich zu lernen ist es jedoch wichtig, dass Du diese Funktionen früher oder später auch selbst programmieren könntest. Um die hier verwendeten Funktionen mit Funktionen aus der Standardlibrary auszutauschen, müssen wir uns im Header string.h umsehen: Dort finden wir die Funktionen strlen als Ersatz für unsere strLength() und strcpy für copyString(). Wir müssen aber aufpassen: Während strlen genauso funktioniert wie strLength(), liefert strcpy leider nicht die Länge des kopierten Strings zurück - unsere Funktion könnte also hier praktischer sein, aber wir wollen mal sehen, was wir mit der Standard-Library hinbekommen:

strlen() und strcpy()

Wichtig ist hierbei, dass strcpy nicht nur die Länge der kopierten Zeichen verheimlicht, sondern auch noch das Ziel als erstes Argument haben möchte. Aber das Programm wird - da wir unsere eigenen Funktionen sparen können, deutlich kürzer.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main( void )
{
  char vorname[]  = "Hans";
  char nachname[] = "Mustermann";  
 
  int vornameL  = strlen( vorname );
  int nachnameL = strlen( nachname );
 
  int length = vornameL + nachnameL + 2;
 
  printf( "%d Bytes werden benötigt\n", length );
 
  char * text = malloc( length );
 
  strcpy( text, vorname );
  text[ vornameL ] = ' ';
  strcpy( &text[ vornameL + 1 ], nachname );
 
  printf( "Der zusammengesetzte Name: '%s'\n", text );
 
  free( text );
 
  return 0;
}

sprintf()

Grundsätzlich wäre alles so einfach, wenn es auf den Bildschirm ausgeben könnte:

printf( "%s %s", vorname, nachname );

Freundlicherweise kann man mit sprintf() auch einfach in den Speicher schreiben. Aber man muss hierbei sehr gut aufpassen, dass man sich hier nicht in der Länge vertut. Zahlen, die per %d eingefügt werden, können schließlich einstellig (z.B. 1) oder auch mehrstellig (z.B. 1234) sein. Genauso muss die Länge der eingefügten Strings berücksichtigt werden.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main( void )
{
  char vorname[]  = "Hans";
  char nachname[] = "Mustermann";  
 
  int length = strlen( vorname ) + strlen( nachname ) + 2;
 
  printf( "%d Bytes werden benötigt\n", length );
 
  char * text = malloc( length );
 
  sprintf( text, "%s %s", vorname, nachname );
 
  printf( "Der zusammengesetzte Name: '%s'\n", text );
 
  free( text );
 
  return 0;
}

Damit haben wir unsere ganzen bisherigen Bemühungen mit der sprintf()-Funktion auf eine Zeile verkürzt - ein Blick in die C-Standard-Library kann sich also lohnen.

Mit sprintf() lassen sich all die schönen Transformationen durchführen, genauso wie mit printf(), entsprechend des übergebenen Formatstrings.

Ziel dieser Lektion

Diese Lektion heißt „dynamische Speicherverwaltung“ und dreht sich vorrangig um die Funktionen malloc() und free(). Aber es geht auch darum, wie man den erhaltenen Speicher verwenden und beschreiben kann. Dazu haben wir zum einen einen Blick in die C-Standard-Library geworfen. Für die Speicherveraltung lohnt auch ein Blick zu den Standard-Funktionen calloc() und realloc(). Verschaffe Dir einen Überblick, was C alles grundsätzlich mitliefert und halte im Hinterkopf dort regelmäßig nachzusehen, ob Du benötigte Funktionalität dort bereits findest. Dein Ziel sollte sein, Dich in die Lage zu versetzen, die Funktionen der C-Standard-Library selbst programmieren zu können, jedoch bevorzugt von den vorhandenen Funktionen Gebrauch zu machen: Jeder C-Programmierer kennt sie und versteht damit auch Deinen Code schneller.

Mit dieser Lektion ist aus vorhandenen Daten erstmals etwas Neues konstruiert worden. Das bedeutet, dass Du nun an einen Punkt ankommst, an dem Du mit Deinem Programm ein Ergebnis produzieren kannst.

Im nächsten Kapitel werden wir uns ansehen, was es neben const noch für Attribute gibt, um Einfluss auf die Verwendung von Datentypen zu nehmen.


Autorendiskussion