Mảng
Tới giờ ta đã biết dùng một biến để giữ một giá trị. Nhưng nếu cần lưu điểm thi của 50 sinh viên thì sao? Khai báo 50 biến riêng lẻ là điều không tưởng. Mảng (array) sinh ra để giải đúng việc đó: gom nhiều giá trị cùng kiểu vào một tên chung, rồi truy cập từng giá trị qua một chỉ số (index) nguyên.
Hãy thấy rõ vì sao 50 biến rời rạc là ngõ cụt. Giả sử bạn đặt tên diem1, diem2 cho
tới diem50. Muốn tính tổng, bạn phải viết một biểu thức cộng dài 50 số hạng. Tệ nhất là
bạn không thể dùng vòng lặp, vì tên biến không phải thứ ta tính toán được: không có cách
nào bảo máy hãy lấy biến có tên là diem ghép với số i. Mỗi biến là một cái tên chết
cứng trong mã nguồn.
Mảng đổi cách đặt vấn đề. Thay vì 50 cái tên, ta có một cái tên và một con số để chọn ô. Con số ấy là dữ liệu, nên nó tính toán được, nên nó chạy được trong vòng lặp. Chính sự kết hợp giữa mảng và vòng lặp mới làm nên sức mạnh: bao nhiêu phần tử cũng chỉ cần đúng một đoạn mã xử lý.
Đổi lại, mảng của C đặt ra hai ràng buộc. Thứ nhất, mọi phần tử phải cùng kiểu. Thứ hai, số phần tử phải biết ngay lúc khai báo và không đổi được về sau; mảng không tự nở ra khi bạn nhét thêm dữ liệu. Và như ta sẽ thấy ở cuối bài, chính mảng cũng không hề biết mình có bao nhiêu phần tử, nên trách nhiệm nhớ con số đó thuộc về bạn.
Thử ngay: xem duyệt mảng chạy từng bước
Bấm ▶ Chạy (hoặc kéo thanh trượt) để theo dõi: biến chỉ số i chạy qua từng ô,
và biến sum cộng dồn giá trị của phần tử đang đứng.
1#include <stdio.h>2int main(void) {3 int a[5] = {10, 20, 30, 40, 50};4 int sum = 0;5 for (int i = 0; i < 5; i++)6 sum += a[i];7 printf("Sum = %d\n", sum);8 return 0;9}
Mảng một chiều
Khai báo và khởi tạo
Một mảng là một dãy ô nhớ liên tiếp, mỗi ô chứa một giá trị cùng kiểu. Khai báo gồm kiểu phần tử, tên mảng và số lượng phần tử đặt trong cặp ngoặc vuông.
#include <stdio.h>
int main(void) {
int a[5]; // an array of 5 integers, indices 0..4
a[0] = 10; // first element
a[1] = 20;
a[2] = 30;
a[3] = 40;
a[4] = 50; // a[4] is the LAST valid element
printf("%d\n", a[2]); // prints 30
return 0;
}
Điều quan trọng nhất phải nhớ ngay: chỉ số của mảng bắt đầu từ 0. Mảng a có 5
phần tử thì chỉ số hợp lệ là 0, 1, 2, 3, 4. Phần tử đầu là a[0], phần tử cuối là
a[4], không phải a[5].
Ta có thể vừa khai báo vừa gán giá trị ban đầu bằng danh sách trong cặp ngoặc nhọn:
int b[5] = {10, 20, 30, 40, 50}; // full initializer list
int c[5] = {1, 2}; // c is {1, 2, 0, 0, 0}, rest are zero
int d[] = {7, 8, 9}; // size inferred as 3 by compiler
int e[100] = {0}; // all 100 elements set to 0
Khi danh sách khởi tạo ngắn hơn số phần tử, phần còn lại được tự động gán 0. Nếu để
trống cặp ngoặc vuông như d, trình biên dịch tự đếm số phần tử trong danh sách.
Mảng khai báo nhưng không khởi tạo (như int a[5];) chứa các giá trị rác ngẫu
nhiên còn sót trong bộ nhớ, chứ không tự động bằng 0. Phải gán giá trị trước khi dùng.
Mảng nằm thế nào trong bộ nhớ
Muốn hiểu mọi hành vi kỳ quặc của mảng, bạn phải nhìn được nó trong bộ nhớ. Hãy hình dung
bộ nhớ là một dãy dài các ô, mỗi ô một byte, và mỗi ô có một số thứ tự gọi là địa chỉ
(address). Khi bạn khai int a[5];, trình biên dịch tìm một vùng liền mạch đủ chứa 5
số nguyên. Mỗi int thường chiếm 4 byte, nên vùng ấy dài 20 byte, và năm phần tử nằm sát
nhau không có khe hở.
Giả sử vùng đó bắt đầu ở địa chỉ 1000. Khi đó a[0] nằm ở byte 1000, a[1] ở byte 1004,
a[2] ở byte 1008, và cứ thế. Bây giờ câu hỏi then chốt: khi bạn viết a[i], máy tìm ô
đó bằng cách nào? Nó làm một phép tính duy nhất, cực nhanh:
dia chi cua a[i] = dia chi bat dau + i * kich thuoc mot phan tu
Với a[2] thì máy tính 1000 + 2 * 4 = 1008, nhảy thẳng tới đó lấy dữ liệu. Nó không
phải đi lần lượt qua a[0] rồi a[1] mới tới nơi. Đây là lý do mảng nhanh: lấy phần tử
thứ 3 hay thứ ba triệu đều tốn đúng một phép nhân và một phép cộng, thời gian như nhau.
Công thức trên cũng giải thích luôn câu hỏi mà ai học C cũng thắc mắc: vì sao chỉ số lại
bắt đầu từ 0 chứ không phải từ 1? Vì chỉ số thực chất không phải số thứ tự, nó là
khoảng cách tính từ đầu mảng. Phần tử đầu tiên nằm ngay tại chỗ bắt đầu, cách 0 ô,
nên chỉ số của nó là 0. Phần tử thứ hai cách đầu mảng đúng 1 ô, nên chỉ số là 1. Hiểu chỉ
số là khoảng cách thay vì thứ tự thì việc đếm từ 0 trở nên tự nhiên, và bạn cũng hết ngạc
nhiên khi thấy phần tử cuối của mảng n phần tử mang chỉ số n - 1.
Còn một hệ quả nữa, và nó là hệ quả nguy hiểm nhất. Phép tính địa chỉ ở trên luôn cho ra
một kết quả, kể cả khi i là 5 hay 100 hay -3. Máy vẫn ngoan ngoãn tính 1000 + 100 * 4 = 1400 rồi đọc byte ở đó, dù ô 1400 chẳng liên quan gì tới mảng của bạn. C không kèm
theo bất kỳ lệnh kiểm tra nào, vì kiểm tra thì tốn thêm thời gian ở mọi lần truy cập,
và C chọn tốc độ. Đó là gốc rễ của lỗi vượt biên mà ta bàn ngay dưới đây.
Duyệt mảng
Sức mạnh của mảng nằm ở chỗ ta có thể dùng vòng lặp để xử lý từng phần tử với một
biến chỉ số chạy. Mẫu duyệt chuẩn là vòng for với biến i chạy từ 0 tới n-1:
#include <stdio.h>
int main(void) {
int a[5] = {10, 20, 30, 40, 50};
int sum = 0;
for (int i = 0; i < 5; i++) // i runs from 0 to 4
sum += a[i]; // add each element
printf("Sum = %d\n", sum); // Sum = 150
return 0;
}
Chú ý điều kiện vòng lặp là i < 5 chứ không phải i <= 5; nếu viết <= ta sẽ chạm
tới a[5], một ô nằm ngoài mảng.
Duyệt mảng kích thước n luôn là for (int i = 0; i < n; i++). Chỉ số chạy từ 0 tới
n-1. Thuộc lòng mẫu này, hầu hết bài toán mảng đều dựa trên nó.
Lỗi vượt biên
C không kiểm tra chỉ số mảng. Nếu ta truy cập a[5] trên mảng chỉ có 5 phần tử (chỉ
số hợp lệ 0 tới 4), trình biên dịch vẫn cho qua, chương trình vẫn chạy, nhưng ta đang
đọc hoặc ghi vào một ô nhớ không thuộc về mảng. Đây gọi là lỗi vượt biên (out
of bounds).
Vượt biên mảng là một trong những lỗi nguy hiểm nhất của C vì nó thường không báo
lỗi ngay. Hậu quả có thể là kết quả sai, dữ liệu của biến khác bị phá, hoặc chương
trình sập bất chợt. Luôn tự kiểm tra chỉ số nằm trong khoảng từ 0 tới n-1.
Vì sao vượt biên lại tệ hơn một lỗi thông thường? Vì hậu quả của nó không xác định, mỗi
lần chạy một kiểu. Hãy theo dõi một trường hợp cụ thể. Bạn khai int a[5]; rồi ngay sau
đó khai int diem = 100;. Trình biên dịch nhiều khả năng đặt diem ngay sát sau 20 byte
của mảng. Bây giờ bạn lỡ ghi a[5] = 999;. Máy tính địa chỉ, thấy nó rơi đúng vào ô của
diem, và ghi 999 vào đó. Không có tiếng động nào cả. Về sau bạn in diem ra và thấy
999 thay vì 100, rồi bạn ngồi soi lại toàn bộ đoạn mã tính điểm, trong khi thủ phạm nằm ở
dòng gán mảng cách đó ba mươi dòng.
Tình huống còn khó chịu hơn khi ô bị chạm không thuộc về biến nào cả. Lúc đó chương trình
có thể chạy đúng hoàn toàn trên máy bạn, qua được mọi lần thử, rồi hỏng trên máy thầy
giáo, vì cách sắp xếp bộ nhớ khác đi một chút. Đây là loại lỗi mà lập trình viên gọi là
lỗi ma: nó xuất hiện và biến mất tuỳ hoàn cảnh. Còn nếu chỉ số vượt xa hẳn, chạm vào vùng
nhớ mà hệ điều hành không cho phép, chương trình sẽ bị chặn và chết ngay với thông báo
kiểu Segmentation fault.
Một, viết i <= n thay vì i < n trong vòng lặp duyệt mảng, làm vòng cuối chạm a[n].
Hai, quên rằng phần tử cuối là a[n-1] chứ không phải a[n], nên đọc phần tử cuối bị
lệch một ô. Ba, dùng chỉ số âm sau một phép trừ, ví dụ a[i-1] khi i đang bằng 0. Bốn,
nhập nhiều phần tử hơn kích thước mảng, chẳng hạn khai int a[100]; rồi cho người dùng
nhập n bất kỳ mà không kiểm tra n <= 100. Trong cả bốn trường hợp, hãy nhớ nguyên
tắc: chỉ số hợp lệ luôn nằm trong đoạn từ 0 tới n - 1, và bạn là người duy nhất kiểm
tra điều đó.
Mảng làm tham số hàm
Ta có thể truyền cả mảng vào hàm để tái sử dụng các thao tác xử lý. Điểm cần lưu ý:
khi truyền mảng, hàm không nhận một bản sao mà nhận chính mảng gốc (thực chất là
địa chỉ phần tử đầu). Vì vậy mọi thay đổi bên trong hàm đều tác động lên mảng gốc. Do
mảng không mang theo thông tin kích thước, ta phải truyền thêm số phần tử n như một
tham số riêng.
#include <stdio.h>
// find the largest element; n is passed separately
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max) max = arr[i];
return max;
}
// double every element; changes affect the ORIGINAL array
void doubleAll(int arr[], int n) {
for (int i = 0; i < n; i++)
arr[i] = arr[i] * 2;
}
int main(void) {
int a[5] = {3, 9, 1, 7, 4};
printf("Max = %d\n", findMax(a, 5)); // Max = 9
doubleAll(a, 5);
printf("a[0] = %d\n", a[0]); // a[0] = 6, original changed
return 0;
}
findMax chỉ đọc mảng nên trả kết quả bằng return. Còn doubleAll ghi đè trực
tiếp lên mảng gốc; sau lời gọi, a[0] đã thành 6. Đây là khác biệt lớn so với truyền
một biến thường: biến thường được sao chép nên hàm không sửa được bản gốc, còn mảng
thì sửa được.
Mảng suy biến thành con trỏ
Vì sao lại có sự khác biệt kỳ lạ đó? Câu trả lời nằm ở một quy tắc của C mà bạn cần biết sớm: khi một mảng được truyền vào hàm, nó suy biến thành con trỏ (array decay). Nói cách khác, thứ thật sự đi qua lời gọi hàm không phải 20 byte dữ liệu của mảng, mà chỉ là địa chỉ của phần tử đầu tiên, gọn trong vài byte.
Điều này rất hợp lý về hiệu năng. Nếu C sao chép cả mảng mỗi lần gọi hàm, thì truyền một
mảng một triệu phần tử sẽ tốn thời gian chép bốn megabyte cho mỗi lần gọi. Truyền địa
chỉ thì chỉ tốn vài byte, bất kể mảng to cỡ nào. Đổi lại, hàm làm việc thẳng trên bản gốc
nên nó sửa được dữ liệu của người gọi, đúng như doubleAll đã làm.
Nhưng cái giá thật sự nằm ở chỗ khác: địa chỉ không mang theo thông tin kích thước. Khi hàm nhận được địa chỉ 1000, nó biết mảng bắt đầu ở đâu nhưng hoàn toàn mù tịt về việc mảng dài 5 hay 5000 phần tử. Thông tin ấy đã mất và không lấy lại được.
Hệ quả trực tiếp là sizeof bên trong hàm cho kết quả sai:
#include <stdio.h>
void thu(int arr[], int n) {
// arr is really a pointer here, not an array
printf("Trong ham : sizeof = %d\n", (int)sizeof(arr)); // size of a pointer
printf("Trong ham : n = %d\n", n); // the real count
}
int main(void) {
int a[5] = {1, 2, 3, 4, 5};
printf("Trong main: sizeof = %d\n", (int)sizeof(a)); // 20 bytes = 5 * 4
thu(a, 5);
return 0;
}
Trong main, sizeof(a) cho 20, đúng là 5 phần tử nhân 4 byte, nên ta chia cho
sizeof(a[0]) sẽ ra số phần tử. Nhưng trong hàm thu, sizeof(arr) chỉ cho kích thước
của một con trỏ, thường là 8 byte trên máy 64 bit, hoàn toàn không liên quan tới mảng.
Nếu bạn quen tay viết int n = sizeof(arr) / sizeof(arr[0]); bên trong hàm, bạn sẽ nhận
được 2 thay vì 5, và vòng lặp của bạn chỉ chạy hai phần tử đầu.
Cách viết int arr[] trong danh sách tham số vì thế là một cách viết gây hiểu nhầm. Nó
trông như một mảng nhưng trình biên dịch âm thầm biến nó thành con trỏ; viết int *arr
hoàn toàn tương đương. Con số 5 trong int arr[5] cũng bị bỏ qua, bạn ghi 5 hay 500 thì
hàm vẫn nhận đúng một con trỏ và không kiểm tra gì cả.
Vì mảng đánh mất kích thước khi vào hàm, mọi hàm nhận mảng đều phải nhận thêm một tham số
n cho biết số phần tử, và người gọi có trách nhiệm truyền đúng con số ấy. Nếu bạn truyền
n lớn hơn kích thước thật, hàm sẽ đọc ra ngoài mảng mà không hề hay biết. Đây cũng là lý
do các hàm chuẩn của C luôn có tham số kích thước, và là lý do chuỗi trong C phải dùng một
mẹo khác để tự đánh dấu điểm cuối, đó là ký tự kết thúc mà bạn sẽ gặp ở bài chuỗi.
Từ đó rút ra một quy ước nghề nghiệp đáng theo: nếu hàm chỉ đọc mảng, hãy khai tham số
là const int arr[]. Từ khoá const nói với người đọc rằng hàm này không sửa dữ liệu của
bạn, và trình biên dịch sẽ báo lỗi nếu bạn lỡ tay ghi vào. Còn nếu hàm có sửa mảng, hãy
nói rõ điều đó trong tên hàm hoặc trong bình luận, vì người gọi không thể đoán ra chỉ bằng
cách nhìn lời gọi.
Mảng hai chiều
Nhiều bài toán cần dữ liệu dạng bảng: bảng điểm theo dòng và cột, bàn cờ, ảnh số. Khi đó ta dùng mảng hai chiều (two-dimensional array), hình dung như một ma trận (matrix) gồm các dòng và cột. Khai báo cần hai cặp ngoặc vuông, một cho số dòng và một cho số cột.
int m[3][4]; // 3 rows, 4 columns
int t[2][3] = { // initialize with nested braces
{1, 2, 3}, // row 0
{4, 5, 6} // row 1
};
m[0][0] = 10; // top-left element
m[2][3] = 20; // bottom-right element (last)
Phần tử ở dòng i cột j được truy cập bằng m[i][j]. Với khai báo int m[3][4],
chỉ số dòng chạy từ 0 tới 2 và chỉ số cột chạy từ 0 tới 3, tổng cộng có 12 phần tử.
Để đi qua mọi phần tử của ma trận, ta dùng hai vòng for lồng nhau: vòng ngoài chạy
theo dòng, vòng trong chạy theo cột.
#include <stdio.h>
int main(void) {
int a[2][3] = { {1, 2, 3}, {4, 5, 6} };
for (int i = 0; i < 2; i++) { // outer loop: rows
for (int j = 0; j < 3; j++) // inner loop: columns
printf("%4d", a[i][j]); // %4d aligns columns
printf("\n"); // new line after each row
}
return 0;
}
Vòng ngoài i cố định một dòng, vòng trong j quét hết các cột của dòng đó, rồi mới
sang dòng kế. Lệnh printf("\n") đặt sau vòng trong giúp xuống dòng mỗi khi hết một
dòng của ma trận.
Khi truyền mảng hai chiều vào hàm, bắt buộc phải ghi rõ số cột trong khai báo tham
số, ví dụ int a[][3]; chỉ số dòng có thể để trống. Trình biên dịch cần số cột để
tính đúng vị trí của một phần tử trong bộ nhớ.
Ma trận thật ra vẫn là một dãy thẳng
Lời nhắc trên nghe có vẻ tuỳ tiện, nhưng nó có lý do rất rõ ràng, và hiểu lý do ấy sẽ gỡ được phần lớn thắc mắc về mảng hai chiều.
Sự thật là bộ nhớ không hề có khái niệm dòng và cột. Bộ nhớ chỉ là một dãy ô thẳng tắp.
Cái ta gọi là ma trận int t[2][3] thực chất được xếp thành một dãy 6 ô liên tiếp, hết
dòng này tới dòng kia. Với ma trận { {1, 2, 3}, {4, 5, 6} }, sáu ô trong bộ nhớ nằm theo
đúng thứ tự 1, 2, 3, 4, 5, 6. Cách sắp xếp hết dòng này rồi mới sang dòng khác gọi là
xếp theo dòng (row major), và C luôn dùng cách này.
Vậy khi bạn viết t[i][j], máy phải quy đổi hai chỉ số về một vị trí duy nhất trong dãy
thẳng ấy. Nó dùng công thức:
vi tri trong day = i * so_cot + j
Kiểm chứng với t[1][2], tức số 6. Ma trận có 3 cột, nên vị trí là 1 * 3 + 2 = 5. Đếm
từ 0, ô thứ 5 trong dãy 1, 2, 3, 4, 5, 6 đúng là số 6. Công thức khớp.
Bây giờ nhìn lại công thức: nó cần biết so_cot. Không có số cột thì máy không tài nào
biết dòng mới bắt đầu từ đâu, vì trong bộ nhớ chẳng có dấu hiệu nào ngăn cách giữa các
dòng. Số dòng thì ngược lại, hoàn toàn không cần cho phép tính. Đó chính xác là lý do khi
truyền ma trận vào hàm, C bắt bạn ghi số cột và cho phép bỏ trống số dòng. Quy tắc này
không tuỳ hứng, nó rơi thẳng ra từ cách bộ nhớ được tổ chức.
Cách xếp theo dòng còn cho một mẹo nhỏ: hãy duyệt ma trận theo đúng thứ tự nó nằm trong bộ nhớ, tức vòng ngoài chạy dòng và vòng trong chạy cột. Làm ngược lại vẫn đúng nhưng chậm hơn, vì máy phải nhảy qua nhảy lại thay vì đọc tuần tự.
Xem chạy thêm: duyệt ma trận hai chiều theo hàng
Bản trace ở đầu bài duyệt một mảng một chiều. Trace này duyệt ma trận a[2][3] và cho thấy công
thức quy đổi hai chỉ số về một vị trí trong dãy thẳng: a[i][j] nằm ở địa chỉ cơ sở cộng
(i * số_cột + j) nhân kích thước một phần tử. Nhờ vậy hai vòng lặp lồng nhau đọc đúng
thứ tự các ô nằm trong bộ nhớ.
1#include <stdio.h>2int main(void) {3 int a[2][3] = {{1, 2, 3}, {4, 5, 6}};4 for (int i = 0; i < 2; i++)5 for (int j = 0; j < 3; j++)6 printf("%d ", a[i][j]);7 printf("\n");8 return 0;9}
Vậy là mảng một chiều hay hai chiều thì cũng chỉ là một dãy ô liên tiếp, khác nhau ở cách ta quy đổi chỉ số ra vị trí. Phần bài tập dưới đây cho bạn tự tay dựng lại cả hai.
Bài tập thực hành
Bài tập 1: lớn nhất, nhỏ nhất, trung bình
Viết chương trình nhập một mảng n số nguyên, sau đó in ra phần tử lớn nhất, phần tử
nhỏ nhất và giá trị trung bình của mảng.
Lời giải chi tiết
Khởi tạo max và min bằng phần tử đầu a[0], và sum bằng 0. Duyệt từ chỉ số 1,
mỗi phần tử cập nhật lại max nếu lớn hơn, min nếu nhỏ hơn, đồng thời cộng dồn vào
sum. Trung bình là sum chia cho n (ép kiểu thực để có phần lẻ).
#include <stdio.h>
int main(void) {
int n;
int a[100];
printf("n = ");
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]); // note the & before each element
int max = a[0], min = a[0], sum = 0;
for (int i = 0; i < n; i++) {
if (a[i] > max) max = a[i]; // update the maximum
if (a[i] < min) min = a[i]; // update the minimum
sum += a[i]; // accumulate the total
}
printf("Max = %d\n", max);
printf("Min = %d\n", min);
printf("Average = %.2f\n", (double)sum / n);
return 0;
}
Bài tập 2: đảo ngược mảng tại chỗ
Viết chương trình đảo ngược một mảng ngay tại chỗ (không dùng mảng phụ): phần tử đầu đổi chỗ với phần tử cuối, phần tử thứ hai đổi với phần tử kế cuối, và cứ thế.
Lời giải chi tiết
Dùng hai chỉ số: i chạy từ đầu, j chạy từ cuối. Mỗi bước đổi chỗ a[i] với a[j]
rồi cho i tiến và j lùi, dừng khi hai chỉ số gặp nhau ở giữa. Việc đổi chỗ cần một
biến tạm tmp.
#include <stdio.h>
int main(void) {
int a[5] = {1, 2, 3, 4, 5};
int n = 5;
for (int i = 0, j = n - 1; i < j; i++, j--) {
int tmp = a[i]; // swap a[i] and a[j]
a[i] = a[j];
a[j] = tmp;
}
for (int i = 0; i < n; i++)
printf("%d ", a[i]); // prints 5 4 3 2 1
printf("\n");
return 0;
}
Mấu chốt là điều kiện i < j: khi hai chỉ số gặp nhau thì mọi cặp đã được đổi xong,
phần tử chính giữa (nếu n lẻ) giữ nguyên.
Bài tập 3: tổng hai đường chéo của ma trận vuông
Nhập một ma trận vuông cấp n, rồi tính và in tổng các phần tử trên đường chéo chính
và tổng các phần tử trên đường chéo phụ.
Lời giải chi tiết
Đường chéo chính gồm các phần tử có chỉ số dòng bằng chỉ số cột, tức a[i][i]. Đường
chéo phụ gồm các phần tử a[i][n-1-i]. Chỉ cần một vòng lặp i duy nhất, cộng cả hai
loại trong cùng một lần duyệt.
#include <stdio.h>
int main(void) {
int n = 3;
int a[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
int main_d = 0, anti_d = 0;
for (int i = 0; i < n; i++) {
main_d += a[i][i]; // main diagonal: row == col
anti_d += a[i][n - 1 - i]; // anti diagonal
}
printf("Main = %d\n", main_d); // 1 + 5 + 9 = 15
printf("Anti = %d\n", anti_d); // 3 + 5 + 7 = 15
return 0;
}
Bài tập 4: vì sao hàm này đếm sai
Đoạn mã dưới đây định viết một hàm đếm số phần tử dương của mảng, nhưng hàm tự suy ra kích thước mảng thay vì nhận nó làm tham số. Hãy chạy thử, giải thích vì sao kết quả sai, rồi sửa lại cho đúng.
#include <stdio.h>
int demDuong(int arr[]) {
int n = sizeof(arr) / sizeof(arr[0]); // this line is the bug
int dem = 0;
for (int i = 0; i < n; i++)
if (arr[i] > 0) dem++;
return dem;
}
int main(void) {
int a[6] = {3, -1, 5, 7, -2, 9};
printf("So duong = %d\n", demDuong(a)); // expected 4, prints 1
return 0;
}
Lời giải chi tiết
Chương trình in ra 1 chứ không phải 4, và lý do nằm gọn ở dòng tính n.
Mẹo sizeof(mang) / sizeof(mang[0]) là mẹo đúng, nhưng nó chỉ đúng ở nơi mảng còn là
mảng, tức trong main. Ở đó sizeof(a) cho 24 byte, tức 6 phần tử nhân 4 byte, chia
cho sizeof(a[0]) bằng 4 thì ra đúng 6.
Nhưng bên trong hàm demDuong, tham số arr không còn là mảng nữa, nó đã suy biến thành
con trỏ ngay lúc truyền vào. Vì vậy sizeof(arr) trả về kích thước của một con trỏ,
thường là 8 byte trên máy 64 bit, chứ không phải 24 byte của mảng. Phép chia thành
8 / 4 = 2, nên n bằng 2. Vòng lặp chỉ xét hai phần tử đầu là 3 và -1, nên chỉ đếm
được một số dương. Con số cụ thể còn phụ thuộc kích thước con trỏ của máy, và chính sự
phụ thuộc đó đã là dấu hiệu chương trình sai.
Điểm cốt lõi: mảng đánh mất thông tin kích thước ngay khi đi qua lời gọi hàm, bên trong hàm không còn cách nào biết mảng dài bao nhiêu. Vì vậy kích thước bắt buộc phải được truyền vào như một tham số riêng, do người gọi cung cấp.
#include <stdio.h>
// n must be passed in; the function cannot recover it
int demDuong(const int arr[], int n) {
int dem = 0;
for (int i = 0; i < n; i++)
if (arr[i] > 0) dem++;
return dem;
}
int main(void) {
int a[6] = {3, -1, 5, 7, -2, 9};
int n = sizeof(a) / sizeof(a[0]); // valid here: a is still an array
printf("So duong = %d\n", demDuong(a, n)); // 4
return 0;
}
Lời giải còn thêm const vào tham số, vì hàm chỉ đọc mảng chứ không sửa. Nhờ vậy trình
biên dịch sẽ chặn nếu ai đó lỡ tay ghi vào arr, và người đọc nhìn chữ ký hàm là biết
ngay dữ liệu của mình an toàn.
Câu hỏi tự kiểm
- 1Mảng int a[5]; có phần tử cuối cùng là ô nào?
- 2Máy tìm địa chỉ của a[i] bằng cách nào?
- 3Bên trong một hàm nhận tham số int arr[], sizeof(arr) cho kết quả gì?
- 4Trong ma trận xếp theo dòng, phần tử t[i][j] nằm ở vị trí nào trong dãy thẳng?
Tóm tắt bài học
Mảng gom nhiều giá trị cùng kiểu vào một tên chung và cho ta chọn từng ô bằng một chỉ số tính toán được. Chính vì chỉ số là dữ liệu chứ không phải tên, mảng mới kết hợp được với vòng lặp, và đó là nguồn sức mạnh thật sự của nó.
Trong bộ nhớ, mảng là một vùng liền mạch, và a[i] được tìm bằng phép tính địa chỉ đầu
cộng i nhân kích thước phần tử. Hiểu công thức này thì ba điều tự sáng ra: chỉ số bắt
đầu từ 0 vì nó là khoảng cách chứ không phải thứ tự, truy cập phần tử nào cũng nhanh như
nhau, và C không thể kiểm tra biên vì phép tính luôn cho ra một địa chỉ nào đó dù chỉ số
sai. Vượt biên vì thế không báo lỗi, nó chỉ âm thầm đọc rác hoặc phá biến khác, đôi khi
còn chạy đúng trên máy này và sai trên máy khác.
Khi truyền vào hàm, mảng suy biến thành con trỏ: hàm nhận địa chỉ ô đầu chứ không nhận
bản sao. Nhờ vậy lời gọi rất rẻ và hàm sửa được mảng gốc, nhưng thông tin kích thước bị
mất hoàn toàn, nên sizeof bên trong hàm cho kết quả vô nghĩa và bạn bắt buộc phải
truyền số phần tử như một tham số riêng.
Mảng hai chiều chỉ là một dãy thẳng được xếp hết dòng này tới dòng kia, và t[i][j] quy
về vị trí i * so_cot + j. Chính vì công thức cần số cột mà không cần số dòng, C bắt bạn
ghi rõ số cột khi truyền ma trận vào hàm. Duyệt ma trận theo thứ tự dòng trước cột sau
cũng vì thế mà nhanh hơn duyệt ngược lại.