BÀI 7. CẤU TRÚC DỮ LIỆU KIỂU MẢNG

Mục tiêu

Sau bài này, học viên:

Khai báo, khởi tạo, nhập, xuất và duyệt mảng một chiều, hai chiều.
Truyền mảng vào hàm và giải thích được vì sao hàm không nhận bản sao của toàn bộ phần tử.
Hiểu quan hệ mảng và con trỏ: tên mảng, phép *, phép &, số học con trỏ, và chỗ chúng không hoán đổi cho nhau.
Xử lý được chuỗi ký tự như mảng char kết thúc bằng '\0', kể cả tự viết các phép tương đương strlen, strcpy, strcmp, strcat.
Hiện thực được tìm tuyến tính, tìm nhị phân, sắp xếp chọn, sắp xếp nổi bọt, chèn có thứ tự, đếm tần suất.
Ở mức cao thủ: bố trí bộ nhớ hàng-trước của mảng hai chiều, độ phức tạp của thuật toán trên mảng, và cấp phát động bằng malloc / free khi số phần tử chỉ biết lúc chạy.

Struct của nhiều mảng khác kiểu là Bài 8. Bài này chỉ có một kiểu cho mỗi mảng.

1. Mảng một chiều

Mảng là một dãy các phần tử cùng kiểu, nằm liền nhau trong bộ nhớ, truy cập bằng chỉ số.

int a[4] đã gán {10, 20, 30, 40} thì bốn ngôi nhà xây sát nhau. Chỉ số là số thứ tự ngôi nhà, bắt đầu từ 0, không phải số nhà trên đường.

chỉ số        0        1        2        3
           ┌────────┬────────┬────────┬────────┐
giá trị    │   10   │   20   │   30   │   40   │
           └────────┴────────┴────────┴────────┘
địa chỉ     0x1000   0x1004   0x1008   0x100C

a[0] là nhà đầu. a[3] là nhà cuối đang có.
a[4] không có nhà. Ghi vào đó là viết sang đất người khác.

Tên a trong biểu thức là địa chỉ 0x1000, tức số nhà của a[0]. Cộng 1 vào con trỏ int thì nhảy sang nhà kế, cách 4 byte, không phải cách 1 byte.

int a[100];
int n = 0;

100 là sức chứa. n là số phần tử đang dùng. Hai số này khác nhau. Đề bài “tối đa 100 số” nghĩa là sức chứa 100, còn n do người dùng nhập và phải thỏa 0 <= n <= 100.

Chỉ số bắt đầu từ 0. Phần tử cuối đang dùng là a[n - 1]. a[n] nằm ngoài phần đang dùng. a[100] nằm ngoài sức chứa. Đọc hoặc ghi ngoài biên là hành vi không xác định. C không kiểm tra hộ.

Khởi tạo:

int b[5] = {1, 2, 3, 4, 5};
int c[5] = {1, 2};      /* phần còn lại bằng 0 */
int d[] = {7, 8, 9};    /* sức chứa suy ra là 3 */

Gán b = d là không hợp lệ. Mảng không phải giá trị gán được. Muốn chép, hãy chép từng phần tử hoặc dùng memcpy khi đã hiểu kích thước byte.

Duyệt đúng:

for (int i = 0; i < n; i++) {
    printf("%d ", a[i]);
}

2. Mảng dùng lại con trỏ của Bài 3

Bài 3 đã đặt nền: biến có số nhà, & lấy số nhà, * mở nhà, NULL là không có nhà. Phần này không dạy lại từ đầu. Nó chỉ nói mảng là nhiều nhà liền nhau và tên mảng, trong biểu thức, chính là số nhà của nhà đầu.

int x = 10;
int *p = &x;
*p = 20;   /* x thành 20 */

Với mảng int a[100]:

a trong biểu thức được chuyển thành địa chỉ phần tử đầu, kiểu int *.
a[i] tương đương *(a + i).
&a[i] tương đương a + i.
Con trỏ int * cộng 1 thì nhảy sizeof(int) byte, không nhảy 1 byte.

Khác biệt quan trọng: sizeof a trong hàm main, ngay tại chỗ khai báo mảng, là kích thước cả mảng. Sau khi truyền vào hàm, tham số int a[] thực chất là int *, sizeof a chỉ là kích thước con trỏ. Vì vậy hàm luôn cần thêm tham số n.

int tong(const int *a, int n)
{
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

const hứa hàm không sửa phần tử qua con trỏ này. Lời gọi tong(a, n) sao chép địa chỉ, không sao chép 100 phần tử. Sửa a[i] trong hàm là sửa đúng mảng của nơi gọi. Đây không phải ngoại lệ ma thuật của “truyền tham chiếu”. Đây là truyền giá trị của một địa chỉ.

NULL là con trỏ không trỏ tới đối tượng. Cấm *p khi p là NULL.

Chuỗi và mảng ký tự dùng cùng mô hình. "Hi" có kiểu mảng char gồm 'H', 'i', '\0'.

3. Mảng hai chiều

int mt[20][30];
int dong, cot;

mt[i][j] là phần tử hàng i, cột j, cả hai chỉ số từ 0. Trong bộ nhớ, các hàng nằm nối tiếp nhau (row-major): hết hàng 0 mới đến hàng 1. mt[i][j] và mt[i][j + 1] thường kề nhau; mt[i][j] và mt[i + 1][j] cách nhau cot phần tử.

Ma trận 2 hàng, 3 cột trên giấy và trong bộ nhớ không cùng hình. Trên giấy là lưới. Trong bộ nhớ là một hàng dài.

Trên giấy                    Trong bộ nhớ, liền một dãy
┌────┬────┬────┐
│ 1  │ 2  │ 3  │  hàng 0     1   2   3   4   5   6
├────┼────┼────┤
│ 4  │ 5  │ 6  │  hàng 1
└────┴────┴────┘

mt[1][0] là số 4, đứng ngay sau mt[0][2].

Khi truyền vào hàm, chiều cột phải có trong kiểu vì máy cần biết mỗi hàng dài bao nhiêu:

int tong_mt(const int mt[][30], int dong, int cot);

Hoặc truyền con trỏ tới hàng. Đừng bỏ chiều cột.

Mảng vuông thêm các đường: chéo chính i == j, chéo phụ i + j == n - 1.

4. Chuỗi

Chuỗi C là mảng char kết thúc bằng '\0'. Chiều dài logic là số ký tự trước '\0', không tính '\0'. Sức chứa phải lớn hơn chiều dài ít nhất 1.

char ten[50];
if (scanf("%49s", ten) != 1) {
    return 1;
}

%49s chừa chỗ cho '\0'. Không có số 49, chuỗi dài sẽ tràn mảng. %s dừng ở khoảng trắng. Muốn đọc cả dòng có dấu cách, dùng fgets.

fgets(buf, sizeof buf, stdin) đọc tối đa sizeof buf - 1 ký tự hoặc đến newline, và luôn thêm '\0' nếu còn chỗ. Nó có thể giữ ký tự \n trong buffer. Hãy bỏ \n cuối nếu đề bài không muốn tính nó là một phần của chuỗi.

Các hàm thư viện <string.h> cần thuộc hợp đồng:

Hàm	Việc	Điều kiện
`strlen`	Đếm đến trước `'\0'`	Chuỗi phải có `'\0'`
`strcpy`	Chép cả `'\0'`	Đích đủ chỗ
`strcat`	Nối vào cuối đích	Đích đủ chỗ cho cả hai và `'\0'`
`strcmp`	So từ điển theo mã	Âm nếu s1 < s2, 0 nếu bằng, dương nếu s1 > s2
`puts`	In chuỗi và thêm một lần xuống dòng	Chuỗi phải có `'\0'`
`gets`	Không có trong bài này và không được dùng	Không chặn độ dài, tràn mảng

Mảng char chưa chắc là chuỗi. Nó là chuỗi chỉ khi có '\0' trong phần sức chứa. char a[3] = {'A', 'B', 'C'}; là ba ký tự, không có kết thúc. char b[] = "ABC"; có bốn ô: 'A', 'B', 'C', '\0'. Đưa a cho strlen hoặc printf("%s") là đi quá biên.

Tự viết lại các hàm này là cách học chuỗi. Gọi thư viện là cách làm việc sau khi đã viết được.

5. Thuật toán nên có trong tay

Thuật toán	Ý tưởng	Thời gian	Điều kiện
Tìm tuyến tính	Xét lần lượt	O(n)	Không cần sắp
Tìm nhị phân	Cắt đôi đoạn	O(log n)	Đã sắp tăng
Sắp xếp chọn	Mỗi lượt chọn min của phần chưa sắp	O(n²)
Sắp xếp nổi bọt	Đổi chỗ cặp ngược	O(n²)	Có thể dừng sớm nếu một lượt không đổi
Chèn giữ thứ tự	Tìm chỗ, dịch phải, đặt vào	O(n) cho một lần chèn	Mảng đã tăng và còn chỗ
Đếm tần suất	Mảng đếm khi miền giá trị nhỏ	O(n + m)	Giá trị nằm trong miền đã biết

Bất biến tìm nhị phân: nếu x có mặt, nó nằm trong a[trai..phai].

6. Cấp phát động

Khi n chỉ biết lúc chạy và có thể lớn hơn mọi hằng sức chứa bạn dám khai báo trên stack:

int *a = malloc((size_t) n * sizeof *a);
if (a == NULL) {
    return 1;
}
/* dùng a[0..n-1] như mảng */
free(a);
a = NULL;

malloc xin n * sizeof(int) byte trên heap, trả NULL nếu thất bại. free trả vùng đó. Không free hai lần. Không dùng sau free. Không free mảng khai báo tĩnh int a[100].

Mỗi malloc trong bài nộp phải có một free trên mọi đường đi, kể cả đường lỗi. Đây là kỷ luật của C mà các ngôn ngữ có bộ gom rác che giùm.

7. Ví dụ

Ví dụ 7.1 — Nhập, xuất, tổng, max

Phân tích. Sức chứa 100. Đọc n rồi n số nguyên. In lại, in tổng và chỉ số của phần tử lớn nhất đầu tiên. Tách hàm.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int nhap(int *a, int suc_chua)
{
    int n;
    printf("n = ");
    if (scanf("%d", &n) != 1 || n < 1 || n > suc_chua) {
        return -1;
    }
    for (int i = 0; i < n; i++) {
        if (scanf("%d", &a[i]) != 1) {
            return -1;
        }
    }
    return n;
}

long long tong(const int *a, int n)
{
    long long s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

int chi_so_max(const int *a, int n)
{
    int vi = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[vi]) {
            vi = i;
        }
    }
    return vi;
}

int main(void)
{
    enum { SUC = 100 };
    int a[SUC];
    int n = nhap(a, SUC);
    if (n < 0) {
        printf("Du lieu khong hop le.\n");
        return 1;
    }
    printf("Tong = %lld\n", tong(a, n));
    int vi = chi_so_max(a, n);
    printf("Max = %d tai chi so %d\n", a[vi], vi);
    return 0;
}

Kết quả.

n = 5
4 9 2 9 1
Tong = 25
Max = 9 tai chi so 1

Phân tích chi tiết. Có hai số 9. Vòng chỉ cập nhật khi >, nên giữ chỉ số đầu tiên. Khởi tạo vi = 0 an toàn vì n >= 1. Nếu cho phép n = 0, hàm max phải từ chối. tong dùng long long để n số int không làm tổng tràn int.

Ví dụ 7.2 — Tìm nhị phân

Phân tích. Mảng đã sắp tăng. Trả chỉ số hoặc -1. Bất biến: đáp án nếu có thì nằm trong [trai, phai].

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int tim_nhi_phan(const int *a, int n, int x)
{
    int trai = 0;
    int phai = n - 1;
    while (trai <= phai) {
        int giua = trai + (phai - trai) / 2;
        if (a[giua] == x) {
            return giua;
        }
        if (a[giua] < x) {
            trai = giua + 1;
        } else {
            phai = giua - 1;
        }
    }
    return -1;
}

int main(void)
{
    int a[] = {1, 3, 4, 7, 9, 12};
    int n = (int) (sizeof a / sizeof a[0]);
    printf("Vi tri 7: %d\n", tim_nhi_phan(a, n, 7));
    printf("Vi tri 5: %d\n", tim_nhi_phan(a, n, 5));
    return 0;
}

Kết quả.

Vi tri 7: 3
Vi tri 5: -1

Phân tích chi tiết. trai + (phai - trai) / 2 tránh tổng trai + phai tràn int khi hai đầu rất lớn. (sizeof a / sizeof a[0]) chỉ đúng tại nơi a còn là mảng thật, không đúng trong hàm đã nhận con trỏ. Mảng chưa sắp mà gọi hàm này có thể trả -1 dù phần tử có mặt: thuật toán đúng, tiền điều kiện bị vi phạm.

Ví dụ 7.3 — Sắp xếp chọn

Phân tích. Mỗi lượt i, tìm chỉ số phần tử nhỏ nhất trên đoạn [i, n), đổi với a[i]. Sau lượt i, đoạn [0, i] là i + 1 phần tử nhỏ nhất, đã sắp.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

void hoan_doi(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}

void sap_chon(int *a, int n)
{
    for (int i = 0; i < n - 1; i++) {
        int vi_min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[vi_min]) {
                vi_min = j;
            }
        }
        if (vi_min != i) {
            hoan_doi(&a[i], &a[vi_min]);
        }
    }
}

int main(void)
{
    int a[] = {5, 1, 4, 2, 8};
    int n = 5;
    sap_chon(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d%s", a[i], i + 1 == n ? "\n" : " ");
    }
    return 0;
}

Kết quả.

1 2 4 5 8

Phân tích chi tiết. Số so sánh luôn (n-1) + (n-2) + … + 1 = n(n-1)/2, dù mảng đã sắp. Nổi bọt có thể dừng sớm; chọn thì không. Ổn định không được bảo đảm theo nghĩa hai phần tử bằng nhau giữ nguyên thứ tự tương đối nếu bạn đổi chỗ qua lại — với khóa là số nguyên trùng, điều đó ít lộ; với struct ở Bài 8 thì lộ. hoan_doi nhận địa chỉ phần tử, đúng Bài 6.

Ví dụ 7.4 — Chèn vào mảng đã tăng

Phân tích. Mảng sức chứa suc, đang có n phần tử sắp tăng. Chèn x vào đúng chỗ, dịch các phần tử lớn hơn sang phải. Thất bại nếu n == suc.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int chen(int *a, int *n, int suc, int x)
{
    int vi;
    if (*n >= suc) {
        return 0;
    }
    vi = 0;
    while (vi < *n && a[vi] < x) {
        vi++;
    }
    for (int i = *n; i > vi; i--) {
        a[i] = a[i - 1];
    }
    a[vi] = x;
    *n += 1;
    return 1;
}

int main(void)
{
    int a[8] = {1, 3, 5, 8};
    int n = 4;
    chen(a, &n, 8, 5);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Kết quả.

1 3 5 5 8

Phân tích chi tiết. Dịch từ phải sang trái. Dịch từ trái sang phải sẽ đè mất a[i] trước khi nó được chép đi. n truyền bằng địa chỉ vì hàm phải tăng số phần tử của nơi gọi. Giá trị 5 được chèn cạnh 5 cũ; vị trí là chỗ đầu tiên a[vi] >= x nên số mới đứng trước các số bằng nó. Nếu muốn đứng sau, điều kiện tìm là a[vi] <= x.

Ví dụ 7.5 — Ma trận: tổng từng hàng, chéo chính

Phân tích. Ma trận d dòng, c cột, tối đa 20×20. In tổng mỗi hàng. Nếu vuông, in tổng chéo chính.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int main(void)
{
    int mt[20][20];
    int d, c;

    printf("dong cot: ");
    if (scanf("%d %d", &d, &c) != 2 || d < 1 || c < 1 || d > 20 || c > 20) {
        return 1;
    }
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < c; j++) {
            if (scanf("%d", &mt[i][j]) != 1) {
                return 1;
            }
        }
    }

    for (int i = 0; i < d; i++) {
        long long s = 0;
        for (int j = 0; j < c; j++) {
            s += mt[i][j];
        }
        printf("Hang %d: %lld\n", i, s);
    }

    if (d == c) {
        long long cheo = 0;
        for (int i = 0; i < d; i++) {
            cheo += mt[i][i];
        }
        printf("Cheo chinh: %lld\n", cheo);
    }
    return 0;
}

Kết quả với ma trận 2×2: 1 2 / 3 4.

dong cot: 2 2
1 2
3 4
Hang 0: 3
Hang 1: 7
Cheo chinh: 5

Phân tích chi tiết. Chéo chính là mt[0][0] + mt[1][1] = 5. Bộ nhớ thực của hàng 0 là 1, 2 liền nhau. Vòng j chạy hết cột trước khi tăng i, trùng thứ tự bộ nhớ, thân thiện với cache khi ma trận lớn. Duyệt cột ngoài, hàng trong sẽ nhảy cóc trong bộ nhớ.

Ví dụ 7.6 — Chuỗi đối xứng và các hàm tự viết

Phân tích. Đọc một từ không chứa khoảng trắng. Đối xứng nếu ký tự i khớp ký tự n - 1 - i với mọi i < n / 2. Tự viết do_dai thay strlen.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int do_dai(const char *s)
{
    int n = 0;
    while (s[n] != '\0') {
        n++;
    }
    return n;
}

int doi_xung(const char *s)
{
    int n = do_dai(s);
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

int main(void)
{
    char s[100];
    if (scanf("%99s", s) != 1) {
        return 1;
    }
    printf("%s\n", doi_xung(s) ? "doi xung" : "khong doi xung");
    return 0;
}

Kết quả.

radar
doi xung

hello
khong doi xung

Phân tích chi tiết. radar: các cặp (r,r), (a,a), d ở giữa không cần cặp. hello: h khác o ngay lập tức. Chuỗi rỗng và chuỗi một ký tự là đối xứng vì vòng không chạy. Quên %99s là lỗ hổng tràn bộ đệm: người dùng đưa 200 ký tự sẽ ghi đè stack. Đó là lỗi bảo mật cổ điển của C, không chỉ lỗi bài tập.

Ví dụ 7.7 — Mảng động (cao thủ)

Phân tích. n có thể tới một triệu, không khai báo int a[1000000] trên stack nếu không biết giới hạn stack của máy. Cấp phát heap, đọc, tính trung bình, giải phóng.

Lưu đồ.

Mã nguồn.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n;
    printf("n = ");
    if (scanf("%d", &n) != 1 || n <= 0) {
        return 1;
    }

    int *a = malloc((size_t) n * sizeof *a);
    if (a == NULL) {
        printf("Het bo nho.\n");
        return 1;
    }

    long long s = 0;
    for (int i = 0; i < n; i++) {
        if (scanf("%d", &a[i]) != 1) {
            free(a);
            return 1;
        }
        s += a[i];
    }
    printf("Trung binh = %.4f\n", (double) s / n);
    free(a);
    return 0;
}

Phân tích chi tiết. Nhánh lỗi giữa chừng vẫn free trước khi return. (size_t) n * sizeof *a tính theo kích thước phần tử thật, không viết số 4. sizeof *a không cấp phát và không đọc giá trị a; nó chỉ hỏi kiểu. Sau free, không in a[0].

8. Bài tập có gợi ý

Bài 7.G1 — Đảo mảng tại chỗ

Gợi ý. Hai chỉ số trai = 0, phai = n - 1, đổi chỗ rồi tiến vào giữa khi trai < phai. Bộ nhớ phụ O(1).

Bài 7.G2 — Tách mảng chẵn lẻ

In các số chẵn giữ nguyên thứ tự tương đối, rồi các số lẻ. Có thể dùng mảng phụ.

Gợi ý. Hai lượt duyệt dễ đúng hơn một lượt rối. Lượt 1 chép chẵn, lượt 2 chép lẻ.

Bài 7.G3 — Xóa mọi phần tử bằng x

Gợi ý. Chỉ số ghi g chạy chậm hơn chỉ số đọc i. Chỉ chép khi a[i] != x. Cuối cùng n = g. Đây là mẫu hai con trỏ.

Bài 7.G4 — Tần suất

Dãy số trong đoạn 0..100. In mỗi giá trị xuất hiện và số lần, theo thứ tự giá trị.

Gợi ý. int dem[101] = {0}; rồi dem[a[i]]++. Đừng dùng mảng đếm nếu giá trị lên tới một tỷ.

Bài 7.G5 — Chuỗi

Viết sao_chep, so_sanh, noi giới hạn bởi sức chứa đích. Nối thất bại nếu không đủ chỗ, không ghi đè quá buffer.

Gợi ý. noi tìm '\0' của đích, rồi chép nguồn, luôn ghi '\0' cuối. Nếu hết chỗ giữa chừng, khôi phục '\0' tại chỗ bắt đầu nối và trả lỗi.

Bài 7.G6 — Ma trận chuyển vị

Gợi ý. Kết quả là ma trận c dòng, d cột với b[j][i] = a[i][j]. Nếu vuông có thể chuyển vị tại chỗ trên tam giác trên.

9. Bài tập tự làm

Cơ bản

Nhập mảng, in các phần tử dương.
Đếm số âm, số không, số dương.
Tìm phần tử nhỏ nhất và số lần nó xuất hiện.
Kiểm tra mảng có sắp tăng ngặt hay không.
Nhập một từ, in độ dài và đảo chuỗi tại chỗ.

Vững

Sắp xếp nổi bọt có cờ dừng sớm. Đếm số lần đổi chỗ với một mảng đã sắp và một mảng đảo.
Chèn x vào mảng tăng, từ chối nếu đầy.
Xóa phần tử tại vị trí k, dồn trái.
Hai mảng đã sắp tăng, trộn thành mảng sắp tăng thứ ba. Đây là lõi của sắp xếp trộn.
Ma trận: tổng biên, tổng chéo chính, tổng chéo phụ, phần tử lớn nhất cùng tọa độ.
Đếm số từ trong một dòng fgets. Từ cách nhau bởi ít nhất một khoảng trắng.

Nâng cao

Sàng Eratosthenes đến n (n <= 1000000) bằng mảng unsigned char. In các nguyên tố hoặc đếm chúng. Giải thích bộ nhớ và thời gian.
Tiền tố. Xây prefix[0] = 0, prefix[i+1] = prefix[i] + a[i]. Trả lời nhiều truy vấn tổng đoạn [l, r] trong O(1) mỗi truy vấn. Nêu vì sao mảng tiền tố dùng long long.
Tìm cặp có tổng bằng S trên mảng đã sắp, hai con trỏ hai đầu. Nếu chưa sắp, nêu phương án sắp rồi tìm, và bậc tổng.
Viết tim_chuoi tương tự strstr: tìm vị trí lần xuất hiện đầu của chuỗi con. Ca rỗng, ca không thấy, ca trùng khít.

Siêu khó, có ứng dụng

Nhật ký nhiệt độ. Tối đa 10000 mẫu double đọc từ bàn phím đến khi hết (hoặc đến một lượt n cho trước). Tính min, max, trung bình, và số mẫu vượt ngưỡng 37.5. Dùng mảng động. In thêm đường trung bình trượt cửa sổ 5: mỗi vị trí từ 4 trở đi, trung bình của 5 mẫu kết thúc tại đó. Giải phóng bộ nhớ. Ca n < 5 không có dòng trung bình trượt.
Bảng điểm một môn, chưa dùng struct. Ba mảng song song: mã số int, điểm giữa kỳ, điểm cuối kỳ. Tìm sinh viên theo mã bằng tìm tuyến tính. In danh sách sắp theo điểm tổng kết 0.4 * giua + 0.6 * cuoi bằng cách sắp chỉ số (mảng int thu_tu[n]), không xáo ba mảng lệch nhau. Đây là bài chuẩn bị cho Bài 8: bạn sẽ thấy ba mảng song song rất dễ lệch, và struct sinh ra để chữa đúng bệnh đó.
Bộ đệm vòng cho cảm biến. Mảng cố định N phần tử. Hai chỉ số dau và so_luong. ghi đè phần tử cũ khi đầy. doc_cu_nhat lấy phần tử cũ nhất còn trong cửa sổ. Không dùng malloc. Chứng minh mọi chỉ số đi qua % N. Viết 8 thao tác giả lập và bảng trạng thái. Đây là cấu trúc thật trong nhúng và trong nhật ký “chỉ giữ N mẫu gần nhất”.

10. Câu hỏi tự kiểm

Sức chứa và số phần tử đang dùng khác nhau thế nào?
Vì sao hàm nhận mảng vẫn cần tham số n?
a[i] viết lại bằng con trỏ như thế nào?
Dịch phần tử sang phải bắt đầu từ đầu nào?
Chuỗi khác mảng ký tự không có '\0' ở chỗ nào?
malloc thất bại thì trả về gì, và ai có trách nhiệm free?

11. Tóm tắt và cầu nối

Mảng là dãy cùng kiểu nằm liền nhau, chỉ số từ 0, không tự biết độ dài, không kiểm tra biên. Tên mảng trở thành địa chỉ phần tử đầu khi truyền vào hàm. Chuỗi là mảng char có '\0'. Thuật toán tìm, sắp, chèn, đếm là cách nghĩ trên vùng nhớ này. Cấp phát động chỉ thay cách xin vùng nhớ, không thay các bất biến.

Bài 8 ghép nhiều kiểu thành một đối tượng: điểm, phân số, sinh viên, thời gian. Mảng struct sẽ thay ba mảng song song. Con trỏ struct sẽ thay việc sao chép cả bản ghi mỗi lần gọi hàm.

12. Đào sâu: mảng là dãy ô liền nhau, tên mảng là địa chỉ ô đầu

Bài 3 đã dạy: con trỏ giữ số nhà, * mở nhà. Mảng là nhiều nhà cùng kiểu xây liền nhau. a[0] là nhà đầu. a[1] là nhà kế tiếp, cách sizeof(int) byte nếu phần tử là int.

Trong biểu thức, tên a trở thành địa chỉ của a[0], kiểu int *. Đó là lý do int *p = a; hợp lệ và p[i] cùng nghĩa a[i]. Hàm nhận int a[] thật ra nhận int *. Chiều dài không đi theo. Bạn phải đưa n.

sizeof a ngay tại nơi khai báo int a[100] là kích thước cả khối. sizeof a trong hàm đã nhận con trỏ là kích thước một địa chỉ. Đừng dùng sizeof để đoán n sau khi đã truyền mảng.

Chuỗi là mảng char có nhà cuối chứa '\0'. strlen đếm đến trước nhà đó. Thiếu '\0' thì hàm đi sang nhà người khác. %s khi scanf cũng ghi một dãy nhà và cần một nhà cho '\0'. %49s với mảng 50 nhà là hợp đồng đó.

Vượt chỉ số là hành vi không xác định, không phải "in rác có kiểm soát". Sắp xếp và tìm kiếm không làm giảm trách nhiệm đó. Chúng chỉ nói bạn sẽ đụng những ô nào, theo thứ tự nào, bao nhiêu lần.

Ví dụ 7.8 — Đảo mảng, hai đầu đi vào

Phân tích. Đảo tại chỗ. trai bắt đầu 0, phai bắt đầu n-1. Chừng nào trai < phai, đổi hai ô rồi tiến lại. Bất biến: phần ngoài đoạn [trai, phai] đã nằm đúng vị trí đảo. Khi trai gặp phai hoặc vượt, cả mảng đã đảo. Bộ nhớ phụ một biến tạm.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

void dao(int *a, int n)
{
    int trai = 0;
    int phai = n - 1;
    while (trai < phai) {
        int t = a[trai];
        a[trai] = a[phai];
        a[phai] = t;
        trai++;
        phai--;
    }
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5};
    dao(a, 5);
    for (int i = 0; i < 5; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Kết quả.

5 4 3 2 1

Phân tích chi tiết. Với n lẻ, phần tử giữa không đổi chỗ với chính nó vì vòng dừng khi trai == phai. Với n = 1, phai là 0, vòng không chạy. Với n = 0, không gọi hàm này; phai = -1 rồi vẫn không vào vòng nếu bạn gọi, nhưng đừng dựa vào chỉ số âm như một thiết kế. Hàm sửa đúng mảng nơi gọi vì nó nhận địa chỉ ô đầu, đúng mô hình Bài 3.

13. Bài tập mở rộng

Dễ

Nhập n và n số, in theo thứ tự ngược. Vẽ lưu đồ một vòng.
Đếm số phần tử chia hết cho 3.
Tìm chỉ số phần tử nhỏ nhất đầu tiên. Ca toàn âm.

Vừa

Xóa mọi phần tử bằng x, dồn trái, cập nhật n. Vẽ lưu đồ hai chỉ số đọc và ghi.
Kiểm tra đối xứng trên mảng số nguyên, không chỉ trên chuỗi.
Ma trận 3x3 nhập sẵn trong mã, in tổng từng cột. Vẽ lưu đồ cột ngoài hay hàng ngoài và nói vì sao bạn chọn.

Khó

Trộn hai mảng đã sắp tăng. Vẽ lưu đồ ba chỉ số i j k. Ca một mảng rỗng.
Sắp xếp nổi bọt có cờ. Vẽ lưu đồ. Đếm số lượt trên mảng đã sắp: phải là 1 lượt không đổi chỗ.
Viết sao_chep chuỗi có tham số sức chứa đích. Thất bại thì đích vẫn là chuỗi hợp lệ, không thiếu '\0'.

Siêu khó

Tìm nhị phân trả về chỉ số trái nhất nếu có nhiều phần tử trùng. Vẽ lưu đồ khác bản trả về bất kỳ. Bất biến phải nói "phần tử bằng x nếu còn thì nằm trong đoạn, và mọi ô trái của trai đều nhỏ hơn x".
Sàng nguyên tố đến n bằng mảng unsigned char. Vẽ lưu đồ gạch bội. In số lượng nguyên tố nhỏ hơn hoặc bằng 100. Kết quả đúng là 25.

Dự án thật

Nhật ký nhiệt độ tuần. Mỗi ngày một double, đủ 7 ngày, lưu mảng. In ngày nóng nhất (chỉ số 0 là thứ Hai), nhiệt độ trung bình, số ngày từ 37.5 trở lên. Tách hàm nhap, chi_so_max, trung_binh, dem_sot. Mỗi hàm một lưu đồ ngắn. Không dùng ba biến rời. Nếu nhập thiếu số, thoát mã 1 và không in trung bình trên dữ liệu dở.

Bộ 25 bài tập

Nhập n và n số, in các số dương. Gợi ý: Duyệt i từ 0 đến n-1, if a[i] > 0 thì in.
Đếm số âm, số 0, số dương trong mảng. Gợi ý: Ba biến đếm, một vòng.
In mảng theo thứ tự ngược. Gợi ý: for từ n-1 xuống 0.
Tìm phần tử nhỏ nhất và số lần nó xuất hiện. Ca toàn âm. Gợi ý: Khởi tạo min bằng a[0], không bằng 0.
Kiểm tra mảng có sắp tăng ngặt hay không. Gợi ý: Một cặp a[i] >= a[i+1] là hết tăng ngặt.
Nhập một từ, in độ dài và đảo tại chỗ. Giữ '\0'. Gợi ý: Độ dài đếm đến trước \0. Đảo bằng hai đầu, không đụng ô \0.
Đếm số phần tử chia hết cho 3. Gợi ý: a[i] % 3 == 0 thì tăng đếm.
Đảo mảng tại chỗ bằng hai chỉ số hai đầu. Gợi ý: while trai < phai thì đổi rồi trai tăng, phai giảm.
Xóa mọi phần tử bằng x, dồn trái, cập nhật n. Gợi ý: Chỉ số ghi chỉ nhích khi phần tử được giữ.
Chèn x vào mảng đã tăng, từ chối nếu đầy. Gợi ý: Dịch từ phải sang trái rồi mới ghi x.
Xóa phần tử tại vị trí k. Gợi ý: Dồn các phần tử sau k sang trái một ô, rồi giảm n.
Sắp xếp chọn hoặc nổi bọt. Mảng đã sắp phải hết sớm nếu bạn dùng nổi bọt có cờ. Gợi ý: Nổi bọt: một lượt không đổi chỗ thì break.
Tìm nhị phân trên mảng đã sắp. Một ca có mặt, một ca không có. Gợi ý: Đoạn [trai, phai]. Giữa = trai + (phai-trai)/2.
Tách mảng thành nhóm chẵn rồi nhóm lẻ, giữ thứ tự tương đối. Gợi ý: Một vòng chép chẵn, một vòng chép lẻ.
Đếm tần suất các giá trị trong đoạn 0..100. Gợi ý: int dem[101] = {0}; rồi dem[a[i]]++.
Ma trận: tổng từng hàng, tổng chéo chính, tổng chéo phụ nếu là ma trận vuông. Gợi ý: Chéo chính i == j. Chéo phụ i + j == n - 1.
Chuyển vị ma trận. Kết quả đổi số dòng và số cột. Gợi ý: b[j][i] = a[i][j]. Mảng kết quả đổi kích thước.
Trộn hai mảng đã sắp tăng. Ca một mảng rỗng. Gợi ý: Ba chỉ số i, j, k. Hết một mảng thì chép nốt mảng kia.
Viết sao_chep, noi, so_sanh có tham số sức chứa. Thiếu chỗ thì thất bại và vẫn có '\0'. Gợi ý: Luôn ghi \0. Hết chỗ thì trả lỗi, không viết quá sức chứa.
Tìm chuỗi con, kiểu strstr. Ca rỗng, ca không thấy, ca trùng cả chuỗi. Gợi ý: Khớp từng vị trí bắt đầu. Chuỗi con rỗng có thể coi là thấy tại 0.
Sàng nguyên tố đến n bằng unsigned char. Đếm số nguyên tố không vượt 100, kết quả đúng là 25. Gợi ý: Mảng đánh dấu. Bội của p bắt đầu từ p*p.
Nhiệt độ tuần. Bảy số double. In ngày nóng nhất, trung bình, số ngày từ 37.5 trở lên. Tách hàm. Nhập thiếu thì thoát mã 1. Gợi ý: Chỉ số 0 là thứ Hai. Hàm max trả chỉ số, không in.
Điểm một môn bằng ba mảng song song. Tìm theo mã. Sắp theo điểm tổng kết bằng mảng chỉ số, không để ba mảng lệch nhau. Gợi ý: Mảng thu_tu[i] = i. Đổi chỗ trong thu_tu, không đổi ba mảng dữ liệu lệch nhau.
Bộ đệm vòng. Mảng cố định N, ghi đè khi đầy, đọc mẫu cũ nhất. Tám thao tác và bảng trạng thái. Mọi chỉ số qua % N. Gợi ý: Vị trí ghi là (dau + so_luong) % N khi chưa đầy. Khi đầy thì dau cũng tiến.
Tổng đoạn. Mảng tiền tố long long. Nhiều truy vấn tổng từ l đến r. Nêu vì sao không dùng int cho tiền tố. Giải phóng bộ nhớ nếu bạn cấp phát động. Gợi ý: Tổng [l,r] = prefix[r+1] - prefix[l]. prefix dùng long long.

Mục tiêu​

1. Mảng một chiều​

2. Mảng dùng lại con trỏ của Bài 3​

3. Mảng hai chiều​

4. Chuỗi​

5. Thuật toán nên có trong tay​

6. Cấp phát động​

7. Ví dụ​

Ví dụ 7.1 — Nhập, xuất, tổng, max​

Ví dụ 7.2 — Tìm nhị phân​

Ví dụ 7.3 — Sắp xếp chọn​

Ví dụ 7.4 — Chèn vào mảng đã tăng​

Ví dụ 7.5 — Ma trận: tổng từng hàng, chéo chính​

Ví dụ 7.6 — Chuỗi đối xứng và các hàm tự viết​

Ví dụ 7.7 — Mảng động (cao thủ)​

8. Bài tập có gợi ý​

Bài 7.G1 — Đảo mảng tại chỗ​

Bài 7.G2 — Tách mảng chẵn lẻ​

Bài 7.G3 — Xóa mọi phần tử bằng x​

Bài 7.G4 — Tần suất​

Bài 7.G5 — Chuỗi​

Bài 7.G6 — Ma trận chuyển vị​

9. Bài tập tự làm​

Cơ bản​

Vững​

Nâng cao​

Siêu khó, có ứng dụng​

10. Câu hỏi tự kiểm​

11. Tóm tắt và cầu nối​

12. Đào sâu: mảng là dãy ô liền nhau, tên mảng là địa chỉ ô đầu​

Ví dụ 7.8 — Đảo mảng, hai đầu đi vào​

13. Bài tập mở rộng​

Dễ​

Vừa​

Khó​

Siêu khó​

Dự án thật​

Bộ 25 bài tập​

Mục tiêu

1. Mảng một chiều

2. Mảng dùng lại con trỏ của Bài 3

3. Mảng hai chiều

4. Chuỗi

5. Thuật toán nên có trong tay

6. Cấp phát động

7. Ví dụ

Ví dụ 7.1 — Nhập, xuất, tổng, max

Ví dụ 7.2 — Tìm nhị phân

Ví dụ 7.3 — Sắp xếp chọn

Ví dụ 7.4 — Chèn vào mảng đã tăng

Ví dụ 7.5 — Ma trận: tổng từng hàng, chéo chính

Ví dụ 7.6 — Chuỗi đối xứng và các hàm tự viết

Ví dụ 7.7 — Mảng động (cao thủ)

8. Bài tập có gợi ý

Bài 7.G1 — Đảo mảng tại chỗ

Bài 7.G2 — Tách mảng chẵn lẻ

Bài 7.G3 — Xóa mọi phần tử bằng x

Bài 7.G4 — Tần suất

Bài 7.G5 — Chuỗi

Bài 7.G6 — Ma trận chuyển vị

9. Bài tập tự làm

Cơ bản

Vững

Nâng cao

Siêu khó, có ứng dụng

10. Câu hỏi tự kiểm

11. Tóm tắt và cầu nối

12. Đào sâu: mảng là dãy ô liền nhau, tên mảng là địa chỉ ô đầu

Ví dụ 7.8 — Đảo mảng, hai đầu đi vào

13. Bài tập mở rộng

Dễ

Vừa

Khó

Siêu khó

Dự án thật

Bộ 25 bài tập