Array 2D di C: array multidimensi, tata letak memori, dan matriks

Array multidimensi adalah array yang elemen-elemennya juga berupa array. int grid[3][4]; bukan tipe grid khusus: itu tiga elemen, masing-masing berupa array berisi empat int, yang disimpan berurutan. Begitu ini dipahami, sisa topiknya mengikuti: tata letaknya, aritmetika indeksnya, dan aturan yang tadinya membingungkan soal mengirimnya ke fungsi.

Dua dimensi sudah mencakup hampir semua kebutuhan praktis, seperti grid, tabel, matriks, papan permainan, dan gambar, jadi itulah yang dipakai di halaman ini.

Deklarasi dan inisialisasi

int grid[3][4];        // 3 rows, 4 columns - 12 ints

Angka pertama adalah jumlah baris, yang kedua jumlah kolom. Inisialisasinya bisa ditulis datar atau dengan kurung kurawal di dalam; kurung kurawal itu layak dipakai karena memperlihatkan bentuknya.

#include <stdio.h>

int main(void) {
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};   // braced by row - clearest
    int b[2][3] = {1, 2, 3, 4, 5, 6};       // flat - same result
    int c[2][3] = {{1, 2}, {4}};            // partial rows: rest are zero
    int d[2][3] = {0};                      // every element zero
    int e[][3]  = {{1, 2, 3}, {4, 5, 6}};   // rows deduced, columns required

    printf("a: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", a[i][j]);
    printf("\nb: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", b[i][j]);
    printf("\nc: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", c[i][j]);
    printf("\nd: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", d[i][j]);
    printf("\ne: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", e[i][j]);
    printf("\n");

    return 0;
}

Bentuk int e[][3] itu penting: kamu boleh mengosongkan jumlah baris dan membiarkan inisialisasinya yang menentukan, tapi jumlah kolom tidak pernah opsional. Bagian berikutnya menjelaskan alasannya.

Tata letak row-major

C menyimpan array 2D dalam urutan row-major: seluruh baris 0, lalu seluruh baris 1, dan seterusnya, dalam satu blok memori yang tidak terputus. Tidak ada array berisi pointer-pointer baris di belakang layar.

int grid[3][4] = {{ 1, 2, 3, 4},
                  { 5, 6, 7, 8},
                  { 9,10,11,12}};

how you picture it            how it actually sits in memory
+----+----+----+----+
|  1 |  2 |  3 |  4 |   row 0   +--+--+--+--+--+--+--+--+--+--+--+--+
+----+----+----+----+           | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|
|  5 |  6 |  7 |  8 |   row 1   +--+--+--+--+--+--+--+--+--+--+--+--+
+----+----+----+----+            \__ row 0 __/\__ row 1 __/\_ row 2 _/
|  9 | 10 | 11 | 12 |   row 2
+----+----+----+----+           grid[i][j] is at element index i*4 + j

Rumus itu, i * columns + j, adalah seluruh mekanismenya, dan karena itulah compiler harus tahu jumlah kolom untuk mengindeks apa pun. Jumlah baris tidak pernah ikut dalam perhitungannya.

Kamu bisa melihat tata letaknya langsung dengan mencetak alamatnya:

#include <stdio.h>

int main(void) {
    int grid[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

    printf("element addresses, in memory order:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            printf("grid[%d][%d] = %2d at %p\n", i, j, grid[i][j], (void *)&grid[i][j]);
        }
    }

    // the same block read as one flat run of 12 ints
    printf("\nflattened: ");
    int *flat = &grid[0][0];
    for (int k = 0; k < 12; k++) {
        printf("%d ", flat[k]);
    }
    printf("\n");

    return 0;
}

Alamatnya naik sebesar sizeof(int) tanpa celah, termasuk di tempat satu baris berakhir dan baris berikutnya dimulai. Loop yang diratakan membuktikannya: flat[k] menelusuri kedua belas elemen sebagai satu deretan.

Tata letak ini juga punya konsekuensi performa yang perlu diketahui: melakukan perulangan per baris lalu per kolom menyentuh memori secara berurutan, dan itu disukai cache CPU. Menukar urutan loop sehingga loop dalam menuruni sebuah kolom akan melompat sejauh satu baris penuh setiap kali, dan bisa berjalan beberapa kali lebih lambat untuk array yang besar.

Nested loop

Dua dimensi butuh dua for loop: loop luar memilih baris, loop dalam menyapu kolom-kolom di baris itu.

#include <stdio.h>

#define ROWS 3
#define COLS 4

int main(void) {
    int grid[ROWS][COLS];

    // fill with a multiplication table
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            grid[i][j] = (i + 1) * (j + 1);
        }
    }

    // print it as a table
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%4d", grid[i][j]);
        }
        printf("\n");
    }

    // row totals and a grand total
    int grand = 0;
    printf("\nrow totals: ");
    for (int i = 0; i < ROWS; i++) {
        int rowSum = 0;
        for (int j = 0; j < COLS; j++) {
            rowSum += grid[i][j];
        }
        grand += rowSum;
        printf("%d ", rowSum);
    }
    printf("\ngrand total: %d\n", grand);

    return 0;
}

Beri nama penghitungnya sesuai artinya (i/row untuk baris, j/col untuk kolom) dan jaga urutannya tetap konsisten: grid[row][col] di mana-mana. Separuh dari semua bug array 2D adalah pasangan indeks yang tertukar.

Ukuran yang ditulis dengan #define juga bukan hiasan: batas loop dan deklarasinya sekarang tidak bisa jadi tidak sinkron saat kamu mengubah bentuknya.

Mengirim array 2D ke fungsi

Inilah aturan yang menjebak semua orang: parameter fungsi harus menyebutkan jumlah kolom.

