Triển khai khái quát các cấu trúc lưu trữ cho C bằng Macro

Một trong những mục đích quan trọng của lập trình khái quát là tạo mã nguồn có thể sử dụng được trong nhiều trường hợp tương tự, đáp ứng nhu cầu tái sử dụng mã nguồn. Các triển khai cấu trúc lưu trữ cho các kiểu phần tử khác nhau có rất nhiều điểm tương đồng, như bố cục bộ nhớ, các thuật toán thêm, xóa phần tử, v.v... Những đặc điểm đó cũng là cơ sở quan trọng để khái quát hóa các triển khai cấu trúc lưu trữ cho C bằng Macro.

[@ Nguyễn Bá Ngọc, ngocnb@soict.hust.edu.vn, 2025]

Mã nguồn: https://github.com/bangoc/cgen/tree/master/macro

Phần I. Cấu trúc lưu trữ ánh xạ khóa => giá trị 4

1. Cây nhị phân tìm kiếm với khóa là chuỗi ký tự <bst.h> 4

1.1. Các đặc điểm 4

1.2. Khai báo và định nghĩa 4

1.2.1. struct si *si(); 5

1.2.2. struct si *si_cmp(struct si*, int (*cmp)(const char *, const char *)); 5

1.2.3. struct si_node *si_put(struct si *t, const char *key, int value); 6

1.2.4. struct si_node *si_get(struct si *t, const char *key); 6

1.2.5. int si_rem(struct si *t, const char *key); 6

1.2.6. void si_free(struct si *t); 7

1.3. Ví dụ minh họa 7

2. Giao diện duyệt cây <tnav.h> 10

2.1. Khai báo và định nghĩa 10

2.1.1. struct bst_node *bst_first_lnr(struct bst *tm); 10

2.1.2. struct bst_node *bst_next_lnr(struct bst_node *n); 10

2.1.3. struct bst_node *bst_first_rnl(struct bst *tm); 11

2.1.4. struct bst_node *bst_next_rnl(struct bst_node *n); 11

2.1.5. struct bst_node *bst_first_lrn(struct bst *tm); 11

2.1.6. struct bst_node *bst_next_lrn(struct bst_node *n); 11

2.1.7. void bst_trav(struct bst*, void (*f)(struct bst_node*, void*), void *u); 12

2.1.8. void bst_walk(); 12

2.2. Mẫu vòng lặp duyệt cây 12

3. Ánh xạ khóa => giá trị dựa trên cây đỏ đen <tmap.h> 14

3.1. Các đặc điểm 14

3.2. Khai báo và định nghĩa 14

3.2.1. struct tmap *tmap(int (*cmp)(const char *, const char *)); 16

3.2.2. struct tmap *tmap_fk(struct tmap *tm, void (*fk)()); 16

3.2.3. struct tmap *tmap_fv(struct tmap *tm, void (*fv)()); 16

3.2.4. struct tmap *tmap_ak(struct tmap*, void (*ak)(key_t*, const key_t)); 17

3.2.5. struct tmap *tmap_av()); 17

3.2.6. struct tmap_node *tmap_put(struct tmap *tm, char *key, int value); 17

3.2.7. struct tmap_node *tmap_get(struct tmap *tm, char *key); 17

3.2.8. int tmap_rem(struct tmap *tm, char *key); 18

3.2.9. void tmap_free(struct tmap *tm); 18

3.3. Ví dụ minh họa 18

4. Ánh xạ khóa => giá trị dựa trên bảng băm <hmap.h> 21

4.1. Các đặc điểm 21

4.2. Khai báo và định nghĩa 21

4.2.1. struct hmap *hmap(); 22

4.2.2. struct hmap *hmap_fk(struct hmap *hm, void (*fk)()); 23

4.2.3. struct hmap *hmap_fv(struct hmap *hm, void (*fv)()); 23

4.2.4. struct hmap *hmap_ak(); 23

4.2.5. struct hmap *hmap_av(); 23

4.2.6. struct hmap *hmap_realloc(struct hmap *hm, int ncap); 24

4.2.7. struct hmap_elem *hmap_put(struct hmap *hm, char *k, int v); 24

4.2.8. int *hmap_get(struct hmap *hm, const char *k); 24

4.2.9. int hmap_rem(struct hmap *hm, const char *k); 24

4.2.10. struct hmap_elem *hmap_first(struct hmap *hm); 25

4.2.11. struct hmap_elem *hmap_next(struct hmap*, struct hmap_elem*); 25

4.2.12. void hmap_trav(); 25

4.2.13. void hmap_free(struct hmap *hm); 26

4.3. Ví dụ minh họa 26

Phần II. Cấu trúc lưu trữ tuần tự 29

5. Mảng cấp phát động - <arr.h> 29

5.1. Các đặc điểm 29

5.2. Các khai báo và định nghĩa 29

5.2.1. arr(elem_t, n) 29

5.2.2. arr_cap(a) 30

5.2.3. arr_reserve(a, cap) 30

5.2.4. arr_for(a, i) 30

5.2.5. arr_rfor(a, i) 30

5.2.6. void arr_free(void *a) 31

5.3. Ví dụ minh họa 31

6. Triển khai vec-tơ cho C - <vect.h> 32

6.1. Các đặc điểm 32

6.2. Các khai báo và định nghĩa 32

6.2.1. struct ivec *ivec(int n); 33

6.2.2. struct ivec *ivec_reserve(struct ivec *v, int newcap); 33

6.2.3. struct ivec *ivec_resize(struct ivec *v, int newsize); 33

6.2.4. struct ivec *ivec_append(struct ivec *v, int elem); 33

6.2.5. struct ivec *ivec_ins(struct ivec *v, int idx, int elem); 33

6.2.6. int ivec_del(struct ivec *v, int idx); 34

6.2.7. int *ivec_at(struct ivec *v, int idx); 34

6.2.8. void ivec_free(struct ivec *v); 34

6.3. Ví dụ minh họa 34

7. Danh sách móc nối đơn - <slist.h> 36

7.1. Các đặc điểm 36

7.2. Các khai báo và định nghĩa 36

7.2.1. struct sll *sll(); 37

7.2.2. struct sll *sll_append(struct sll *list, int value); 37

7.2.3. struct sll *sll_prepend(struct sll *list, int value); 37

7.2.4. int sll_dfirst(struct sll *list); 37

7.2.5. struct sll *sll_ins(struct sll *list, int idx, int value); 38

7.2.6. struct sll *sll_insa(struct sll *list, struct sll_node *pos, int value); 38

7.2.7. struct sll_node *sll_at(struct sll *list, int idx); 38

7.2.8. int sll_del(struct sll *list, int idx); 38

7.2.9. struct sll *sll_push(struct sll *list, int elem); 38

7.2.10. int *sll_top(struct sll *list); 39

7.2.11. int sll_pop(struct sll *list); 39

7.2.12. struct sll *sll_enq(struct sll *list, int elem); 39

7.2.13. int *sll_peek(struct sll *list); 39

7.2.14. int sll_deq(struct sll *list); 39

7.2.15. int sll_empty(struct sll *list); 39

7.2.16. void sll_free(struct sll *list); 40

7.3. Ví dụ minh họa 40

8. Danh sách móc nối kép - <dll.h> 42

8.1. Các đặc điểm 42

8.2. Các khai báo và định nghĩa 42

8.2.1. struct dll *dll(); 43

8.2.2. struct dll *dll_append(struct dll *list, int value); 43

8.2.3. struct dll *dll_prepend(struct dll *list, int value); 43

8.2.4. struct dll *dll_ins(struct dll *list, int idx, int value); 43

8.2.5. struct dll *dll_insa(struct dll *list, struct dll_node *pos, int value); 44

8.2.6. struct dll *dll_insb(struct dll *list, struct dll_node *pos, int value); 44

8.2.7. struct dll_node *dll_at(struct dll *list, int idx); 44

8.2.8. int dll_dfirst(struct dll *list); 44

8.2.9. int dll_dlast(struct dll *list); 44

8.2.10. int dll_dnode(struct dll *list, struct dll_node *node); 44

8.2.11. int dll_del(struct dll *list, int idx); 45

8.2.12. int dll_empty(struct dll *list); 45

8.2.13. void dll_free(struct dll *list); 45

Phần I. Cấu trúc lưu trữ ánh xạ khóa => giá trị

1. Cây nhị phân tìm kiếm với khóa là chuỗi ký tự <bst.h>

<bst.h> - Triển khai cấu trúc tra cứu khóa => giá trị dựa trên cây nhị phân tìm kiếm cơ bản nhất, không cân bằng. Trong đó khóa là chuỗi ký tự độ dài cố định, người dùng có thể tùy chỉnh kích thước khóa và kiểu dữ liệu của giá trị.

1.1. Các đặc điểm

