Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 15.520 phút đọc

Mảng struct

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

  • Khai báo và duyệt mảng struct
  • Sắp xếp mảng struct theo nhiều tiêu chí
  • So sánh bố trí theo bản ghi với bố trí theo cột
  • Chọn đúng bố trí cho từng bài toán

Mảng struct là cách biểu diễn một danh sách bản ghi, và nó xuất hiện trong gần như mọi chương trình thật. Bài này cũng giới thiệu một quyết định thiết kế ít người mới biết: cùng dữ liệu, hai cách bố trí, và chênh lệch tốc độ có thể tới nhiều lần.

#Khai báo và duyệt

khai-bao.c
typedef struct {
    char   ten[32];
    int    tuoi;
    double diem;
} SinhVien;

/* Khai báo và khởi tạo cùng lúc */
SinhVien ds[] = {
    { .ten = "An",    .tuoi = 20, .diem = 8.5 },
    { .ten = "Binh",  .tuoi = 22, .diem = 7.0 },
    { .ten = "Cuong", .tuoi = 19, .diem = 9.0 },
};

size_t n = sizeof ds / sizeof ds[0];

/* Duyệt bằng chỉ số */
for (size_t i = 0; i < n; ++i)
    printf("%-8s %3d %.1f\n", ds[i].ten, ds[i].tuoi, ds[i].diem);

/* Duyệt bằng con trỏ */
for (const SinhVien *p = ds; p < ds + n; ++p)
    printf("%-8s %3d %.1f\n", p->ten, p->tuoi, p->diem);
terminal
./khai-bao
An        20 8.5
Binh      22 7.0
Cuong     19 9.0

#Thêm, xóa, tìm

thao-tac.c
enum { TOI_DA = 100 };

typedef struct {
    SinhVien phan_tu[TOI_DA];
    size_t   n;
} Lop;

/* Thêm vào cuối. Trả về 0 nếu ổn, âm một nếu đầy. */
int lop_them(Lop *l, const SinhVien *sv)
{
    if (l == NULL || sv == NULL) return -1;
    if (l->n >= TOI_DA)          return -1;

    l->phan_tu[l->n++] = *sv;      /* gán cả struct, chép 48 byte */

    return 0;
}

/* Tìm theo tên. Trả về chỉ số, hoặc n nếu không thấy. */
size_t lop_tim(const Lop *l, const char *ten)
{
    if (l == NULL || ten == NULL) return 0;

    for (size_t i = 0; i < l->n; ++i)
        if (strcmp(l->phan_tu[i].ten, ten) == 0)
            return i;

    return l->n;
}

/* Xóa theo chỉ số, giữ nguyên thứ tự. Tốn O(n). */
int lop_xoa(Lop *l, size_t i)
{
    if (l == NULL || i >= l->n) return -1;

    memmove(&l->phan_tu[i], &l->phan_tu[i + 1],
            (l->n - i - 1) * sizeof l->phan_tu[0]);

    --l->n;

    return 0;
}

/* Xóa nhanh, KHÔNG giữ thứ tự. Tốn O(1). */
int lop_xoa_nhanh(Lop *l, size_t i)
{
    if (l == NULL || i >= l->n) return -1;

    l->phan_tu[i] = l->phan_tu[--l->n];      /* đưa phần tử cuối vào chỗ trống */

    return 0;
}
Thao tácGiữ thứ tựĐộ phức tạpDùng khi
Thêm cuốiO(1)Luôn, đây là cách rẻ nhất
Thêm giữaO(n)Khi thứ tự quan trọng
Xóa giữ thứ tựO(n)Danh sách người dùng nhìn thấy
Xóa nhanhKhôngO(1)Tập hợp không có thứ tự
Tìm tuyến tínhO(n)Dữ liệu chưa sắp xếp
Tìm nhị phânO(log n)Dữ liệu đã sắp theo khóa tìm

#Sắp xếp theo nhiều tiêu chí

sap-xep.c
#include <stdlib.h>
#include <string.h>

static int theo_ten(const void *x, const void *y)
{
    const SinhVien *a = x;
    const SinhVien *b = y;

    return strcmp(a->ten, b->ten);
}

static int theo_diem_giam(const void *x, const void *y)
{
    const SinhVien *a = x;
    const SinhVien *b = y;

    return (a->diem < b->diem) - (a->diem > b->diem);
}

