Ok. Trước hết chúng ta cần có sub-program hỗ trợ chèn thêm phần tử mới vào List một cách nhanh chóng để có thể kiểm thử các sub-program ở bài trước.
list_unshift
Từ shift hay left shift được sử dụng để mô tả việc dồn các phần tử trong một tập dữ liệu sang phía bên trái của tập hợp một bước di chuyển, và như vậy sẽ có phần tử đầu tiên được tách ra khỏi tập hợp dữ liệu. JavaScript sử dụng tên unshift để mô tả thao tác dịch chuyển các phần tử theo chiều ngược lại sang phía bên phải và tạo khoảng trống để chèn phần tử mới vào ngay sau thao tác đó.
#include "../list.h" void list_unshift ( List $list , Item $item ) { int $length = list_length ($list); if ($length == 0) { $list->first = $item; $list->last = $item; } else { $item->next = $list->first; $list->first->prev = $item; // --- $list->first = $item; } }
Ở đây chúng ta sẽ chỉ xử lý logic thao tác ở cấp độ vỏ bọc Item chứ không làm việc trực tiếp với kiểu data cụ thể. Trong trường hợp bạn muốn tạo ra các sub-program làm việc trực tiếp với các kiểu data cụ thể thì có thể sử dụng chỉ dẫn #define để tạo macro chứa tham số type và thay thế tên kiểu dữ liệu vào. Bây giờ chúng ta sẽ viết code chạy thử tại main.
#include <stdio.h>
#include <stddef.h>
#include "list.h" int main ( int $argc , char** $argv ) { List $list = list_new (); Item $item = NULL; // - - - - - - - - - $item = item_new (); *((val*) $item->data) = 0; list_unshift ($list, $item); // - - - - - - - - - $item = item_new (); *((val*) $item->data) = 1; list_unshift ($list, $item); // - - - - - - - - - $item = item_new (); *((val*) $item->data) = 2; list_unshift ($list, $item); // - - - - - - - - - printf ("List's length: %i \n", list_length ($list)); Item $cursor = $list->first; loop : if ($cursor != NULL) { printf ("Stored data: %f \n", *((val*) $cursor->data)); $cursor = $cursor->next; // --- goto loop; } return 0; }
Ở cửa sổ dòng lệnh, lần này chúng ta sẽ cần biên dịch thêm cả các tệp trong thư mục src/list và src/list/item.
gcc src\main.c src\list\*.c src\list\item\*.c -o bin\main
bin\main List's length: 3
Stored data: 2.000000 Stored data: 1.000000
Stored data: 0.000000
Như vậy là khi chúng ta duyệt List xuất phát từ vị trí đầu tiên thì những phần tử được thêm vào danh sách sau - đã được hiển thị trước đúng với logic dự kiến của unshift, và hàm list_length cũng đã hoạt động ổn.
list_shift
Để đồng thuận với logic Procedural của list_unshift ở trên thì thao tác lấy ra phần tử đầu tiên ở đây chúng ta cũng sẽ thực hiện biến đổi $list đã có thay vì trả về mảng con hoàn toàn mới với các phần tử được sao chép.
#include <stddef.h>
#include "../list.h" Item list_shift (List $list) { int $length = list_length ($list); Item $result; if ($length == 0) { $result = NULL; } else { $result = $list->first; $list->first = $list->first->next; } return $result; }
Và ở code chạy thử tại main chúng ta sẽ chỉnh sửa để in ra độ dài length trước và sau khi shift.
#include <stdio.h>
#include <stddef.h>
#include "list.h" int main ( int $argc , char** $argv ) { List $list = list_new (); Item $item = NULL; // - - - - - - - - - $item = item_new (); *((val*) $item->data) = 0; list_unshift ($list, $item); // - - - - - - - - - $item = item_new (); *((val*) $item->data) = 1; list_unshift ($list, $item); // - - - - - - - - - $item = item_new (); *((val*) $item->data) = 2; list_unshift ($list, $item); // - - - - - - - - - printf ("List's length: %i \n", list_length ($list)); Item $first = list_shift ($list); printf ("First: %f \n", *((val*) $first->data)); Item $second = list_shift ($list); printf ("Second: %f \n", *((val*) $second->data)); printf ("List's length after being shifted: %i \n", list_length ($list)); return 0; }
gcc ... -o ...
bin\main List's length: 3 First: 2.000000 List's length after being shifted: 1
push & pop
Các thao tác xử lý ở vị trí cuối danh sách List có logic hoạt động tương đồng và chỉ thay đổi một chút vì vậy nên có lẽ chúng ta sẽ không cần viết code chạy thử.
#include "../list.h" void list_push ( List $list , Item $item ) { int $length = list_length ($list); if ($length == 0) { $list->last = $item; $list->first = $item; } else { $item->prev = $list->last; $list->last->next = $item; // --- $list->last = $item; } }
#include <stddef.h>
#include "../list.h" Item list_pop (List $list) { int $length = list_length ($list); Item $result; if ($length == 0) { $result = NULL; } else { $result = $list->last; $list->last = $list->last->prev; } return $result; }
[Imperative Programming + C] Bài 18 - Simplicity DSA List (tiếp theo)