Ordnen Sie ein 2D-Array einem 1D-Array zu

Ich möchte ein 2D-Array mit einem 1D-Array darstellen. Eine Funktion übergibt die beiden Angaben (x, y) und den zu speichernden Wert. Diese beiden Angaben würden ein einzelnes Element eines 1D-Arrays darstellen und entsprechend einstellen. Ich weiß, dass das 1D-Array die Größe arrayWidth × arrayHeight haben muss, aber ich weiß nicht, wie jedes Element festgelegt werden soll.

Wie unterscheide ich beispielsweise (2,4,3) von (4,2,3)? Ich habe versucht, das Array als x * y festzulegen, aber 2 * 4 und 4 * 2 führen zu derselben Stelle im Array, und sie müssen unterschiedlich sein.

Sie müssen entscheiden, ob die Array-Elemente in Zeilen- oder Spaltenreihenfolge gespeichert werden, und dann konsistent sein. http://en.wikipedia.org/wiki/Row-major_order

Die Sprache C verwendet die Zeilenreihenfolge für mehrdimensionale Arrays

Um dies mit einem eindimensionalen Array zu simulieren, multiplizieren Sie den Zeilenindex mit der Breite und fügen den Spaltenindex folgendermaßen hinzu:

 int array[width * height];

 int SetElement(int row, int col, int value)
 {
    array[width * row + col] = value;  
 }

Die typische Formel für die Neuberechnung von 2D-Array-Indizes in 1D-Array-Index lautet

index = indexX * arrayWidth + indexY;

Alternativ können Sie verwenden

index = indexY * arrayHeight + indexX;

(vorausgesetzt, dies arrayWidthwird entlang der X-Achse und arrayHeightentlang der Y-Achse gemessen )

Natürlich kann man sich viele verschiedene Formeln einfallen lassen, die alternative eindeutige Zuordnungen bieten, aber normalerweise ist dies nicht erforderlich.

In C / C ++ - Sprachen werden integrierte mehrdimensionale Arrays im Speicher gespeichert, sodass sich der letzte Index am schnellsten ändert, dh für ein Array, das als deklariert ist

int xy[10][10];

Element xy[5][3]wird sofort xy[5][4]im Speicher gefolgt . Möglicherweise möchten Sie auch dieser Konvention folgen und eine der beiden oben genannten Formeln auswählen, je nachdem, welchen Index (X oder Y) Sie als den "letzten" der beiden betrachten.

Beispiel: Wir möchten ein 2D-Array mit den Größen SIZE_X und SIZE_Y darstellen. Das bedeutet, dass wir MAXY aufeinanderfolgende Zeilen mit MAXX-Größe haben werden. Daher ist die eingestellte Funktion

void set_array( int x, int y, int val ) { array[ x * SIZE_Y + y ] = val; }

Das wäre:

int get_array( int x, int y ) { return array[ x * SIZE_Y + y ]; }

Wie andere gesagt haben C-Karten in Zeilenreihenfolge

   #include <stdio.h>

   int main(int argc, char **argv) {
   int i, j, k;
   int arr[5][3];
   int *arr2 = (int*)arr;

       for (k=0; k<15; k++) {
          arr2[k] = k;
          printf("arr[%d] = %2d\n", k, arr2[k]);
       }

       for (i=0; i<5; i++) {
         for (j=0; j< 3; j++) {
            printf("arr2[%d][%d] = %2d\n", i, j ,arr[i][j]);
         }
       } 
    } 

Ausgabe:

arr[0] =  0
arr[1] =  1
arr[2] =  2
arr[3] =  3
arr[4] =  4
arr[5] =  5
arr[6] =  6
arr[7] =  7
arr[8] =  8
arr[9] =  9
arr[10] = 10
arr[11] = 11
arr[12] = 12
arr[13] = 13
arr[14] = 14
arr2[0][0] =  0
arr2[0][1] =  1
arr2[0][2] =  2
arr2[1][0] =  3
arr2[1][1] =  4
arr2[1][2] =  5
arr2[2][0] =  6
arr2[2][1] =  7
arr2[2][2] =  8
arr2[3][0] =  9
arr2[3][1] = 10
arr2[3][2] = 11
arr2[4][0] = 12
arr2[4][1] = 13
arr2[4][2] = 14

am Beispiel eines Zeilenmajors:

A(i,j) = a[i + j*ld]; // where ld is the leading dimension
                      // (commonly same as array dimension in i)

// matrix like notation using preprocessor hack, allows to hide indexing
#define A(i,j) A[(i) + (j)*ld]

double *A = ...;
size_t ld = ...;
A(i,j) = ...;
... = A(j,i);

Es ist wichtig, die Daten so zu speichern, dass sie in den verwendeten Sprachen abgerufen werden können. C-Sprache speichert in Zeilenreihenfolge (die gesamte erste Zeile steht an erster Stelle, dann die gesamte zweite Zeile, ...), wobei jeder Index von 0 bis zur Dimension 1 läuft. Die Reihenfolge des Arrays x [2] [3] ist also x [0] [0], x [0] [1], x [0] [2], x [1] [0], x [1] [ 1], x [1] [2]. In der Sprache C wird x [i] [j] an derselben Stelle gespeichert wie ein eindimensionaler Array-Eintrag x1dim [i * 3 + j]. Wenn die Daten auf diese Weise gespeichert werden, können sie leicht in der Sprache C abgerufen werden.

Fortran und MATLAB sind unterschiedlich. Sie werden in Spalten-Hauptreihenfolge gespeichert (die gesamte erste Spalte kommt zuerst, dann die gesamte zweite Zeile, ...) und jeder Index läuft von 1 bis zu seiner Dimension. Die Indexreihenfolge ist also umgekehrt zu C und alle Indizes sind 1 größer. Wenn Sie die Daten in der Reihenfolge C speichern, kann FORTRAN X_C_language [i] [j] mit X_FORTRAN (j + 1, i + 1) finden. Zum Beispiel ist X_C_language [1] [2] gleich X_FORTRAN (3,2). In eindimensionalen Arrays liegt dieser Datenwert bei X1dim_C_language [2 * Cdim2 + 3], was der gleichen Position wie bei X1dim_FORTRAN (2 * Fdim1 + 3 + 1) entspricht. Denken Sie daran, dass Cdim2 = Fdim1 ist, da die Reihenfolge der Indizes umgekehrt ist.

MATLAB ist dasselbe wie FORTRAN. Ada ist dasselbe wie C, außer dass die Indizes normalerweise bei 1 beginnen. Jede Sprache hat die Indizes in einer dieser C- oder FORTRAN-Ordnungen und die Indizes beginnen bei 0 oder 1 und können entsprechend angepasst werden, um an die gespeicherten Daten zu gelangen.

Es tut mir leid, wenn diese Erklärung verwirrend ist, aber ich denke, es ist genau und wichtig, dass ein Programmierer sie kennt.

Sie sollten in der Lage sein, mit einem einfachen Zeiger auf das 2d-Array zuzugreifen. Das Array [x] [y] wird im Zeiger als p [0x * Breite + 0y] [0x * Breite + 1y] ... [0x * Breite + n-1y] [1x * Breite + 0y] usw. Angeordnet .