Bỏ qua điều hướng, tới nội dung chính
Học C
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" };
Mảng con trỏ chỉ chứa ba địa chỉ. Nội dung chuỗi nằm ở chỗ khác và chiếm đúng chỗ nó cần.
Biểu thứcKiểuNghĩa là
tenconst 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 charKý tự đầu của chuỗi thứ hai
*tenconst char *Giống ten[0]
**tenconst charGiống ten[0][0]
sizeof tensize_t24, 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ấtBa con trỏ, 24 byteSáu mươi byte dữ liệu
Bộ nhớ dùng cho ví dụ ba tên24 byte cộng 25 byte chuỗi60 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ôngKhông nếu trỏ vào hằng chuỗi
Đổi chỗ hai phần tửĐổi hai con trỏ 8 byteChép 20 byte ba lần
Bố cục bộ nhớRời rạcLiên tục
Truyền vào hàmchar **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ầnNghĩa là
argcSố đố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ốngNên chọnVì sao
Danh sách hằng chuỗi cố địnhMảng con trỏKhông tốn chỗ thừa, khai báo gọn
Chuỗi độ dài chênh lệch nhiềuMảng con trỏTiết kiệm bộ nhớ đáng kể
Cần sắp xếp hoặc đổi chỗ nhiềuMả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ắnMảng hai chiềuKhô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ỗiMảng hai chiềuMảng con trỏ trỏ vào hằng chuỗi thì không ghi được
Số phần tử biết lúc chạyMảng con trỏ cấp phát độngMả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ử

  1. Khai báo mảng con trỏ ba chuỗi, in đủ sáu biểu thức trong bảng đầu bài.
  2. So sánh sizeof củ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.
  3. 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.
  4. 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 $?.
  5. Sắp xếp mảng con trỏ chuỗi bằng qsort, viết hàm so sánh đúng hai tầng.
  6. Đ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.
  7. 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ành char (*)[N]. Hai kiểu này không truyền lẫn cho nhau.
  • argv là 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.