[Imperative Programming + C] Bài 16 – Simplicity DSA List (tiếp theo)

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 Listpush/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"intlist_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)