Như vậy là sau khi xuất phát từ cấu trúc lưu trữ của một mảng đơn thuần literal array
thì chúng ta cũng đã định nghĩa được một kiểu danh sách đơn thuần literal array
với các ô nhớ void*
được bọc trong các struct item
chứa thêm thông tin tham chiếu tới các vỏ bọc của các void*
liền trước và liền sau.
Lúc này nếu như chúng ta cứ lưu trữ địa chỉ tham chiếu của struct item
đầu tiên và gọi đó là list
thì ý nghĩa cũng tương tự như khi chúng ta có con trỏ array
thực ra chỉ lưu trữ duy nhất ô nhớ void*
đầu tiên của mảng nhưng vẫn được gọi là mảng. Hoàn toàn phù hợp.
Container
Tuy nhiên để thuận tiện hơn cho các thao tác sử dụng sau này thì chúng ta vẫn sẽ đặt góc tham chiếu từ các ngôn ngữ lập trình bậc cao cũng như khi nhìn nhận kiểu Array
là một struct
có chứa literal array
và các thông tin hỗ trợ là dung lượng tối đa capacity
và độ dài hiệu dụng length
.
Ở đây chúng ta có kiểu cấu trúc của literal list
với các struct item
được tạo ra ngẫu nhiên và xin cấp phát bộ nhớ rời rạc thì yếu tố capacity
chắc chắn là sẽ không cần thiết; Và thêm vào đó thì việc xác định điểm kết thúc của list
cũng hoàn toàn khả thi chứ không giống như literal array
vì vậy nên chúng ta cũng không cần lưu trữ và cập nhật thường xuyên độ dài hiệu dụng hay số phần tử đang có mặt length
.
Và ở một thời điểm bất kỳ khi chúng ta muốn kiểm tra số phần tử đang có mặt trong list
thì có thể tạo ra một con trỏ Item $cursor
và đếm từ phần tử đầu tiên cho đến khi tìm thấy $cursor->next
là một con trỏ NULL
, hoặc thao tác đếm theo chiều ngược lại xuất phát từ phần tử cuối cùng của list
. Vì vậy nên một địa chỉ tham chiếu đại diện cho list
sẽ chỉ cần cung cấp cho chúng ta biết địa chỉ tham chiếu của phần tử đầu tiên first
và phần tử cuối cùng last
của literal list
nhằm hỗ trợ cho các thao tác duyệt dữ liệu có thể chọn chiều di chuyển thuận lợi.
typedef double val;
typedef void* ref; typedef struct item { struct item* prev; void* data; struct item* next;
} item_struct; typedef item_struct* Item; typedef struct { Item first; Item last;
} list_struct; typedef list_struct* List;
Constructors
Như vậy là chúng ta đang có thêm các struct
mô tả Item
và List
cần được xây dựng các trình khởi tạo để có cú pháp sử dụng gọn gàng hơn.
// --- typedef ...
// --- constructors Item item_new (void);
List list_new (void);
Trình khởi tạo cho Item
, chúng ta chỉ cần copy/paste
từ code ví dụ của phần trước.
#include <stdlib.h>
#include <stddef.h>
#include "../../list.h" Item item_new (void) { Item $item = malloc (sizeof (item_struct)); $item->prev = NULL; $item->data = malloc (sizeof (void*)); $item->last = NULL; return $item; }
Còn đối với List
thì chúng ta chỉ cần cấp phát bộ nhớ cho struct
và trỏ các con trỏ bên trong về NULL
.
#include <stdlib.h>
#include "../list.h" List list_new (void) { List $list = malloc (sizeof (list_struct)); $list->first = NULL; $list->last = NULL; return $list; }
Riêng trường hợp khởi tạo bằng cách liệt kê các phần tử đã biết thì chúng ta có thể liệt kê bằng cú pháp mảng literal array
và nạp vào cấu trúc List
bằng một trình khởi tạo list_from
sẽ được nói đến sau khi chúng ta đã viết xong các sub-program
hỗ trợ khác.
Utilities
Các thao tác thường sử dụng với List
chủ yếu là tương tác ở các vị trí đầu/cuối và kiểm tra độ dài hay số lượng phần tử đang có mặt trong List
. Với mục đích ban đầu xuất phát từ việc tìm hiểu những kiến thức bổ trợ cho logic hoạt động của JavaScript
nên mình sẽ đặt tên các sub-program
theo các phương thức của JS Array
.
// --- typedef ...
// --- constructors ...
// --- utilities int list_length (List $list); void list_unshift (List $list, Item $item);
Item list_shift (List $list); void list_push (List $list, Item $item);
Item list_pop (List $list);
Lưu ý:
- Thao tác
unshift
có tên gọi khác thường dùng làappend
- Tương tự thì
shift
còn có tên gọi làhead
- Và cặp thao tác ở vị trí cuối
List
push/pop
còn được gọi làprepend/last
Ngoài ra thì trong các môi trường Functional
như Elm
, PureScript
, hay Haskell
, thì chúng ta còn có thêm list_init
để tách lấy List
loại trừ phần tử cuối cùng và list_tail
để tách lấy List
loại trừ phần tử đầu tiên.
Ở đây chúng ta sẽ có thao tác kiểm tra độ dài được xử lý trước và để dành các cặp thao tác tiếp theo cho bài viết sau. Và như đã mô tả trước đó thì chúng ta chỉ cần tạo ra một con trỏ Item $cursor
và bắt đầu đếm từ phần tử đầu tiên hoặc phần tử cuối cùng của List
cho đến khi gặp con trỏ NULL
.
#include <stddef.h>
#include "../list.h" int list_length (List $list) { int $counter = 0; Item $cursor = $list->first; loop : if ($cursor != NULL) { $counter += 1; $cursor = $cursor->next; // --- goto loop; } return $counter; }
Tạm thời thì chúng ta sẽ không viết code chạy thử ở main
vì chưa có các sub-program
hỗ trợ thao tác chèn các Item
vào List
nhanh chóng, và tiếp tục di chuyển ngay tới các cặp thao tác tiếp theo.
(chưa đăng tải) [Imperative Programming + C] Bài 17 - Simplicity DSA List (tiếp theo)