Bài 10.118 phút đọc

Ma trận

Sau bài này bạn sẽ làm được

Khai báo và khởi tạo mảng hai chiều đúng cách
Giải thích bố cục lưu theo hàng và công thức địa chỉ
Hiểu vì sao tham số mảng hai chiều bắt buộc ghi số cột
Chọn đúng cách truyền ma trận vào hàm

Mảng hai chiều là mảng của mảng. Câu đó nghe đơn giản nhưng giải thích được toàn bộ những chỗ khó của chương này: vì sao chiều thứ hai bắt buộc phải ghi khi truyền vào hàm, vì sao thứ tự vòng lặp ảnh hưởng tốc độ, và vì sao m[1][2] lại nằm ở ô thứ sáu.

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

int m[3][4];                 /* 3 hàng, mỗi hàng 4 cột, tổng 12 phần tử */

int a[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } };     /* rõ ràng nhất */
int b[2][3] = { 1, 2, 3, 4, 5, 6 };             /* tương đương, điền theo hàng */
int c[][3]  = { { 1, 2, 3 }, { 4, 5, 6 } };     /* chiều đầu tự suy ra là 2 */
int d[2][3] = { { 1 }, { 4 } };                 /* {1,0,0} và {4,0,0} */
int e[2][3] = { 0 };                            /* cả 6 ô bằng 0 */

Chiều thứ hai không bao giờ được lược bỏ

int c[][3] = { { 1, 2, 3 }, { 4, 5, 6 } };   /* hợp lệ */
int f[2][]  = { { 1, 2, 3 }, { 4, 5, 6 } };   /* lỗi biên dịch */
int g[][]   = { { 1, 2, 3 } };                /* lỗi biên dịch */

Lý do nằm ở mục bố cục ngay bên dưới. Trình biên dịch cần biết một hàng dài bao nhiêu để tính địa chỉ. Số hàng thì nó đếm được từ danh sách khởi tạo.

Khởi tạo có chỉ định cũng dùng được

/* Ma trận đơn vị 3x3, chỉ ghi những ô khác 0 */
int don_vi[3][3] = {
    [0][0] = 1,
    [1][1] = 1,
    [2][2] = 1,
};

/* Bảng khoảng cách, chỉ ghi các cặp có đường đi */
int kc[4][4] = {
    [0][1] = 5, [0][2] = 3,
    [1][3] = 2,
    [2][3] = 7,
};

Dùng hằng số cho kích thước

enum { HANG = 3, COT = 4 };

int m[HANG][COT];

for (size_t i = 0; i < HANG; ++i)
    for (size_t j = 0; j < COT; ++j)
        m[i][j] = 0;

Đặt tên cho kích thước làm mã dễ đọc và dễ sửa. Dùng enum hoặc #define đều được, nhưng enum có ưu điểm là trình gỡ lỗi nhìn thấy tên.

#Bố cục trong bộ nhớ

Lưu theo hàng

C xếp toàn bộ hàng 0 trước, rồi tới hàng 1, rồi hàng 2. Trong bộ nhớ, mảng hai chiều là một dãy phẳng liên tục, không có con trỏ nào ở giữa.

Bên trên là cách bạn nghĩ về ma trận. Bên dưới là cách nó thật sự nằm trong bộ nhớ: ba hàng nối đuôi nhau.

/* Công thức địa chỉ của mảng hai chiều */
&m[i][j]  ==  (char *)m + (i * SO_COT + j) * sizeof m[0][0]

phang.c

#include <stdio.h>

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

    /* Duyệt như mảng hai chiều */
    for (size_t i = 0; i < 3; ++i)
        for (size_t j = 0; j < 4; ++j)
            printf("%d ", m[i][j]);

    printf("\n");

    /* Duyệt như mảng một chiều 12 phần tử, cho ra đúng thứ tự đó */
    int *p = &m[0][0];

    for (size_t k = 0; k < 12; ++k)
        printf("%d ", p[k]);

    printf("\n");
    printf("sizeof m       = %zu\n", sizeof m);
    printf("sizeof m[0]    = %zu\n", sizeof m[0]);
    printf("sizeof m[0][0] = %zu\n", sizeof m[0][0]);

    return 0;
}

terminal

./phang

1 2 3 4 5 6 7 8 9 10 11 12 
1 2 3 4 5 6 7 8 9 10 11 12 
sizeof m       = 48
sizeof m[0]    = 16
sizeof m[0][0] = 4

Biểu thức	Kiểu	Ý nghĩa	sizeof
m	int (*)[4] sau phân rã	Con trỏ tới hàng đầu	48 khi chưa phân rã
m[0]	int[4] sau phân rã thành int *	Hàng thứ nhất	16
m[0][0]	int	Một phần tử	4
&m[0][0]	int *	Địa chỉ phần tử đầu	8

#Truyền ma trận vào hàm

void f(int m[3][4]);      /* thực chất là int (*m)[4] */
void g(int m[][4]);       /* giống hệt f */
void h(int (*m)[4]);      /* giống hệt, và đây là sự thật */

void sai(int m[][]);      /* lỗi biên dịch */
void sai2(int **m);       /* biên dịch được nhưng SAI NGHĨA, xem cảnh báo dưới */

truyen.c

enum { COT = 4 };

void in_ma_tran(size_t hang, const int m[][COT])
{
    for (size_t i = 0; i < hang; ++i) {
        for (size_t j = 0; j < COT; ++j)
            printf("%4d", m[i][j]);

        putchar('\n');
    }
}

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

in_ma_tran(3, m);

