WikiDer > Array

Für die astronomisch Bedeutung des Wortes, insbesondere eine Kombination mehrerer Radioteleskope, sehen Interferometrie.

EIN Array (Englisch für Warteschlange oder Serie) ist am Computerprogrammierung von Computers ein Datenstruktur die aus einer Liste von Elementen besteht. Jedes Element hat einen eindeutigen Index, der dieses Element identifiziert.

Während ein Array eine einfache Datenstruktur ist, können damit mächtige Dinge getan werden. Vektoren in einem mehrdimensionalen Raum kann zum Beispiel mit einem einfachen Array und in einer Sprache wie . implementiert werden perl zum Beispiel Arrays von Verweisen auf Hashes (assoziative Arrays) gemacht werden.

Das einfachste Implementierung eines Arrays, wie in C passiert, ist eine Reihe aufeinanderfolgender Speicherzellen.

Reine Arrays

Ein reines Array hat als Index eine Sammlung aufeinanderfolgender Ganzzahlen oder einen anderen diskreten Datentyp. Die Elemente eines solchen Arrays werden normalerweise sequentiell im Speicher gespeichert. Ein Beispiel für eine reine Array-Sprache ist C. In C und den meisten anderen reinen Array-Sprachen besteht die zusätzliche Anforderung darin, dass Arrays homogen sind, d. h. alle Elemente des Arrays sind gleich Art sein.

Wenn Arrays als eine Reihe aufeinanderfolgender Speicherzellen implementiert sind, ist die Adresse der ich-das Element in einem homogenen Array gegeben durch b(i-1)*s, bei welchem b ist die Startadresse des Arrays und so die Größe (in Speichereinheiten) jedes Elements im Array. Die Effizienz der Indexierung ist also ${Displaystil O(1)}$.

Der Vorteil von (homogenen) reinen Arrays besteht darin, dass die Indizierung sehr effizient implementiert werden kann. Der Nachteil besteht darin, dass jedes Array einen einzelnen zusammenhängenden Speicherblock erfordert. Dies kann zu einer Fragmentierung des Speichers führen.

Es ist auch möglich, ein Array mit a . zu implementieren verlinkte Liste anstelle eines fortlaufenden Speicherblocks. Die effizienteste ist in diesem Fall ${Anzeigestil O(x)}$ Anstatt von ${Displaystil O(1)}$. Die Nachteile einer solchen Implementierung bestehen darin, dass die Indizierung weniger effizient ist und mehr Speicher benötigt wird (mindestens ein zusätzlicher Zeiger für jedes Element). Der Vorteil ist, dass eine solche Implementierung flexibler ist: Arrays müssen nicht homogen sein, sondern können auch dynamisch sein.

Assoziative Arrays

sehen Assoziatives Array für den Hauptartikel zu diesem Thema.

Für ein assoziatives Array gibt es weniger Einschränkungen beim Index: Es dürfen nicht diskrete Werte als Index verwendet werden. Außerdem muss in vielen Sprachen mit assoziativen Arrays der Index nicht homogen sein: die Indexwerte müssen nicht gleich sein Art sein. Beispiele für Sprachen mit assoziativen Arrays sind PHP, perl und Javascript.

Assoziative Arrays werden im Allgemeinen mit implemented Hashtabellen und sind in der Praxis immer dynamisch.

Dynamische Arrays

Ein dynamisches Array kann die Länge ändern. Dies kann implizit erfolgen, indem Elemente hinzugefügt oder entfernt werden, oder explizit mithilfe eines speziellen Syntaxkonstrukts (wie z ReDim-Anweisung in Visual Basic). Andere Sprachen, die dynamische Arrays unterstützen, sind zum Beispiel Perl undl lispeln.

Beispiel in C

Beispiel für ein Array von ganzen Zahlen im Programmiersprache C:

int-Array [2]; // Ein Array mit 2 ganzen Zahlen (keines der Elemente hat (noch) einen Wert) array[0] = 1; // Gibt das allererste Element im Array zurück value 1array[1] = 3; // Gibt das zweite Element im Array-Wert zurück 3

Der Name des Arrays ist "array" und die im Array gespeicherten Werte sind 1 und 3. Diese Werte können jetzt mit verwendet werden Array[0] und Array[1]. In einigen Programmiersprachen (z.B. C oder PHP) ist der Index des ersten Wertes im Array, in anderen Programmiersprachen ist dies 1. Es gibt auch Sprachen, bei denen man die Untergrenze selbst bestimmen kann (zum Beispiel perl).

Mehrdimensionale Arrays

Ein zweidimensionales Array, bei dem jedes Element im Array ein Array für sich ist

Das oben erwähnte Beispiel ist ein eindimensionales Array, auch genannt Vektor erwähnt. In vielen Programmiersprachen ist es auch möglich, mehrdimensionale Arrays zu verwenden. Ein zweidimensionales Array heißt auch a Matrix erwähnt.

Es gibt mehrere Möglichkeiten, ein mehrdimensionales Array im Computerspeicher darzustellen. Eine Möglichkeit besteht darin, ein Array mit zu erstellen Zeiger zu anderen Arrays (siehe Bild). Wenn wir uns ein zweidimensionales Array als Tabelle mit Zeilen und Spalten vorstellen, dann sind die Zeilen separate Arrays. Dies hat den Vorteil, dass die Zeilen nicht alle gleich lang sein müssen (das sogenannte 'jagged Array'); die Länge kann sogar dynamisch angepasst werden.

Eine andere Möglichkeit besteht darin, die Zeilen sequentiell als Elemente in einem eindimensionalen Array zu speichern. Ein zweidimensionales Array mit ich Reihen und nein Spalten werden dann eindimensional groß ich×nein. Die erste Zeile wird dann in den Elementen 1 bis gespeichert nein, die zweite in den Elementen nein 1 bis 2nein, etc. Der Vorteil dieser Darstellung liegt in der Geschwindigkeit: Alle Elemente liegen zusammen im Speicher, es müssen keine Zeiger auf andere Teile des Speichers verfolgt werden.

In beiden Fällen ist die Erweiterung auf dreidimensionale und mehrdimensionale Arrays möglich, indem ein Array aus zweidimensionalen Arrays erstellt wird usw.

Array-Unterstützung in einigen Sprachen

Eine Liste der Array-Unterstützung in einigen Sprachen:

C

Nur reine, homogene, nicht dynamische Arrays. Diese werden notwendigerweise als sequenzieller Speicherblock implementiert, da C eine Eins-zu-Eins-Zuordnung zwischen Arrays und . ist Zeigermanipulation spezifiziert.

Pascal

Nur reine, homogene, nicht dynamische Arrays. Diese können im Gegensatz zu C nicht mit Zeigern manipuliert werden.

perl, Python, Rubin

Sowohl reine, heterogene, dynamische Arrays (Listen) als assoziative Arrays (hashes).

C und Java

Reine, homogene, nicht dynamische Arrays. C bietet Unterstützung für dynamische und assoziative Arrays über die STL und Java über die Standardbibliothek. Darüber hinaus ist es in beiden Sprachen möglich, heterogene Arrays zu imitieren mit Behälter.

PHP, Javascript und lua

Nur assoziative Arrays, die auch als reguläre Arrays verwendet werden können.

Haskell

Reine und assoziative Arrays gehören zur Standardbibliothek.

Nicht-reine funktionale Sprachen wie OCaml

Reine, homogene, dynamische Arrays und assoziative Arrays.

Siehe die Kategorie Datenstruktur des Arrays von Wikimedia Commons für Mediendateien zu diesem Thema.