Algorithmen und Datenstrukturen in C/ Felder

Wikipedia hat einen Artikel zum Thema:

Feld (Datentyp)

Ein Feld (oder Array) ist eine Datenstruktur, die mehrere Elemente eines Datentyps fortlaufend im Speicher anordnet. Die Größe des Feldes ist beliebig wählbar, muss jedoch zum Übersetzungszeitpunkt feststehen. Eine Änderung der Größe zur Laufzeit ist nicht möglich. Als Datentyp kann jeder in C gültige Typ benutzt werden, auch Strukturen. Zu unterscheiden ist außerdem zwischen ein- und mehrdimensionalen Feldern.

Auch bei dynamisch erzeuten Feldern kann die Feldgröße nach der Erstellung nicht mehr geändert werden. Hier müsste ein neues, größeres Feld angelegt, die Elemente umkopiert und der Speicher des alten Feldes freigegeben werden.

Der Zugriff auf ein Element eines Feldes erfolgt über einen ganzzahligen Index. Das erste Element hat den Index 0! Für ein Feld mit 100 Elementen darf der Index also die Werte von 0 bis 99 annehmen! Vorsicht! Indexfehler bei Feldzugriffen kommen häufig vor und werden vom C-Compiler nicht beanstandet! Wenn man eine Operation außerhalb der Feldgröße ausführt, kann es zu Speicherfehlern und zum Programmabsturz kommen.

Vorteile

Zugriffe auf Elemente eines Arrays erfolgen in konstanter Laufzeit.
Ungeordneter Zugriff auf Elemente eines Arrays ist einfach und effizient möglich.

Nachteile

Die Größe eines Feldes lässt sich zur Laufzeit nicht mehr verändern.

Eindimensionale Felder

Das folgende Beispiel zeigt, wie man ein eindimensionales Feld aufbaut und ausgibt:

#include <stdio.h>

#define ARR_SIZE 10
 