int ** không phải là ma trận

void sai(int **m)
{
    printf("%d\n", m[1][2]);   /* đọc bậy, chương trình sập */
}

int m[3][4];

sai(m);        /* trình biên dịch cảnh báo, và nếu bạn ép kiểu thì nó sập */

Với int **m, biểu thức m[1] nghĩa là đọc tám byte ở vị trí thứ hai và coi nó như một địa chỉ. Nhưng trong mảng hai chiều thật, tám byte đó là hai số nguyên chứ không phải địa chỉ. Kết quả là chương trình đi tới một vùng nhớ hoàn toàn ngẫu nhiên.

Ba cách truyền ma trận, chọn cách nào

Cách	Nguyên mẫu	Ưu và nhược
Số cột cố định	void f(size_t h, int m[][COT])	Đơn giản, an toàn, nhưng chỉ dùng được với đúng số cột đó
Mảng phẳng kèm hai kích thước	void f(int *m, size_t h, size_t c)	Linh hoạt mọi kích thước, nhưng phải tự viết m[i * c + j]
Tham số mảng độ dài thay đổi	void f(size_t h, size_t c, int m[h][c])	Cú pháp đẹp nhất, nhưng là tính năng tùy chọn của C11

phang-kem-kich-thuoc.c

/* Cách linh hoạt nhất mà vẫn di động: coi ma trận là mảng phẳng. */
void in_ma_tran(const int *m, size_t hang, size_t cot)
{
    for (size_t i = 0; i < hang; ++i) {
        for (size_t j = 0; j < cot; ++j)
            printf("%4d", m[i * cot + j]);

        putchar('\n');
    }
}

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

in_ma_tran(&m[0][0], 3, 4);      /* truyền địa chỉ phần tử đầu */

Một macro làm cú pháp dễ chịu hơn

#define O(m, c, i, j) ((m)[(size_t)(i) * (c) + (j)])

void in_ma_tran(const int *m, size_t hang, size_t cot)
{
    for (size_t i = 0; i < hang; ++i) {
        for (size_t j = 0; j < cot; ++j)
            printf("%4d", O(m, cot, i, j));

        putchar('\n');
    }
}

#Vì sao bắt buộc ghi số cột

Câu trả lời nằm gọn trong công thức địa chỉ: i * SO_COT + j. Trình biên dịch không thể sinh mã cho m[i][j] nếu không biết SO_COT. Số hàng thì không cần, vì nó không xuất hiện trong công thức.

Hàm không biết số cột

void f(int m[][]);        /* lỗi: array type has incomplete element type */

void g(int **m);          /* biên dịch được nhưng hiểu sai bố cục */

Số cột nằm trong kiểu, hoặc trong tham số

void f(size_t hang, int m[][4]);           /* số cột nằm trong kiểu */

void g(int *m, size_t hang, size_t cot);   /* số cột là tham số */

terminal

# Kiểm chứng: hai hàng cách nhau đúng COT * sizeof(int) byte

./khoang-cach

&m[0][0] = 0x7ffd1c2a3e10
&m[1][0] = 0x7ffd1c2a3e20
chenh lech = 16 byte = 4 cot * 4 byte

#Ba chiều trở lên

int khoi[2][3][4];       /* 2 lớp, mỗi lớp 3 hàng, mỗi hàng 4 cột */

/* Công thức địa chỉ mở rộng tự nhiên */
&khoi[i][j][k]  ==  (char *)khoi + ((i * 3 + j) * 4 + k) * sizeof(int)

/* Quy tắc truyền vào hàm: chỉ chiều ĐẦU TIÊN được lược bỏ */
void f(int k[][3][4]);   /* hợp lệ */
void g(int k[2][3][4]);  /* hợp lệ, con số 2 bị bỏ qua */
void h(int k[][][4]);    /* lỗi */

/* Mảng lớn phải là toàn cục hoặc static, hoặc cấp phát động ở Chương 14 */
static double luoi[100][100][100];      /* nằm ở .bss, an toàn */

int main(void)
{
    double luoi2[100][100][100];        /* 8 MB trên ngăn xếp, sập ngay */

    return 0;
}

Tự làm thử

In địa chỉ của mọi phần tử một ma trận ba nhân bốn, xác nhận chúng liên tiếp theo đúng thứ tự hàng.
Duyệt cùng một ma trận bằng hai cặp ngoặc vuông và bằng con trỏ phẳng một chiều, so sánh kết quả.
In sizeof của m, m[0] và m[0][0], giải thích ba con số.
Viết ba phiên bản hàm in ma trận theo ba cách trong bảng, so sánh chỗ gọi và tính linh hoạt.
Thử truyền int m[3][4] vào hàm nhận int **, đọc cảnh báo, rồi ép kiểu và quan sát chương trình sập.
Khai báo double a[100][100][100] làm biến cục bộ và quan sát chương trình sập, sau đó thêm static và chạy lại.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

Mảng hai chiều lưu theo hàng: toàn bộ hàng 0, rồi hàng 1, rồi hàng 2, liên tục không đứt quãng.
Địa chỉ tính bằng (i * số_cột + j) * sizeof(phần tử), nên số cột là thông tin bắt buộc còn số hàng thì không.
Khi truyền vào hàm, chỉ chiều đầu tiên được lược bỏ. int m[][] là lỗi.
int ** không phải ma trận. Nó hiểu bố cục hoàn toàn khác và làm chương trình sập.
Ma trận lớn phải khai báo static hoặc cấp phát động, vì ngăn xếp chỉ có vài megabyte.