Feld (Datentyp)

Ein Feld (englisch Array [əˈɹeɪ] (Betonung auf 2. Silbe) für ‚Anordnung‘, ‚Aufstellung‘, ‚Reihe‘, ‚Reihung‘, ‚Bereich‘) bezeichnet in der Informatik eine Datenstruktur. Dabei wird zwischen einem Standard-Feld und dem assoziativen Array unterschieden.

Standard-Feld

Mit Hilfe eines Feldes können Daten eines üblicherweise einheitlichen Datentyps so im Speicher eines Computers abgelegt werden, dass ein Zugriff auf die Daten über einen Index möglich wird. Das (Standard-)Feld verwendet im Gegensatz zum assoziativen Feld einen ganzzahligen Index zur Adressierung. Dieser beginnt, bei einem Feld mit N Elementen, standardmäßig je nach Programmiersprache bei 0 (C++: 0,1,2,…,N-1) oder 1 (Fortran: 1,2,3,...,N), kann jedoch oftmals auch frei gewählt werden (42,43,44,…,N+41).

Beispiele

Im Folgenden wird ein symbolischer Beispielcode verwendet (der Startindex sei 1):

• Vektor (eindimensional)

Vektor := (10, -11, 12)

So liefert Vektor[2] den Wert -11.

• Matrix oder Tabelle (zweidimensional)

In einer Matrix werden die waagerechten 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 := 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 Beispielanweisungen 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-)Feld Teil des Sprachumfangs. Die objektorientierten Programmiersprachen können diese Felder als Objekte nachbilden.

Adressierung eines Feldes

Letztlich müssen auch die in einem Feld gespeicherten Elemente in einem linearen Speicher abgelegt werden. Die Elemente eines eindimensionalen Vektors werden hintereinander im Speicher abgelegt, bei einer zweidimensionalen Matrix werden die Elemente entweder als Zeilen- oder als Spaltenvektoren hintereinander abgelegt, bei einem dreidimensionalen Feld werden entsprechend viele Matrizen hintereinander abgelegt, usw.

Speicherabbildungsfunktion

Ein Programm, das auf das Datenfeld oder einzelne Elemente davon zugreifen will, muss die Speicheradresse eines beliebigen Elements in einem Feld errechnen.

In einem n-dimensionalen Feld $A[i_1:k_1, i_2:k_2, \ldots, i_n:k_n]$ wird die Adresse eines Elements a[j₁,j₂,..,j_n] beispielsweise mit Hilfe der Formel $(j_n-i_n) + \sum_{s=1}^{n-1}( (j_s-i_s) \cdot \prod_{t=s+1}^{n} (k_t-i_t+1))$ berechnet. Man nennt diese Formel auch Speicherabbildungsfunktion.

Die dargestellte Formel ist nur eine von mindestens zwei Alternativen, je nachdem, in welcher Reihenfolge die Indices zu Speicherblöcken zusammengefasst werden, vom Ersten hin zum Letzten oder gerade umgekehrt. Im Englischen unterscheidet man hier Row-major order (zeilenweise Anordnung) und Column-major order (spaltenweise Anordnung). Es ist normalerweise Sache der Laufzeitumgebung des jeweiligen Compilers, welche Variante ein Programm verwendet.

Dope-Vektor

Da die Produkte $\prod_{t=s+1}^{n} (\ldots)$ in obiger 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.

Programmeffizienz

Wenn in einem Computer ein solches Feld im RAM gehalten wird, erfolgen Zugriffe auf Feldelemente in der Regel am schnellsten, wenn direkt aufeinander folgende Adressen abgerufen werden. Der Programmierer ist also gehalten, die Reihenfolge der Indices im Feld so festzulegen, dass dies in der innersten Schleife ebenso erfolgt. Da die Speicherabbildungsfunktion vom Compiler abhängt, sollte sich der Programmierer über diese Details informieren und dann im Programm den in der innersten Schleife durchlaufenen Index so definieren, dass er den Einerschritten in der Speicherbelegung entspricht.

Feld in freierer Form

In manchen Programmiersprachen – als Beispiel kann Java dienen – sind Feldinhalte nicht auf Elemente eines einzelnen Datentyps eingeschränkt, es können Objekte oder allgemeine Datenstrukturen fast beliebiger Zusammensetzung und Reihenfolge gespeichert werden. In Java muss auch nicht jede Zeile eines zweidimensionalen Arrays gleich lang sein. Die obigen Adressrechnungen muss die Laufzeitumgebung der jeweiligen Programmiersprache dann entsprechend anders und ggf. aufwändiger gestalten.

Assoziatives Feld

Eine Sonderform bildet das „assoziative Array“. Es verwendet keinen numerischen Index, sondern sogenannte Schlüssel zur Indizierung und damit zur Adressierung der Elemente. Da die Anzahl der Elemente nicht feststeht und diese in undefinierter Reihenfolge enthalten sind, ist es kein echtes Feld. Am häufigsten werden „assoziative Felder“ als Hashtabelle umgesetzt.

Siehe auch

• Liste (Datenstruktur)
• Baum (Graphentheorie)
• Vektorprozessor
• Zuweisungskompatibilität

Weblinks

 Wiktionary: Array – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

 Commons: Array-Datenstruktur – Sammlung von Bildern, Videos und Audiodateien

 Wikibooks: Algorithmen und Datenstrukturen in C/ Felder – Lern- und Lehrmaterialien

• Das Array, unendliche Weiten? – Dimensionen von Arrays auf www.aspheute.com