Strukturen verwalten

Wieso muss man Strukturen verwalten?

Grundsätzlich habt ihr jetzt das Wissen von C, um aufwendige Programme zu schreiben. CounterStrike, Word, Firefox. Und vermutlich werdet ihr euch jetzt überfordert vorkommen, weil ihr zwar schon einiges wisst, aber noch über keine Erfahrungen verfügt, diese Dinge auch anzuwenden. Dies ist ein C-Tutorial, ihr lernt hier also die Programmiersprache C. Hier liegt die Betonung auf Sprache - nicht auf Sprechen. Man programmiert, in dem man Ideen formuliert, dafür braucht man eine Sprache. Dieses Kapitel soll dazu anleiten, etwas mit der Sprache zu spielen und Möglichkeiten auszuloten.

Um Sprechen zu lernen und sich rhetorisch geschickt auszudrücken, dazu gibt es ein anderes Kapitel in der Informatik, das Kapitel der Algorithmen und Datenstrukturen. Wir werden in diesem Programmiersprachen-Tutorial in beide Kapitel kurz an der Oberfläche kratzen. Sobald ihr wisst, was ihr programmieren wollt, findet ihr dort entsprechende Lösungen und habt in diesem Tutorial die Möglichkeit erlernt, die Lösungen für den Computer verständlich zu formulieren.

Das Schöne an dieser Lektion ist: Es gibt sprachlich nichts Neues zu lernen, es geht darum Wissen aus den vorherigen Lektionen anzuwenden - also bekanntes Vokabular in einem ganzen Satz sprechen. Als wir lernten eine Datenstruktur zu beschreiben, haben wir Daten zusammengefasst, die in ihrer Bedeutung zusammengehören: Bei der Bildschirmauflösung haben wir Breite und Höhe des Bildschirms in eine Struktur gebracht und bei Personen Vor- und Nachname, das Alter und die Adresse. Nun werden wir uns ein wenig damit beschäftigen, dass Datenstrukturen wachsen können und organisiert werden wollen.

Arrays - Die Grundlage von Allem

Die Grundlage aller Datenstrukturen kennen wir bereits: Das Array. Hierbei werden die Daten einfach hintereinander in eine Reihe gepackt. Grundsätzlich unterscheidet sich eine Struktur nicht groß von einem Array, auch hier werden Daten hintereinander gepackt. Beim Beispiel mit der Bildschirmauflösung sind dies Breite und Höhe. Legt man mehrere Bildschirmauflösungen in ein Array, so reihen sich die Daten innerhalb der Struktur hintereinander auf: Breite für Index 0 und Höhe für Index 0, Breite für Index 1 und Höhe für Index 1… und so weiter. In einer Struktur, wie ScreenResolution, weiß man dass die Breite ganz vorne liegt (also am Index 0) und die Höhe hinter der Breite. Wenn die Breite als Integer-Datentypen 4 Bytes benötigt, so belegt die Breite die Indizes 0, 1, 2 und 3. Die Höhe liegt dahinter ab Index 4.

Um das Ganze etwas salopp zu sagen: Die absolute Grundlage Daten im Speicher zu halten ist sie so in den Speicher zu packen, dass man sie wiederfindet und das geht nun mal sehr einfach und vor allem sehr schnell, in dem die Daten einfach hintereinander im Speicher liegen. Wenn Du Dir mit Deiner Vorstellung vom Speicher noch unsicher bist, so findest Du sprachunabhängig im Startbereich eine eine Erklärung zum Gesamtspeicher.

Dynamische Datenstrukturen: der Zeiger

Mit den C-Strings haben wir eine Datenstruktur kennen gelernt, auf die in der Regel mit einem Zeiger gezeigt wird. Wir wissen, wo die Buchstaben im Speicher liegen und wir können beliebig lange Texte ganz einfach dadurch an eine Funktion weitergeben, indem wir nur die Adresse an die Funktion übergeben. Die Funktion selbst kann sich dann die benötigten Daten abholen.

Zeiger haben also den Vorteil, dass sie sehr klein sind und problemlos weitergereicht werden können. Sie haben aber dafür den Nachteil, dass sie eventuell irgendwohin zeigen können, wo gar keine Daten liegen - oder die falschen Daten, zum Beispiel durch ein fehlerhaft durchgeführtes Casting.

Vor Zeigern darf man keine Angst haben, aber Respekt ist angebracht. Zeiger braucht man immer, sobald etwas ein wenig aufwendiger wird.

