Cấu trúc dữ liệu tổng quát trong C: Hướng dẫn chi tiết

Giới thiệu

Trong lập trình C, việc sử dụng các cấu trúc dữ liệu tổng quát là rất quan trọng, đặc biệt là khi không có tính năng template giống như trong C++. Thay vào đó, chúng ta thường sử dụng con trỏ void* để có thể trỏ tới bất kỳ loại dữ liệu nào. Ví dụ, một nút trong cây đỏ-đen có thể được định nghĩa như sau:

typedef struct rb_node rb_node_t;
struct rb_node {
  rb_node_t *child[2];  // 0 = trái; 1 = phải
  rb_node_t *parent;
  void      *data;
};

Tuy nhiên, việc sử dụng con trỏ thay vì lưu trữ dữ liệu trực tiếp trong nút có một số nhược điểm:

• Cần một cuộc gọi riêng để malloc() cho dữ liệu và một cuộc gọi riêng để free() khi giải phóng nó.
• Truy cập dữ liệu chậm hơn vì nó nằm ở một vị trí bộ nhớ khác với nút (không nằm trong cùng một dòng cache).

Nếu kích thước dữ liệu bạn cần lưu trữ nhỏ hơn hoặc bằng sizeof(void*), ví dụ như một int, bạn có thể lưu trữ và truy xuất dữ liệu trực tiếp từ data bằng cách sử dụng ép kiểu:

node->data = (void*)i;  // lưu trữ int
// ...
i = (int)node->data;    // truy xuất int

Nhưng nếu kích thước dữ liệu lớn hơn sizeof(void*), bạn sẽ cần phải malloc bộ nhớ riêng cho nó — hoặc không phải sao?

Cây nhị phân cân bằng, đặc biệt là cây đỏ-đen, là các cấu trúc dữ liệu cốt lõi trong khoa học máy tính (cùng với danh sách liên kết và bảng băm). Trong bài viết này, tôi sẽ trình bày cách làm cho cây đỏ-đen tổng quát trong C; tôi sẽ không đi sâu vào chi tiết của các thuật toán cây đỏ-đen vì mặc dù chúng không quá khó, nhưng chúng hơi phức tạp và làm phân tán mục tiêu của bài viết này.

Nếu bạn muốn tìm hiểu thêm về các thuật toán đứng sau các cây đỏ-đen, có rất nhiều tài nguyên trực tuyến và trong sách. Cuốn sách và tài liệu tham khảo mà tôi sử dụng là cuốn "Introduction to Algorithms, 4th ed.", của Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest và Clifford Stein, MIT Press, ISBN 9780262046305, §13.

Thành viên mảng linh hoạt (FAM)

Có một cách tốt hơn: sử dụng thành viên mảng linh hoạt (FAM) cho data:

struct rb_node {
  rb_node_t *child[2];  // 0 = trái; 1 = phải
  rb_node_t *parent;
  alignas( max_align_t ) char data[];
};

Như tôi đã viết trong bài viết trước, thành viên cuối cùng của một struct có nhiều thành viên có tên có thể là một thành viên mảng linh hoạt, tức là một mảng có kích thước không xác định. Thông thường, một struct như vậy phục vụ như một "header" cho một vùng nhớ lớn hơn.

Nếu chữ ký của rb_tree_insert() bao gồm data_size, thì một nút mới có thể được malloc và dữ liệu có thể được sao chép vào nút như sau:

new_node = malloc( sizeof(rb_node_t) + data_size );
memcpy( new_node->data, data, data_size );

Lưu ý: vì data của một nút là một mảng, nên việc chỉ định tên của nó trong một biểu thức sẽ khiến nó "thối hóa" thành một con trỏ trỏ tới phần tử đầu tiên của nó như thể là &new_node->data[0].

Vì data_size được truyền như một tham số, điều này cho phép mỗi nút có kích thước khác nhau nếu cần thiết.

Vì C chỉ cho phép một cấu trúc có tối đa một FAM, việc sử dụng một FAM chỉ cho phép lưu trữ một khối dữ liệu duy nhất, không phải một khóa và một giá trị riêng biệt như std::map của C++. Nhưng bạn không thực sự cần một khóa và giá trị được lưu trữ riêng biệt: chỉ cần lưu trữ cả hai trong data. Ví dụ, nếu bạn muốn lưu trữ một thứ như số từ, bạn có thể định nghĩa như sau:

struct word_count {
  char     *word;
  unsigned  count;
};

Và lưu trữ điều đó trong FAM. Một hàm so sánh sẽ chỉ so sánh word và bỏ qua count. Hoặc bạn có thể chỉ lưu trữ một giá trị duy nhất. Do đó, một cây đỏ-đen sử dụng FAM có thể thực hiện được một tập hợp hoặc một bản đồ.

Mặc dù việc sử dụng một thành viên mảng linh hoạt loại bỏ những nhược điểm đã đề cập, nhưng nó cũng tạo ra một số nhược điểm riêng:

