Feld (Datentyp)

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.

Inhaltsverzeichnis

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[j1,j2,..,jn] 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

Weblinks

Wiktionary Wiktionary: Array – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
 Commons: Array-Datenstruktur – Sammlung von Bildern, Videos und Audiodateien

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Feld — (von althochdeutsch feld ‚offenes, nicht bewaldetes Land‘) bezeichnet in der Automatisierungstechnik den Bereich außerhalb von Schaltschränken, siehe Feldgerät in Bergbau und Bergrecht das Grubenfeld in der Datentechnik ein untergeordnetes… …   Deutsch Wikipedia

  • Datentyp — Formal bezeichnet ein Datentyp in der Informatik die Zusammenfassung von Objektmengen mit den darauf definierten Operationen. Dabei werden durch den Datentyp des Datensatzes unter Verwendung einer so genannten Signatur ausschließlich die Namen… …   Deutsch Wikipedia

  • Ordinaler Datentyp — Formal bezeichnet ein Datentyp in der Informatik die Zusammenfassung von Objektmengen mit den darauf definierten Operationen. Dabei werden durch den Datentyp des Datensatzes unter Verwendung einer so genannten Signatur ausschließlich die Namen… …   Deutsch Wikipedia

  • Primitiver Datentyp — Formal bezeichnet ein Datentyp in der Informatik die Zusammenfassung von Objektmengen mit den darauf definierten Operationen. Dabei werden durch den Datentyp des Datensatzes unter Verwendung einer so genannten Signatur ausschließlich die Namen… …   Deutsch Wikipedia

  • Assoziatives Feld — Das Assoziative Array ist eine Datenstruktur, die – anders als ein echtes Array – nichtnumerische Schlüssel (zumeist Zeichenketten) verwendet, um die enthaltenen Elemente zu adressieren; diese liegen in keiner festgelegten Reihenfolge vor.… …   Deutsch Wikipedia

  • Struktur (Datentyp) — Der Datentyp Struktur (engl. structure) bezeichnet einen Verbund. Durch seine Fähigkeit andere Variablen verschiedener Datentypen zu umfassen, kann eine Struktur zu übersichtlicherem und dynamischem Quelltext verhelfen. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Datentypen — Formal bezeichnet ein Datentyp in der Informatik die Zusammenfassung von Objektmengen mit den darauf definierten Operationen. Dabei werden durch den Datentyp des Datensatzes unter Verwendung einer so genannten Signatur ausschließlich die Namen… …   Deutsch Wikipedia

  • Ordinale Datentypen — Formal bezeichnet ein Datentyp in der Informatik die Zusammenfassung von Objektmengen mit den darauf definierten Operationen. Dabei werden durch den Datentyp des Datensatzes unter Verwendung einer so genannten Signatur ausschließlich die Namen… …   Deutsch Wikipedia

  • Datenstrukturen — In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre… …   Deutsch Wikipedia

  • Win Ali — WinAli ist ein Modell Assembler (siehe auch Assemblersprache) für Windows und DOS. Der generierte Maschinencode wird mit einem Modellrechner ausgeführt, der eine Emulation eines echten Prozessors darstellt. WinAli ist dazu gedacht, um Assembler… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”