- vừa được xem lúc

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

0 0 19

Người đăng: Semi Dev

Theo Viblo Asia

Câu hỏi thắc mắc mới về việc các ngôn ngữ Functional sử dụng List làm cấu trúc chủ đạo để lưu trữ tập giá trị có phần hơi lạc đề so với dự định ban đầu mà mình bắt đầu cái mini project này. Tuy nhiên đó là điểm đặc biệt của phương thức học theo vết dầu loang, cứ biết tới đâu thì tò mò tới đó, và cứ như vậy thì mới có động lực để tiếp tục mầy mò kiến thức mới.

Câu chuyện lúc này quay trở lại với tư tưởng lập trình hàm Functional vốn đậm chất Toán Học và mọi thứ xuất phát từ biểu thức f(x) = ... x. Một hàm luôn được biểu thị ở dạng biểu thức chứ không phải là một chuỗi các chỉ thị trình tự, và vì vậy các ngôn ngữ Functional chủ đạo thì hầu hết là đều có cú pháp thuần Declarative.

; Chỉ có các định nghĩa và các cấu trúc gắn kèm để giải thích bổ nghĩa cho các yếu tố đã sử dụng của định nghĩa trước đó; Không có các chỉ thị trình tự và cũng vì vậy nên sẽ không có các vòng lặp, bởi như chúng ta đã biết thì bản chất của vòng lặp chính là một chuỗi chỉ thị trình tự được điều hướng xoay vòng lặp lại bởi các nhãn gắn tên label :.

Recursion

Hệ quả tiếp theo là không có công cụ để lặp thao tác trên các tập dữ liệu và lúc này chúng ta lại quay lại với chủ đề Đệ Quy recursion. Và nếu bạn để ý thì bản thân định nghĩa struct item mà chúng ta đã viết cũng là một định nghĩa Đệ Quy với các trường dữ liệu bên trong trỏ về các giá trị của chính kiểu dữ kiệu struct item đang định nghĩa.

Và trong môi trường thuần Declarative thì lối tư duy Đệ Quy cũng lại là phương thức chủ đạo để giải quyết tất cả mọi vấn đề logic chứ không chỉ các tác vụ tính toán tập hợp. Có lẽ đây chính là lý do khiến List được sử dụng làm container chính cho các tập dữ liệu trong các môi trường Functional.

list_populate

Nhân tiện thì chúng ta đang còn thiếu phương thức khởi tạo List cho phép liệt kê các phần tử đã biết với một dạng cú pháp thu gọn nào đó. Chúng ta sẽ mượn cú pháp khởi tạo mảng sẵn có của C, và trình khởi tạo list_from sẽ nhận vào một mảng thuần literal array đang chứa sẵn nội dung để chuyển đổi thành List.

// --- typedef ...
// --- constructors Item item_new (void);
List list_new (void); void list_populate (List $list, void* $literal_array, int $length);

Trình khởi tạo list_populate ở đây vẫn sẽ được xây dựng trên logic biến đổi List ban đầu sau đó trả về kết quả thông qua tham số $list; Tuy nhiên thao tác nạp dữ liệu từ mảng sẽ được xử lý theo phương cách Đệ Quy.

#include "../list.h" void list_populate ( List $list , void* $literal_array , int $length ) { val* $val_pointer = $literal_array; Item $item; if ($length == 0) { /* do nothing */ ; } else { $item = item_new (); *((val*) $item->data) = $val_pointer[0]; list_unshift ($list, $item); $val_pointer += 1; $length -= 1; list_populate ($list, $val_pointer, $length); } }

Sau đó tại code chạy thử main, chúng ta đã có thể mượn cú pháp khởi tạo mảng sẵn có của C.

#include <stdio.h>
#include <stddef.h>
#include "list.h" int main ( int $argc , char** $argv ) { val $number_array[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; List $list = list_new (); list_populate ($list, $number_array, 10); Item $cursor = $list->first; loop : if ($cursor != NULL) { printf ("%f \n", *((val*) $cursor->data)); $cursor = $cursor->next; goto loop; } return 0; }

Và kiểm tra kết quả tại cửa sổ dòng lệnh..

gcc src\main.c src\list\*.c src\list\item\*.c -o bin\main
bin\main 9.000000 8.000000
7.000000
6.000000
5.000000
4.000000
3.000000
2.000000
1.000000
0.000000

List Variants

