Bài 13.320 phút đọc
Mảng con trỏ
Sau bài này bạn sẽ làm được
- Phân biệt mảng con trỏ với mảng hai chiều
- Đọc và xử lý đối số dòng lệnh
- Sắp xếp mảng con trỏ hiệu quả
- Chọn đúng cấu trúc cho từng bài toán
Mảng con trỏ là cấu trúc bạn dùng khi cần một danh sách các chuỗi độ dài khác nhau. Nó cũng chính là cách chương trình của bạn nhận đối số dòng lệnh, nên hiểu nó là bước đầu để viết công cụ dòng lệnh thật.
#Khai báo và bố cục
const char *ten[3] = { "An", "Nguyen Van Binh", "Cuong" };| Biểu thức | Kiểu | Nghĩa là |
|---|---|---|
| ten | const char ** | Sau phân rã, con trỏ tới phần tử đầu |
| ten[1] | const char * | Con trỏ tới chuỗi thứ hai |
| ten[1][0] | const char | Ký tự đầu của chuỗi thứ hai |
| *ten | const char * | Giống ten[0] |
| **ten | const char | Giống ten[0][0] |
| sizeof ten | size_t | 24, tức ba con trỏ 8 byte |
mang-con-tro.c
#include <stdio.h>
#include <string.h>
int main(void)
{
const char *ten[] = { "An", "Nguyen Van Binh", "Cuong" };
size_t n = sizeof ten / sizeof ten[0];
for (size_t i = 0; i < n; ++i)
printf("%zu: [%s] dai %zu\n", i, ten[i], strlen(ten[i]));
printf("sizeof ten = %zu\n", sizeof ten);
return 0;
}terminal
./mang-con-tro
0: [An] dai 2 1: [Nguyen Van Binh] dai 15 2: [Cuong] dai 5 sizeof ten = 24
#So với mảng hai chiều
| const char *a[3] | char a[3][20] | |
|---|---|---|
| Bản chất | Ba con trỏ, 24 byte | Sáu mươi byte dữ liệu |
| Bộ nhớ dùng cho ví dụ ba tên | 24 byte cộng 25 byte chuỗi | 60 byte, dùng hay không cũng chiếm |
| Độ dài mỗi phần tử | Tùy ý | Cố định, tối đa 19 ký tự |
| Sửa nội dung được không | Không nếu trỏ vào hằng chuỗi | Có |
| Đổi chỗ hai phần tử | Đổi hai con trỏ 8 byte | Chép 20 byte ba lần |
| Bố cục bộ nhớ | Rời rạc | Liên tục |
| Truyền vào hàm | char ** | char (*)[20] |
so-sanh.c
#include <stdio.h>
int main(void)
{
const char *a[3] = { "An", "Nguyen Van Binh", "Cuong" };
char b[3][20] = { "An", "Nguyen Van Binh", "Cuong" };
printf("mang con tro : %zu byte\n", sizeof a); /* 24 */
printf("mang hai chieu: %zu byte\n", sizeof b); /* 60 */
/* a[0][0] = 'X'; lỗi: hằng chuỗi chỉ đọc */
b[0][0] = 'X'; /* hợp lệ */
printf("%s %s\n", a[0], b[0]); /* An Xn */
return 0;
}Khi nào bộ nhớ chênh nhau nhiều
/* Một nghìn tên, dài trung bình 10 ký tự, dài nhất 100 ký tự */
char *a[1000]; /* 8 KB con trỏ, cộng khoảng 11 KB chuỗi = 19 KB */
char b[1000][101]; /* 101 KB, dùng thật khoảng 11 KB, lãng phí 90 KB */Chênh lệch càng lớn khi độ dài các phần tử càng khác nhau. Nhưng nếu độ dài gần bằng nhau thì mảng hai chiều lại thắng, vì nó không tốn 8 byte con trỏ cho mỗi phần tử và dữ liệu liên tục nên đọc nhanh hơn.
#Đối số dòng lệnh
int main(int argc, char **argv);
int main(int argc, char *argv[]); /* hoàn toàn tương đương */| Thành phần | Nghĩa là |
|---|---|
| argc | Số đối số, luôn ít nhất là 1 |
| argv[0] | Tên chương trình như người dùng gõ |
| argv[1] tới argv[argc-1] | Các đối số thật |
| argv[argc] | Luôn là NULL, chuẩn bảo đảm |
doi-so.c
#include <stdio.h>
int main(int argc, char **argv)
{
printf("argc = %d\n", argc);
for (int i = 0; i < argc; ++i)
printf("argv[%d] = [%s]\n", i, argv[i]);
printf("argv[argc] = %p\n", (void *)argv[argc]); /* luôn NULL */
return 0;
}terminal
./doi-so mot hai ba
argc = 4 argv[0] = [./doi-so] argv[1] = [mot] argv[2] = [hai] argv[3] = [ba] argv[argc] = (nil)
Một công cụ dòng lệnh đầy đủ
dem-tu.c
#include <stdio.h>
#include <string.h>
static void dung(const char *ten)
{
fprintf(stderr,
"Dung: %s [-c|-w|-l] <file>...\n"
" -c dem ky tu\n"
" -w dem tu\n"
" -l dem dong\n",
ten);
}
int main(int argc, char **argv)
{
int che_do = 'l';
int i = 1;
/* Đọc các tùy chọn ở đầu */
for (; i < argc && argv[i][0] == '-'; ++i) {
if (strcmp(argv[i], "--") == 0) { ++i; break; }
if (argv[i][1] == '\0' || argv[i][2] != '\0') {
dung(argv[0]);
return 1;
}
switch (argv[i][1]) {
case 'c': case 'w': case 'l':
che_do = argv[i][1];
break;
default:
dung(argv[0]);
return 1;
}
}
if (i >= argc) {
dung(argv[0]);
return 1;
}
for (; i < argc; ++i) {
FILE *f = fopen(argv[i], "r");
if (f == NULL) {
perror(argv[i]);
continue;
}
/* ... đếm theo che_do ... */
fclose(f);
}
return 0;
}terminal
./dem-tu -w a.txt b.txt
./dem-tu -x
Dung: ./dem-tu [-c|-w|-l] <file>... -c dem ky tu -w dem tu -l dem dong
#Sắp xếp mảng con trỏ
sap-xep.c
#include <stdlib.h>
#include <string.h>
static int so_sanh(const void *x, const void *y)
{
const char *const *a = x;
const char *const *b = y;
return strcmp(*a, *b);
}
const char *ten[] = { "Cuong", "An", "Binh", "Dung" };
size_t n = sizeof ten / sizeof ten[0];
qsort(ten, n, sizeof ten[0], so_sanh);
for (size_t i = 0; i < n; ++i)
printf("%s ", ten[i]); /* An Binh Cuong Dung */Vì sao nhanh hơn sắp xếp mảng hai chiều
terminal
# Sắp một trăm nghìn chuỗi dài trung bình 50 ký tự
./do-sap-xep
mang con tro : 0.041 s mang hai chieu : 0.318 s ti le : 7.8 lan
Mỗi phép đổi chỗ trong mảng con trỏ chỉ chuyển 8 byte địa chỉ. Trong mảng hai chiều, nó phải chép cả 51 byte nội dung, ba lần cho một phép hoán đổi. Với chuỗi dài hơn thì chênh lệch còn lớn hơn nữa.
#Chọn cấu trúc nào
| Tình huống | Nên chọn | Vì sao |
|---|---|---|
| Danh sách hằng chuỗi cố định | Mảng con trỏ | Không tốn chỗ thừa, khai báo gọn |
| Chuỗi độ dài chênh lệch nhiều | Mảng con trỏ | Tiết kiệm bộ nhớ đáng kể |
| Cần sắp xếp hoặc đổi chỗ nhiều | Mảng con trỏ | Chỉ đổi địa chỉ, không chép nội dung |
| Chuỗi dài gần bằng nhau và ngắn | Mảng hai chiều | Không tốn 8 byte con trỏ mỗi phần tử, dữ liệu liên tục |
| Cần sửa nội dung từng chuỗi | Mảng hai chiều | Mảng con trỏ trỏ vào hằng chuỗi thì không ghi được |
| Số phần tử biết lúc chạy | Mảng con trỏ cấp phát động | Mảng hai chiều tĩnh không làm được |
Trỏ vào hằng chuỗi rồi sửa
char *ten[3] = { "An", "Binh", "Cuong" };
ten[0][0] = 'X'; /* chương trình sập: ghi vào .rodata */Cấp bộ đệm ghi được
/* Cách 1: mảng hai chiều */
char ten[3][16] = { "An", "Binh", "Cuong" };
ten[0][0] = 'X'; /* hợp lệ */
/* Cách 2: mảng con trỏ trỏ vào bộ đệm riêng */
char bo_dem[3][16] = { "An", "Binh", "Cuong" };
char *ten2[3] = { bo_dem[0], bo_dem[1], bo_dem[2] };
ten2[0][0] = 'X'; /* hợp lệ */Tự làm thử
- Khai báo mảng con trỏ ba chuỗi, in đủ sáu biểu thức trong bảng đầu bài.
- So sánh
sizeofcủa mảng con trỏ và mảng hai chiều chứa cùng dữ liệu, giải thích chênh lệch. - Viết chương trình in mọi đối số dòng lệnh, thử với dấu nháy để truyền đối số có dấu cách.
- Cài công cụ dòng lệnh có ít nhất hai tùy chọn và thông báo cách dùng, kiểm tra mã thoát bằng
echo $?. - Sắp xếp mảng con trỏ chuỗi bằng
qsort, viết hàm so sánh đúng hai tầng. - Đo thời gian sắp xếp một trăm nghìn chuỗi bằng mảng con trỏ và mảng hai chiều.
- Cài kỹ thuật sắp xếp gián tiếp: giữ dữ liệu nguyên vẹn và sắp hai mảng con trỏ theo hai tiêu chí khác nhau.
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 con trỏ chỉ chứa địa chỉ, nội dung nằm rời rạc và chiếm đúng chỗ nó cần.
- Mảng con trỏ phân rã thành
char **, mảng hai chiều phân rã thànhchar (*)[N]. Hai kiểu này không truyền lẫn cho nhau. argvlà mảng con trỏ, vàargv[argc]luôn làNULL.- Sắp xếp mảng con trỏ nhanh hơn nhiều vì mỗi phép đổi chỗ chỉ chuyển tám byte địa chỉ.
- Chọn mảng con trỏ khi độ dài chênh lệch hoặc cần sắp xếp, chọn mảng hai chiều khi cần sửa nội dung và độ dài đều nhau.