„Array (Datentyp)“ – Versionsunterschied

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.

Die häufigste konkrete 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.

Spezielle Richtfunkantennen benutzen Arrays von Antennen und in der Akustik werden Mikrofonarrays zur Ortung von Schallquellen eingesetzt. RAIDs verwenden Arrays von Festplatten zur sicheren Speicherung von Daten.

(Standard-)Array

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 $\sum _{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)