Algorithmen und Datenstrukturen in C/ Felder

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Wikipedia hat einen Artikel zum Thema:

Ein Feld (oder Array) ist eine statische Datenstruktur, das Daten eines einheitlichen Datentyps speichert. Der Datentyp und die Größe des Feldes können beliebig variieren, müssen aber zur Laufzeit feststehen. Zu unterscheiden ist außerdem zwischen ein- und mehrdimensionalen Feldern.

Der Zugriff auf ein Feld erfolgt über einen ganzzahligen Index. Dies wird auch Adressierung genannt. Es ermöglicht zum Lesen und Schreiben einen beliebigen Zugriff auf die Daten in einem Feld. Ein Datensatz an einem konkreten Index ist ein Element.

Im Umgang mit Feldern muss man beachten, dass diese eine feste Größe haben. Wenn man eine Operation außerhalb der definierten Größe ausführt, kann es zu Speicherfehlern und damit zum Programmabsturz kommen.

Vorteile

  • Operationen und Funktionen mit Feldern sind sehr einfach zu implementieren.
  • Lesen und Schreiben über die Adressierung ist schnell und komfortabel möglich.

Nachteile

  • Die Größe eines Feldes lässt sich zur Laufzeit nicht mehr verändern. Man kann jedoch mit einer dynamischen Speicherverwaltung ein neues Feld erstellen.

Eindimensionale Felder[Bearbeiten]

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

 1 #include <stdio.h>
 2  
 3 void printArray(int* array, int length) {
 4     int i;
 5     
 6     // Feld auslesen
 7     for (i = 0; i < length; i++)
 8         printf("%d ", array[i]);
 9 
10     printf("\n");
11 }
12  
13 int main(void) {
14     int array[10];
15     int i;
16 
17     // Feld mit Zahlen füllen
18     for (i = 0; i < 10; i++)
19         array[i] = i;
20 
21     printArray(array, 10);
22     return 0;
23 }

In der Hauptfunktion wird das Feld array[] mit dem Datentyp Integer und der Größe 10 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

Algorithmen[Bearbeiten]

Einfügen[Bearbeiten]

Um in ein Feld an einer Position etwas einzufügen, müssen alle Elemente rechts von der Einfügeposition 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:

 1 void insertArray(int* array, int length, int value, int pos) {
 2     int i;
 3 
 4     if (pos < length)
 5     {
 6         for (i = length; i > pos; i--)
 7             array[i] = array[i - 1];
 8         array[i] = value;
 9         length++;
10     }
11     else if (pos == length)
12     {
13         array[pos] = value;
14         length++;
15     }
16 }

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[Bearbeiten]

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:

1 void deleteArray(int* array, int length, int index) {
2     int i;
3 
4     if (index < length) {
5         for (i = index + 1; i < length; i++)
6             array[i - 1] = array[i];
7         length--;
8     }
9 }

Suchen[Bearbeiten]

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.

1 int searchArray(int key, int* array, int length) {
2     int i;
3 
4     for (i = 0; i < length; i++)
5         if (array[i] == key)
6             return i;
7  
8     return -1;
9 }

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[Bearbeiten]

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[Bearbeiten]

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:

 1 #include <stdio.h>
 2 
 3 int main(void) {
 4     // Deklaration eines zweidimensionalen Feldes
 5     int array[10][10];
 6     int i, j;
 7 
 8     // Füllen des Feldes mit Zahlen
 9     for (i = 0; i < 10; i++)
10         for (j = 0; j < 10; j++)
11             array[i][j] = i + j;
12     
13     // Ausgabe der Zahlen        
14     for (i = 0; i < 10; i++)
15         for (j = 0; j < 10; j++)
16             printf("%d ", array[i][j]);
17 }

Vierdimensionales Feld:

 1 #include <stdio.h>
 2 
 3 int main(void) {
 4     // Deklaration eines vierdimensionalen Feldes
 5     int array[10][10][10][10];
 6     int i, j, k, l;
 7 
 8     // Füllen des Feldes mit Zahlen
 9     for (i = 0; i < 10; i++)
10         for (j = 0; j < 10; j++)
11             for (k = 0; k < 10; k++)
12                 for (l = 0; l < 10; l++)
13                     array[i][j][k][l] = i + j + k + l;
14     
15     // Ausgabe der Zahlen        
16     for (i = 0; i < 10; i++)
17         for (j = 0; j < 10; j++)
18             for (k = 0; k < 10; k++)
19                 for (l = 0; l < 10; l++)
20                     printf("%d ", array[i][j][k][l]);
21 
22     return 0;
23 }

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[Bearbeiten]

Skalarprodukt zweier Vektoren[Bearbeiten]

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

 1 #include <stdio.h>
 2 #define SIZE 3
 3 
 4 int main(void) {
 5     // Vektoren definieren
 6     int vector_a[SIZE] = {1, 4, 5};
 7     int vector_b[SIZE] = {3, 2, 2};
 8     int i, result = 0;
 9     
10     // Skalarprodukt berechnen
11     for (i = 0; i < SIZE; i++)
12         result += vector_a[i] * vector_b[i];
13     
14     printf("%d", result);
15     
16     return 0;
17 }

Überschreiten der Feldgröße[Bearbeiten]

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.

 1 #include <stdio.h>
 2 
 3 int main(void) {
 4     int a = 1;
 5     int b[1];
 6     int c = 1;
 7 	
 8     // in Speicher schreiben
 9     b[-2] = 2;
10     b[-1] = 2;
11     b[0] = 2;
12     b[1] = 2;
13     b[2] = 2;
14 	
15     printf("Wert von 'a': %d\n", a);
16     printf("Wert von 'c': %d\n", c);
17 		
18     return 0;
19 }

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.