Arrays von Arrays

Zunächst können wir Arrays von Arrays definieren, zum Beispiel ein Spielfeld für ein Tic-Tac-Toe-Spiel. Das geht einfach in dem wir mehr Klammern einfügen:

  char playField[3][3];

Aber wie sieht das im Speicher aus - fragen wir den Computer, in dem wir ein entsprechendes Testprogramm schreiben:

#include <stdio.h>
#include <stdlib.h>
 
int main( void )
{
  char playField[3][3];
  unsigned int x, y;
 
  printf( "Das Spielfeld ist %d Bytes groß.\n", sizeof( playField ));
 
  for( x = 0; x < 3; ++x )
  {
    for( y = 0; y < 3; ++y )
    {
      playField[x][y] = ' ';
      printf( "Addresse von %d/%d: %lx\n", x, y, &( playField[x][y] ) );
    }
  }
 
  return EXIT_SUCCESS;
}

und schauen uns das Ergebnis an:

xin@trinity:/data/home/xin/workspace/proggen.org/c/tutorial/meta$ gcc tictactoe.c 
xin@trinity:/data/home/xin/workspace/proggen.org/c/tutorial/meta$ ./a.out 
Das Spielfeld ist 9 Bytes groß.
Addresse von 0/0: 7fffadda5290
Addresse von 0/1: 7fffadda5291
Addresse von 0/2: 7fffadda5292
Addresse von 1/0: 7fffadda5293
Addresse von 1/1: 7fffadda5294
Addresse von 1/2: 7fffadda5295
Addresse von 2/0: 7fffadda5296
Addresse von 2/1: 7fffadda5297
Addresse von 2/2: 7fffadda5298

Wir sehen zunächst, dass das Array 9 Bytes groß ist und die Adressen sagen uns, dass die einzelnen Elemente direkt hintereinander liegen. Diese Form des Arrays ist also in Wirklichkeit ein Array[9], und der Zugriff bedeutet hier in Wirklichkeit mit Array[x*3+y]:

#include <stdio.h>
#include <stdlib.h>
 
int main( void )
{
  char playField[9];
  unsigned int x, y;
 
  printf( "Das Spielfeld ist %lu Bytes groß.\n", sizeof( playField ));
 
  for( x = 0; x < 3; ++x )
  {
    for( y = 0; y < 3; ++y )
    {
      playField[3*x+y] = ' ';
      printf( "Addresse von %d/%d: %p\n", x, y, &( playField[3*x+y] ) );
    }
  }
 
  return EXIT_SUCCESS;
}

und das Ergebnis sieht vergleichbar aus: 9 Bytes groß und die einzelnen Elemente des Arrays liegen hintereinander im Array:

xin@trinity:/data/home/xin/workspace/proggen.org/c/tutorial/meta$ gcc tictactoe2.c 
xin@trinity:/data/home/xin/workspace/proggen.org/c/tutorial/meta$ ./a.out 
Das Spielfeld ist 9 Bytes groß.
Addresse von 0/0: 0x7ffc3b7f89b0
Addresse von 0/1: 0x7ffc3b7f89b1
Addresse von 0/2: 0x7ffc3b7f89b2
Addresse von 1/0: 0x7ffc3b7f89b3
Addresse von 1/1: 0x7ffc3b7f89b4
Addresse von 1/2: 0x7ffc3b7f89b5
Addresse von 2/0: 0x7ffc3b7f89b6
Addresse von 2/1: 0x7ffc3b7f89b7
Addresse von 2/2: 0x7ffc3b7f89b8

Dass die Adressen bei den Programmen unterschiedlich sind, kommt nicht durch die Änderung des Programms, sondern ändert sich auch mit jedem Programmaufruf, eben je nachdem, wohin das Programm in den Speicher geladen wurde.

Arrays von Zeigern

Wir können natürlich auch Arrays von Zeigern erstellen und diese Zeiger können natürlich auch auf Arrays zeigen. Wir können das Spielfeld zum Beispiel mit Zeigern aufbauen, schauen wir uns das ganze als Quelltext an:

#include <stdio.h>
#include <stdlib.h>
 
int main( void )
{
  char * playField[3];
  unsigned int x, y;
 
  for( x = 0; x < 3; ++x )
    playField[x] = (char*) malloc(3);
 
  printf( "Das Spielfeld ist %lu Bytes groß.\n", sizeof( playField ));
 
  for( x = 0; x < 3; ++x )
  {
    for( y = 0; y < 3; ++y )
    {
      playField[x][y] = ' ';
      printf( "Addresse von %d/%d: %p\n", x, y, &( playField[x][y] ) );
    }
  }
 
  for( x = 0; x < 3; ++x )
    free( playField[x] );
 
  return EXIT_SUCCESS;
}

