Arrays

Video zum Kapitel

Übersicht

C ist keine objektorientierte Programmiersprache, sondern rein prozedural. Deswegen kann man in C auch keine Objekte im Sinne von Java verwalten.

Trotzdem kann man mit Arrays, Structs und Unions höherwertige Datentypen erzeugen.

C ist nicht objektorientiert ⇒ keine Klassen
Drei Möglichkeiten, höhere Datenstrukturen zu definieren

Arrays: Sammlung von gleichartigen Werten
(→ Java Array)
Structs: Sammlung von Variablen unterschiedlichen Typs
(→ Java Klasse ohne Methoden)
Unions: Mehrere Variablen, aber nur ein Wert zu einer Zeit
(nichts Vergleichbares in Java)

Arrays

Der einfachste, komplexe Datentyp in C ist das Array. Arrays in C sehen denen in Java sehr ähnlich, es gibt aber einige subtile Unterschiede, auf die man als Java-Programmierer schnell hereinfallen kann.

Deklaration über Typ und Anzahl der Elemente
z. B. int werte[100]
Zugriff mit [x]

Indices gehen von 0 – N-1
keine Überprüfung der Grenzen

Werden im Speicher zusammenhängend abgelegt (= Java)
C weiß nicht, wie lang ein Array ist (↔ Java)

nur im deklarierenden Block kann man mit sizeof(a) / sizeof(a[0]) die Größe bestimmen
Programmierer muss die Länge speichern
int x[10]; x[10] = 42; → subtile Fehler (Speicher-Überschreiber)

Die Deklaration von Arrays und der Zugriff auf die Elemente entspricht weitgehend dem Vorgehen in Java.

int i;
int x[3];
x[0] = 1;
x[1] = 2;
x[2] = 3;

for (i = 0; i < 3; i++) {
    printf("%d ", x[i]); /* -> 1 2 3 */
}

Man kann, wie in Java, das Array direkt bei der Deklaration mit deiner Liste {...} initialisieren. Tut man dies, darf man die Länge weglassen, die der Compiler dann selbst aus der Liste ermittelt.

int i;
int x[] = { 1, 2, 3 };
x[2] = 4;

for (i = 0; i < 3; i++) {
    printf("%d ", x[i]); /* -> 1 2 4 */
}

Allerdings überprüft der C-Compiler nicht, ob der Zugriff überhaupt innerhalb der Array-Grenzen liegt:

int x[] = { 1, 2, 3 };
printf("%d ", x[4]); /* undefiniertes Ergebnis, was auch immer im Speicher liegt  */

Deswegen muss man als C-Programmierer*in immer die Länge des Arrays an Funktionen, die man aufruft, mitgeben. Das ist der Grund, warum die main-Funktion die Signatur int main(int, char**) hat, da man andernfalls die Länge der Argumentenliste nicht kennen würde.

Bei der Übergabe an eine Funktion ist die Größe nicht mehr bekannt
Größe muss zusätzlich übergeben werden (sehr häufige Fehlerquelle)

#include <stdio.h>
void listElements(int a[], int len) {
    printf("size in function: %ld\n", sizeof(a) / sizeof(int)); /* -> 2 */
    for (int i = 0; i < len; i++) {
        printf("%d\n", a[i]);
   }
}

int main(int argc, char** argv) {
    int a[] = { 1, 2, 3, 4, 5 };
    printf("size in main: %ld\n", sizeof(a) / sizeof(int)); /* -> 5 */
    listElements(a, 5);
}

Man sieht in dem Beispiel deutlich, dass in der Funktion listElements das Array a nur noch als ein Zeiger vom Typ int* mit 8 Byte Länge vorliegt, sodass sizeof(a) / sizeof(int) 2 ergibt. Die Funktion kann die Länge des Arrays nicht mehr bestimmen und muss sie deshalb als Parameter len übergeben bekommen.

C betrachtet Arrays einfach nur als einen zusammenhängenden Speicherblock. Der Compiler beschafft ausreichend Speicher, um die deklarierten Elemente abzulegen. Bei einem Array T[n] vom Typ T nach der Formel sizeof(T) * n.

Die Array-Variable ist dann – aus Sicht des Compilers – einfach nur ein Zeiger vom Typ T* auf das erste Element des Arrays.

Arrays werden als Zeiger auf das erste Element verwaltet
a ist dasselbe wie &a[0]
Einen Array-Parameter einer Funktion kann man als Array (int a[]) oder Pointer (int* a) deklarieren
Man kann Arrays auch per Pointer-Arithmetik behandeln

int a[] = { 1, 2, 3, 4, 5 };
int *p = &a[0]; /* Pointer auf erstes Element */
int *e; /* Pointer auf aktuelles Element */

