Wie werden 3D-Arrays in C gespeichert?

Lesezeit: 6 Minuten

Ich verstehe, dass Arrays in C in Zeilenhauptordnung zugewiesen werden. Daher gilt für ein 2 x 3-Array:

0  1
2  3
4  5

Wird im Speicher abgelegt als

0 1 2 3 4 5

Was ist jedoch, wenn ich ein 2 x 3 x 2-Array habe:

0  1
2  3
4  5

und

6  7
8  9
10 11

Wie werden diese im Gedächtnis gespeichert? Ist einfach aufeinanderfolgend wie:

0 1 2 3 4 5 6 7 8 9 10 11

Oder geht es anders? Oder hängt es von etwas ab?

  • Das erste Array in der Frage ist eigentlich 3×2, z int a[3][2];

    – Alexey Kukanov

    7. Mai 2011 um 12:44 Uhr


  • @Alexey: Das ist interessant – vielleicht ist das die Wurzel meiner Verwirrung. Sollten Arrays in C deklariert werden als array[ny][nx] wo ny und nx sind die Anzahl der Elemente in y- und x-Richtung. Bedeutet das außerdem, dass mein 3D-Array als deklariert werden sollte array[nz][ny][nx]?

    – robintw

    7. Mai 2011 um 19:17 Uhr

aroths Benutzeravatar
aroth

Auf einer niedrigen Ebene gibt es so etwas wie ein mehrdimensionales Array nicht. Es gibt nur einen flachen Speicherblock, der groß genug ist, um eine bestimmte Anzahl von Elementen aufzunehmen. In C ist ein mehrdimensionales Array konzeptionell ein Array, dessen Elemente ebenfalls Arrays sind. Also wenn du es tust:

int array[2][3];

Konzeptionell erhalten Sie am Ende:

array[0] => [0, 1, 2]
array[1] => [0, 1, 2]

Dies führt dazu, dass die Elemente zusammenhängend im Speicher angeordnet werden, weil array[0] und array[1] enthalten eigentlich keine Daten, sie sind nur Verweise auf die beiden inneren Arrays. Beachten Sie, dass dies bedeutet, dass nur die [0, 1, 2] Einträge belegen tatsächlich Speicherplatz. Wenn Sie dieses Muster auf die nächste Dimension erweitern, können Sie Folgendes sehen:

int array[2][3][2];

… gibt Ihnen eine Struktur wie:

array[0] => [0] => [0, 1]
            [1] => [0, 1]
            [2] => [0, 1]
array[1] => [0] => [0, 1]
            [1] => [0, 1]
            [2] => [0, 1]

Die weiterhin die Elemente nacheinander im Speicher anordnet (wie oben nur die [0, 1] Einträge belegen tatsächlich Platz im Speicher, alles andere ist nur ein Teil einer Referenz auf einen dieser Einträge). Wie Sie sehen können, wird dieses Muster fortgesetzt, egal wie viele Dimensionen Sie haben.

Und nur so zum Spaß:

int array[2][3][2][5];

Gibt Ihnen:

array[0] => [0] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [1] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [2] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
array[1] => [0] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [1] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [2] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]

Alle “Maße” werden nacheinander im Speicher abgelegt.

In Betracht ziehen

    int arr[4][100][20];

das kannst du sagen arr[1] und arr[2] (vom Typ int[100][20]) sind zusammenhängend
oder das arr[1][42] und arr[1][43] (vom Typ int[20]) sind zusammenhängend
oder das arr[1][42][7] und arr[1][42][8] (vom Typ int) sind zusammenhängend

Benutzeravatar von sje397
sje397

Ja, Sie haben Recht – sie werden nacheinander gespeichert. Betrachten Sie dieses Beispiel:

#include <stdio.h>

int array3d[2][3][2] = {
  {{0, 1}, {2, 3}, {3, 4}},
  {{5, 6}, {7, 8}, {9, 10}}
};

int main()
{
  int i;
  for(i = 0; i < 12; i++) {
    printf("%d ", *((int*)array3d + i));
  }
  printf("\n");
  return 0;
}

Ausgabe:

0 1 2 3 3 4 5 6 7 8 9 10

  • Hallo, ich bin nur neugierig, wie ich dieses 3D-Array als Matrix visualisieren kann und wie es die Elemente zugewiesen hat?

    – bhansa

    24. April 2016 um 9:04 Uhr

Benutzeravatar von Thies Heidecke
Thies Heidecke

Ja, sie werden nur in fortlaufender Reihenfolge gespeichert. Das kannst du so testen:

#include <stdio.h>

int main (int argc, char const *argv[])
{
  int numbers [2][3][4] = {{{1,2,3,4},{5,6,7,8},{9,10,11,12}}
                          ,{{13,14,15,16},{17,18,19,20},{21,22,23,24}}};

  int i,j,k;

  printf("3D:\n");
  for(i=0;i<2;++i)
    for(j=0;j<3;++j)
      for(k=0;k<4;++k)
        printf("%i ", numbers[i][j][k]);

  printf("\n\n1D:\n");
  for(i=0;i<24;++i)
    printf("%i ", *((int*)numbers+i));

  printf("\n");

  return 0;
}

Das bedeutet, dass Zugriffe auf ein multiindiziertes Array mit Dimensionen (N,M,L) wie folgt in eindimensionale Zugriffe umgewandelt werden:

array[i][j][k] = array[M*L*i + L*j + k]