Nun schauen wir uns die Ausgabe an:

Das Spielfeld ist 24 Bytes groß.
Addresse von 0/0: 0x14fd010
Addresse von 0/1: 0x14fd011
Addresse von 0/2: 0x14fd012
Addresse von 1/0: 0x14fd030
Addresse von 1/1: 0x14fd031
Addresse von 1/2: 0x14fd032
Addresse von 2/0: 0x14fd050
Addresse von 2/1: 0x14fd051
Addresse von 2/2: 0x14fd052

Das Array playField ist hier 24 Byte groß - 3 Adressen zu je 8 Byte (auf einem 64 Bit-System). An den Adressen zeigt sich, dass sich jede Spalte im Spielfeld an unterschiedlichen Stellen im Speicher befinden, zumindest nicht hintereinander. Wenn wir genau hinsehen, stellen wir auch fest, dass die Adressen bei diesem Betriebssystem (Debian Linux 2.6.35.3) hier im Freispeicher befinden (der Speicher wurde mit malloc() angefordert), statt als lokale Variable der Funktion main auf dem Stack zu liegen (die Speicherstelle ist extrem groß: Die Adressen zuvor begannen mit 7fff). Wir erkennen, dass das Betriebssystem statt der 3 Byte, die wir benötigen, gleich 32 Bytes (hexadizimal 20) anfordert.

Wir sind so deutlich flexibler, wir können zum Beispiel mitten im Programm eine Spalte austauschen, indem wir eine andere Spalte erstellen und ins Array stellen. Bei sehr kleinen Datensätzen - wie hier - verbrauchen wir sehr viel mehr Speicher für die Verwaltung der Daten als für die Daten selbst. Bei sehr großen Datensätzen müssen wir so nur eine Adresse austauschen, so benötigen wir zwar mehr Speicher, können aber mit wenig Aufwand Daten schnell austauschen. Stellen wir uns einen Browser mit Tabs vor - es ist einfacher die Adresse auf die Darstellung der Website auszutauschen als das komplette Darstellung. Hier lohnt sich der Mehraufwand also!

Einfache Listen

Wir haben nun Arrays von Zeigern gemacht, was uns erlaubte, die Spalten in einem Spielfeld auszutauschen. Bei den Zeilen des Spielfeldes müssen wir weiterhin aufwendig kopieren. Das ist ja noch kein nennenswertes Problem für einen modernen Computer. Aber dieses Problem gibt es häufiger, zum Beispiel bei den Zeilen eines Texteditors. Das kann bereits aufwendiger werden. Ein Text könnte zum Beispiel so aussehen:

char * zeilen[10];

Das wären 10 Zeilen, denen wir mit malloc() noch Speicher geben müssten. Doch was passiert, wenn der Benutzer einen größeren Text wünscht und die elfte Zeile hinzufügt? Oder wenn er eine Zeile mittig einfügen oder löschen möchte? Es besteht also ein Interesse, hier kein unflexibles Array anzuwenden, sondern lieber ein etwas flexibleres Konstrukt. Denken wir nochmal kurz daran, wie der Computer C-Strings verarbeitet: Es ist einfach der Zeiger auf das erste Element. Ein Text könnte als Zeiger auf die erste Zeile dargestellt werden.

struct TextLine * Text;

Dann bleibt die Frage, wie eine Zeile aussieht. Zum Beispiel so:

struct TextLine
{
  struct TextLine * Next;
 
  char            * Content;
};

In der Datenstruktur „TextLine“ befindet sich ein Zeiger, der auf die nächste TextLine-Struktur zeigt. Wir können nun also beliebig viele Zeilen hintereinander hängen, solange bis der „Next“-Zeiger durch einen Nullpointer dargestellt wird, genau wie das Nullbyte beim C-String. Wir können die dritte und vierte Zeile dadurch vertauschen, indem wir den Nachfolger der zweiten Zeile auf die vierte Zeile zeigen lassen, den Nachfolger der dritten Zeile auf den Nachfolger der vierten und den Nachfolger der vierten Zeile auf die dritte Zeile zeigen lassen.

