Cấu trúc dữ liệu cơ bản

Các cấu trúc dữ liệu cơ bản: mảng, list, stack, queue, heap, tree và hash table

1. Mảng - Array

• Tập hợp cố định các thành phần cùng kiểu.

• Lưu trữ kế tiếp nhau trên bộ nhớ

• Truy cập ngẫu nhiên bằng chỉ số

• Kích thước cố định

• Sắp đặt các phần tử phức tạp

1. Linked List - Danh sách liên kết

• Truy cập tuần tự

• Mỗi phần tử có thông tin về phần tử tiếp theo

• Sắp đặt phần tử đơn giản

• Kích thước linh động

Một số dạng danh sách liên kết: Danh sách liên kết vòng, Danh sách liên kết kép, Danh sách liên kết vòng kép.

1. Stack - Ngăn xếp

• Thêm, xóa phần tử được thực hiện ở một đầu

• Tuân theo cơ chế LIFO (Last In First Out)

1. Queue - Hàng đợi

• Thêm vào một đầu và lấy ra ở đầu còn lại

• Tuân theo cơ chế FIFO (First In First Out)

Một số hàng đợi thông dụng:

• Priority Queue: mỗi phần tử có một độ ưu tiên và phần tử có độ ưu tiên cao được xử lý trước phần tử có độ ưu tiên thấp.

• Dequeue (double-ended queue): có thể thêm hoặc lấy phần tử ở cả hai đầu

• Input-restricted Deque: có thể xóa ở cả hai đầu, nhưng chỉ được thêm ở một đầu

• Output-retricted Deque: có thể thêm ở cả hai đầu, nhưng chỉ được xóa ở một đầu

1. Heap - Đống

• Cấu trúc dữ liệu dựa trên cây

• Giá trị node cha luôn lớn hơn giá trị node con

• Dùng để hiện thực Priority Queue

• Ứng dụng trong nhiều thuật toán đồ thị (Dijkstra) hay Heap Sort

1. Tree - Cây Duyệt cây:

• Duyệt trước: Thăm nút gốc, rồi thăm lần lượt cây con từ trái sang phải cũng theo thứ tự trước.

• Duyệt giữa: Thăm cây con trái theo thứ tự giữa, rồi thăm nút gốc sau đó lần lượt thăm các cây còn lại của nút gốc từ trái sang phải theo thứ tự giữa.

• Duyệt sau: Lần lượt thăm hết cây con của nút gốc, từ trái sang phải theo thứ tự sau, cuối cùng thăm nút gốc.

Một số loại cây thông dụng:

• Binary Tree: mỗi nút có tối đa 2 nút con

• Full binary tree: là cây nhị phân mà mỗi nút có 0 hoặc 2 nút con.

• Perfect binary tree: là cây nhị phân mà tất cả nút không phải nút lá có đúng 2 nút con và các nút lá có cùng độ sâu.

• Complete binary tree: mỗi tầng trừ tầng sâu nhất đều đầy đủ các nút lá, và khi thêm nút thì thêm nút bên trái trước.

• Cây nhị phân tìm kiếm: tại nút bất kì, khóa của nó luôn lớn hơn khóa nút con bên trái và nhỏ hơn khóa của nút con bên phải. Tham khảo

• AVL (Cây nhị phân cân bằng): là cây nhị phân tìm kiếm mà tại mỗi nút, chiều cao của hai cây con sai khác nhau không quá 1. Tham khảo

• Cây nhị phân cân bằng hoàn toàn: là cây nhị phân tìm kiếm mà tại mỗi nút, số nút của cây con trái chênh lệch không quá một so với số nút của cây con phải.

• Red-Black Tree: là cây tìm kiếm nhị phân tìm kiếm có tính chất: nút gốc và các nút lá luôn là màu đen, mỗi nút là đỏ hoặc đen, cả 2 con của mọi nút đỏ là đen, tất cả đường đi từ một nút bất kì tới lá đều có số nút đen bằng nhau. Tham khảo

1. Hash Table - Bảng băm

• Sử dụng hàm băm (hash function) để ánh xạ từ giá trị khóa thành giá trị số và dùng giá trị số này để đánh chỉ số cho bảng dữ liệu.

• Bảng băm lưu trữ các record

• Dung hòa giữa thời gian truy xuất và không gian lưu trữ

• Hàm băm tốt phải thỏa mãn: tính toán nhanh, các khóa được phân bố đều trong bảng, ít xảy ra đụng độ. Tham khảo