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

Thêm phần tử

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

  • Cài thêm đầu và thêm cuối trong O(1)
  • Xử lý đúng trường hợp danh sách rỗng ở cả hai hàm
  • Cài chèn vào vị trí bất kỳ và kiểm tra biên
  • Giải thích vì sao mỗi hàm đều phải cập nhật tail

Ba hàm thêm, ba tình huống. Điểm chung của cả ba là cùng một cái bẫy: trường hợp danh sách đang rỗng, và thứ tự nối lại con trỏ. Sai một trong hai là mất dữ liệu hoặc rò rỉ bộ nhớ.

#Thêm đầu, O(1)

list.c
/* Thêm vào đầu. Trả về 0 nếu thành công, -1 nếu hết bộ nhớ. */
int list_them_dau(List *l, int data)
{
    Node *n = node_tao(data);

    if (n == NULL) return -1;

    n->next = l->head;           /* 1. nút mới trỏ vào đầu cũ */
    l->head = n;                 /* 2. đầu mới là nút vừa tạo */

    if (l->tail == NULL)         /* 3. danh sách trước đó rỗng */
        l->tail = n;

    ++l->size;

    return 0;
}
Trạng thái trướcheadtailSau khi thêm đầu 5
RỗngNULLNULLhead và tail cùng trỏ vào nút 5
Một nút [10]-> 10-> 10head -> 5 -> 10, tail vẫn -> 10
Ba nút [10, 20, 30]-> 10-> 30head -> 5 -> 10 -> 20 -> 30, tail vẫn -> 30

#Thêm cuối, O(1) nhờ tail

list.c (tiếp)
/* Thêm vào cuối. O(1) vì có tail, nếu không thì phải duyệt hết danh sách. */
int list_them_cuoi(List *l, int data)
{
    Node *n = node_tao(data);

    if (n == NULL) return -1;

    if (l->tail != NULL)
        l->tail->next = n;       /* nối nút cuối cũ vào nút mới */
    else
        l->head = n;             /* danh sách rỗng, nút mới cũng là đầu */

    l->tail = n;                 /* nút mới luôn thành cuối */
    ++l->size;

    return 0;
}
O(n) mỗi lần thêm cuối
/* Không giữ tail, phải duyệt mỗi lần */
int list_them_cuoi_cham(List *l, int data)
{
    Node *n = node_tao(data);

    if (n == NULL) return -1;

    if (l->head == NULL) { l->head = n; ++l->size; return 0; }

    Node *p = l->head;

    while (p->next != NULL) p = p->next;      /* O(n) mỗi lần gọi */

    p->next = n;
    ++l->size;

    return 0;
}
O(1) nhờ tail
/* Giữ tail, mỗi lần thêm cuối là O(1) */
if (l->tail != NULL) l->tail->next = n;
else                 l->head = n;

l->tail = n;
terminal
# Thêm 200000 phần tử vào cuối, hai cách
./do-them-cuoi 200000
co tail    : 0.008 s
khong tail : 12.470 s
cham hon   : 1558.8 lan

Con số đó không phải là hằng số nhân. Bản không có tail tốn tổng cộng khoảng n bình phương chia hai phép nhảy con trỏ, tức 2 tỷ lần với n bằng 200000. Tăng n lên gấp đôi thì chênh lệch tăng gấp bốn.

#Chèn vào vị trí bất kỳ

Nối n->next trước, rồi mới sửa truoc->next. Đảo thứ tự là mất luôn phần đuôi.
list.c (tiếp)
/* Chèn vào vị trí i, tức sau khi chèn thì phần tử mới có chỉ số i.
   Cho phép i bằng size, nghĩa là thêm vào cuối.
   Trả về 0 nếu ổn, -1 nếu i quá lớn hoặc hết bộ nhớ. */
int list_chen(List *l, size_t i, int data)
{
    if (i > l->size)     return -1;
    if (i == 0)          return list_them_dau(l, data);
    if (i == l->size)    return list_them_cuoi(l, data);

    /* Đi tới nút đứng ngay TRƯỚC vị trí i, tức nút có chỉ số i-1.
       Vòng lặp chạy đúng i-1 bước, và chắc chắn không chạm NULL
       vì 0 < i < size. */
    Node *truoc = l->head;

    for (size_t k = 0; k + 1 < i; ++k)
        truoc = truoc->next;

    Node *n = node_tao(data);

    if (n == NULL) return -1;

    n->next     = truoc->next;      /* 1. nút mới nối vào phần đuôi */
    truoc->next = n;                /* 2. nút trước nối vào nút mới */

    ++l->size;

    return 0;
}

#Thứ tự nối con trỏ quyết định đúng sai

Sai thứ tự
truoc->next = n;                /* mất địa chỉ phần đuôi */
n->next     = truoc->next;      /* giờ n->next chính là n */
Đúng thứ tự
n->next     = truoc->next;      /* n giữ lấy phần đuôi */
truoc->next = n;                /* rồi mới cắt liên kết cũ */