Ok.. như vậy là kết quả tìm hiểu về cấu trúc lưu trữ List đã giúp mình trả lời được khá nhiều câu hỏi mà bản thân vẫn luôn thắc mắc từ khi bắt đầu học JavaScript và cả những câu hỏi mới phát sinh khi biết tới Functional.

Thực tế thì trong tài liệu DSA mà mình đọc tham khảo có một vài biến thể của List và biến thể mà chúng ta đã sử dụng ở đây được gọi là Danh Sách Hai Chiều Doubly Linked List. Biến thể này cho phép thực hiện thao tác lặp từ cả hai đầu của List tùy vào bối cảnh áp dụng và loại dễ triển khai hơn thì chỉ hỗ trợ một chiều di chuyển next hoặc prev.

Như vậy là sau khi tìm hiểu về ArrayList, và sau đó là một lý thuyết bỏ ngỏ về Vector, chúng ta đã biết rằng khi nói về một cấu trúc dữ liệu thì thực ra chúng ta đang có các khía cạnh quan tâm là:

  • Cách tổ chức và sắp xếp dữ liệu trong bộ nhớ theo kiểu liên tiếp hoặc rời rạc.
  • Giao diện lập trình cung cấp ra bên ngoài và giới hạn.
  • * Các thuật toán xử lý liên quan.

Trong số đó thì yếu tố cuối cùng mang tính chất tối ưu hiệu năng là điểm mà mình tạm thời lược bỏ trong cái mini project này bởi chưa có điểm ứng dụng phù hợp; Và yếu tố giao diện lập trình kèm theo giới hạn thao tác lại là điểm rất quan trọng mà mình muốn tìm hiểu để có thể lựa chọn kiểu cấu trúc dữ liệu phù hợp hơn khi viết code.

Và vì vậy nên trong những bài viết tiếp theo, chúng ta sẽ tìm hiểu về các cấu trúc dữ liệu mang ý nghĩa trọng tâm nhấn vào việc cung cấp giao diện lập trình để giới hạn thao tác trên tập dữ liệu. Điều này sẽ giúp cho chúng ta có thể lược bỏ bớt một phần logic sàng lọc các trường hợp ngoại lệ exception nhờ giới hạn thao tác của cấu trúc dữ liệu và giảm thiểu khả năng phát sinh lỗi vận hành phần mềm.

(chưa đăng tải) [Imperative Programming + C] Bài 20 - Simplicity DSA Stack (mở đầu)

Bình luận

Bài viết tương tự

- vừa được xem lúc

Closure trong Javascript - Phần 2: Định nghĩa và cách dùng

Các bạn có thể đọc qua phần 1 ở đây. Để mọi người không quên, mình xin tóm tắt gọn lại khái niệm lexical environment:.

0 0 66

- vừa được xem lúc

Var vs let vs const? Các cách khai báo biến và hằng trong Javascript

Dạo này mình tập tành học Javascript, thấy có 2 cách khai báo biến khác nhau nên đã tìm tòi sự khác biệt. Nay xin đăng lên đây để mọi người đọc xong hy vọng phân biệt được giữa let và var, và sau đó là khai báo hằng bằng const.

0 0 47

- vừa được xem lúc

VueJS: Tính năng Mixins

Chào mọi người, hôm nay mình sẽ viết về Mixins và 1 số vấn đề trong sử dụng Mixins hay ho mà mình gặp trong dự án thực. Trích dẫn từ trang chủ của VueJS:.

0 0 41

- vừa được xem lúc

Asset Pipeline là cái chi chi?

Asset Pipeline. Asset pipeline là cái chi chi. . Giải thích:.

0 0 69

- vừa được xem lúc

Tạo data table web app lấy dữ liệu từ Google Sheets sử dụng Apps Script

Google Sheets là công cụ tuyệt vời để lưu trữ bảng tính trực tuyến, bạn có thể truy cập bảng tính bất kỳ lúc nào ở bất kỳ đâu và luôn sẵn sàng để chia sẻ với người khác. Bài này gồm 2 phần.

0 0 280

- vừa được xem lúc

Học Deep Learning trên Coursera miễn phí

Bạn muốn bắt đầu với Deep Learning nhưng không biết bắt đầu từ đâu? Bạn muốn có một công việc ở mức fresher về Deep Learning? Bạn muốn khoe bạn bè về kiến thức Deep Learning của mình. Bắt đầu từ đâu.

0 0 50