Diese Datenstruktur nennt man „einfach verkettete Liste“, wobei einfach nicht nur soviel wie simpel, sondern eben auch einfach im Gegensatz zu zweifach bedeutet. Zweifach verkettete Listen sind ebenfalls sehr üblich, denn häufig will man nicht nur wissen, welche Zeile folgt, sondern auch welche Zeile vor einem liegt:

struct TextLine
{
  struct TextLine * Next;
  struct TextLine * Previous;
 
  char            * Content;
};

Nun können wir uns frei - vor und zurück - durch die Zeilen bewegen. Die Liste ist eine elementare Datenstruktur, mit ihr kann man alles verwalten, was sich in irgendeiner Weise sortieren lassen muss oder Datensätze, deren Anzahl sich im laufenden Programm ändern (zum Beispiel die Prozess-Liste eines Betriebssystems, die noch lebenden Gegner beim Ego-Shooter usw.).

siehe auch: Datenstruktur Liste

Komplexere Datenstrukturen

Neben den Listen, lassen sich viele weitere Datenstrukturen formulieren. Schauen wir uns ein Stück HTML-Code an:

<body background="white">
  <h1>proggen.org</h1>
  C-Tutorial
</body>

Diese Datenstruktur wird als DOM (Document Object Model) bezeichnet. Ein Knoten, zum Beispiel „body“ kann Parameter besitzen, wie auch eine Liste von Unterknoten, zum Beispiel „h1“. Ein Knoten kann aber auch nur ein Stück Text sein, zum Beispiel „proggen.org“ als Knoten unterhalb von „H1“ oder „C-Tutorial“ unterhalb von Body.

Der Knoten „Body“ hat also eine Liste aus Knoten, nämlich H1 und dem Text „C-Tutorial“. H1 selbst hat wieder eine Liste mit Unterknoten, darin befindet sich der Text „proggen.org“. Weiterhin hat der Knoten „Body“ einen Parameter.

Um das auszudrücken brauchen wir zwei Datenstrukturen. Die erste der beiden repräsentiert einen Parameter:

struct Parameter
{
  struct Parameter * Next;
 
  char * Name;
  char * Value;
};

Damit lässt sich eine Liste von Parametern abbilden und in die Unterknoten einbinden. Für die Unterknoten wird folgende Struktur verwendet:

struct Node
{
  struct Node      * Next;
 
  char             * Text;         // Falls es ein Textknoten, wie "proggen.org" ist.
  struct Parameter * Parameter;    // Zeiger auf den ersten Parameter wie background bei <body ...>
  struct Node      * SubNode;      // H1 ist der erste Subknoten von body.
};

Mit diesen beiden Strukturen können wir bereits einen HTML-Code mit C beschreiben. Doch warum sollte man das eigentlich tun? Schließlich ist es einfach HTML in HTML zu beschreiben, statt in derart komplizierten Strukturen. Aus genau dem Grund beschreibt man Webseiten auch in HTML, doch ein Webbrowser muss aus dem HTML-Code schließlich maschinenverständlich einlesen und damit arbeiten können, um daraus die entsprechende Darstellung auf dem Bildschirm zu generieren. Hier kommen wir als C-Programmierer dann ins Rennen.

Ziel dieser Lektion

Das Ziel dieser Lektion ist darauf aufmerksam zu machen, dass man mit den bisher gelernten Mitteln komplexe Daten beschreiben kann. Das schlussendlich auch zu tun ist eine Sache der Erfahrung. Wem das HTML-Beispiel beispielsweise noch nicht klar ist, der muss sich nicht gleich Sorgen machen. Wir werden auf diese Strukturen später noch einmal eingehen und sie wirklich in die Hände nehmen, so dass man sie auch besser begreifen kann.

Wichtig ist zu Wissen, dass sich die bekannten Sprachmerkmale in vielerlei Hinsicht kombinieren lassen, so dass man noch mehr mit ihnen anfangen kann. Für eine Übersicht über Datenstrukturen empfehle ich einen Blick ins Kapitel Datenstrukturen. Was mir für dieses Kapitel wichtig ist, dass die hier verwendeten Listen mit dem Element „Next“ einen Datensatz enthalten, der überhaupt keine Daten beinhaltet, sondern nur der Organisation der Daten. Indirekt ist die Reihenfolge der Daten darin enthalten, aber vorrangig handelt es sich um eine Information, wo weitere Daten zu finden sind, die den Benutzer selbst nicht interessiert. Diese Information interessiert nur den Software-Entwickler, damit er seine Daten organisiert bekommt.

siehe auch