Wie werden mehrdimensionale Arrays im Speicher formatiert?

In C weiß ich, dass ich mit dem folgenden Code ein zweidimensionales Array auf dem Heap dynamisch zuweisen kann:

int** someNumbers = malloc(arrayRows*sizeof(int*));

for (i = 0; i < arrayRows; i++) {
    someNumbers[i] = malloc(arrayColumns*sizeof(int));
}

Dies erzeugt eindeutig ein eindimensionales Array von Zeigern auf eine Reihe separater eindimensionaler Arrays von Ganzzahlen, und “Das System” kann herausfinden, was ich meine, wenn ich danach frage:

someNumbers[4][2];

Aber wenn ich ein 2D-Array statisch deklariere, wie in der folgenden Zeile …:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

…wird eine ähnliche Struktur auf dem Stack erstellt oder hat sie eine völlig andere Form? (dh ist es ein 1D-Array von Zeigern? Wenn nicht, was ist es und wie werden Verweise darauf herausgefunden?)

Außerdem, als ich sagte: “Das System”, was ist eigentlich dafür verantwortlich, das herauszufinden? Der Kern? Oder sortiert es der C-Compiler beim Kompilieren?

Ein statisches zweidimensionales Array sieht aus wie ein Array von Arrays – es ist einfach zusammenhängend im Speicher angeordnet. Arrays sind nicht dasselbe wie Zeiger, aber da Sie sie oft ziemlich austauschbar verwenden können, kann es manchmal verwirrend werden. Der Compiler behält jedoch den Überblick, wodurch alles gut ausgerichtet wird. Sie müssen bei statischen 2D-Arrays, wie Sie sie erwähnen, vorsichtig sein, denn wenn Sie versuchen, eines an eine Funktion zu übergeben, die ein nimmt int ** Parameter, werden schlimme Dinge passieren. Hier ist ein kurzes Beispiel:

int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}};

Im Speicher sieht das so aus:

0 1 2 3 4 5

exakt das Gleiche wie:

int array2[6] = { 0, 1, 2, 3, 4, 5 };

Aber wenn Sie versuchen, zu bestehen array1 zu dieser Funktion:

void function1(int **a);

Sie erhalten eine Warnung (und die App kann nicht richtig auf das Array zugreifen):

warning: passing argument 1 of ‘function1’ from incompatible pointer type

Denn ein 2D-Array ist nicht dasselbe wie int **. Das automatische Zerfallen eines Arrays in einen Pointer geht sozusagen nur “eine Ebene tief”. Sie müssen die Funktion wie folgt deklarieren:

void function2(int a[][2]);

oder

void function2(int a[3][2]);

Alles glücklich zu machen.

Dasselbe Konzept erstreckt sich auf n-dimensionale Arrays. Wenn Sie diese Art von lustigen Geschäften in Ihrer Bewerbung ausnutzen, wird es jedoch im Allgemeinen nur schwieriger zu verstehen. Seien Sie also vorsichtig da draußen.

Die Antwort basiert auf der Idee, dass C das nicht wirklich tut haben 2D-Arrays – es hat Arrays-of-Arrays. Wenn Sie dies erklären:

int someNumbers[4][2];

Du fragst nach someNumbers ein Array aus 4 Elementen sein, wobei jedes Element dieses Arrays vom Typ ist int [2] (was selbst ein Array von 2 ist ints).

Der andere Teil des Rätsels besteht darin, dass Arrays immer zusammenhängend im Speicher angelegt werden. Wenn Sie fragen:

sometype_t array[4];

dann sieht das immer so aus:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_t nebeneinander gelegte Objekte ohne Leerzeichen). Also bei dir someNumbers Array-of-Arrays, sieht es so aus:

| int [2]    | int [2]    | int [2]    | int [2]    |

Und jede int [2] element ist selbst ein Array, das so aussieht:

| int        | int        |

Insgesamt erhalten Sie also Folgendes:

| int | int  | int | int  | int | int  | int | int  |

unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

im Speicher ist gleich:

unsigned char SingleArray[10]={0,1,2,3,4,5,6,7,8,9};

Als Antwort auf Ihre Frage: Beides, obwohl der Compiler den größten Teil der Schwerarbeit übernimmt.

Bei statisch zugewiesenen Arrays ist “The System” der Compiler. Es reserviert den Speicher wie für jede Stapelvariable.

Im Fall des malloc-Arrays ist “The System” der Implementierer von malloc (normalerweise der Kernel). Alles, was der Compiler zuweist, ist der Basiszeiger.

Der Compiler wird den Typ immer so behandeln, wie er deklariert ist, außer in dem Beispiel, das Carl gegeben hat, wo er austauschbare Verwendungen herausfinden kann. Deshalb, wenn Sie in a passieren [][] zu einer Funktion muss davon ausgegangen werden, dass es sich um eine statisch zugewiesene Ebene handelt, wobei davon ausgegangen wird, dass ** Zeiger auf Zeiger ist.

Angenommen, wir haben a1 und a2 wie folgt definiert und initialisiert (c99):

int a1[2][2] = {{142,143}, {144,145}};
int **a2 = (int* []){ (int []){242,243}, (int []){244,245} };

a1 ist ein homogenes 2D-Array mit einfachem kontinuierlichem Layout in Speicher und Ausdruck (int*)a1 wird zu einem Zeiger auf sein erstes Element ausgewertet:

a1 --> 142 143 144 145

a2 wird von einem heterogenen 2D-Array initialisiert und ist ein Zeiger auf einen Wert vom Typ int*dh Dereferenzierungsausdruck *a2 wird zu einem Wert vom Typ ausgewertet int*muss das Speicherlayout nicht kontinuierlich sein:

a2 --> p1 p2
       ...
p1 --> 242 243
       ...
p2 --> 244 245

Trotz völlig unterschiedlicher Speicheranordnung und Zugriffssemantik sieht die Grammatik der Sprache C für Array-Zugriffsausdrücke sowohl für homogene als auch für heterogene 2D-Arrays genau gleich aus:

• Ausdruck a1[1][0] wird Wert holen 144 aus a1 Reihe
• Ausdruck a2[1][0] wird Wert holen 244 aus a2 Reihe

Der Compiler weiß, dass der Zugriffsausdruck für a1 arbeitet nach Art int[2][2]wenn der Zugriffsausdruck für a2 arbeitet nach Art int**. Der generierte Assemblercode folgt der homogenen oder heterogenen Zugriffssemantik.

Der Code stürzt normalerweise zur Laufzeit ab, wenn ein Array vom Typ int[N][M] wird typgecastet und dann als Typ zugegriffen int**zum Beispiel:

((int**)a1)[1][0]   //crash on dereference of a value of type 'int'

Um auf ein bestimmtes 2D-Array zuzugreifen, betrachten Sie die Speicherzuordnung für eine Array-Deklaration, wie im folgenden Code gezeigt:

    0  1
a[0]0  1
a[1]2  3

Um auf jedes Element zuzugreifen, reicht es aus, nur das Array, an dem Sie interessiert sind, als Parameter an die Funktion zu übergeben. Verwenden Sie dann offset for column, um auf jedes Element einzeln zuzugreifen.

int a[2][2] ={{0,1},{2,3}};

void f1(int *ptr);

void f1(int *ptr)
{
    int a=0;
    int b=0;
    a=ptr[0];
    b=ptr[1];
    printf("%d\n",a);
    printf("%d\n",b);
}

int main()
{
   f1(a[0]);
   f1(a[1]);
    return 0;
}