Bản sai tạo ra một nút tự trỏ vào chính nó, và toàn bộ phần đuôi danh sách không còn ai giữ địa chỉ, tức rò rỉ bộ nhớ. Vòng lặp duyệt tiếp theo sẽ chạy vô hạn ở nút n.

terminal
gcc -std=c17 -g chen-sai.c -o t && timeout 3 ./t
[10, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, ...
# Phần đuôi bị mất hẳn, valgrind thấy ngay
valgrind --leak-check=full ./t-ngan
==7788== 32 bytes in 2 blocks are definitely lost in loss record 1 of 1
==7788==    at 0x4848899: malloc (vg_replace_malloc.c:381)
==7788==    by 0x1091A5: node_tao (chen-sai.c:12)

#Xử lý hết bộ nhớ

Cả ba hàm đều tạo nút trước, kiểm tra NULL, rồi mới đụng vào danh sách. Thứ tự đó không phải ngẫu nhiên: nó bảo đảm khi hàm thất bại thì danh sách vẫn y nguyên như trước lúc gọi.

Mức bảo đảmNghĩa là gìHàm nào của ta đạt được
Không bảo đảmThất bại thì cấu trúc có thể ở trạng thái bất kỳKhông hàm nào, và cũng không nên
Bảo đảm cơ bảnThất bại thì cấu trúc vẫn hợp lệ, nhưng nội dung có thể đổiMức tối thiểu
Bảo đảm mạnhThất bại thì cấu trúc y hệt như trước khi gọiCả ba hàm thêm
Sửa trạng thái trước khi biết thành công
int list_them_dau_te(List *l, int data)
{
    ++l->size;                   /* sửa trước */

    Node *n = malloc(sizeof *n);

    if (n == NULL) return -1;    /* size đã sai, bất biến 4 vỡ */

    n->data = data;
    n->next = l->head;
    l->head = n;

    return 0;
}
Cấp phát xong mới sửa trạng thái
int list_them_dau(List *l, int data)
{
    Node *n = node_tao(data);

    if (n == NULL) return -1;    /* chưa đụng gì vào l, mọi bất biến còn nguyên */

    n->next = l->head;
    l->head = n;

    if (l->tail == NULL) l->tail = n;

    ++l->size;

    return 0;
}

Người gọi phải kiểm tra giá trị trả về

main.c
#include <stdio.h>

#include "list.h"

int main(void)
{
    List l;

    list_khoi_tao(&l);

    for (int i = 1; i <= 5; ++i)
        if (list_them_cuoi(&l, i * 10) != 0) {
            fprintf(stderr, "Het bo nho\n");
            list_huy(&l);
            return 1;
        }

    list_in(&l);

    if (list_them_dau(&l, 5) != 0)  { list_huy(&l); return 1; }
    if (list_chen(&l, 3, 99) != 0)  { list_huy(&l); return 1; }

    list_in(&l);

    printf("chen ngoai bien: %d\n", list_chen(&l, 100, 0));

    list_huy(&l);

    return 0;
}
terminal
gcc -std=c17 -Wall -Wextra -g list.c main.c -o t && ./t
[10, 20, 30, 40, 50]  (size = 5)
[5, 10, 20, 99, 30, 40, 50]  (size = 7)
chen ngoai bien: -1
# Valgrind cần bản không bật sanitizer
valgrind --leak-check=full ./t
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts

Tự làm thử

  1. Cài cả ba hàm thêm, rồi gọi list_kiem_tra ở Bài 21.2 sau mỗi lần gọi để xác nhận bất biến còn nguyên.
  2. Cố tình bỏ dòng cập nhật tail trong list_them_dau, rồi thêm đầu một phần tử vào danh sách rỗng và thêm cuối một phần tử nữa. Giải thích kết quả nhận được.
  3. Viết bản list_them_cuoi không dùng tail rồi đo thời gian thêm 50000, 100000 và 200000 phần tử. Xác nhận tỷ lệ tăng theo bình phương.
  4. Cài list_chen_sau(List *l, Node *truoc, int data) nhận thẳng con trỏ. Đây là trường hợp O(1) thật sự.
  5. Cài list_them_da(List *l, const int *a, size_t n) thêm nhiều phần tử cùng lúc, và giữ được bảo đảm mạnh: thất bại giữa chừng thì danh sách y như trước khi gọi.

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

  • Thêm đầu và thêm cuối đều là O(1), nhưng thêm cuối chỉ O(1) khi có tail.
  • Mọi hàm thêm đều phải xử lý riêng trường hợp danh sách đang rỗng, vì khi đó nút mới vừa là đầu vừa là cuối.
  • Thứ tự nối con trỏ là bắt buộc: gán n->next trước, sửa truoc->next sau. Đảo lại là mất phần đuôi.
  • Chèn vào vị trí i hợp lệ với i từ 0 tới size, tức n cộng 1 vị trí cho n phần tử.
  • Cấp phát trước rồi mới sửa trạng thái, để hàm thất bại vẫn để lại danh sách y nguyên.