Bài 21.226 phút đọc

Danh sách liên kết đơn

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

Thiết kế struct List với ba trường và nêu bất biến của nó
Viết hàm tạo nút trả về NULL đúng cách khi hết bộ nhớ
Hủy toàn bộ danh sách mà không chạm vào con trỏ đã giải phóng
Kiểm tra bất biến bằng một hàm tự kiểm

Một con trỏ head trần là đủ để có danh sách, nhưng mọi hàm sẽ phải nhận và trả lại nó, còn đếm số phần tử thì phải duyệt. Gói lại thành một struct làm mã gọn hơn và cho bạn chỗ để phát biểu những điều luôn phải đúng.

#Vì sao cần một struct bao ngoài

Con trỏ trần

/* Chỉ có con trỏ head trần */
Node *head = NULL;

head = them_dau(head, 10);     /* phải nhận rồi gán lại */
head = them_dau(head, 20);

size_t n = dem(head);          /* O(n) mỗi lần muốn biết số phần tử */

/* Thêm cuối phải duyệt hết danh sách, O(n) */

Struct bao ngoài

typedef struct {
    Node  *head;      /* nút đầu, NULL khi rỗng */
    Node  *tail;      /* nút cuối, để thêm cuối trong O(1) */
    size_t size;      /* số phần tử, để hỏi trong O(1) */
} List;

List l;

list_khoi_tao(&l);
list_them_dau(&l, 10);         /* hàm tự sửa head, không phải gán lại */
list_them_cuoi(&l, 20);        /* O(1) nhờ tail */

printf("%zu\n", l.size);       /* O(1) nhờ size */

Ba trường này không phải quy ước cố định. tail chỉ đáng giữ nếu bạn thật sự thêm vào cuối, còn size chỉ đáng giữ nếu bạn thật sự hỏi số phần tử. Mỗi trường thêm vào là một thứ nữa phải nhớ cập nhật ở mọi hàm, và quên cập nhật là nguồn lỗi kinh điển của chương này.

#Bốn bất biến phải giữ

Bất biến

Một mệnh đề luôn đúng về trạng thái của cấu trúc, ở mọi thời điểm bên ngoài hàm nhìn thấy được. Nó có thể tạm sai ở giữa thân hàm, nhưng phải đúng lại trước khi hàm trả về.

Bất biến	Ý nghĩa	Hàm nào dễ làm hỏng
head là NULL khi và chỉ khi size bằng 0	Không có danh sách rỗng mà head khác NULL	Xóa phần tử cuối cùng
tail là NULL khi và chỉ khi head là NULL	Hai con trỏ luôn cùng rỗng hoặc cùng không rỗng	Thêm vào danh sách đang rỗng
tail->next luôn là NULL	tail thật sự là nút cuối	Thêm cuối mà quên cập nhật tail
size bằng đúng số nút đi được từ head	size không nói dối	Mọi hàm thêm và xóa

Viết bất biến ra thành chú thích ngay trong header

Bốn dòng chú thích này có giá trị hơn nhiều so với việc bạn cố nhớ. Khi sửa lỗi, câu hỏi đầu tiên luôn là bất biến nào đang bị vi phạm, và có sẵn danh sách thì bạn kiểm được từng cái một.

list.h

#ifndef LIST_H
#define LIST_H

#include <stddef.h>

typedef struct Node {
    int          data;
    struct Node *next;
} Node;

/* Bất biến của List, luôn đúng ngoài thân các hàm list_*:
     1. head == NULL  khi và chỉ khi  size == 0
     2. tail == NULL  khi và chỉ khi  head == NULL
     3. tail != NULL  thì  tail->next == NULL
     4. size == số nút đi được từ head theo next                   */
typedef struct {
    Node  *head;
    Node  *tail;
    size_t size;
} List;

void   list_khoi_tao(List *l);
void   list_huy(List *l);
size_t list_so_phan_tu(const List *l);
void   list_in(const List *l);

#endif

#Khởi tạo và tạo nút

list.c

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

#include "list.h"