• Việc chèn dữ liệu vào một cây yêu cầu sao chép nó vào một nút. Đối với dữ liệu lớn, điều này có thể tốn kém.
• Nếu bạn muốn xóa một nút khỏi cây nhưng giữ lại dữ liệu của nó, bạn phải sao chép nó ra trước.

Có nhược điểm theo cả hai cách. Giống như hầu hết mọi thứ trong khoa học máy tính, đây là một sự đánh đổi. Nhưng điều gì sẽ xảy ra nếu có một cách để cho phép người dùng chọn phương pháp lưu trữ dữ liệu nào để sử dụng, tức là bên ngoài nút qua con trỏ hoặc bên trong nút?

Vị trí dữ liệu

Giả sử chúng ta thêm liệt kê sau:

enum rb_dloc {
  RB_DINT,  // Nút chứa dữ liệu nội bộ.
  RB_DPTR   // Nút chứa một con trỏ tới dữ liệu.
};
typedef enum rb_dloc rb_dloc_t;

Và sau đó rb_tree chứa một thành viên của kiểu đó:

struct rb_tree {
  rb_node_t   *root;    // Nút gốc của cây.
  rb_cmp_fn_t  cmp_fn;  // Hàm so sánh dữ liệu.
  rb_dloc_t    dloc;    // Vị trí dữ liệu của nút.
  rb_node_t    nil;     // Sentinel nil.
};
typedef struct rb_tree rb_tree_t;

Cuối cùng, chúng ta thêm các macro trợ giúp sau:

#define RB_DINT(NODE)  ( (void*)(NODE)->data )
#define RB_DPTR(NODE)  ( *(void**)RB_DINT( (NODE) ) )

Nơi RB_DINT(node) truy cập dữ liệu được lưu trữ nội bộ trong node và RB_DPTR(node) truy cập dữ liệu bằng cách sử dụng node như một con trỏ tới nó.

Trong trường hợp bạn tự hỏi làm thế nào có thể có RB_DINT và RB_DPTR vừa là các hằng số liệt kê vừa là các macro tiền xử lý, như tôi đã đề cập trong bài viết về macro của mình, tiền xử lý không mở rộng một macro giống như hàm nếu nó không được theo sau bởi (; do đó, RB_DINT hoặc RB_DPTR không theo sau bởi ( sẽ tham chiếu tới hằng số liệt kê.

Với tất cả điều đó, một rb_dloc được truyền vào hàm để khởi tạo một cây đỏ-đen:

void rb_tree_init( rb_tree_t *tree, rb_dloc_t dloc,
                   rb_cmp_fn_t cmp_fn );

Khi chèn vào một cây đỏ-đen thông qua rb_tree_insert:

rb_insert_rv_t rb_tree_insert( rb_tree_t *tree, void *data,
                               size_t data_size ) {
  // ...
  if ( tree->dloc == RB_DINT ) {
    new_node = malloc( sizeof(rb_node_t) + data_size );
    memcpy( RB_DINT( z_new_node ), data, data_size );
  }
  else {
    new_node = malloc( sizeof(rb_node_t) + sizeof(void*) );
    RB_DPTR( z_new_node ) = data;
  }
  // ...

Khi dloc là RB_DINT, rb_node được malloc đủ lớn cho nút và dữ liệu mà được memcpy vào vị trí; khi dloc là RB_DPTR, chỉ con trỏ tới dữ liệu được sao chép.

Một hàm trợ giúp:

inline void* rb_node_data( rb_tree_t const *tree,
                           rb_node_t const *node ) {
  return tree->dloc == RB_DINT ? RB_DINT(node) : RB_DPTR(node);
}

Lấy con trỏ tới dữ liệu của một nút bất kể nó được lưu trữ ở đâu và:

static inline int rb_tree_cmp( rb_tree_t const *tree,
                               rb_node_t *node,
                               void const *data ) {
  return (*tree->cmp_fn)( data, rb_node_data( tree, node ) );
}

So sánh dữ liệu mới với dữ liệu tại node để tìm hoặc chèn.

Ngoài rb_node_data và rb_tree_insert sử dụng dloc, tất cả các phần còn lại của mã để tìm kiếm, xóa và duyệt nút đều giống hệt như bất kỳ triển khai cây đỏ-đen nào khác.

Trong số các nơi khác, tôi sử dụng một cây đỏ-đen trong cdecl. Các tệp nguồn là red_black.h và red_black.c.

Kết luận

Sử dụng các thành viên mảng linh hoạt hoạt động cho bất kỳ cấu trúc dữ liệu nào sử dụng các nút được cấp phát động (danh sách liên kết, bảng băm, tập hợp hoặc bản đồ) và cho phép người dùng chọn xem dữ liệu được lưu trữ nội bộ trong các nút hay bên ngoài qua con trỏ để phù hợp với hoàn cảnh cụ thể của người dùng.