#include <stdio.h>

#define COLS 4

// the column size is required; the row count comes as a separate argument
void print_grid(int grid[][COLS], int rows) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%4d", grid[i][j]);
        }
        printf("\n");
    }
}

// exactly the same parameter, written as the pointer it really is
void scale_grid(int (*grid)[COLS], int rows, int factor) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < COLS; j++) {
            grid[i][j] *= factor;
        }
    }
}

int main(void) {
    int grid[3][COLS] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

    print_grid(grid, 3);
    scale_grid(grid, 3, 10);
    printf("\nafter scaling:\n");
    print_grid(grid, 3);

    return 0;
}

Alasannya adalah decay. Mengirim grid mengubahnya menjadi pointer ke elemen pertamanya, dan elemennya adalah baris, jadi tipenya int (*)[4]: pointer ke array berisi 4 int. Agar grid[i][j] punya arti, compiler harus tahu seberapa panjang satu baris, dan itulah angka 4. Jumlah baris memang tidak ada di tipenya, dan karena itulah jumlah baris dikirim sebagai argumen terpisah.

Perhatikan bahwa int (*grid)[COLS] dan int grid[][COLS] adalah parameter yang sama yang ditulis dengan dua cara. Tanda kurungnya wajib, karena int *grid[COLS] justru berarti array berisi pointer. Perbedaan itu dibahas di halaman pointer dan array.

Kalau jumlah kolom baru diketahui saat runtime, parameter variably-modified dari C99 memungkinkanmu mengirimnya lebih dulu:

void print_any(int rows, int cols, int grid[rows][cols]);

rows dan cols harus dideklarasikan sebelum parameter array yang memakainya. Kalau fitur itu tidak tersedia, alternatif yang umum adalah array 1D datar ditambah aritmetika indeks manual:

#include <stdio.h>
#include <stdlib.h>

// treat a flat block as rows x cols and do the arithmetic yourself
void print_flat(const int *data, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%4d", data[i * cols + j]);
        }
        printf("\n");
    }
}

int main(void) {
    int rows = 2, cols = 5;

    int *data = malloc((size_t)rows * cols * sizeof *data);
    if (data == NULL) return 1;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            data[i * cols + j] = i * 10 + j;
        }
    }

    print_flat(data, rows, cols);
    free(data);
    return 0;
}

data[i * cols + j] persis seperti yang ditulis compiler untukmu di kasus ukuran tetap. Melakukannya sendiri hanya butuh satu baris dan bekerja untuk bentuk apa pun yang ditentukan saat runtime.

Contoh matriks

Perkalian matriks menyatukan seluruh isi halaman ini: tiga nested loop di atas penyimpanan row-major.

#include <stdio.h>

#define N 3

void multiply(const int a[][N], const int b[][N], int out[][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int total = 0;
            for (int k = 0; k < N; k++) {
                total += a[i][k] * b[k][j];
            }
            out[i][j] = total;
        }
    }
}

void print_matrix(const char *label, const int m[][N]) {
    printf("%s\n", label);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%5d", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main(void) {
    int a[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int b[N][N] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}};
    int product[N][N] = {0};

    print_matrix("A:", a);
    print_matrix("B:", b);

    multiply(a, b, product);
    print_matrix("A x B:", product);

    // transpose A in place
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {     // start at i+1 to swap each pair once
            int temp = a[i][j];
            a[i][j] = a[j][i];
            a[j][i] = temp;
        }
    }
    print_matrix("A transposed:", a);

    return 0;
}

Ada dua detail yang layak ditiru. Loop k di bagian dalam memasangkan a[i][k] dengan b[k][j]: satu indeks menelusuri baris, yang lain menelusuri kolom. Lalu transpose memulai loop dalamnya dari j = i + 1: kalau dimulai dari 0, setiap pasangan akan ditukar dua kali dan matriksnya tidak berubah.

Tiga dimensi dan seterusnya

Polanya berlanjut, begitu juga aturan soal parameter fungsi: setiap dimensi kecuali yang pertama harus dideklarasikan.

#include <stdio.h>

int main(void) {
    // 2 layers, 3 rows, 4 columns
    int cube[2][3][4] = {0};

    for (int z = 0; z < 2; z++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 4; j++) {
                cube[z][i][j] = z * 100 + i * 10 + j;
            }
        }
    }

    for (int z = 0; z < 2; z++) {
        printf("layer %d:\n", z);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 4; j++) {
                printf("%5d", cube[z][i][j]);
            }
            printf("\n");
        }
    }

    printf("\ntotal elements: %zu\n", sizeof cube / sizeof cube[0][0][0]);
    return 0;
}

Dalam praktiknya, tiga dimensi adalah titik di mana array berukuran tetap mulai terasa merepotkan, dan kebanyakan kode beralih ke blok datar dengan indeks yang dihitung, atau ke array berisi struct yang menamai arti setiap sumbunya.

Kesalahan umum

• Menulis grid[i, j]. Operator koma mengevaluasi i, membuangnya, lalu mengindeks dengan j. Kodenya bisa dikompilasi. Hasilnya salah. Pakai grid[i][j].
• Indeks yang tertukar. grid[col][row] membaca elemen sungguhan dari tempat yang salah, jadi tidak ada error yang bisa menangkapnya. Jaga urutan [row][col] di mana-mana.
• Tidak menulis ukuran kolom di parameter. void f(int grid[][]) tidak bisa dikompilasi, dan di situ compiler sedang menyelamatkanmu.
• Keluar dari batas. Seperti array lainnya, tidak ada pemeriksaan batas. grid[0][5] pada grid [3][4] diam-diam membaca grid[1][1], karena tata letaknya bersambung dan aritmetikanya tidak peduli.