/* Nhiều tiêu chí: điểm giảm dần, cùng điểm thì tên tăng dần */
static int theo_diem_roi_ten(const void *x, const void *y)
{
    const SinhVien *a = x;
    const SinhVien *b = y;

    if (a->diem != b->diem)
        return (a->diem < b->diem) - (a->diem > b->diem);

    return strcmp(a->ten, b->ten);
}

qsort(ds, n, sizeof ds[0], theo_diem_roi_ten);
terminal
./sap-xep
Cuong    19 9.0
An       20 8.5
Binh     22 7.0

Sắp xếp gián tiếp bằng mảng chỉ số

gian-tiep.c
/* Giữ dữ liệu nguyên vẹn, chỉ sắp một mảng con trỏ trỏ vào nó. */
SinhVien *chi_muc[100];

for (size_t i = 0; i < n; ++i)
    chi_muc[i] = &ds[i];

static int ct_theo_ten(const void *x, const void *y)
{
    const SinhVien *const *a = x;
    const SinhVien *const *b = y;

    return strcmp((*a)->ten, (*b)->ten);
}

qsort(chi_muc, n, sizeof chi_muc[0], ct_theo_ten);

/* ds không đổi, nhưng chi_muc[i] duyệt theo thứ tự tên */
for (size_t i = 0; i < n; ++i)
    printf("%s\n", chi_muc[i]->ten);

#Hai cách bố trí dữ liệu

Bố trí theo bản ghi
Một mảng struct. Mọi trường của một bản ghi nằm liền nhau trong bộ nhớ.
Bố trí theo cột
Nhiều mảng song song, mỗi mảng chứa một trường của mọi bản ghi.
hai-bo-tri.c
/* Bố trí theo bản ghi */
typedef struct { float x, y, z; int ma; } Hat;

Hat hat[1000000];

/* Bố trí theo cột */
typedef struct {
    float *x, *y, *z;
    int   *ma;
    size_t n;
} HatTheoCot;
Theo bản ghi, trong bộ nhớ:
   [x0 y0 z0 ma0][x1 y1 z1 ma1][x2 y2 z2 ma2] ...

Theo cột:
   [x0 x1 x2 ...][y0 y1 y2 ...][z0 z1 z2 ...][ma0 ma1 ma2 ...]
Tình huốngBản ghiTheo cột
Xử lý một bản ghi đầy đủNhanh, mọi trường nằm cùng một dòng bộ nhớ đệmChậm, phải đọc bốn vùng rời nhau
Duyệt một trường của mọi bản ghiChậm, mỗi lần đọc kéo theo trường không dùngNhanh, đọc liền mạch và véc tơ hóa được
Thêm và xóa bản ghiĐơn giảnPhải sửa mọi mảng
Mã dễ đọcRấtKém hơn
Số lần cấp phátMộtMột cho mỗi trường
do-bo-tri.c
/* Bài toán: cộng 1.0 vào trường x của một triệu hạt */

/* Theo bản ghi: mỗi lần đọc kéo theo cả y, z, ma dù không dùng */
for (size_t i = 0; i < n; ++i)
    hat[i].x += 1.0f;

/* Theo cột: đọc liền mạch, trình biên dịch véc tơ hóa được */
for (size_t i = 0; i < n; ++i)
    h.x[i] += 1.0f;
terminal
gcc -O2 -o do do-bo-tri.c && ./do
theo ban ghi : 0.0041 s
theo cot     : 0.0009 s
ti le        : 4.6 lan

#Chương trình quản lý hoàn chỉnh

quan-ly.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { TOI_DA = 100, DAI_TEN = 32 };

typedef struct {
    char   ten[DAI_TEN];
    int    tuoi;
    double diem;
} SinhVien;

typedef struct {
    SinhVien phan_tu[TOI_DA];
    size_t   n;
} Lop;

static void in_tieu_de(void)
{
    printf("%-4s %-16s %5s %6s\n", "STT", "Ho ten", "Tuoi", "Diem");
    printf("--------------------------------------\n");
}

static void in_sv(size_t stt, const SinhVien *sv)
{
    printf("%-4zu %-16s %5d %6.1f\n", stt, sv->ten, sv->tuoi, sv->diem);
}