Khóa có kiểu chuỗi ký tự độ dài cố định. Người dùng có thể tùy chỉnh độ dài của khóa. Triển khai tự quản lý vùng nhớ cấp phát cho khóa. Việc mặc định kiểu chuỗi ký tự cho khóa vẫn đảm bảo tính linh động để sử dụng trong nhiều trường hợp khác nhau. Ví dụ, nếu muốn sử dụng kiểu số làm khóa thì có thể chuyển số sang chuỗi, tham khảo hàm sprintf, tuy không phải lựa chọn hiệu quả nhất nhưng khá đơn giản vì không cần thay đổi triển khai cây. Tương tự với những kiểu dữ liệu khác.
So sánh khóa được mặc định thực hiện bằng hàm strcmp, trong các trường hợp đặc biệt khác, ví dụ cần so sánh không phân biệt chữ hoa chữ thường, v.v.., người dùng có thể thay đổi cmp = hàm so sánh phù hợp.
Người dùng tự đặt tên cho cấu trúc dữ liệu, định danh đó phải đảm bảo tính duy nhất và được sử dụng làm tiền tố cho các định danh thành phần.
Người dùng có thể tùy chỉnh kiểu dữ liệu của giá trị, tuy nhiên phải đảm bảo có thể sao chép dữ liệu bằng phép gán. Bên cạnh đó nếu có liên kết đến vùng nhớ động bên ngoài thì người dùng cần tự giải phóng khi xóa nút, triển khai không thực hiện giải phóng bộ nhớ động bên ngoài gắn với giá trị.

1.2. Khai báo và định nghĩa

Macro BST_DECL_IMPL kết hợp 2 Macro BST_DECL và BST_IMPL - Khai báo và định nghĩa cấu trúc lưu trữ.

Các tham số:

tname: Tên cấu trúc điều khiển, đồng thời là tiền tố cho các hàm giao diện.
key_size: Kích thước khóa, phải là số nguyên dương.
value_t: Kiểu dữ liệu của giá trị

Ví dụ:

BST_DECL_IMPL(si, 256, int) - Khai báo và định nghĩa 1 cấu trúc lưu trữ khóa-giá trị với tên là si (ánh xạ chuỗi ký tự => số nguyên), trong đó khóa có kiểu char[256] và giá trị có kiểu int.

Macro BST_DECL_IMPL(si, 256, int) sinh các định nghĩa và khai báo cho các thành phần sau:

struct si_node {
char key[256];
int value;
struct si_node *left, *right, *top;
};
struct si {
struct si_node *root;
int (*cmp)(const char *, const char *);
int size;
};

Định danh si được cung cấp trong macro được sử dụng làm tên cấu trúc điều khiển chính và được sử dụng làm tiền tố cho các định danh thành phần khác như si_node.

Các hàm giao diện sau được định nghĩa cho cấu trúc si:

1.2.1. struct si *si();

struct si *si();

Hàm tạo cấu trúc điều khiển, được thiết kế trùng tên với tên cấu trúc. Ví dụ sử dụng: struct si *t = si();

Trong trường hợp cần sử dụng hàm khác strcmp để so sánh khóa thì có thể thiết lập lại trường cmp (xem hàm si_cmp).

Giá trị trả về:

Hàm trả về con trỏ tới đối tượng struct si được tạo.

1.2.2. struct si si_cmp(struct si, int (cmp)(const char , const char *));

struct si *si_cmp(struct si* t,

int (*cmp)(const char *key1, const char *key2));

Thiết lập hàm so sánh cho cây ánh xạ được trỏ tới bởi t. Đối số cmp là con trỏ tới 1 hàm nhận 2 hằng chuỗi ký tự và trả về 1 giá trị kiểu int.

Giá trị trả về:

Hàm trả về con trỏ t.

1.2.3. struct si_node si_put(struct si t, const char *key, int value);

struct si_node *si_put(struct si *t, const char *key, int value);

Hàm thêm cặp khóa-giá trị vào lưu trữ. Chuỗi được trỏ tới bởi key sẽ được sao chép vào trong nút, có thể thay đổi hoặc giải phóng bộ nhớ đang được trỏ tới bởi key sau đó mà không ảnh hưởng tới dữ liệu được lưu trữ.

Giá trị trả về:

Hàm si_put trả về NULL nếu key là khóa mới, chưa có trong cây. Trong trường hợp ngược lại, nếu key đã có trong lưu trữ thì hàm trả về con trỏ tới nút tương ứng với key^[1].

1.2.4. struct si_node si_get(struct si t, const char *key);

struct si_node *si_get(struct si *t, const char *key);

Hàm tìm khóa trong cây.

Giá trị trả về:

Hàm trả về con trỏ tới nút tương ứng với khóa nếu tìm thấy, hoặc NULL nếu khóa không có trong cây.

1.2.5. int si_rem(struct si t, const char key);

int si_rem(struct si *t, const char *key);

Hàm xóa nút tương ứng với khóa trong cây. Nếu tìm thấy khóa trong cây thì xóa nút và giải phóng bộ nhớ đã cấp phát cho nút, nếu ngược lại thì bỏ qua, cây không thay đổi.

Giá trị trả về:

Hàm trả về 1 nếu đã xóa nút, trong trường hợp ngược lại - cây không thay đổi hàm trả về 0.

1.2.6. void si_free(struct si *t);

void si_free(struct si *t);

Hàm hủy, giải phóng bộ nhớ đã cấp phát trong cây.

Giá trị trả về:

Hàm không trả về giá trị nào.

1.3. Ví dụ minh họa

Sau đây là ví dụ xử lý dữ liệu khóa - giá trị cổ điển. Chương trình đọc và thực hiện các lệnh. Trong đó: Lệnh insert - thêm 1 từ vào lưu trữ, nếu từ đã tồn tại thì tăng biến đếm thêm 1. Lệnh freq - xem tần suất của 1 từ. Lệnh rem - xóa từ khỏi cây. Lệnh print không có tham số - xuất khóa cùng với tần suất theo thứ tự tăng dần khóa. Chương trình kết thúc sau khi đọc hết dữ liệu từ luồng nhập. Giả sử từ có ít hơn 32 ký tự.

#include "bst.h"
#include <stdio.h>
#include <string.h>
BST_DECL_IMPL(bst, 32, int)
int main() {
struct bst *t = bst();
char cmd[32], word[32];
while (scanf("%s", cmd) == 1) {
if (strcmp(cmd, "print") == 0) {
printf("Traverse: \n"); // Xem tnav.h
for (struct bst_node *n = bst_first_lnr(t);
n; n = bst_next_lnr(n)) {
printf("%s: %d\n", n->key, n->value);
}
continue;
}
scanf("%s", word);
if (strcmp(cmd, "insert") == 0) {
struct bst_node *n = bst_put(t, word, 1);
if (n) {
++n->value;
printf("freq(%s) updated = %d\n",
word, n->value);
} else {
printf("Inserted %s\n", word);
}
} else if (strcmp(cmd, "freq") == 0) {
struct bst_node *n = bst_get(t, word);
printf("freq(%s) = %d\n",
word, n? n->value: 0);
} else if (strcmp(cmd, "rem") == 0) {
if (bst_rem(t, word)) {
printf("Deleted %s\n", word);
}
}
}
bst_free(t);
}

Ví dụ dữ liệu đầu vào:

insert aaa

insert bbb

insert aaa

insert ccc

freq bbb

freq aaa

rem aaa

freq aaa

insert aaa

Dữ liệu đầu ra thu được tương ứng:

Inserted aaa

Inserted bbb

freq(aaa) updated = 2

Inserted ccc

freq(bbb) = 1

freq(aaa) = 2

Traverse:

aaa: 2

bbb: 1

ccc: 1

Deleted aaa

Traverse:

bbb: 1

ccc: 1

freq(aaa) = 0

Inserted aaa

Traverse:

aaa: 1

bbb: 1

ccc: 1

!Các hàm có tiền tố bst do định danh bst đã được sử dụng trong khai báo và định nghĩa, xem dòng 5.

2. Giao diện duyệt cây <tnav.h>

Các hàm duyệt cây được tách riêng với bst.h để giải quyết vấn đề dùng chung mã nguồn với tmap.h (triển khai cây đỏ đen), tránh trùng lặp mã nguồn.

2.1. Khai báo và định nghĩa

Macro TNAV_DECL_IMPL khai báo và định nghĩa các hàm duyệt cây nhị phân, có thể sử dụng được cho cả cây nhị phân tìm kiếm cân bằng và cây nhị phân tìm kiếm không cân bằng.

Các tham số:

tname: Tên cấu trúc cây.

Ví dụ sử dụng:

TNAV_DECL_IMPL(bst) - Khai báo và định nghĩa các hàm duyệt cây nhị phân cho cây bst, sử dụng bst làm tiền tố cho tên hàm. Các hàm sau được định nghĩa:

2.1.1. struct bst_node bst_first_lnr(struct bst tm);

struct bst_node *bst_first_lnr(struct bst *tm);

Hàm tìm nút đầu tiên theo thứ tự duyệt LNR (Trái, Nút, Phải) trong cây. Tương ứng với nút trái nhất - nút với khóa cực tiểu trong cây nhị phân tìm kiếm. Hỗ trợ duyệt cây nhị phân tìm kiếm theo chiều thuận (thứ tự tự nhiên).

Giá trị trả về:

Nếu không có nút nào trong cây thì hàm trả về NULL, nếu ngược lại thì trả về con trỏ tới nút đầu tiên trong cây theo thứ tự duyệt LNR.

2.1.2. struct bst_node bst_next_lnr(struct bst_node n);

struct bst_node *bst_next_lnr(struct bst_node *n);

Hàm tìm nút tiếp theo của n theo thứ tự duyệt LNR. Tương ứng với nút có khóa nhỏ nhất lớn hơn khóa của n.

Giá trị trả về:

Nếu không tồn tại nút tiếp theo thì hàm trả về NULL, nếu ngược lại thì trả về con trỏ tới nút tiếp theo của n theo thứ tự LNR.

2.1.3. struct bst_node bst_first_rnl(struct bst tm);

struct bst_node *bst_first_rnl(struct bst *tm);

Hàm tìm nút đầu tiên theo thứ tự duyệt RNL trong cây. Tương ứng với nút phải nhất - nút với khóa cực đại trong cây nhị phân tìm kiếm. Hỗ trợ duyệt cây nhị phân tìm kiếm theo chiều ngược (khóa từ lớn đến nhỏ).

Giá trị trả về:

Nếu không có nút nào trong cây thì hàm trả về NULL, nếu ngược lại thì trả về con trỏ tới nút đầu tiên trong cây theo thứ tự duyệt RNL.

2.1.4. struct bst_node bst_next_rnl(struct bst_node n);

struct bst_node *bst_next_rnl(struct bst_node *n);

Hàm tìm nút tiếp theo của n theo thứ tự duyệt RNL. Tương ứng với nút có khóa lớn nhất nhỏ hơn khóa của n.

Giá trị trả về:

Nếu không tồn tại nút tiếp theo thì hàm trả về NULL, nếu ngược lại thì trả về con trỏ tới nút tiếp theo của n theo thứ tự RNL.

2.1.5. struct bst_node bst_first_lrn(struct bst tm);

struct bst_node *bst_first_lrn(struct bst *tm);

Hàm tìm nút đầu tiên theo thứ tự duyệt LRN trong cây. Tương ứng với nút trái sâu nhất trong cây nhị phân - nút lá - không có cả nhánh trái và nhánh phải. Hỗ trợ duyệt để xóa cây.

Giá trị trả về:

Nếu không có nút nào trong cây thì hàm trả về NULL, nếu ngược lại thì trả về con trỏ tới nút đầu tiên trong cây theo thứ tự duyệt LRN.

2.1.6. struct bst_node bst_next_lrn(struct bst_node n);

struct bst_node *bst_next_lrn(struct bst_node *n);

Hàm tìm nút tiếp theo của n theo thứ tự duyệt LRN.

Giá trị trả về:

Nếu không tồn tại nút tiếp theo thì hàm trả về NULL, nếu ngược lại thì trả về con trỏ tới nút tiếp theo của n theo thứ tự LRN.

2.1.7. void bst_trav(struct bst, void (f)(struct bst_node, void), void *u);

void bst_trav(struct bst *tm, void (*f)(struct bst_node *, void *u), void *u);

Hàm duyệt và xử lý các nút trong cây theo phong cách lập trình hàm. Duyệt cây được thực hiện bằng gọi hàm đệ quy, theo thứ tự tự nhiên - thứ tự LNR.

Các tham số:

tm: Con trỏ tới cây nhị phân tìm kiếm
f: Con trỏ hàm xử lý nút của cây
u: Con trỏ tới dữ liệu của người dùng, được chuyển tiếp cho f.

Giá trị trả về:

Hàm không trả về giá trị.

2.1.8. void bst_walk();

void bst_walk(struct bst_node *n, void (*f)(struct bst_node *n, void *u),

void *u, enum nav_dir first, enum nav_dir second, enum nav_dir third);

Hàm khái quát tiến trình duyệt nút của cây, cho phép tùy chỉnh tiến trình duyệt. Ví dụ duyệt các nút của cây tm theo thứ tự LNR:

bst_walk(tm->root, f, u, LEFT, NODE, RIGHT);

Giá trị trả về:

Hàm không trả về giá trị.

2.2. Mẫu vòng lặp duyệt cây

Có thể duyệt cây với vòng lặp for, và sử dụng các điều khiển lặp break; continue:

for (struct si_node *cur = bst_first_lnr(t); cur; cur = bst_next_lnr(cur)) {

// Các xử lý

}

Con trỏ cur lần lượt trỏ tới các nút trong cây t theo thứ tự tương đương với duyệt đệ quy theo thứ tự lnr, tuy nhiên có nhiều lựa chọn điều khiển hơn phương án duyệt đệ quy.

Bên cạnh đó cũng có thể duyệt cây theo phong cách hàm với các hàm bst_trav và bst_walk. Ví dụ duyệt và in các cặp khóa - giá trị như sau:

void nprint(struct bst_node *n, void *u) {
printf(" (%s, %d)", n->key, n->value);
}
bst_trav(t, nprint, NULL);
bst_walk(t->root, nprint, NULL, RIGHT, LEFT, NODE);

Dòng 4 - duyệt và in các nút theo thứ tự mặc định LNR, dòng 5 - theo thứ tự RLN.

3. Ánh xạ khóa => giá trị dựa trên cây đỏ đen <tmap.h>

Khác với cây nhị phân tìm kiếm cơ bản - <bst.h>, các nút có thể được kết hợp lệch hẳn về 1 phía (ví dụ thêm 1 dãy nút theo thứ tự tăng dần khóa) khiến độ phức tạp của các thao tác là O(N). Cây đỏ đen là 1 loại cây nhị phân tìm kiếm gần cân bằng (chiều cao 2 nhánh lệch nhau không quá 2) với thuật toán hiệu quả để duy trì tính cân bằng của cây. Các xử lý để duy trì tính cân bằng của cây được thực hiện sau khi thêm và xóa nút. Cây đỏ đen có nhiều ứng dụng thực tiễn vì đảm bảo được độ phức tạp thao tác O(log2N) trong trường hợp tổng quát. Triển khai trong <tmap.h> cho phép người dùng tùy chỉnh cả kiểu dữ liệu của khóa và kiểu dữ liệu của giá trị.

3.1. Các đặc điểm

Người dùng có thể tùy chỉnh kiểu dữ liệu của khóa. Giá trị của khóa được truyền cho hàm so sánh (cmp) thay vì con trỏ tới khóa như hàm so sánh cho qsort.
Nếu có bộ nhớ ngoài được cấp phát cho khóa (khóa là con trỏ) thì có thể thiết lập hàm fk để giải phóng bộ nhớ của khóa khi xóa nút.
Người dùng cũng có thể tùy chỉnh kiểu dữ liệu của giá trị. Trong trường hợp giá trị chứa liên kết đến vùng nhớ được cấp phát bên ngoài thì có thể thiết lập hàm fv để giải phóng bộ nhớ của giá trị khi xóa nút.

3.2. Khai báo và định nghĩa

Macro TMAP_DECL_IMPL khai báo và định nghĩa cấu trúc lưu trữ.

Các tham số:

tname: Tên cấu trúc điều khiển.
keytype: Kiểu dữ liệu của khóa.
valtype: Kiểu dữ liệu của giá trị.

Ví dụ sử dụng:

TMAP_DECL_IMPL(tmap, char *, int) Khai báo và định nghĩa cấu trúc tra cứu với tên là tmap, trong đó khóa có kiểu char * và giá trị có kiểu int. Các cấu trúc điều khiển sau được khai báo và định nghĩa:

struct tmap_node {
char *key;
int value;
enum tmap_node_colors color;
struct tmap_node *left;
struct tmap_node *right;
struct tmap_node *top;
};
struct tmap {
struct tmap_node *root;
int (*cmp)(const char *, const char *);
void (*fk)();
void (*fv)();
int size;
};

Bên cạnh đó các hàm hỗ trợ duyệt cây như trong mục 2 cũng được khai báo và định nghĩa:

struct tmap_node *tmap_first_lrn(struct tmap *tm);

struct tmap_node *tmap_next_lrn(struct tmap_node *n);

struct tmap_node *tmap_first_lnr(struct tmap *tm);

struct tmap_node *tmap_next_lnr(struct tmap_node *n);

struct tmap_node *tmap_next_rnl(struct tmap_node *n);

struct tmap_node *tmap_first_rnl(struct tmap *tm);

void tmap_trav(struct tmap *tm,

void (*f)(struct tmap_node *n, void *u),

void *u);

void tmap_walk(struct tmap_node *n,

void (*f)(struct tmap_node *n, void *u),

void *u,

enum nav_dir first,

enum nav_dir second,

enum nav_dir third);

Các hàm xử lý lưu trữ được khai báo tương tự như trong <bst.h>, tuy nhiên trong triển khai có thêm thuật toán phức tạp để duy trì tính cân bằng của cây. các hàm giao diện quản lý sau được khai báo và định nghĩa:

3.2.1. struct tmap tmap(int (cmp)(const char , const char ));

struct tmap *tmap(int (*cmp)(const char *, const char *));

Hàm tạo cây. Đối số cmp là con trỏ hàm so sánh khóa của cây, là thành phần bắt buộc trong hoạt động của cây. Hàm so sánh được khai báo với nguyên mẫu để đảm bảo an toàn trong truyền tham số. Các tham số const char * được khai báo theo kiểu của khóa, trong trường hợp này khóa có kiểu char *, được truyền theo giá trị, vì vậy hàm so sánh nhận các đối số kiểu const char *.

Giá trị trả về:

Hàm trả về con trỏ tới đối tượng tmap mới được tạo.

3.2.2. struct tmap tmap_fk(struct tmap tm, void (*fk)());

struct tmap *tmap_fk(struct tmap *tm, void (*fk)());

Hàm thiết lập con trỏ fk. Con trỏ fk được sử dụng để xóa bộ nhớ cấp phát động của khóa (nếu có). Con trỏ fk được thiết kế khái quát, không gắn với nguyên mẫu, để tương thích đồng thời với tham số void * và các tham số cụ thể - như hàm hủy của các cấu trúc lưu trữ.

Giá trị trả về:

Hàm trả về con trỏ tm.

3.2.3. struct tmap tmap_fv(struct tmap tm, void (*fv)());

struct tmap *tmap_fv(struct tmap *tm, void (*fv)());

Hàm thiết lập con trỏ fv. Con trỏ fv được sử dụng để xóa bộ nhớ cấp phát động của khóa (nếu có). Con trỏ fv cũng được thiết kế khái quát, không gắn với nguyên mẫu, để tương thích đồng thời với tham số void * và các tham số cụ thể - như hàm hủy của các cấu trúc lưu trữ.

Giá trị trả về:

Hàm trả về con trỏ tm.

3.2.4. struct tmap tmap_ak(struct tmap, void (ak)(key_t, const key_t));

struct tmap *tmap_ak(struct tmap *tm, void (*ak)(key_t *des, const key_t src));

Hàm thiết lập con trỏ ak. Nếu được thiết lập thì hàm được trỏ tới bởi ak sẽ được gọi để gán giá trị của tham số khóa trong hàm put cho trường key của nút. Nếu không được thiết lập thì toán tử gán được sử dụng.

Giá trị trả về:

Hàm trả về con trỏ tm.

3.2.5. struct tmap *tmap_av());

struct tmap *tmap_av(struct tmap *tm,

void (*av)(value_t *des, const value_t src));

Hàm thiết lập con trỏ av. Nếu được thiết lập thì hàm sẽ được kích hoạt khi gán giá trị cho trường value của nút, nếu không được thiết lập thì toán tử gán được sử dụng.

Giá trị trả về:

Hàm trả về con trỏ tm.

3.2.6. struct tmap_node tmap_put(struct tmap tm, char *key, int value);

struct tmap_node *tmap_put(struct tmap *tm, char *key, int value);

Đưa cặp khóa-giá trị vào lưu trữ trong tm. Nếu khóa chưa tồn tại thì tạo nút mới và sao chép các tham số key và value vào trong nút, nếu ngược lại thì bỏ qua - cây không thay đổi.

Giá trị trả về:

Nếu khóa chưa tồn tại thì hàm trả về NULL, nếu ngược lại thì trả về nút tương ứng với khóa trong lưu trữ.

3.2.7. struct tmap_node tmap_get(struct tmap tm, char *key);

struct tmap_node *tmap_get(struct tmap *tm, char *key);

Tìm nút tương ứng với khóa trong cây.

Giá trị trả về:

Nếu không tìm thấy khóa thì hàm trả về NULL, nếu ngược lại thì trả về con trỏ tới nút tương ứng với khóa.

3.2.8. int tmap_rem(struct tmap tm, char key);

int tmap_rem(struct tmap *tm, char *key);

Xóa nút tương ứng với khóa trong cây. Nếu không tìm thấy khóa thì bỏ qua - cây không thay đổi, nếu ngược lại thì xóa và giải phóng bộ nhớ của nút tương ứng với khóa, gọi các hàm fk và fv để giải phóng bộ nhớ ngoại được gắn với khóa và giá trị nếu được thiết lập.

Giá trị trả về:

Hàm trả về 0 nếu không tìm thấy khóa trong cây, nếu ngược lại - tìm thấy khóa và đã xóa nút thì trả về 1.

3.2.9. void tmap_free(struct tmap *tm);

void tmap_free(struct tmap *tm);

Hàm giải phóng bộ nhớ cho cấu trúc lưu trữ tm.

Giá trị trả về:

Hàm không trả về giá trị.

3.3. Ví dụ minh họa

Mã nguồn đếm từ, về cơ bản tương tự như mã nguồn sử dụng bst, tuy nhiên có sự khác biệt về hiệu năng xử lý.

#include "tmap.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
TMAP_DECL_IMPL(rbt, char *, int)
void str_assign(char **des, const char *src) {
*des = strdup(src);
}
int main() {
struct rbt *t = rbt(strcmp);
rbt_ak(t, str_assign);
rbt_fk(t, free);
char cmd[32], word[32];
while (scanf("%s", cmd) == 1) {
if (strcmp(cmd, "print") == 0) {
printf("Traverse: \n");
struct rbt_node *n = rbt_first_lnr(t);
for (; n; n = rbt_next_lnr(n)) {
printf("%s: %d\n", n->key, n->value);
}
continue;
}
scanf("%s", word);
if (strcmp(cmd, "insert") == 0) {
struct rbt_node *n = rbt_put(t, word, 1);
if (n) {
++n->value;
printf("freq(%s) updated = %d\n",
word, n->value);
} else {
printf("Inserted %s\n", word);
}
} else if (strcmp(cmd, "freq") == 0) {
struct rbt_node *n = rbt_get(t, word);
printf("freq(%s) = %d\n",
word, n? n->value: 0);
} else if (strcmp(cmd, "rem") == 0) {
if (rbt_rem(t, word)) {
printf("Deleted %s\n", word);
}
}
}
rbt_free(t);
}

Việc cho phép tùy chỉnh kiểu dữ liệu của khóa làm tăng tính khái quát so với triển khai <bst.h>, tuy nhiên tùy chỉnh này đồng thời cũng làm tăng tính phức tạp của mã nguồn.

Dòng 7 - TMAP_DECL_IMPL(rbt, char *, int): Định nghĩa cấu trúc lưu trữ dựa trên cây đỏ đen với tên là rbt, khóa có kiểu char * và giá trị có kiểu int.

Dòng 14 - Thiết lập hàm gán giá trị cho khóa, cấp phát bộ nhớ động và sao chép chuỗi đối số.

Dòng 15 - Thiết lập hàm giải phóng bộ nhớ động của khóa khi xóa nút.

4. Ánh xạ khóa => giá trị dựa trên bảng băm <hmap.h>

<hmap.h> triển khai bảng băm dựa trên mảng, sử dụng hàm băm để chuyển đổi khóa thành số nguyên, mã số nguyên tiếp tục được chuyển đổi thành chỉ số mảng, thông qua đó có thể truy cập nhanh đến các phần tử trong lưu trữ bằng khóa. Tuy nhiên từ các khóa khác nhau có thể thu được cùng 1 chỉ số mảng, hiện tượng này được biết đến là xung đột chỉ số, việc phân giải xung đột có thể làm giảm hiệu quả của các thao tác. Tăng kích thước mảng có thể giúp giảm xác suất xung đột chỉ số, làm tăng hiệu quả xử lý, đó là sự bù trừ giữa dung lượng bộ nhớ và hiệu quả xử lý.

4.1. Các đặc điểm

Dung lượng mảng cơ sở của bảng băm là lũy thừa của 2. Đặc điểm này cho phép di chuyển chỉ số với gia tốc - bước di chuyển tăng dần.
Chỉ số mảng ban đầu là phần dư của mã băm khi chia cho số nguyên lớn nhất trong phạm vi dung lượng. Nếu vị trí gắn với chỉ số trong mảng đã được sử dụng thì di chuyển đến vị trí tiếp theo - cho tới khi gặp vị trí trống.
Có thể tùy chỉnh kiểu dữ liệu của cả khóa và giá trị.
Có thể tùy chỉnh hàm băm khóa, hàm so sánh khóa (để phát hiện trùng lặp khóa - phần tử đã tồn tại).
Có thể tùy chỉnh các hàm giải phóng bộ nhớ động gắn với khóa và giá trị.

4.2. Khai báo và định nghĩa

Macro HMAP_DECL_IMPL khai báo và định nghĩa bảng băm.

Các tham số:

hname: Tên cấu trúc lưu trữ.
key_t: Kiểu dữ liệu của khóa.
value_t: Kiểu dữ liệu của giá trị.

Ví dụ sử dụng:

HMAP_DECL_IMPL(hmap, char *, int) Khai báo và định nghĩa cấu trúc lưu trữ hmap với khóa kiểu char * và giá trị kiểu int. Các cấu trúc được khai báo và định nghĩa:

struct hmap_elem {
char *key;
int value;
unsigned hash;
enum hmap_elem_state state;
};
struct hmap {
struct hmap_elem *elems;
struct hmap_elem *end;
int mod;
unsigned mask;
int size;
int cap;
int used;
unsigned (*ha)(const char *);
int (*cmp)(const char *, const char *);
void (*fk)();
void (*fv)();
void (*ak)(key_t *des, const key_t src);
void (*av)(value_t *des, const value_t src);
};

Trong đó struct hmap_elem là kiểu phần tử trong mảng cơ sở của bảng băm, trường hash là mã băm của khóa, trường state để đánh dấu trạng thái sử dụng phần tử mảng. Còn struct hmap là cấu trúc điều khiển của bảng băm.

Các hàm giao diện được khai báo và định nghĩa:

4.2.1. struct hmap *hmap();

struct hmap *hmap(unsigned (*ha)(const char *),

int (*cmp)(const char *, const char *));

Hàm tạo bảng băm, khởi tạo các hàm bắt buộc phải có đối với bảng băm: Hàm băm giá trị khóa ha, và hàm so sánh khóa cmp (để phát hiện khóa trùng lặp khóa). Các giá trị khóa được truyền cho ha và cmp, trong trường hợp này khóa có kiểu char *, vì vậy các tham số của hàm có kiểu const char *.

Giá trị trả về:

Hàm trả về con trỏ tới đối tượng bảng băm mới được tạo.

4.2.2. struct hmap hmap_fk(struct hmap hm, void (*fk)());

struct hmap *hmap_fk(struct hmap *hm, void (*fk)());

Thiết lập con trỏ hàm fk - giải phóng bộ nhớ động gắn với khóa nếu cần.

Giá trị trả về:

Con trỏ hm.

4.2.3. struct hmap hmap_fv(struct hmap hm, void (*fv)());

struct hmap *hmap_fv(struct hmap *hm, void (*fv)());

Thiết lập con trỏ hàm fv - giải phóng bộ nhớ động gắn với giá trị nếu cần.

Giá trị trả về:

Con trỏ hm.

4.2.4. struct hmap *hmap_ak();

struct hmap *hmap_ak(struct hmap *hm,

void (*ak)(key_t *des, const key_t src));

Thiết lập con trỏ hàm ak - sử dụng để gán giá trị cho khóa. Nếu ak không được thiết lập thì giá trị khóa được thiết lập bằng phép gán (=), nếu ak được thiết lập thì hàm được trỏ tới bởi ak được gọi để thiết lập khóa trong bảng băm.

Giá trị trả về:

Hàm trả về con trỏ hm.

4.2.5. struct hmap *hmap_av();

struct hmap *hmap_av(struct hmap *hm,

void (*av)(value_t *des, const value_t src));

Thiết lập con trỏ hàm av - sử dụng để gán giá trị cho trường value. Nếu av không được thiết lập thì giá trị của trường value được thiết lập bằng phép gán (=), nếu av được thiết lập thì hàm được trỏ tới bởi av được gọi để thiết lập giá trị cho value trong bảng băm.

Giá trị trả về:

Hàm trả về con trỏ hm.

4.2.6. struct hmap hmap_realloc(struct hmap hm, int ncap);

struct hmap *hmap_realloc(struct hmap *hm, int ncap);

Hàm cấp phát lại bộ nhớ cho bảng băm. Nếu biết trước giới hạn số lượng phần tử thì có thể yêu cầu cấp phát dung lượng đủ dùng, để tránh cấp phát lại nhiều lần trong quá trình thêm dần từng phần tử vào bảng băm khiến kích thước tăng dần. Qua đó nâng cao được hiệu năng xử lý.

Nếu dung lượng được yêu cầu < kích thước hiện tại, hoặc không thay đổi thì bảng băm không thay đổi.

Giá trị trả về:

Hàm trả về con trỏ hm.

4.2.7. struct hmap_elem hmap_put(struct hmap hm, char *k, int v);

struct hmap_elem *hmap_put(struct hmap *hm, char *k, int v);

Hàm đưa cặp khóa-giá trị vào lưu trữ. Nếu khóa chưa tồn tại thì đưa dữ liệu vào 1 phần tử mảng cơ sở, nếu ngược lại - khóa đã tồn tại thì trả về con trỏ tới phần tử hiện đang có trong mảng.

Giá trị trả về:

Hàm trả về NULL nếu khóa chưa tồn tại, trong trường hợp ngược lại hàm trả về con trỏ tới phần tử mảng tương ứng với khóa.

4.2.8. int hmap_get(struct hmap hm, const char *k);

struct hmap_elem *hmap_get(struct hmap *hm, const char *k);

Tim phần tử bảng băm tương ứng với khóa.

Giá trị trả về:

Hàm trả về NULL nếu không tìm thấy phần tử tương ứng với khóa, trong trường hợp ngược lại hàm trả về phần tử mảng băm tương ứng với khóa.

4.2.9. int hmap_rem(struct hmap hm, const char k);

int hmap_rem(struct hmap *hm, const char *k);

Xóa phần tử bảng băm tương ứng với khóa, đồng thời gọi các hàm fk và fv để giải phóng bộ nhớ ngoài được gắn với khóa và giá trị nếu cần.

Giá trị trả về:

Hàm trả về 0 nếu khóa không tồn tại, trong trường hợp ngược lại - đã tìm thấy và xóa phần tử - hàm trả về 1.

4.2.10. struct hmap_elem hmap_first(struct hmap hm);

struct hmap_elem *hmap_first(struct hmap *hm);

Hàm tìm phần tử đầu tiên trong bảng băm - phần tử mảng có chỉ số nhỏ nhất được sử dụng. Hỗ trợ duyệt tuần tự các phần tử bảng băm.

Giá trị trả về:

Hàm trả về NULL nếu chưa có phần tử nào của mảng được sử dụng, trong trường hợp ngược lại hàm trả về con trỏ tới phần tử đầu tiên của bảng băm.

4.2.11. struct hmap_elem hmap_next(struct hmap, struct hmap_elem*);

struct hmap_elem *hmap_next(struct hmap *hm, struct hmap_elem *n);

Hàm tìm phần tử tiếp theo của n trong bảng băm hm - phần tử mảng có chỉ số nhỏ nhất lớn hơn chỉ số của n, được sử dụng, trong giới hạn mảng cơ sở.

Giá trị trả về:

Hàm trả về NULL nếu không tồn tại phần tử tiếp theo của n, trong trường hợp ngược lại hàm trả về con trỏ tới phần tử tiếp theo của n trong bảng băm hm.

4.2.12. void hmap_trav();

void hmap_trav(struct hmap *hm,

void (*f)(struct hmap_elem *n, void *u), void *u);

Hàm hỗ trợ duyệt các phần tử bảng băm theo phong cách hàm. Hàm được trỏ tới bởi con trỏ f được gọi lần lượt với từng phần tử của bảng băm cùng với con trỏ u của người dùng.

Giá trị trả về:

Hàm không trả về giá trị.

4.2.13. void hmap_free(struct hmap *hm);

void hmap_free(struct hmap *hm);

Hàm giải phóng bộ nhớ đã được cấp phát cho bảng băm hm. Các con trỏ hàm fk và fv được sử dụng để giải phóng bộ nhớ ngoài gắn với khóa và giá trị nếu được thiết lập.

Giá trị trả về:

Hàm không trả về giá trị.

4.3. Ví dụ minh họa

Mã nguồn giải quyết bài toán đếm tần suất từ về hình thức có nhiều điểm tương đồng với lời giải cùng bài toán bằng ánh xạ dựa trên cây đỏ đen <tmap.h>. Tuy nhiên có sự khác biệt bản chất về thuật toán sử dụng, hiệu năng và dung lượng bộ nhớ sử dụng.

#include "hmap.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
HMAP_DECL_IMPL(hmap, char *, int)
void str_assign(char **des, const char *src) {
*des = strdup(src);
}
int main() {
struct hmap *hm = hmap(hash_s, strcmp);
hmap_ak(hm, str_assign);
hmap_fk(hm, free);
char cmd[32], word[32];
while (scanf("%s", cmd) == 1) {
if (strcmp(cmd, "print") == 0) {
printf("Traverse: \n");
struct hmap_elem *e = hmap_first(hm);
for (; e; e = hmap_next(hm, e)) {
printf("%s: %d\n", e->key, e->value);
}
continue;
}
scanf("%s", word);
if (strcmp(cmd, "insert") == 0) {
struct hmap_elem *e = hmap_put(hm, word, 1);
if (e) {
++e->value;
printf("freq(%s) updated = %d\n",
word, e->value);
} else {
printf("Inserted %s\n", word);
}
} else if (strcmp(cmd, "freq") == 0) {
struct hmap_elem *e = hmap_get(hm, word);
printf("freq(%s) = %d\n",
word, e? e->value: 0);
} else if (strcmp(cmd, "rem") == 0) {
if (hmap_rem(hm, word)) {
printf("Deleted %s\n", word);
}
}
}
hmap_free(hm);
}

Dòng 15 thiết lập hàm str_assign để gán gía trị cho khóa trong bảng băm, dòng 16 thiết lập hàm giải phóng bộ nhớ cho khóa. Với cấu hình đó bảng băm sẽ tự quản lý bộ nhớ cấp phát cho khóa - Cấp phát và sao chép giá trị khi đưa vào, giải phóng bộ nhớ khi xóa.

Phần II. Cấu trúc lưu trữ tuần tự

5. Mảng cấp phát động - <arr.h>

Mảng là cấu trúc lưu trữ tự nhiên duy nhất là 1 phần của ngôn ngữ lập trình C. Mảng là 1 cấu trúc lưu trữ bậc thấp, hiệu quả nhất trong xử lý tuần tự, nhưng cũng dễ mắc lỗi, ví dụ như sử dụng chỉ số mảng nằm ngoài khoảng cấp phát. Mảng theo định dạng T a[n]; được cấp phát trong ngăn xếp (Stack), phụ thuộc vào tùy chỉnh hệ điều hành, thông thường không quá lớn, ví dụ 8 MiB trên Ubuntu (có thể tăng thêm). Các mảng rất lớn, có thể chiếm hết vùng nhớ còn trống của RAM được cấp phát trong vùng nhớ động (Heap), được quản lý với các hàm malloc, realloc, calloc và free.

Triển khai <arr.h> là 1 đóng gói đơn giản của các thao tác quản lý bộ nhớ động cơ bản thành các thao tác xử lý mảng cụ thể hơn, nhằm hạn chế lỗi và đơn giản hóa việc sử dụng mảng động.

5.1. Các đặc điểm

Mảng được cấp phát trong vùng nhớ động và có thể được cấp phát lại.
Cấp phát 1 vùng nhớ riêng phía trước vùng nhớ mảng để lưu kích thước.
Các thao tác được đóng gói bằng Macro thay vì hàm, việc sử dụng Macro giúp tránh được phụ thuộc vào kiểu dữ liệu.

5.2. Các khai báo và định nghĩa

Mảng động được sử dụng thông qua con trỏ tới phần tử đầu tiên của nó, không định nghĩa các cấu trúc điều khiển. Các Macro và hàm giao diện sau được khai báo và định nghĩa:

5.2.1. arr(elem_t, n)

arr(elem_t, n)

Cấp phát vùng nhớ động cho mảng n phần tử kiểu elem_t. Phía gọi tự đảm bảo tính hợp lệ của n.

Ví dụ sử dụng: int *a = arr(int, 10);

Giá trị biểu thức:

Con trỏ tới phần tử đầu tiên trong mảng.

5.2.2. arr_cap(a)

arr_cap(a)

Trả về dung lượng (số lượng phần tử) đã cấp phát cho a.

Ví dụ sử dụng:

Đối với a trong: int *a = arr(int, 100);

arr_cap(a) có giá trị = 100.

Giá trị biểu thức:

Dung lượng đã cấp phát cho mảng.

5.2.3. arr_reserve(a, cap)

arr_reserve(a, cap)

Cấp phát lại bộ nhớ cho a.

Giá trị biểu thức:

Con trỏ tới phần tử đầu tiên trong mảng a.

5.2.4. arr_for(a, i)

arr_for(a, cap)

Duyệt mảng a với chỉ số i, đây là phiên bản giản lược của vòng lặp for:

for (int i = 0; i < arr_cap(a); ++i)

Giá trị biểu thức:

arr_for là phiên bản viết tắt của vòng lặp duyệt tuần tự phần tử mảng bằng chỉ số. Là phần đầu của câu lệnh lặp, không phải biểu thức có giá trị.

5.2.5. arr_rfor(a, i)

arr_rfor(a, cap)

Duyệt mảng a với chỉ số i theo thứ tự ngược, đây là phiên bản giản lược của vòng lặp for:

for (int i = arr_cap(a) - 1; i >= 0; --i)

Giá trị biểu thức:

arr_rfor là phiên bản viết tắt của vòng lặp duyệt tuần tự phần tử mảng bằng chỉ số theo thứ ngược. Là phần đầu của câu lệnh lặp, không phải biểu thức có giá trị.

5.2.6. void arr_free(void *a)

void arr_free(void *a)

Hàm giải phóng bộ nhớ đã cấp phát cho mảng a.

Giá trị trả về:

Hàm không trả về giá trị.

5.3. Ví dụ minh họa

Minh họa 1 chương trình nhập số nguyên n và sau đó nhập n số nguyên, rồi cuối cùng in ra dãy số đã nhập theo thứ tự ngược lại với mảng động.

#include "arr.h"
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int *a = arr(int, n);
arr_for(a, i) {
scanf("%d", &a[i]);
}
arr_rfor(a, i) {
printf(" %d", a[i]);
}
printf("\n");
arr_free(a);
}

6. Triển khai vec-tơ cho C - <vect.h>

Triển khai vec-tơ <vect.h> đóng gói mảng an toàn hơn so với mảng động <arr.h>. Cấp phát lại bộ nhớ là 1 thao tác tương đối phức tạp, và để tránh cấp phát lại bộ nhớ quá thường xuyên, trong triển khai vec-tơ sử dụng 2 tham số để hỗ trợ quản lý bộ nhớ là size - kích thước - số lượng phần tử đã sử dụng, và cap - dung lượng - số lượng phần tử đã cấp phát. Vec-tơ là 1 triển khai hiệu quả, và có thể là lựa chọn mặc định nếu không có lý do đặc biệt nào khác, để xử lý dãy phần tử trong điều kiện không biết trước số lượng phần tử. Các lựa chọn thay thế khác có thể kể đến như sử dụng danh sách móc nối đơn để triển khai hàng đợi vào trước - ra trước (FIFO).

6.1. Các đặc điểm

Thay đổi số lượng phần tử có thể kéo theo cấp phát lại bộ nhớ cho vec-tơ.
Thêm phần tử vào cuối dãy đơn giản hơn khi thêm vào các vị trí khác. Khi thêm vào các vị trí khác như giữa dãy, hoặc đầu dãy sẽ tiêu tốn chi phí di chuyển các phần tử trong mảng để tạo ô trống cho phần tử mới.

6.2. Các khai báo và định nghĩa

Macro VECT_DECL_IMPL khai báo và định nghĩa cấu trúc vec-tơ.

Ví dụ sử dụng: VECT_DECL_IMPL(ivec, int) - khai báo cấu trúc vec-tơ ivect với các phần tử có kiểu int. Các thành phần sau được khai báo và định nghĩa, cấu trúc điều khiển:

struct ivec {
int size;
int cap;
int *elems;
};

size và cap lần lượt là kích thước và dung lượng vec-tơ, elems là con trỏ tới vùng nhớ mảng. Các hàm giao diện sau được khai báo và định nghĩa:

6.2.1. struct ivec *ivec(int n);

struct ivec *ivec(int n);

Hàm tạo cấu trúc vec-tơ n là số lượng phần tử ban đầu, dung lượng được khởi tạo >= kích thước, là thuộc tính trong suốt đối với các giao diện người dùng.

Giá trị trả về:

Hàm trả về con trỏ tới đối tượng vec-tơ mới được tạo.

6.2.2. struct ivec ivec_reserve(struct ivec v, int newcap);

struct ivec *ivec_reserve(struct ivec *v, int newcap);

Cấp phát bộ nhớ cho các phần tử của vec-tơ, newcap là dung lượng mới phải >= số lượng phần tử hiện có. Nếu newcap > dung lượng hiện tại thì phần mở rộng được khởi tạo với tất cả các bit = 0.

Giá trị trả về:

Hàm trả về con trỏ v, giá trị v->elems có thể đã thay đổi.

6.2.3. struct ivec ivec_resize(struct ivec v, int newsize);

struct ivec *ivec_resize(struct ivec *v, int newsize);

Thay đổi kích thước vec-tơ, tăng dung lượng nếu kích thước được yêu cầu lớn hơn dung lượng hiện tại.

Giá trị trả về:

Hàm trả về con trỏ v.

6.2.4. struct ivec ivec_append(struct ivec v, int elem);

struct ivec *ivec_append(struct ivec *v, int elem);

Thêm phần tử vào cuối vec-tơ.

Giá trị trả về:

Hàm trả về con trỏ v.

6.2.5. struct ivec ivec_ins(struct ivec v, int idx, int elem);

struct ivec *ivec_ins(struct ivec *v, int idx, int elem);

Thêm phần tử vào vị trí với chỉ số = idx trong vec-tơ v. Các phần tử từ vị trí idx hiện tại trong v được dịch chuyển sang phải.

Giá trị trả về:

Hàm trả về con trỏ v.

6.2.6. int ivec_del(struct ivec *v, int idx);

int ivec_del(struct ivec *v, int idx);

Xóa phần tử ở vị trí idx khỏi vec-tơ v. Nếu idx nằm ngoài khoảng giá trị hợp lệ đối với chỉ số thì bỏ qua, nếu ngược lại thì xóa phần tử khỏi vec-tơ v.

Giá trị trả về:

Hàm trả về 0 nếu không có phần tử nào bị xóa (khi chỉ số idx không hợp lệ), hoặc trả về 1 nếu đã có phần tử bị xóa.

6.2.7. int ivec_at(struct ivec v, int idx);

int *ivec_at(struct ivec *v, int idx);

Con trỏ tới phần tử với chỉ số = idx trong vec-tơ v.

Giá trị trả về:

Hàm trả về NULL nếu chỉ số mảng không hợp lệ, trong trường hợp ngược lại hàm trả về con trỏ tới phần tử với chỉ số = idx trong vec-tơ v.

6.2.8. void ivec_free(struct ivec *v);

void ivec_free(struct ivec *v);

Hàm giải phóng bộ nhớ được cấp phát cho vec-tơ v.

Giá trị trả về:

Hàm không trả về giá trị.

6.3. Ví dụ minh họa

Viết chương trình nhập 1 dãy số nguyên không biết trước số lượng phần tử từ luồng nhập tiêu chuẩn, sau đó in ra màn hình số lượng phần tử đã nhập, dung lượng đã cấp phát và dãy số đã nhập theo thứ tự ngược lại.

#include "vec.h"
#include <stdio.h>
VEC_DECL_IMPL(ivec, int)
int main() {
int elem;
struct ivec *v = ivec(0);
while (scanf("%d", &elem) == 1) {
ivec_append(v, elem);
}
printf("size = %d, cap = %d\n",
v->size, v->cap);
vrfor(v, i) {
printf(" %d", v->elems[i]);
}
printf("\n");
ivec_free(v);
}

Dòng 8 tạo vec-tơ với số lượng phần tử ban đầu là 0, để thêm dần các phần tử.

Dòng 10 thêm phần tử vào cuối dãy theo tiến trình đọc dữ liệu, bộ nhớ cho vec-tơ được cấp phát lại khi cần thêm dung lượng.

Ví dụ dữ liệu đầu vào và đầu ra khi thực hiện chương trình:

Đầu vào:

3 1 2 5 6 12 13

Đầu ra:

size = 7, cap = 8

13 12 6 5 2 1 3

Đầu vào:

3 2 1 5 6 2 10 11 21 15 22 8 9

Đầu ra:

size = 13, cap = 16

9 8 22 15 21 11 10 2 6 5 1 2 3

7. Danh sách móc nối đơn - <slist.h>

Danh sách móc nối đơn là cấu trúc dữ liệu liên kết tương đối đơn giản, là cấu trúc cơ sở để triển khai ngăn xếp và hàng đợi.

7.1. Các đặc điểm

Các phần tử được cấp phát bộ nhớ riêng trong RAM, sau đó được hợp lại thành danh sách liên tục bằng các liên kết.
Lưu các con trỏ tới đầu và cuối danh sách.
Mỗi nút chỉ chứa 1 con trỏ tới nút tiếp theo.
Có thể xử lý hiệu quả thao tác thêm và xóa phần tử ở đầu và cuối danh sách, thêm và xóa phần tử ở giữa danh sách là thao tác phức tạp hơn do phải di chuyển trên danh sách, thường từ đầu danh sách.

7.2. Các khai báo và định nghĩa

Macro SLIST_DECL khai báo và định nghĩa danh sách móc nối đơn. Các tham số:

sname: Tên cấu trúc điều khiển đồng thời là tiền tố cho các giao diện.
elem_t: Kiểu dữ liệu phần tử.

Ví dụ sử dụng:

SLIST_DECL_IMPL(sll, int) khai báo và định nghĩa cấu trúc danh sách móc nối đơn với tên là sll, các phần tử dữ liệu có kiểu int.

Các cấu trúc điều khiển sau được khai báo và định nghĩa:

struct sll_node {
int value;
struct sll_node *next;
};
struct sll {
struct sll_node *first;
struct sll_node *last;
int size;
};

sll_node là cấu trúc nút của danh sách móc nối, sll là cấu trúc điều khiển của danh sách móc nối. Trong đó value là phần tử được lưu, next là con trỏ tới nút tiếp theo, next == NULL nếu không tồn tại nút tiếp theo đối với nút ở cuối danh sách, first và last lần lượt là con trỏ tới nút ở đầu và cuối danh sách, firt == last == NULL nếu danh sách rỗng, size là số lượng phần tử trong danh sách, size == 0 nếu danh sách rỗng.

Đồng thời các hàm giao diện sau cũng được khai báo và định nghĩa:

7.2.1. struct sll *sll();

struct sll *sll();

Hàm tạo danh sách móc nối đơn.

Giá trị trả về:

Hàm trả về con trỏ tới cấu trúc điều khiển mới được tao.

7.2.2. struct sll sll_append(struct sll list, int value);

struct sll *sll_append(struct sll *list, int value);

Thêm phần tử vào cuối danh sách.

Giá trị trả về:

Hàm trả về con trỏ list.

7.2.3. struct sll sll_prepend(struct sll list, int value);

struct sll *sll_prepend(struct sll *list, int value);

Thêm phần tử vào đầu danh sách.

Giá trị trả về:

Hàm trả về con trỏ list.

7.2.4. int sll_dfirst(struct sll *list);

int sll_dfirst(struct sll *list);

Nếu danh sách rỗng hoặc con trỏ NULL thì bỏ qua, nếu ngược lại thì xóa nút ở đầu danh sách.

Giá trị trả về:

Hàm trả về số lượng nút đã xóa.

7.2.5. struct sll sll_ins(struct sll list, int idx, int value);

struct sll *sll_ins(struct sll *list, int idx, int value);

Chèn phần tử vào vị trí có chỉ số idx trong danh sách. Nếu chỉ số idx không hợp lệ thì bỏ qua.

Giá trị trả về:

Hàm trả về con trỏ list.

7.2.6. struct sll sll_insa(struct sll list, struct sll_node *pos, int value);

struct sll *sll_insa(struct sll *list, struct sll_node *pos, int value);

Chèn phần tử vào sau vị trí được trỏ tới bởi pos trong list. Nếu list == NULL hoặc list không rỗng nhưng pos == NULL thì bỏ qua.

Giá trị trả về:

Hàm trả về con trỏ list.

7.2.7. struct sll_node sll_at(struct sll list, int idx);

struct sll_node *sll_at(struct sll *list, int idx);

Truy cập nút ở vị trí có chỉ số idx trong list.

Giá trị trả về:

Hàm trả về NULL nếu chỉ số không hợp lệ, trong trường hợp ngược lại hàm trả về con trỏ tới nút.

7.2.8. int sll_del(struct sll *list, int idx);

int sll_del(struct sll *list, int idx);

Xóa nút ở vị trí có chỉ số idx trong list. Nếu chỉ số idx không hợp lệ thì bỏ qua.

Giá trị trả về:

Hàm trả về số lượng nút đã xóa.

7.2.9. struct sll sll_push(struct sll list, int elem);

struct sll *sll_push(struct sll *list, int elem);

Hàm giao diện ngăn xếp. Đưa phần tử vào ngăn xếp.

Giá trị trả về:

Hàm trả về con trỏ list.

7.2.10. int sll_top(struct sll list);

int *sll_top(struct sll *list);

Hàm giao diện ngăn xếp. Truy cập phần tử ở đỉnh ngăn xếp/

Giá trị trả về:

Hàm trả về con trỏ ở đỉnh ngăn xếp.

7.2.11. int sll_pop(struct sll *list);

int sll_pop(struct sll *list);

Hàm giao diện ngăn xếp. Xóa phần tử khỏi ngăn xếp. Nếu ngăn xếp rỗng thì bỏ qua.

Giá trị trả về:

Hàm trả về số lượng phần tử đã xóa.

7.2.12. struct sll sll_enq(struct sll list, int elem);

struct sll *sll_enq(struct sll *list, int elem);

Hàm giao diện hàng đợi. Đưa phần tử vào hàng đợi.

Giá trị trả về:

Hàm trả về con trỏ list.

7.2.13. int sll_peek(struct sll list);

int *sll_peek(struct sll *list);

Hàm giao diện hàng đợi. Truy cập phần tử ở đầu hàng đợi.

Giá trị trả về:

Hàm trả về con trỏ tới phần tử ở đầu hàng đợi.

7.2.14. int sll_deq(struct sll *list);

int sll_deq(struct sll *list);

Hàm giao diện hàng đợi. Xóa phần tử khỏi hàng đợi. Nếu hàng đợi rỗng thì bỏ qua.

Giá trị trả về:

Hàm trả về số lượng phần tử đã xóa.

7.2.15. int sll_empty(struct sll *list);

int sll_empty(struct sll *list);

Kiểm tra nếu hàng đợi rỗng.

Giá trị trả về:

Hàm trả về 1 nếu hàng đợi rỗng, trong trường hợp ngược lại hàm trả về 0.

7.2.16. void sll_free(struct sll *list);

void sll_free(struct sll *list);

Xóa các phần tử khỏi danh sách.

Giá trị trả về:

Hàm không trả về giá trị.

7.3. Ví dụ minh họa

Viết chương trình giả lập hàng đợi sinh viên nhận đồ ký gửi. Chương trình hỗ trợ các lệnh sau:

enq Họ-tên viết tắt của sinh viên (không chứa khoảng trắng, ít hơn 32 ký tự)- Ghi nhận sinh viên đi vào hàng đợi.
fetch - Trả đồ cho sinh viên - chương trình in ra tên sinh viên và xóa khỏi hàng đợi.
len - Xuất ra màn hình độ dài hàng đợi.

#include "slist.h"
#include <stdio.h>
#include <string.h>
struct stud {
char name[32];
};
SLIST_DECL_IMPL(sll, struct stud)
#define sequal(s1, s2) (strcmp(s1, s2) == 0)
int main() {
struct sll *q = sll();
char cmd[10];
struct stud sv;
while (scanf("%s", cmd) == 1) {
if (sequal(cmd, "enq")) {
scanf("%s", sv.name);
sll_enq(q, sv);
} else if (sequal(cmd, "fetch")) {
printf("%s\n", sll_peek(q)->name);
sll_deq(q);
} else if (sequal(cmd, "len")) {
printf("%d\n", q->size);
}
}
sll_free(q);
}

Minh họa hoạt động, dữ liệu đầu vào:

enq AnNV

enq BiTT

enq HongNT

fetch

enq HaiNT

fetch

len

Đầu ra tương ứng:

AnNV

BiTT

8. Danh sách móc nối kép - <dll.h>

<dll.h> triển khai danh sách móc nối kép, mỗi nút chứa 2 con trỏ tới nút tiếp theo và nút trước của nó.

8.1. Các đặc điểm

Các nút được cấp phát độc lập trong RAM, có thể nằm ở các vùng nhớ khác nhau, được kết hợp lại thành 1 danh sách tuần tự.
Lưu con trỏ tới nút ở đầu và cuối danh sách.
Mỗi nút chứa 2 con trỏ tới nút đứng trước và sau nó trong danh sách.
Có thể xử lý hiệu quả thao tác thêm và xóa phần tử ở đầu và cuối danh sách, xử lý thêm hoặc xóa phần tử ở giữa danh sách là thao tác phức tạp hơn do phải di chuyển trên danh sách.
Sử dụng con trỏ tới 1 nút trong danh sách có thể thêm phần tử vào trước hoặc sau nó trong danh sách.

8.2. Các khai báo và định nghĩa

Macro DLIST_DECL_IMPL khai báo và định nghĩa cấu trúc danh sách móc nối kép. Các tham số:

dlname: Tên cấu trúc lưu trữ đồng thời là tiền tố cho các thành phần.
elem_t: Kiểu dữ liệu phần tử.

Ví dụ sử dụng: DLIST_DECL_IMPL(dll,int) - Khai báo và định nghĩa danh sách móc nối kép tên là dll với kiểu phần tử là int.

struct dll_node {
int value;
struct dll_node *next;
struct dll_node *prev;
};
struct dll {
struct dll_node *first;
struct dll_node *last;
int size;
};

Các cấu trúc dll_node là nút của danh sách, dll là cấu trúc điều khiển của danh sách. Trong đó value là dữ liệu được lưu trong nút, next và prev là các con trỏ tới nút tiếp theo và nút trước, first và last là các con trỏ tới đầu và cuối danh sách, size là số lượng phần tử của nút.

Các Hàm giao diện sau được khai báo và định nghĩa:

8.2.1. struct dll *dll();

struct dll *dll();

Tạo cấu trúc điều khiển.

Giá trị trả về:

Hàm trả về con trỏ tới đối tượng mới được tạo.

8.2.2. struct dll dll_append(struct dll list, int value);

struct dll *dll_append(struct dll *list, int value);

Thêm phần tử vào cuối danh sách.

Giá trị trả về:

Hàm trả về con trỏ list.

8.2.3. struct dll dll_prepend(struct dll list, int value);

struct dll *dll_prepend(struct dll *list, int value);

Thêm phần tử vào đầu danh sách.

Giá trị trả về:

Hàm trả về con trỏ list.

8.2.4. struct dll dll_ins(struct dll list, int idx, int value);

struct dll *dll_ins(struct dll *list, int idx, int value);

Chèn phần tử vào vị trí có chỉ số idx trong danh sách. Nếu chỉ số không hợp lệ thì bỏ qua. Chỉ số = 0 tương đương với chèn vào đầu danh sách, chỉ số = size tương đương với chèn vào cuối danh sách.

Giá trị trả về:

Hàm trả về con trỏ list.

8.2.5. struct dll dll_insa(struct dll list, struct dll_node *pos, int value);

struct dll *dll_insa(struct dll *list, struct dll_node *pos, int value);

Chèn phần tử vào sau nút được xác định bằng con trỏ pos.

Giá trị trả về:

Hàm trả về con trỏ list.

8.2.6. struct dll dll_insb(struct dll list, struct dll_node *pos, int value);

struct dll *dll_insb(struct dll *list, struct dll_node *pos, int value);

Chèn phần tử vào trước nút được xác định bằng con trỏ pos.

Giá trị trả về:

Hàm trả về con trỏ list.

8.2.7. struct dll_node dll_at(struct dll list, int idx);

struct dll_node *dll_at(struct dll *list, int idx);

Truy cập nút theo chỉ số idx.

Giá trị trả về:

Nếu chỉ số idx không hợp lệ thì hàm trả về NULL, hàm trả về con trỏ tới nút có chỉ số idx trong trường hợp ngược lại.

8.2.8. int dll_dfirst(struct dll *list);

int dll_dfirst(struct dll *list);

Xóa nút ở đầu danh sách. Nếu không tồn tại phần tử đầu tiên thì bỏ qua.

Giá trị trả về:

Hàm trả về số lượng nút đã xóa.

8.2.9. int dll_dlast(struct dll *list);

int dll_dlast(struct dll *list);

Xóa nút ở cuối danh sách. Nếu không tồn tài phần tử đầu tiên thì bỏ qua.

Giá trị trả về:

Hàm trả về số lượng nút đã xóa.

8.2.10. int dll_dnode(struct dll list, struct dll_node node);

int dll_dnode(struct dll *list, struct dll_node *node);

Xóa nút được trỏ tới bởi node trong danh sách. Nếu node == NULL hoặc rỗng, hoặc list == NULL thì bỏ qua.

Giá trị trả về:

Hàm trả về số lượng nút đã xóa.

8.2.11. int dll_del(struct dll *list, int idx);

int dll_del(struct dll *list, int idx);

Xóa nút có chỉ số idx trong list. Nếu list == NULL hoặc rỗng, hoặc idx là chỉ số không hợp lệ thì bỏ qua.

Giá trị trả về:

Hàm trả về số lượng nút đã xóa.

8.2.12. int dll_empty(struct dll *list);

int dll_empty(struct dll *list);

Kiểm tra list có rỗng hay không, list phải trỏ tới 1 danh sách đã được cấp phát bộ nhớ.

Giá trị trả về:

Hàm trả về 1 nếu danh sách rỗng, trong trường hợp ngược lại hàm trả về 0.

8.2.13. void dll_free(struct dll *list);

void dll_free(struct dll *list);

Giải phóng bộ nhớ đã được cấp phát cho danh sách.

Giá trị trả về:

Hàm không trả về giá trị.

!Lưu ý: Mã nguồn được chia sẻ công khai và tự do, vì vậy người sử dụng tự xử lý các vấn đề có thể phát sinh khi sử dụng mã nguồn. Tài liệu vẫn đang trong giai đoạn tiếp tục hoàn thiện, các ý kiến góp ý, hiệu chỉnh, thảo luận, và các ý kiến khác nếu có vui lòng gửi về email: ngocnb@soict.hust.edu.vn.

[1] Thiết kế này thuận tiện cho các bài toán điển hình như đếm số lần xuất hiện của từ.