void list_khoi_tao(List *l)
{
    l->head = NULL;
    l->tail = NULL;
    l->size = 0;
}

/* Cấp một nút mới đã điền sẵn data và next bằng NULL.
   Trả về NULL nếu hết bộ nhớ. Hàm nội bộ, không xuất ra header. */
static Node *node_tao(int data)
{
    Node *n = malloc(sizeof *n);

    if (n == NULL) return NULL;

    n->data = data;
    n->next = NULL;

    return n;
}

size_t list_so_phan_tu(const List *l)
{
    return l->size;      /* O(1), nhờ bất biến số 4 */
}

Có thể dùng calloc để bớt một dòng

static Node *node_tao(int data)
{
    Node *n = calloc(1, sizeof *n);      /* mọi byte bằng 0, next tự là NULL */

    if (n == NULL) return NULL;

    n->data = data;

    return n;
}

Cách này chỉ an toàn vì trên mọi nền tảng thực tế con trỏ NULL được biểu diễn bằng toàn bit 0. Chuẩn C không bảo đảm điều đó, dù chưa ai gặp nền tảng nào khác. Bài 14.7 đã bàn kỹ. Với mã dạy học thì gán tường minh n->next = NULL rõ ràng hơn.

#Duyệt và in

list.c (tiếp)

void list_in(const List *l)
{
    printf("[");

    for (const Node *p = l->head; p != NULL; p = p->next) {
        printf("%d", p->data);

        if (p->next != NULL) printf(", ");
    }

    printf("]  (size = %zu)\n", l->size);
}

Vòng lặp for (Node *p = head; p; p = p->next) là mẫu bạn sẽ gõ hàng trăm lần trong chương này. Ba phần của nó: bắt đầu từ đầu, dừng khi hết, và mỗi bước nhảy sang nút kế.

#Hủy danh sách

Lưu next trước khi giải phóng
Sau free(p) thì p->next là đọc vùng đã giải phóng, tức hành vi không xác định. Phải cầm địa chỉ nút kế trong một biến riêng trước.
Giải phóng nút hiện tại
Một lần free cho mỗi lần malloc, không hơn không kém.
Đưa danh sách về trạng thái rỗng hợp lệ
Gọi lại list_khoi_tao để head, tail và size cùng về 0. Nhờ vậy gọi list_huy hai lần vẫn an toàn.

Dùng sau khi giải phóng

void list_huy(List *l)
{
    for (Node *p = l->head; p != NULL; p = p->next)
        free(p);              /* p->next đọc vùng đã giải phóng */

    list_khoi_tao(l);
}

Lưu next trước

void list_huy(List *l)
{
    Node *p = l->head;

    while (p != NULL) {
        Node *ke = p->next;      /* lưu TRƯỚC khi free */

        free(p);
        p = ke;
    }

    list_khoi_tao(l);            /* gọi hai lần vẫn an toàn */
}

terminal

# Bản sai chạy được nhiều lần rồi mới sập, đúng kiểu lỗi bộ nhớ

gcc -std=c17 -g -fsanitize=address huy-sai.c -o t-asan && ./t-asan

ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000018
READ of size 8 at 0x602000000018 thread T0
    #0 in list_huy huy-sai.c:5

0x602000000018 is located 8 bytes inside of 16-byte region
freed by thread T0 here:
    #0 in free
    #1 in list_huy huy-sai.c:4

# Bản đúng, kiểm bằng valgrind trên bản dịch không bật sanitizer

gcc -std=c17 -g list.c main.c -o t && valgrind --leak-check=full ./t

All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts

Đừng gọi list_huy rồi tiếp tục dùng con trỏ cũ

Node *giu = l.head;

list_huy(&l);

printf("%d\n", giu->data);      /* con trỏ treo, xem Bài 14.11 */

Đây là lỗi con trỏ treo ở Bài 14.11, chỉ đổi bối cảnh. Quy tắc vẫn vậy: sau khi hủy một cấu trúc, mọi con trỏ trỏ vào bên trong nó đều hết hạn.

#Hàm tự kiểm tra bất biến

