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

90

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.

Blackbinary
quelle

Antworten:

158

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;  
 }
John Knoeller
quelle
6
Ich denke, diese Antwort ist klarer, besonders für Anfänger ist es besser, keine Funktionen in einer Zeile zu schreiben ... !! Es ist sowieso eine schlechte Übung .. :)
Lipis
2
Diese Antwort ist auch nützlich, wenn Sie einen Compiler (z. B. eingebettete Systeme) haben, der keine ordnungsgemäße Unterstützung für mehrdimensionale Arrays bietet
Alex Marshall
1
Es ist erstaunlich, wie viele Menschen dieselbe Frage richtig beantworten können, aber nur EINER von ihnen sagt es auf eine leicht verständliche Weise. Dies ist eine so einfache Antwort wie es nur geht. John ist jedoch der einzige, der tatsächlich eine gute Antwort darauf gibt. Der Rest ist Müll, der nur von denen leicht verstanden werden kann, die die Antwort bereits kennen. Vielen Dank, John, dass du tatsächlich Englisch statt Alien sprichst. Nur um zu zeigen, wie schlecht manche Leute unterrichten und wie gut Lehrer wie John Knoeller wissen, wie man viel effektiver vereinfacht und kommuniziert als alle anderen.
user2948630
6
Es wäre gut zu zeigen, wie diese Zuordnung invertiert werden kann: Wenn der Index des 1D-Arrays ist alphaund das 2D-Array eine Dimension Nin beide Richtungen mit Indizes hat x, y, dann laut @JohnKnoeller , alpha=x+N*y. Der Weg, dies umzukehren, wäre Einstellung x=alpha%Nund y= (alpha-alpha%N)/N.
Tim
Ich komme fast jeden Tag hierher!
Felipe Gutierrez
23

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.

Ameise
quelle
16

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 ]; }
Kornel Kisielewicz
quelle
1
Ihre MAXXund MAXYWerte werden zum Verwechseln genannt, weil die Maximalwerte xund ysind MAXX - 1und MAXY - 1jeweils. Vielleicht SIZE_Xund SIZE_Yvielleicht besser?
Café
3
[y * maxx + x] ist die Spaltenreihenfolge, nicht die Zeilenreihenfolge. Dies ist die Art und Weise, wie Matlab funktioniert, aber nicht die Art und Weise, wie Arrays normalerweise in C funktionieren.
John Knoeller
@jeder: Wenn Sie nicht die Daten berühren, sondern nur diese beiden Funktionen zum Abrufen / Festlegen verwenden und dieselbe Formel verwenden, können Sie dies wie DIESES oder DAS tun. (Garantiert!)
Imacake
Ein Makro ist hier möglicherweise besser geeignet, damit Sie keine unnötigen Funktionsaufrufe für einen Datenzugriff auf niedriger Ebene stapeln (insbesondere, da die 1d-Indizierung in Pseudo-2d-Arrays manchmal eine Optimierungstechnik ist.
krs013
Angenommen, der Code ist ein Klassenmitglied, wird dieser Code eingefügt. Ansonsten ist explizites Inline VIEL besser als ein Makro.
Kornel Kisielewicz
7

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
Sammy
quelle
3

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);
Anycorn
quelle
1

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.

Kennzeichen
quelle
-2

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 .

Arthur Kalliokoski
quelle