Mảng 2 chiều trong C: mảng nhiều chiều, bộ nhớ và ma trận

Mảng nhiều chiều là mảng mà mỗi phần tử của nó lại là một mảng. int grid[3][4]; không phải một kiểu lưới đặc biệt nào cả: đó là ba phần tử, mỗi phần tử là một mảng bốn số int, nằm nối tiếp nhau. Khi đã hiểu điều đó, phần còn lại tự nhiên theo sau: cách bố trí trong bộ nhớ, phép tính chỉ số, và quy tắc tưởng như khó hiểu khi truyền chúng vào hàm.

Hai chiều đã đủ cho gần như mọi nhu cầu thực tế: lưới, bảng, ma trận, bàn cờ game, hình ảnh. Vì vậy bài này tập trung vào mảng 2 chiều.

Khai báo và khởi tạo

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

Số thứ nhất là số hàng, số thứ hai là số cột. Có thể viết giá trị khởi tạo phẳng hoặc dùng cặp ngoặc nhọn bên trong; nên dùng ngoặc nhọn vì chúng cho thấy hình dạng của mảng.

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

Cách viết int e[][3] rất quan trọng: bạn có thể bỏ trống số hàng để giá trị khởi tạo tự quyết định, nhưng số cột thì không bao giờ được bỏ. Phần tiếp theo giải thích lý do.

Bố cục row-major

C lưu mảng 2 chiều theo thứ tự row-major: toàn bộ hàng 0, rồi toàn bộ hàng 1, cứ thế tiếp tục, trong một khối nhớ liền mạch. Phía sau không hề có một mảng các con trỏ tới từng hàng.

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

Công thức i * columns + j chính là toàn bộ cơ chế, và cũng là lý do trình biên dịch phải biết số cột thì mới truy cập được bất kỳ phần tử nào. Số hàng không bao giờ tham gia vào phép tính.

Bạn có thể thấy trực tiếp cách bố trí này bằng cách in ra địa chỉ:

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

Các địa chỉ tăng dần đúng bằng sizeof(int) mà không có khoảng trống nào, kể cả ở chỗ một hàng kết thúc và hàng tiếp theo bắt đầu. Vòng lặp duyệt phẳng chứng minh điều đó: flat[k] đi qua cả mười hai phần tử như một dãy liền.

Cách bố trí này còn ảnh hưởng tới hiệu năng: duyệt theo hàng rồi tới cột sẽ chạm vào bộ nhớ theo đúng thứ tự, điều mà bộ nhớ đệm CPU rất ưa. Đảo thứ tự lồng vòng lặp để vòng trong đi xuống theo cột thì mỗi bước sẽ nhảy qua cả một hàng, và trên mảng lớn có thể chạy chậm hơn vài lần.

Vòng lặp lồng nhau

Hai chiều thì cần hai vòng lặp for: vòng ngoài chọn hàng, vòng trong quét các cột của hàng đó.

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

Đặt tên biến đếm theo ý nghĩa của nó (i/row cho hàng, j/col cho cột) và giữ thứ tự nhất quán: grid[row][col] ở mọi nơi. Một nửa số bug với mảng 2 chiều là do đảo ngược cặp chỉ số.

Các kích thước tạo bằng #define cũng không chỉ để trang trí: nhờ chúng, giới hạn vòng lặp và khai báo mảng không thể lệch nhau khi bạn đổi hình dạng mảng.

Truyền mảng 2 chiều vào hàm

Đây là quy tắc khiến ai cũng vấp: tham số của hàm phải khai báo số cột.

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

Lý do nằm ở sự suy biến (decay). Khi truyền grid, nó được chuyển thành con trỏ tới phần tử đầu tiên, mà phần tử của nó là các hàng, nên kiểu là int (*)[4]: con trỏ tới một mảng 4 số int. Để grid[i][j] có nghĩa, trình biên dịch phải biết một hàng dài bao nhiêu, và đó chính là số 4. Số hàng thực sự không có trong kiểu, nên nó phải được truyền như một đối số riêng.

Lưu ý int (*grid)[COLS] và int grid[][COLS] là cùng một tham số được viết theo hai cách. Cặp ngoặc tròn là bắt buộc, vì int *grid[COLS] lại là một mảng các con trỏ. Sự khác biệt này được giải thích trong bài con trỏ và mảng.

Nếu số cột chỉ biết được lúc chạy, tham số có kích thước thay đổi (variably-modified) của C99 cho phép bạn truyền nó vào trước:

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

rows và cols phải được khai báo trước tham số mảng dùng chúng. Ở nơi không hỗ trợ cách này, giải pháp thường gặp là một mảng 1 chiều phẳng cộng với tự tính chỉ số:

#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] chính xác là thứ trình biên dịch viết hộ bạn trong trường hợp kích thước cố định. Tự làm chỉ tốn một dòng và dùng được cho mọi hình dạng được quyết định lúc chạy.

Ví dụ về ma trận

Nhân ma trận gom toàn bộ nội dung bài này lại: ba vòng lặp lồng nhau trên vùng nhớ 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;
}

Có hai chi tiết đáng học theo. Vòng lặp k bên trong ghép a[i][k] với b[k][j]: một chỉ số đi dọc một hàng, chỉ số kia đi dọc một cột. Và phép chuyển vị bắt đầu vòng trong ở j = i + 1: nếu bắt đầu từ 0, mỗi cặp sẽ bị hoán đổi hai lần và ma trận giữ nguyên như cũ.

Ba chiều trở lên

Quy luật vẫn mở rộng như vậy, và quy tắc về tham số hàm cũng thế: mọi chiều trừ chiều đầu tiên đều phải được khai báo.

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

Trong thực tế, đến ba chiều thì mảng kích thước cố định bắt đầu trở nên cồng kềnh, và phần lớn code chuyển sang một khối phẳng với chỉ số tự tính, hoặc một mảng các struct đặt tên rõ ý nghĩa của từng trục.

Lỗi thường gặp

• Viết grid[i, j]. Toán tử dấu phẩy tính i, bỏ nó đi, rồi truy cập bằng j. Code vẫn biên dịch được. Nhưng sai. Hãy dùng grid[i][j].
• Đảo ngược chỉ số. grid[col][row] đọc một phần tử có thật nhưng ở sai chỗ, nên không có lỗi nào để bắt. Giữ thứ tự [row][col] ở mọi nơi.
• Bỏ số cột trong tham số. void f(int grid[][]) không biên dịch được, và đó là trình biên dịch đang cứu bạn.
• Truy cập ngoài phạm vi. Như mọi mảng khác, không có kiểm tra giới hạn. grid[0][5] trên một lưới [3][4] sẽ âm thầm đọc grid[1][1], vì bố cục liền mạch và phép tính chẳng quan tâm.