Ich denke, Sie haben Ihre eigene Frage beantwortet. Mehrdimensionale Arrays werden in zeilenweiser Reihenfolge gespeichert.

Siehe Abschnitt 3.3.2.1 der ANSI-C-Spezifikation (es gibt auch ein konkretes Beispiel):

Aufeinanderfolgende tiefgestellte Operatoren bezeichnen ein Mitglied eines mehrdimensionalen Array-Objekts. Wenn E ein n-dimensionales Array ( n = 2) mit Dimensionen ixj “x … x” k ist, dann wird E (anders als ein L-Wert verwendet) in einen Zeiger auf ein ( n – 1)-dimensionales Array umgewandelt mit den Maßen j “x … x” k . Wenn der unäre *-Operator explizit oder implizit als Ergebnis der Subskription auf diesen Zeiger angewendet wird, ist das Ergebnis das ( n -1)-dimensionale Array, auf das gezeigt wird, das selbst in einen Zeiger konvertiert wird, wenn es nicht als Lvalue verwendet wird . Daraus folgt, dass Arrays in der Reihenfolge der wichtigsten Zeilen gespeichert werden (der letzte Index variiert am schnellsten).

Für Ihr Beispiel können Sie es einfach ausprobieren und sehen – http://codepad.org/10ylsgPj

Angenommen, Sie haben ein Array char arr[3][4][5]. Es ist ein Array von 3 Arrays von 4 Arrays von 5 Zeichen.

Nehmen wir der Einfachheit halber an, dass der Wert in arr[x][y][z] ist xyz und in arr[1][2][3] wir speichern 123.

Das Layout im Speicher ist also:

  |  00  01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  16  17  18  19
--+--------------------------------------------------------------------------------   
00| 000 001 002 003 004 010 011 012 013 014 020 021 022 023 024 030 031 032 033 034 
20| 100 101 102 103 104 110 111 112 113 114 120 121 122 123 124 130 131 132 133 134 
40| 200 201 202 203 204 210 211 212 213 214 220 221 222 223 224 230 231 232 233 234

arr[0], arr[1] und arr[2] kommen nacheinander, aber jedes Element in ist vom Typ char[4][5] (das sind die drei Reihen in der Tabelle).

arr[x][0] - arr[x][3] kommen auch nacheinander, und jedes Element in ihnen ist vom Typ char[5] (Das sind die vier Teile jeder Zeile in der Tabelle, 000 – 004 ist ein Element davon arr[0][0] )

arr[x][y][0] - arr[x][y][4] sind 5 Bytes, die hintereinander kommen.

Benutzeravatar von Alexey Kukanov
Alexey Kukanov

Um den Kommentar von OP zur Hauptfrage zu beantworten (es wird etwas lang, also habe ich mich für eine Antwort entschieden, nicht für einen Kommentar):

Sollten Arrays in C deklariert werden als array[ny][nx] wo ny und nx sind die Anzahl der Elemente in y- und x-Richtung. Bedeutet das außerdem, dass mein 3D-Array als deklariert werden sollte array[nz][ny][nx]?

In der Mathematik hat eine MxN-Matrix M Zeilen und N Spalten. Eine übliche Notation für ein Matrixelement ist a(i,j), 1<=i<=M, 1<=j<=N. Die erste Matrix in Ihrer Frage ist also eine 3×2-Matrix.

Tatsächlich unterscheidet sie sich von der Notation, die typischerweise für zB GUI-Elemente verwendet wird. Eine 800×600 Bitmap hat 800 Pixel horizontal (entlang der X-Achse) und 600 Pixel vertikal (entlang der Y-Achse). Wenn einige es als Matrix beschreiben möchten, wäre es in mathematischer Notation eine 600×800-Matrix (600 Zeilen, 800 Spalten).

Jetzt werden mehrdimensionale Arrays in C so im Speicher gespeichert, dass a[i][j+1] ist neben a[i][j] während a[i+1][j] N Elemente entfernt ist. Es wird normalerweise gesagt, dass “der letzte Index am schnellsten variiert” oder oft als “von Zeilen gespeichert”: Eine Zeile (dh Elemente mit demselben ersten Index) in einer zweidimensionalen Matrix wurde zusammenhängend im Speicher platziert, während eine Spalte (gleicher zweiter Index ) bestehen aus weit voneinander entfernt liegenden Elementen. Aus Performancegründen ist es wichtig zu wissen: Der Zugriff auf benachbarte Elemente ist normalerweise viel schneller (aufgrund von HW-Caches usw.), daher sollten beispielsweise verschachtelte Schleifen so organisiert werden, dass die innerste über den letzten Index iteriert.

Zurück zur Frage: Wenn Ihr geistiges Bild (Abstraktion) eines 2D-Arrays das eines Gitters in karthesischen Koordinaten ist, dann können Sie es sich so vorstellen array[NY][NX] in C. Wenn Sie jedoch echte 2D- oder 3D-Daten als Array beschreiben müssen, hängt die Wahl der Indizes wahrscheinlich von anderen Dingen ab: Datenformate, bequeme Notation, Leistung usw. Zum Beispiel, wenn die In-Memory-Darstellung für eine Bitmap ist array[NX][NY] In einem Format, mit dem Sie arbeiten müssen, werden Sie es so deklarieren, und vielleicht müssen Sie nicht einmal wissen, dass die Bitmap sozusagen “transponiert” wird 🙂

1397320cookie-checkWie werden 3D-Arrays in C gespeichert?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy