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

strcat

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

  • Dùng strcat đúng và kiểm tra chỗ trống trước khi nối
  • Giải thích vì sao nối nhiều lần trong vòng lặp là O(n bình phương)
  • Viết hàm nối chuỗi chạy tuyến tính
  • Chọn giữa strcat, strncat và snprintf

Nối chuỗi có một đặc điểm mà cộng số không có: hàm phải tìm điểm cuối của chuỗi đích trước khi nối. Nếu bạn nối trong vòng lặp, việc tìm đó lặp lại mỗi lượt, và chương trình chuyển từ tuyến tính sang bậc hai mà không có dấu hiệu gì trong mã.

#Cách dùng

#include <string.h>

char *strcat(char *dich, const char *nguon);

Tìm byte kết thúc của dich, ghi nguon bắt đầu từ đó, rồi đặt byte kết thúc mới. Trả về dich.

strcat.c
#include <stdio.h>
#include <string.h>

int main(void)
{
    char s[32] = "Xin ";

    strcat(s, "chao ");
    strcat(s, "the gioi");

    printf("[%s]\n", s);          /* [Xin chao the gioi] */
    printf("%zu\n", strlen(s));   /* 17 */

    return 0;
}

#Kiểm tra chỗ trống trước khi nối

Nối mù
char s[16] = "Xin chao ";

strcat(s, "mot cai ten rat dai");   /* cần 29 byte, mảng chỉ 16: ghi tràn 13 byte */
Kiểm tra rồi mới nối
char s[16] = "Xin chao ";

if (strlen(s) + strlen(them) + 1 <= sizeof s)
    strcat(s, them);
else
    fprintf(stderr, "Khong du cho\n");
Thành phầnVì sao có mặt
strlen(s)Độ dài phần đã có
strlen(them)Độ dài phần sắp thêm
+ 1Byte kết thúc của chuỗi kết quả
<= sizeof sToàn bộ phải nằm gọn trong mảng

strncat, và vì sao con số của nó khác strncpy

char *strncat(char *dich, const char *nguon, size_t n);

Nối nhiều nhất n ký tự từ nguồn, rồi luôn thêm byte kết thúc. Ở điểm này nó tử tế hơn strncpy. Nhưng con số n có nghĩa khác hẳn: nó là số ký tự thêm vào, không phải kích thước bộ đệm.

char s[16] = "Xin chao ";

strncat(s, them, sizeof s);            /* SAI: có thể ghi tới 16 byte nữa */
strncat(s, them, sizeof s - strlen(s) - 1);   /* đúng nhưng dài dòng */

#Bài toán Shlemiel

Joel Spolsky đặt tên hiện tượng này theo một câu chuyện cười về người thợ sơn vạch kẻ đường: mỗi ngày anh ta sơn được ít hơn, vì phải đi từ thùng sơn đặt ở đầu đường tới chỗ đang sơn.

shlemiel.c
char s[100001] = "";

for (int i = 0; i < 10000; ++i)
    strcat(s, "abcdefghij");     /* mỗi lời gọi phải duyệt lại từ đầu s */
LượtĐộ dài s trước khi nốiSố byte strcat phải duyệt
100
21010
32020
.........
10 00099 99099 990

Tổng số byte duyệt là 0 + 10 + 20 + ... + 99990, khoảng năm trăm triệu. Với một trăm nghìn lượt, con số đó thành năm mươi tỷ. Đây là độ phức tạp bậc hai, dù mã trông như một vòng lặp đơn giản.

terminal
./shlemiel
strcat trong vong lap, 10 000 luot : 0.198 s
strcat trong vong lap, 100 000 luot: 19.4 s
noi tuyen tinh, 100 000 luot       : 0.001 s

#Nối chuỗi tuyến tính

Cách sửa rất đơn giản: nhớ vị trí cuối thay vì đi tìm lại mỗi lượt.

tuyen-tinh.c
char   s[100001];
size_t len = 0;

s[0] = '\0';

for (int i = 0; i < 10000; ++i) {
    int n = snprintf(s + len, sizeof s - len, "abcdefghij");

    if (n < 0 || (size_t)n >= sizeof s - len)
        break;                      /* hết chỗ */

    len += (size_t)n;
}

Một hàm nối tích lũy dùng lại được

noi.c
#include <stdio.h>
#include <string.h>

typedef struct {
    char  *bo_dem;
    size_t co;        /* kích thước bộ đệm */
    size_t len;       /* độ dài chuỗi hiện tại */
    int    tran;      /* 1 nếu đã có lần nào không đủ chỗ */
} BoNoi;

static void noi_khoi_tao(BoNoi *b, char *bo_dem, size_t co)
{
    b->bo_dem = bo_dem;
    b->co     = co;
    b->len    = 0;
    b->tran   = 0;

    if (co > 0) bo_dem[0] = '\0';
}

static void noi_them(BoNoi *b, const char *s)
{
    if (b->tran || b->co == 0) return;

    size_t con_lai = b->co - b->len;
    int    n = snprintf(b->bo_dem + b->len, con_lai, "%s", s);

    if (n < 0 || (size_t)n >= con_lai) {
        b->tran = 1;
        b->len  = b->co - 1;
        return;
    }

    b->len += (size_t)n;
}
dung.c
char  bo_dem[64];
BoNoi b;

noi_khoi_tao(&b, bo_dem, sizeof bo_dem);

noi_them(&b, "Xin ");
noi_them(&b, "chao ");
noi_them(&b, "the gioi");

if (b.tran)
    fprintf(stderr, "Chuoi bi cat\n");
else
    printf("[%s] do dai %zu\n", b.bo_dem, b.len);
terminal
./dung
[Xin chao the gioi] do dai 17

#Chọn giữa ba hàm

HàmGiới hạn theoLuôn kết thúc chuỗiChi phí mỗi lời gọi
strcatKhông cóCóĐộ dài đích cộng độ dài nguồn
strncatSố ký tự thêm vàoCóĐộ dài đích cộng n
snprintf tại vị tríChỗ còn lại của bộ đệmCóChỉ độ dài nguồn

Tự cài strcat

my-strcat.c
char *my_strcat(char *dich, const char *nguon)
{
    char *d = dich;

    while (*d != '\0')      /* đi tới cuối chuỗi đích, đây là phần tốn thời gian */
        ++d;

    while ((*d++ = *nguon++) != '\0')
        ;

    return dich;
}

Vòng lặp thứ nhất chính là nguyên nhân của bài toán Shlemiel. Nhìn thấy nó bằng mắt giúp bạn nhớ rằng strcat không hề rẻ.

Tự làm thử

  1. Nối ba chuỗi bằng strcat vào một mảng đủ lớn, rồi thử với mảng quá nhỏ dưới -fsanitize=address.
  2. Gọi strcat vào một mảng chưa khởi tạo và quan sát chuyện gì xảy ra.
  3. Đo thời gian nối mười nghìn và một trăm nghìn lần bằng strcat, xác nhận tỷ lệ khoảng một trăm lần.
  4. Cài cấu trúc BoNoi trong bài, dùng nó nối một trăm nghìn mảnh và đo thời gian.
  5. Viết hàm ghép đường dẫn từ thư mục, tên và phần mở rộng bằng cả strcat và snprintf, so sánh số dòng.
  6. Cài my_strcat và kiểm thử so với hàm chuẩn, gồm cả trường hợp nối chuỗi rỗng.

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

  • strcat phải duyệt hết chuỗi đích trước khi nối, nên chi phí của nó phụ thuộc cả độ dài đích.
  • Chuỗi đích phải đã hợp lệ trước khi nối. Nối vào mảng chưa khởi tạo là hành vi không xác định.
  • Công thức kiểm tra chỗ trống là strlen(dich) + strlen(nguon) + 1 <= sizeof dich.
  • Nối trong vòng lặp biến chương trình thành bậc hai. Hãy nhớ vị trí cuối thay vì tìm lại mỗi lượt.
  • Con số của strncat là số ký tự thêm vào, không phải kích thước bộ đệm. Đây là khác biệt với strncpy.