Memetakan larik 2D ke larik 1D

Saya ingin mewakili array 2D dengan array 1D. Sebuah fungsi akan melewatkan dua indikasi (x, y) dan nilai yang akan disimpan. Kedua indikasi ini akan mewakili satu elemen dari larik 1D, dan menyetelnya sesuai. Saya tahu array 1D harus memiliki ukuran arrayWidth × arrayHeight, tetapi saya tidak tahu cara mengatur setiap elemen.

Misalnya, bagaimana cara membedakan (2,4,3) dari (4,2,3)? Saya mencoba mengatur array sebagai x * y, tetapi 2 * 4 dan 4 * 2 akan menghasilkan tempat yang sama dalam array dan saya ingin keduanya berbeda.

Anda perlu memutuskan apakah elemen array akan disimpan dalam urutan baris atau urutan kolom dan kemudian konsisten dengannya. http://en.wikipedia.org/wiki/Row-major_order

Bahasa C menggunakan urutan baris untuk array Multidimensi

Untuk mensimulasikan ini dengan array dimensi tunggal, Anda mengalikan indeks baris dengan lebarnya, dan menambahkan indeks kolom sebagai berikut:

 int array[width * height];

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

Rumus umum untuk penghitungan ulang indeks larik 2D menjadi indeks larik 1D adalah

index = indexX * arrayWidth + indexY;

Atau Anda bisa menggunakan

index = indexY * arrayHeight + indexX;

(dengan asumsi bahwa arrayWidthdiukur sepanjang sumbu X, dan arrayHeightsepanjang sumbu Y)

Tentu saja, seseorang dapat menemukan banyak rumus berbeda yang memberikan pemetaan unik alternatif, tetapi biasanya tidak perlu.

Dalam bahasa C / C ++, array multidimensi bawaan disimpan dalam memori sehingga indeks terakhir berubah paling cepat, artinya untuk array yang dideklarasikan sebagai

int xy[10][10];

elemen xy[5][3]segera diikuti oleh xy[5][4]dalam memori. Anda mungkin ingin mengikuti konvensi itu juga, memilih salah satu dari dua rumus di atas bergantung pada indeks mana (X atau Y) yang Anda anggap "terakhir" dari keduanya.

Contoh: kami ingin mewakili larik 2D dengan ukuran SIZE_X dan SIZE_Y. Itu berarti kita akan memiliki MAXY baris berurutan dengan ukuran MAXX. Karenanya fungsi setnya adalah

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

Mendapatkannya adalah:

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

Seperti yang dikatakan orang lain peta C dalam urutan baris

   #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]);
         }
       } 
    } 

Keluaran:

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

menggunakan contoh baris utama:

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);

Penting untuk menyimpan data dengan cara yang dapat diambil dalam bahasa yang digunakan. Penyimpanan bahasa C dalam urutan baris-mayor (semua baris pertama datang pertama, lalu semua baris kedua, ...) dengan setiap indeks berjalan dari 0 hingga dimensinya-1. Jadi urutan larik x [2] [3] adalah x [0] [0], x [0] [1], x [0] [2], x [1] [0], x [1] [ 1], x [1] [2]. Jadi dalam bahasa C, x [i] [j] disimpan di tempat yang sama sebagai entri array 1 dimensi x1dim [i * 3 + j]. Jika data disimpan seperti itu, mudah untuk diambil kembali dalam bahasa C.

Fortran dan MATLAB berbeda. Mereka menyimpan dalam urutan kolom-utama (semua kolom pertama datang lebih dulu, lalu semua baris kedua, ...) dan setiap indeks berjalan dari 1 ke dimensinya. Jadi urutan indeks adalah kebalikan dari C dan semua indeks adalah 1 lebih besar. Jika Anda menyimpan data dalam urutan bahasa C, FORTRAN dapat menemukan X_C_language [i] [j] menggunakan X_FORTRAN (j + 1, i + 1). Misalnya, X_C_language [1] [2] sama dengan X_FORTRAN (3,2). Dalam larik 1 dimensi, nilai data tersebut berada di X1dim_C_language [2 * Cdim2 + 3], yang posisinya sama dengan X1dim_FORTRAN (2 * Fdim1 + 3 + 1). Ingatlah bahwa Cdim2 = Fdim1 karena urutan indeksnya terbalik.

MATLAB sama dengan FORTRAN. Ada sama dengan C kecuali indeks biasanya dimulai dari 1. Bahasa apa pun akan memiliki indeks di salah satu pesanan C atau FORTRAN dan indeks akan mulai dari 0 atau 1 dan dapat disesuaikan untuk mendapatkan data yang disimpan.

Mohon maaf jika penjelasan ini membingungkan, namun menurut saya cukup akurat dan penting untuk diketahui oleh seorang programmer.

Anda harus dapat mengakses array 2d dengan penunjuk sederhana di tempatnya. Array [x] [y] akan diatur dalam pointer sebagai p [0x * width + 0y] [0x * width + 1y] ... [0x * width + n-1y] [1x * width + 0y] dll .