Oh.. vậy là cái project nho nhỏ simplicity-dsa-c đã phải tạm dừng một thời gian khá dài để nhường chỗ cho các bài viết chính của Series có trọng tâm là giới thiệu các mô hình lập trình chính. Sau khi hoàn thành xong Sub-Series Procedural và quay trở lại chạm vào Elm lần nữa thì mình mới nhớ ra là đang để dành các bài viết về cấu trúc lưu trữ List ở đây và quết định thực hiện tiếp một vài bài viết về simplicity-dsa-c.
Đây cũng xem như là để tạo khoảng trống thời gian cho việc ôn lại cú pháp căn bản của Elm trước khi tiếp tục tìm hiểu về việc xây dựng SPA và nếu như bạn là một người bắt đầu đồng hành từ Sub-Series Declarative hoặc Functional thì cũng sẽ có thời gian để lướt lại các bài viết về Elm trong Sub-Series Declarative. Và sau khi thực hiện xong một vài bài viết về List trong cái mini project ở đây để tìm hiểu về các cấu trúc dữ liệu ở cấp độ tổng quan thì chúng ta sẽ quay lại với Elm tại Sub-Series Declarative.
List
Khi nói tới việc tổ chức và lưu trữ dữ liệu ở dạng tập hợp các bản ghi hay các giá trị cùng kiểu thì ở các ngôn ngữ Procedural người ta thường nhắc tới cấu trúc mảng Array đầu tiên, thế nhưng trong các ngôn ngữ Functional thì câu trả lời phổ biến nhất lại là List với điểm khác biệt căn bản là các List không bị giới hạn về dung lượng lưu trữ và không hỗ trợ tham chiếu bằng trị số chỉ vị trí index của các phần tử.
Lý do tại sao các ngôn ngữ Functional lại sử dụng List phổ biến như vậy thì chúng ta sẽ để dành cho những bài viết sau cùng, sau khi đã biết cách tổ chức lưu trữ dữ liệu bằng cấu trúc này. Và để bắt đầu tìm hiểu về List thì chúng ta sẽ xuất phát với ví dụ lưu trữ dữ liệu trong mảng đơn thuần literal array của C. Chúng ta vẫn sẽ xem xét trường hợp mảng chưa định kiểu với các ô nhớ là các biến con trỏ void* để có khả năng lưu trữ một giá trị primitive hoặc một địa chỉ tham chiếu reference.
#include <stdio.h>
#include <stdlib.h> typedef double val;
typedef void* ref; int main ( int $argc , char** $argv ) { int $capacity = 9; void* $literal_array = malloc (8 * $capacity); val* $val_pointer = $literal_array; *($val_pointer + 0) = 'A'; ref* $ref_pointer = $literal_array; *($ref_pointer + 1) = "Message"; printf ("Stored character: %c \n", (char) $val_pointer[0]); printf ("Stored string: %s \n", $ref_pointer[1]); return 0; }
Như vậy là chúng ta đã tạo ra một cấu trúc mảng đơn thuần với 9 ô nhớ có độ rộng bằng nhau và là 8 bit để có thể lựa chọn lưu trữ địa chỉ tham chiếu hoặc giá trị primitive nào đó không quá lớn và trong biên độ của double. Sau đó chúng ta đã sử dụng ô nhớ đầu tiên qua kiểu con trỏ val* để lưu vào đó một giá trị primitive là ký tự 'A' và sử dụng ô nhớ tiếp theo qua kiểu con trỏ ref* để lưu vào đó địa chỉ tham chiếu của chuỗi "Message".
Mục đích của chúng ta khi tạo ra List vẫn là tạo ra các ô nhớ void* để có thể lựa chọn lưu trữ linh động như vậy. Tuy nhiên vì đặc đính của List là không giới hạn dung lượng lưu trữ vì vậy nên các ô nhớ void* lúc này sẽ không được cấp phát với số lượng cố định từ đầu và vì vậy cũng sẽ không có vị trí liền kề nhau trong bộ nhớ đệm của máy tính.
Chính vì vậy nên trong trường hợp này khi sử dụng ô nhớ void* đầu tiên qua kiểu con trỏ val* hay ref* có độ rộng là 8 bit thì chúng ta cũng sẽ không thể thực hiện thao tác bước tới các ô nhớ liên tiếp như kiểu pointer + 0, pointer + 1, pointer + 2, v.v... Và đây có lẽ là lý do căn bản để giải thích cho việc cấu trúc List mặc định không hỗ trợ truy xuất các phần tử lưu trữ thông qua các trị số chỉ vị trí index.
Oh.. nếu vậy thì làm thế nào để lặp qua nội dung của một List giống như khi chúng ta đang có địa chỉ tham chiếu của phần tử đầu tiên của một mảng Array? Hay làm thế nào để chúng ta có thể bước lần lượt tới các phần tử tiếp theo đã được lưu trữ trong cấu trúc List?
Item
Giải pháp để di chuyển từ ô nhớ void* đầu tiên tới ô nhớ tiếp theo lúc này là chúng ta sẽ phải có thêm các thông tin mô tả bổ trợ cho mỗi ô nhớ lưu trữ dữ liệu của List. Cụ thể là mỗi ô nhớ void* lúc này sẽ được bọc trong một struct kèm theo các trường lưu trữ địa chỉ tham chiếu của các ô nhớ liền trước và liền sau trong List.
Thông thường thì người ta thường gọi các struct như thế này là nguyên tố element hoặc nút giao node, bởi vì thiết kế vỏ bọc này còn được sử dụng trong các cấu trúc dữ liệu khác mà chúng ta sẽ tìm hiểu sau này có tên gọi đại loại như tree. Tuy nhiên ở đây mình gọi là item trong trường hợp sử dụng với List để dễ liên tưởng tới các danh sách nội dung mà chúng ta thấy trong cuộc sống thường nhật hoặc các danh sách unordered list trong HTML.
typedef double val;
typedef void* ref; typedef struct item { struct item* prev; void* data; struct item* next;
} item_struct; typedef item_struct* Item;
Như vậy là đứng từ vị trí của mỗi Item đang chứa một ô nhớ void* để lưu trữ dữ liệu thì chúng ta có thể di chuyển tới một Item liền kề trước đó prev hoặc di chuyển tới Item tiếp theo next. Bây giờ chúng ta hãy thử tạo ra một vài Itemđược kết nối với nhau và lặp qua các nội dung lưu trữ trong một lượt thao tác.
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "list.h"
Sau khi nạp các thư viện cần thiết thì chúng ta cần tự động hóa thao tác khởi tạo struct và trả về con trỏ Item..
Item item_new (void) { Item $item = malloc (sizeof (item_struct)); $item->data = malloc (8); $item->prev = NULL; $item->next = NULL; return $item; }
Rồi tới hàm main chứa code chạy thử..
int main ( int $argc , char** $argv ) { Item $first = item_new (); *((val*) $first->data) = 0; // - - - - - - - - - Item $second = item_new (); *((val*) $second->data) = 1; $first->next = $second; $second->prev = $first; // - - - - - - - - - Item $last = item_new (); *((val*) $last->data) = 2; $second->next = $last; $last->prev = $second; // - - - - - - - - - Item $cursor = $first; loop : if ($cursor != NULL) { printf ("Stored data: %f \n", *((val*) $cursor->data)); $cursor = $cursor->next; // --- goto loop; } return 0; }
Và ở cửa sổ dòng lệnh..
cd simplicity-dsa-c
gcc src\main.c -o bin\main
bin\main Stored data: 0.000000 Stored data: 1.000000
Stored data: 2.000000
Coding Convention
Bài viết mở đầu giới thiệu về cấu trúc List của chúng ta tới đây xem như đã hoàn thành và các phương thức thao tác với List chúng ta sẽ để dành cho các bài viết tiếp theo. Còn trong phần Coding Convention thì mình muốn cập nhật lại một số quy ước riêng mà mình sử dụng trong code của simplicity-dsa-c về việc đặt tên biến và cấu trúc thư mục chứa các tệp mã nguồn.
Cụ thể là sau khi sử dụng ngôn ngữ Ada ở lớp mẫu giáo thì thói quen đọc code của mình bị thay đổi theo và rất cần có sự tương phản tốt giữa tên biến và các từ khóa của ngôn ngữ. Vì vậy nên mặc dù không thể sử dụng các tên định danh theo kiểu Uppercase_Name của Ada ở đây thì mình cũng đặt thử vào phía trước tên của các biến cục bộ và các tham số của các sub-program ký hiệu $ thường dùng của một số ngôn ngữ khác như XQuery, PHP, hay một số thư viện JavaScript.
Tuy nhiên vị trí tên các trường dữ liệu của struct thì vẫn sẽ sử dụng cách đặt tên thông thường và không có thêm ký hiệu $ để phân biệt với các tham số và các biến cục bộ của các sub-program và mặt khác là để cú pháp tham chiếu gọn gàng hơn một chút. Thay vì $item->$first thì chúng ta có $item->first và ký hiệu $ chủ yếu là để đọc đoạn khai báo các biến nhanh hơn bởi có xuất hiện thêm các tên định kiểu dữ liệu ở phía trước.
Còn lại thì nhìn chung tên của các biến và các sub-program vẫn sẽ sử dụng kiểu lowercase_name như từ đầu project tới giờ. Quy ước đặt tên này có lẽ là rất thân thuộc nếu như bạn tới với Sub-Series này từ nguồn nào đó khác như Google tìm kiếm và đã biết tới ngôn ngữ PHP trước đó. Còn về mặt cấu trúc thư mục chứa mã nguồn thì đây là cấu trúc mà mình đang sử dụng hiện tại:
simplicity-dsa-c
├── bin
│ └── main.exe
└── src ├── array │ ├── concat.c │ ├── destroy.c │ ├── from.c │ ├── new.c │ └── slice.c ├── array.h ├── book │ ├── destroy.c │ └── new.c ├── book.h ├── list │ ├── item │ │ └── ... │ └── ... ├── list.h └── main.c
Source code: GitHub.com
Mỗi một kiểu dữ liệu sẽ có một thư mục đại diện riêng ví dụ array, list, v.v... Cái book là từ ví dụ của những bài viết trước đó và có thể sẽ không phải sử dụng lại nhưng mình vẫn tạm thời giữ lại cho đến khi thực hiện xong cái mini project này. Bên cạnh đó là các tệp khai báo header.h sẽ được đặt cùng cấp với các thư mục đại diện để cú pháp sử dụng sẽ không phải viết tên của thư mục đại diện khi #include, ví dụ code ở main thay vì #include "list/list.h" thì chúng ta chỉ cần viết #include "list.h".
[Imperative Programming + C] Bài 16 - Simplicity DSA List (tiếp theo)