void printArray(int* array, int length)
{
    int i;
    
    // Feld auslesen
    for (i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}
 
int main(void)
{
    int array[ARR_SIZE];
    int i;

    // Feld mit Zahlen füllen
    for (i = 0; i < ARR_SIZE; i++)
    {
        array[i] = i;
    }

    printArray(array, ARR_SIZE);
    return 0;
}

In der Hauptfunktion wird das Feld array[] vom Datentyp Integer und einer Größe von zehn Elementen erstellt. Das Feld wird mit den Zahlen 0 bis 9 gefüllt. Anschließend wird das Feld durch die Funktion printArray() ausgegeben:

0 1 2 3 4 5 6 7 8 9

In diesem Beispiel entspricht die Zahl in jedem Element seinem Index. Der Index i eines Feldes der Größe N ist immer 0 <= i < N bzw. 0 <= i <= (N - 1).

Algorithmen

Einfügen

Um in ein Feld, das bereits teilweise fortlaufend mit Daten gefüllt ist, an einer Position ein Datum einzufügen, müssen alle Elemente rechts von der Einfügeposition um eins nach rechts geschoben werden:

0 1 2 4 5 6 7 8 9
      ^ Einfügeposition i=3 für Zahl 3
0 1 2   4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

Alternativ kann man natürlich auch an das Ende einfügen. Folgende Funktion deckt beide Möglichkeiten ab:

void insertArray(int* array, int length, int value, int pos) {
    int i;

    if (pos < length)
    {
        for (i = length; i > pos; i--)
            array[i] = array[i - 1];
        array[i] = value;
        length++;
    }
    else if (pos == length)
    {
        array[pos] = value;
        length++;
    }
}

Wenn die Einfügeposition index kleiner ist als die Anzahl der Zahlen length im Feld array[] dann schiebe alle Elemente ab Einfügeposition nach recht und füge das neue Element mit value ein. Sonst hänge das Element an das Ende des Feldes.

Löschen

Möchte man ein Element aus dem Feld löschen, so genügt es, alle Elemente rechts um eine Position nach links zu verschieben und die Anzahl der vorhandenen Elemente im Feld um eines zu vermindern. Etwa so:

0 1 2 3 4 5 6 7 8 9
    ^ Element i=2 löschen
0 1 3 4 5 6 7 8 9

Hier ist der Algorithmus:

void deleteArray(int* array, int length, int index) {
    int i;

    if (index < length) {
        for (i = index + 1; i < length; i++)
            array[i - 1] = array[i];
        length--;
    }
}

Suchen

Folgender Algorithmus der linearen Suche ist für ein kleines Feld anwendbar. Ab einer gewissen Anzahl von Elementen im Feld ist es ratsam, einen der schnelleren Suchalgorithmen zu verwenden.

int searchArray(int key, int* array, int length) {
    int i;

    for (i = 0; i < length; i++)
        if (array[i] == key)
            return i;
 
    return -1;
}

Jedes Element im Feld array[] wird mit key verglichen. Wenn der Vergleich stimmt, wird der Index des Elementes zurück gegeben. Wird kein Element gefunden, wird -1 zurück gegeben.

Sortieren

Zum Sortieren von Zahlen in Feldern gibt es einen ganzen Haufen an Algorithmen. Detailierte Erklärungen mit Beispielen finden sich im dazugehörigen Kapitel Sortieralgorithmen.

Mehrdimensionale Felder

Theoretisch lassen sich Felder mit unendlich vielen Dimensionen erstellen. Jedoch verweigert der Compiler bereits sehr früh die Kompilierung. Der Speicherbedarf steigert sich exponentiell. Von einem Feld mit mehr als vier Dimensionen ist bereits dringend abzuraten.

Zweidimensionales Feld:

#include <stdio.h>

int main(void) {
    // Deklaration eines zweidimensionalen Feldes
    int array[10][10];
    int i, j;

    // Füllen des Feldes mit Zahlen
    for (i = 0; i < 10; i++)
        for (j = 0; j < 10; j++)
            array[i][j] = i + j;
    
    // Ausgabe der Zahlen        
    for (i = 0; i < 10; i++)
        for (j = 0; j < 10; j++)
            printf("%d ", array[i][j]);
}

Vierdimensionales Feld:

#include <stdio.h>

int main(void) {
    // Deklaration eines vierdimensionalen Feldes
    int array[10][10][10][10];
    int i, j, k, l;

    // Füllen des Feldes mit Zahlen
    for (i = 0; i < 10; i++)
        for (j = 0; j < 10; j++)
            for (k = 0; k < 10; k++)
                for (l = 0; l < 10; l++)
                    array[i][j][k][l] = i + j + k + l;
    
    // Ausgabe der Zahlen        
    for (i = 0; i < 10; i++)
        for (j = 0; j < 10; j++)
            for (k = 0; k < 10; k++)
                for (l = 0; l < 10; l++)
                    printf("%d ", array[i][j][k][l]);

    return 0;
}

Die Algorithmen für den Umgang mit mehrdimensionalen Feldern funktionieren genau wie die für eindimensionale Felder. Man muss sie lediglich um die entsprechenden Dimensionen erweitern.

Beispiele

Skalarprodukt zweier Vektoren

In diesem Beispiel werden zwei Vektoren in einem eindimensionalen Feld gespeichert. Anschließend wird das Skalarprodukt berechnet und ausgegeben.

#include <stdio.h>
#define SIZE 3

int main(void) {
    // Vektoren definieren
    int vector_a[SIZE] = {1, 4, 5};
    int vector_b[SIZE] = {3, 2, 2};
    int i, result = 0;
    
    // Skalarprodukt berechnen
    for (i = 0; i < SIZE; i++)
        result += vector_a[i] * vector_b[i];
    
    printf("%d", result);
    
    return 0;
}

Überschreiten der Feldgröße

Ein weiteres Beispiel für den Umgang mit Feldern in C ist das absichtliche Überschreiten der Feldgröße um andere Daten im Speicher zu manipulieren.
Es werden zwei Variablen a und c sowie ein Feld b mit der Größe 1 definiert. Die Variablen haben den Wert 1. Nun wird auf über den Index des Feldes b auf den Speicher links und rechts neben dem Feld zugegriffen. Dort befinden sich auch die Variablen a und c. Durch die folgende Zuweisung bekommen die beiden Variablen jetzt ebenfalls den Wert 2.

#include <stdio.h>

int main(void) {
    int a = 1;
    int b[1];
    int c = 1;
	
    // in Speicher schreiben
    b[-2] = 2;
    b[-1] = 2;
    b[0] = 2;
    b[1] = 2;
    b[2] = 2;
	
    printf("Wert von 'a': %d\n", a);
    printf("Wert von 'c': %d\n", c);
		
    return 0;
}

Als Ausgabe kann kommen:

Wert von 'a': 2
Wert von 'c': 2

Sobald der Compiler jedoch anfängt mit optimieren, landen a und c in CPU Registern und man überschreibt seinen eigenen Stack und somit die Rücksprungadresse. Der große Crash ist programmiert. Daher sind solche Tricksereien nicht zu empfehlen.