Data Structures – Cấu trúc dữ liệu (P3)

Cấu trúc dữ liệu là khối xây dựng cơ bản của lập trình máy tính. Chúng xác định cách tổ chức, lưu trữ và thao tác dữ liệu trong một chương trình. Hiểu cấu trúc dữ liệu là rất quan trọng để phát triển các thuật toán hiệu quả và hiệu quả. Trong hướng dẫn này, chúng ta sẽ khám phá các cấu trúc dữ liệu được sử dụng phổ biến nhất, như Arrays, Linked Lists, Stacks, Queues, Trees and Graphs, …

Các cấu trúc dữ liệu phổ biến

7. Heap

Heap là một cấu trúc dữ liệu dựa trên Cây đặc biệt, trong đó cây là cây nhị phân hoàn chỉnh. Nói chung, Heap có thể có hai loại:

Max-Heap: Trong Max-Heap, khóa có tại nút gốc phải lớn nhất trong số các khóa có ở tất cả các nút con của nó. Thuộc tính tương tự phải đúng đệ quy cho tất cả các cây con trong Cây nhị phân đó.
Min-Heap: Trong Min-Heap, khóa có tại nút gốc phải ở mức tối thiểu trong số các khóa có ở tất cả các nút con của nó. Thuộc tính tương tự phải đúng đệ quy cho tất cả các cây con trong Cây nhị phân đó.

8. Hash

Băm là một Cấu trúc dữ liệu quan trọng được thiết kế để sử dụng một hàm đặc biệt gọi là hàm Hash được sử dụng để ánh xạ một giá trị nhất định bằng một khóa cụ thể để truy cập các phần tử nhanh hơn. Hiệu quả của việc ánh xạ phụ thuộc vào hiệu quả của hàm băm được sử dụng.

Đặt hàm băm H(x) ánh xạ giá trị x tại chỉ mục x%10 trong một mảng. Ví dụ: nếu danh sách các giá trị là [11, 12, 13, 14, 15] thì nó sẽ được lưu lần lượt tại các vị trí {1, 2, 3, 4, 5} trong mảng hoặc bảng Hash.

9. Matrix

Ma trận đại diện cho một tập hợp các số được sắp xếp theo thứ tự hàng và cột. Cần đặt các phần tử của ma trận trong dấu ngoặc đơn hoặc dấu ngoặc đơn.

Một ma trận có 9 phần tử được hiển thị dưới đây.

10. Trie

Trie là một cấu trúc dữ liệu truy xuất thông tin hiệu quả. Sử dụng Trie, độ phức tạp của tìm kiếm có thể được đưa đến giới hạn tối ưu (độ dài khóa). Nếu chúng ta lưu trữ các khóa trong cây tìm kiếm nhị phân, một BST cân bằng tốt sẽ cần thời gian tỷ lệ thuận với M * log N, trong đó M là độ dài chuỗi tối đa và N là số lượng khóa trong cây. Sử dụng Trie, chúng ta có thể tìm kiếm khóa trong thời gian O(M). Tuy nhiên, hình phạt nằm ở yêu cầu lưu trữ của Trie.

11. Graph

Đồ thị là một cấu trúc dữ liệu bao gồm một tập hợp các nút (đỉnh) được kết nối bởi các cạnh. Đồ thị được sử dụng để thể hiện mối quan hệ giữa các đối tượng và được sử dụng rộng rãi trong khoa học máy tính, toán học và các lĩnh vực khác. Đồ thị có thể được sử dụng để mô hình hóa nhiều hệ thống trong thế giới thực, chẳng hạn như mạng xã hội, mạng giao thông và mạng máy tính.