Trong bài 5 cấu trúc dứ liệu dành cho Pro Javascripter, Worklabs Coding School đã giới thiệu một số cấu trúc dữ liệu quan trọng mà các lập trình viên cần phải nắm chắc để có thể làm việc nhanh và hiệu quả nhất. Để giúp bạn hiểu rõ hơn về các cấu trúc dữ liệu này, WCS gửi đến bạn hai bài tập ngắn để áp dụng các kiến thức về Queue và Linked List.

Queue: Tạo các số dưới dạng mã nhị phân từ 1 đến n

Đề bài: Xây dựng một function findBin(n) để tạo ra một dãy các số từ 1 đến n dưới dạng mã nhị phân, sử dụng một cấu trúc Queue

Dữ liệu đầu vào: nhập một số tự nhiên n

n = 3

Kết quả:

result = ["1","10","11"]

Trong hệ thống số nhị phân, các số được tạo ra bằng cách thêm “0” hoặc “1” vào số trước đó. Như vậy, một số nhị phân bất kỳ, ta sẽ có được hai số nhị khác. Ví dụ

  • Dạng nhị phân của 1 là 1
  • Dạng nhị phân của 2 là 10 được tạo ra bằng cách thêm 0 vào 1
  • Dạng nhị phân của 3 là 11, được tạo ra bằng cách thêm 1 vào 1

Bạn có thể tìm hiểu thêm về hệ số nhị phân tại đây.

Để giải quyết vấn đề này, ta có thể sử dụng cấu trúc Queue và một vòng lặp. Về cơ bản, mỗi khi ta tạo được một số nhị phân, ta sẽ đẩy số nhị phân này vào hàng đợi. Đến thời điểm xử lý một mã nhị phân bất kỳ trong hàng đợi, ta có thể tạo ra thêm hai mã nhị phân cho hai số tiếp theo.

Có thể thấy ở hàng số 7 trong file index.js, mã nhị phân đầu tiên trong chuỗi là 1 được đẩy vào hàng đợi. Trong mỗi vòng lặp, ta sẽ lấy phần từ ở cuối hàng đợi ra để đẩy vào mảng kết quả theo đúng quy tắc First In – First Out. Với mỗi một một mã nhị phân được lấy ra từ hàng đợi này, ta lại tạo thêm được hai mã nhị phân khác trong chuỗi và tiếp tục đẩy vào hàng đợi chờ xử lý (dòng 11 – 15).

Vòng lặp sẽ tiếp tục đến khi độ dài của mảng kết quả bằng n, lúc đó ta có kết quả cần tìm nằm trong mảng result.

Linked List: Đảo chiều Linked List

Đề bài: Xây dựng một function reverse() để đảo chiều một linked list cho trước.

LinkedList = 0->1->2->3-4

Kết quả:

LinkedList = 4->3->2->1->0

Để giải quyết vấn đề này, ta sử dụng một vòng lặp để lặp qua mọi phần từ trong Linked list. Vòng lặp hoạt động như sau:

  • Với một currentNode, ta tạm gán liên kết của nó cho nextNode.
  • Sau đó, ta thay đổi liên kết của currentNode trỏ đến previousNode.
  • currentNode sẽ trở thành previousNode cho vòng lặp tiếp theo.
  • nextNode (vốn là liên kết của `currentNode`) sẽ trở thành currentNode
  • Vòng lặp sẽ tiếp tục cho đến khi ta không còn currentNode nữa (currentNode = null)

Cuối cùng, ta điều chỉnh lại head của linked list, là previousNode cuối cùng của vòng lặp. Sau khi hoàn tất, ta đã có kết quả đảo ngược một Linked list cho trước.

Tạm kết

Với hai bài tập đơn giản trên, WCS hy vọng bạn có thể hiểu rõ hơn về Linked List và Queue và cách sử dụng hai cấu trúc dữ liệu này trong Javascript. Trong tương lai, WCS sẽ tiếp tục gửi đến bạn nhiều bài tập hơn về các cấu trúc dữ liệu quan trọng của Javascript. Mời ban theo dõi WorkLabs Blog để không bỏ lỡ nhé.