Array (Datentyp)

Ein Array [əˈɹeɪ] (engl.: Anordnung, Aufstellung, Reihe, Reihung, Feld, Bereich), zu deutsch Feld, ist der Sammelbegriff für eine Anordnung, Aufstellung, Reihe von gleichen Elementen in festgelegter Art und Weise.

Verwendung findet der Begriff Array als Beschreibung für eine Datenstruktur in der Informatik. Dabei wird zwischen dem (Standard-)Array und dem assoziativen Array unterschieden. RAIDs verwenden Arrays von Festplatten zur sicheren Speicherung von Daten.

Arrays aus Strahlungssensoren werden u.a. in CCD- und CMOS-Bildsensoren, in sogenannten Focal Plane Arrays aus Infrarot-Fotodioden oder Mikrobolometern als Bildsensor für sichtbares Licht und Infrarot verwendet.

Spezielle Richtfunk-Antennen benutzen Arrays von Antennen (Phased Array Antenne).

In der Akustik werden Mikrofonarrays zur Ortung von Schallquellen eingesetzt.

Array in der Informatik

Mit Hilfe eines Arrays können Daten eines einheitlichen Datentyps geordnet so im Speicher eines Computers abgelegt werden, dass ein Zugriff auf die Daten über einen Index möglich wird. Das (Standard-)Array verwendet im Gegensatz zum assoziativen Array einen ganzzahligen Index zur Adressierung.

Beispiele

Im folgenden wird ein symbolischer Beispielcode verwendet:

Vektor (Eindimensional)

Vektor = (10, -11, 12)

So liefert Vektor(2) den Wert -11 (hier wird die Zahl 1 als Startindex definiert; in der Praxis ist es meistens 0).

Matrix oder Tabelle (Zweidimensional)

In einer Matrix werden die waagrechten Einträge (Felder, Zellen) als Zeilen, die Senkrechten als Spalten bezeichnet. Ein einzelnes Element ist also durch Nennung von Zeile und Spalte eindeutig bezeichnet (adressiert). Üblich ist die Adressierung über ein Tupel (0,0) oder A1 für Spalte A, Zeile 1.

Schachfeld is array(8,8) of String

array definiert die Anordnung der Einträge, of den Typ des Eintrags

Schachfeld = ("Turm_W","Springer_W","Läufer_W", … ,"Turm_W",
              "Bauer_W,"Bauer_W"   ,"Bauer_W" , … ,"Bauer_W",
              "Leer"  ,"Leer",     ,"Leer"    , … ,"Leer",
              "Leer"  ,"Leer",     ,"Leer"    , … ,"Leer",
              "Leer"  ,"Leer",     ,"Leer"    , … ,"Leer",
              "Leer"  ,"Leer",     ,"Leer"    , … ,"Leer",
              "Bauer_S,"Bauer_S"   ,"Bauer_S" , … ,"Bauer_S",
              "Turm_S","Springer_S","Läufer_S", … ,"Turm_S")

Die Beispielsanweisungen Schachfeld(3,3) := Schachfeld (1,2) und Schachfeld(1,2) := "Leer" liefern den Eröffnungszug „Weißer Springer auf C3“.

In den meisten höheren Programmiersprachen ist das (Standard-)Array Teil des Sprachumfangs. Die objektorientierten Programmiersprachen können diese Arrays als Objekte nachbilden.

Adressierung eines Arrays

Da letztlich auch die in einem Array gespeicherten Elemente in einem linearen Speicher abgelegt werden müssen, gibt es die Möglichkeit über den so genannten Dope-Vektor die Speicheradresse eines beliebigen Elements in einem Array zu errechnen.

In einem $n$ -dimensionalen Array $A[i_{1}:k_{1},i_{2}:k_{2},\ldots ,i_{n}:k_{n}]$ wird die Adresse eines Elements $a[j_{1},j_{2},..,j_{n}]$ mit Hilfe der Formel $\sum _{s=1}^{n-1}((j_{s}+i_{s})\cdot \prod _{t=s+1}^{n}(k_{t}-i_{t}+1))$ berechnet.

Da die Produkte $\prod _{t=s+1}^{n}(\ldots )$ in dieser Formel konstant sind, können sie einmalig berechnet werden und der daraus resultierende Dope-Vektor d ermöglicht dann über die Formel $\deg _{t=1}^{n}(j_{t}+i_{t})\cdot d_{t}$ eine sehr schnelle Berechnung der Adresse eines jeden gespeicherten Elements.

Assoziatives Array

Eine Sonderform bildet das assoziative Array. Es verwendet keinen numerischen Index, sondern einen so genannten Schlüssel zur Indizierung und damit zur Adressierung eines Elements. Am häufigsten werden assoziative Arrays als Hashtabelle umgesetzt.

Implementierung

Hier folgen Tipps zur Implementierung:

Zeiger und Arrays

Naheliegend wäre, dass die einzelnen Arrayelemente direkt hintereinander im Speicher abgelegt sind. Das ist zumindest bei „hardwarenahen“ Programmiersprachen tatsächlich der Fall. Man sieht (vor allem in C) oft Konstrukte, bei denen mit Zeigern auf Arrays zugegriffen wird. Ein kleines Beispiel in C soll diese Thematik verständlich erläutern:

  /* Ein Array mit der Länge 5 vom Typ Integer (Ganzzahl) anlegen */
  int iArray[5];
  /* Eine Zeigervariable, die auf einen Integer-Wert im Speicher zeigen kann */
  int *zeiger;
  /* Eine Integer-Variable als Zähler für die Zählschleife */
  int i;
  
  /* Array mit Beispieldaten (Ganze Zahlen von 10 bis 15) füllen */
  for(i=10;i<15;i++)
     iArray[i-10] = i;
  
  /* Adresse des Zeigers auf Adresse des 3. Arrayelementes setzen */
  zeiger = &(iArray[3]);
  
  /* Ausgabe der Speicherzelle, die um "1 Einheit" */
  /* (= Länge einer Integervariable) nach der Adresse des Zeigers steht */
  printf("%d\n", *(zeiger+1));
  
  /* Andere Ausgaben */
  printf("%d\n", *zeiger);
  printf("%d\n", *(zeiger-1));

Dieses Programm gibt folgendes aus:

  14
  13
  12

Siehe auch

Liste (Datenstruktur)
Baum (Graphentheorie)
Mikrofonarray (Mikrofonanordnung und wird auch Beamformer oder akustische Kamera genannt)
Microarray (Sammelbezeichnung für moderne molekularbiologische Untersuchungssysteme)