for (e = p; e < p + 5; e++) {
    printf("%d\n", *e);
}

Der Code des Beispiels ist identisch mit:

int i;
int a[] = { 1, 2, 3, 4, 5 };

for (i = 0; i < 5; i++) {
    printf("%d\n", a[i]);
}

Aufgrund des Pointer-Characters eines Arrays, sind folgende Konstrukte identisch:

&a[0] ⇔ a
a[0] ⇔ *a
a[i] ⇔ *(a + i)

Dynamische Arrays

Die Größe eines Arrays muss bei der Deklaration (z. B. int x[10]) durch eine Konstante bestimmt sein, da der Compiler bereits den Speicher für das Array reservieren muss. D. h. der Ausdruck SIZE in T v[SIZE] muss eine Konstante zur Compilezeit sein. Kann man die Größe nicht durch eine Konstante ausdrücken, bleibt nur das Array mithilfe von malloc() und free() dynamisch zu erzeugen und zu verwalten.

Die Größe eines Arrays für Deklarationen der Art int a[10] müssen zur Compilezeit bekannt sein
Dynamische Arrays müssen mit malloc oder calloc erzeugt werden

int *a, size = 4;

a = (int*) malloc(sizeof(int) * size); /* Speicher für Array holen */

/* Elemente zuweisen */
a[0] = 1;
a[1] = 2;
*(a + 2) = 3;
*(a + 3) = 4;
/* Array benutzen */
free(a); /* Speicher freigeben */

Das vollständige Programm sieht wie folgt aus:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
    int *a, size = 4;

    a = (int*) malloc(sizeof(int) * size); /* Speicher für Array holen */

    /* Elemente zuweisen */
    a[0] = 1;
    a[1] = 2;
    *(a + 2) = 3;
    *(a + 3) = 4;

    free(a); /* Speicher freigeben */
}

Das Programm hat das Problem, dass es von Hand die Größe des benötigten Speichers per sizeof(int) * size berechnet. Eleganter ist es die calloc-Funktion zu verwenden, die den Speicher auch direkt mit 0x00 füllt und so verhindert, dass man alte Werte im Speicher sieht.

Verwendung von calloc

int *a, size = 4;

a = (int*) calloc(size, sizeof(int)); /* Speicher für Array holen */

/* Elemente zuweisen */
a[0] = 1;
a[1] = 2;
*(a + 2) = 3;
*(a + 3) = 4;

/* Array benutzen */

free(a); /* Speicher freigeben */

Variable Length Arrays (VLA)

Sowohl die statische Größenangabe zur Compilezeit als auch die Programmierung von dynamischen Arrays mit malloc ist teilweise sehr mühsam. Bei malloc kommt noch hinzu, dass eine Allokation auf dem Heap mehr Rechenzeit benötigt, als die Verwendung des Stacks, weil der Speicher auf dem Heap verwaltet werden muss. Es gibt zwar mit alloca eine Möglichkeit dynamisch zur Laufzeit Speicher auf dem Stack zu belegen, diese Funktion ist aber nicht standardisiert und damit nicht auf allen Plattformen verfügbar.

Aus diesem Grund hat C99 eine weitere Möglichkeit eröffnet, Arrays dynamisch zu erstellen und auf dem Stack zu alloziert.

Variable Length Arrays (VLA) – seit C99

Größe des Arrays ist zur Compilezeit noch unbekannt
Speicher wird erst zur Laufzeit auf dem Stack alloziert
können nur Block- oder Funktions-Scope haben
können als Funktionsparameter verwendet werden
kennen, wie normale Arrays, ihre eigene Größe nicht

for (int i = 1; i < 10; i++) {
    int a[i]; /* VLA deklarieren */
    printf("%zu\n", sizeof(a)); /* 4, 8, 12, ... */
}

Das VLAs nicht als globale Variablen existieren können liegt daran, dass für globale Variablen der Platz bereits beim Compilieren im Datensegment reserviert werden muss. Zur Laufzeit kann dieses nicht einfach vergrößert werden.

Eine Größe von 0 ist für VLAs nicht zulässig. Außerdem kann man sie – logischerweise – nicht mit einem Array-Initializer {...} initialisieren, weil die Größe zur Compilezeit nicht bekannt und damit die Anzahl der Elemente im Initializer ebenfalls nicht bestimmt sind.

Der Speicher für VLAs wird auf dem Stack alloziert, sodass man einen plattformübergreifenden Ersatz für die nicht-standardisierte alloca-Funktion bekommt.

VLAs als Funktionsparameter

Größe muss in der Parameterliste vor dem VLA stehen
void f(size_t x, int a[x]) { }
Bei Funktions-Prototypen kann ein * verwendet werden
void f(size_t x, int a[*]);