static void lop_in(const Lop *l)
{
    in_tieu_de();

    for (size_t i = 0; i < l->n; ++i)
        in_sv(i + 1, &l->phan_tu[i]);

    printf("Tong: %zu sinh vien\n", l->n);
}

static int doc_dong(char *s, size_t co)
{
    if (fgets(s, (int)co, stdin) == NULL) return -1;

    s[strcspn(s, "\n")] = '\0';

    return 0;
}

static int lop_nhap_mot(Lop *l)
{
    if (l->n >= TOI_DA) return -1;

    SinhVien sv = { 0 };
    char     dong[64];

    printf("Ho ten: ");
    if (doc_dong(sv.ten, sizeof sv.ten) != 0) return -1;

    printf("Tuoi  : ");
    if (doc_dong(dong, sizeof dong) != 0)     return -1;
    if (sscanf(dong, "%d", &sv.tuoi) != 1)    return -1;

    printf("Diem  : ");
    if (doc_dong(dong, sizeof dong) != 0)     return -1;
    if (sscanf(dong, "%lf", &sv.diem) != 1)   return -1;

    l->phan_tu[l->n++] = sv;

    return 0;
}

static double lop_diem_tb(const Lop *l)
{
    if (l->n == 0) return 0.0;

    double tong = 0.0;

    for (size_t i = 0; i < l->n; ++i)
        tong += l->phan_tu[i].diem;

    return tong / (double)l->n;
}

static int theo_diem_giam(const void *x, const void *y)
{
    const SinhVien *a = x;
    const SinhVien *b = y;

    if (a->diem != b->diem)
        return (a->diem < b->diem) - (a->diem > b->diem);

    return strcmp(a->ten, b->ten);
}

int main(void)
{
    static Lop l;

    while (lop_nhap_mot(&l) == 0)
        ;

    qsort(l.phan_tu, l.n, sizeof l.phan_tu[0], theo_diem_giam);

    lop_in(&l);
    printf("Diem trung binh: %.2f\n", lop_diem_tb(&l));

    return 0;
}
terminal
printf 'An\n20\n8.5\nBinh\n22\n7.0\nCuong\n19\n9.0\n' | ./quan-ly
Ho ten: Tuoi  : Diem  : Ho ten: Tuoi  : Diem  : Ho ten: Tuoi  : Diem  : Ho ten: STT  Ho ten            Tuoi   Diem
--------------------------------------
1    Cuong               19    9.0
2    An                  20    8.5
3    Binh                22    7.0
Tong: 3 sinh vien
Diem trung binh: 8.17

Tự làm thử

  1. Khai báo mảng struct và duyệt bằng cả hai cách, in địa chỉ từng phần tử để xác nhận chúng cách nhau đúng sizeof.
  2. Cài đủ bốn thao tác thêm, tìm, xóa giữ thứ tự và xóa nhanh, so sánh kết quả của hai kiểu xóa.
  3. Thay memmove bằng memcpy trong hàm xóa, chạy dưới valgrind và quan sát cảnh báo.
  4. Viết ba hàm so sánh khác nhau và sắp cùng một mảng theo ba cách.
  5. Cài sắp xếp gián tiếp bằng mảng con trỏ, đo thời gian so với sắp trực tiếp với struct 256 byte.
  6. Cài cùng bài toán bằng hai bố trí dữ liệu, đo thời gian cộng một trường của một triệu bản ghi.
  7. Mở rộng chương trình quản lý: thêm chức năng tìm theo tên, xóa, và ghi ra file.

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 struct nằm liên tiếp trong bộ nhớ, và mọi quy tắc về mảng ở Chương 9 vẫn áp dụng nguyên vẹn.
  • Dùng memmove chứ không phải memcpy khi dồn mảng, vì hai vùng chồng lấn nhau.
  • Xóa giữ thứ tự tốn O(n), xóa nhanh bằng cách đưa phần tử cuối vào chỗ trống tốn O(1) nhưng làm hỏng thứ tự.
  • Sắp xếp gián tiếp qua mảng con trỏ nhanh hơn nhiều với struct lớn, và cho phép giữ nhiều thứ tự cùng lúc.
  • Bố trí theo bản ghi dễ đọc và đủ nhanh cho hầu hết chương trình. Bố trí theo cột chỉ đáng khi có hàng triệu bản ghi và chỉ dùng vài trường.