Bốn bất biến ở trên kiểm được bằng mã. Trong bản gỡ lỗi, gọi hàm này ở cuối mỗi hàm sửa đổi thì lỗi lộ ra ngay tại chỗ gây ra nó, thay vì hai trăm dòng sau.

list.c (tiếp)

#include <assert.h>

/* Chỉ dùng khi gỡ lỗi. Với NDEBUG thì mọi assert biến mất, xem Bài 19.4. */
void list_kiem_tra(const List *l)
{
    assert(l != NULL);

    /* Bất biến 1 và 2 */
    assert((l->head == NULL) == (l->size == 0));
    assert((l->tail == NULL) == (l->head == NULL));

    /* Bất biến 3 */
    if (l->tail != NULL) assert(l->tail->next == NULL);

    /* Bất biến 4, và tiện thể phát hiện chu trình */
    size_t dem = 0;

    for (const Node *p = l->head; p != NULL; p = p->next) {
        ++dem;
        assert(dem <= l->size);      /* vượt quá tức là có chu trình */

        if (p->next == NULL) assert(p == l->tail);
    }

    assert(dem == l->size);
}

Chi phí O(n) là chấp nhận được khi gỡ lỗi

Hàm này duyệt cả danh sách nên gọi nó sau mỗi thao tác biến chương trình từ O(n) thành O(n bình phương). Điều đó hoàn toàn ổn trong bản gỡ lỗi với dữ liệu nhỏ. Bọc nó trong #ifndef NDEBUG để bản phát hành không mất gì.

#ifdef NDEBUG
#define LIST_KIEM_TRA(l)  ((void)0)
#else
#define LIST_KIEM_TRA(l)  list_kiem_tra(l)
#endif

Chương trình thử

main.c

#include <stdio.h>

#include "list.h"

int main(void)
{
    List l;

    list_khoi_tao(&l);
    list_in(&l);

    /* Dựng tay ba nút để thử, các hàm thêm nằm ở Bài 21.3 */
    if (list_them_cuoi(&l, 10) != 0) return 1;
    if (list_them_cuoi(&l, 20) != 0) { list_huy(&l); return 1; }
    if (list_them_cuoi(&l, 30) != 0) { list_huy(&l); return 1; }

    list_in(&l);
    printf("so phan tu = %zu\n", list_so_phan_tu(&l));

    list_huy(&l);
    list_in(&l);

    list_huy(&l);      /* gọi lần hai, vẫn an toàn */

    return 0;
}

terminal

gcc -std=c17 -Wall -Wextra -g list.c main.c -o t && ./t

[]  (size = 0)
[10, 20, 30]  (size = 3)
so phan tu = 3
[]  (size = 0)

Tự làm thử

Viết list.h và list.c với ba hàm list_khoi_tao, list_in, list_huy, kèm bốn dòng chú thích bất biến.
Cài list_kiem_tra rồi cố tình làm hỏng một bất biến, ví dụ tăng size mà không thêm nút, và xác nhận assert bắt được.
Viết bản list_huy sai như trong bài, chạy dưới -fsanitize=address và đọc kỹ báo cáo.
Thêm trường Node *tail vào rồi bỏ đi. Đo bằng clock thời gian thêm 100000 phần tử vào cuối trong hai trường hợp.
Viết list_dem_thuc(const List *l) duyệt để đếm, rồi so với l->size sau một loạt thao tác ngẫu nhiên.

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

Gói head, tail, size vào một struct làm mọi hàm gọn hơn và cho tail lẫn size chỗ để sống.
Bốn bất biến của List phải được viết ra thành chú thích và kiểm được bằng mã.
Hàm tạo nút phải đặt next bằng NULL và trả về NULL khi hết bộ nhớ.
Hủy danh sách bắt buộc lưu next trước khi free, rồi đưa struct về trạng thái rỗng hợp lệ để gọi lại vẫn an toàn.
Hàm tự kiểm tra tốn O(n) nhưng chỉ chạy trong bản gỡ lỗi, và nó bắt lỗi ngay tại nơi gây ra.