1. Xây dựng một node trong danh sách liên đơn Danh sách liên kết đơn (singly linked list) có đặc điểm là mỗi node (phần tử) chỉ liên kết với node đứng sau nó trong danh sách. Mỗi node trong danh sách liên kết gồm 2 phần: Phần dữ liệu (data) dùng để lưu nội […]
Cấu trúc dữ liệu và giải thuật
Các thao tác cơ bản trên danh sách liên kết đơn (Singly Linked List)
Có nhiều thao tác trên danh sách liên kết đơn như thêm node, hủy node, tìm kiếm node trong danh sách, sắp xếp danh sách,… 1. Định nghĩa danh sách liên kết đơn Giả sử, chúng ta tạo một danh sách liên kết đơn lưu trữ một dãy số nguyên như sau: 2. Khởi tạo […]
Xây dựng danh sách liên kết kép (Doubly Linked List) với con trỏ (pointer)
1. Định nghĩa danh sách liên kết kép Danh sách liên kết kép (doubly linked list) có đặc điểm là mỗi phần tử liên kết với phần tử đứng trước và đứng sau nó trong danh sách. Giả sử, chúng ta tạo ra một danh sách liên kết kép lưu trữ một dãy số nguyên […]
Ngăn xếp (stack) là gì? Cách xây dựng ngăn xếp
1. Ngắn xếp (stack) là gì? Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính, hoạt động theo cơ chế LIFO (Last In First Out), tạm dịch là “vào sau ra trước”. Có nghĩa là phần tử nào được thêm vào sau trong stack thì sẽ được lấy ra trước. Có thể hình […]
Hàng đợi (queue) là gì? Cách xây dựng hàng đợi
1. Hàng đợi (queue) là gì? Hàng đợi (queue) là một cấu trúc dữ liệu hoạt động theo cơ chế FIFO (First In First Out), tạm dịch là “vào trước ra trước”. Có nghĩa là phần tử nào được thêm hàng đợi trước thì sẽ được lấy ra trước. Có thể hình dung hàng đợi […]
Cấu trúc dữ liệu dạng cây là gì? Đặc điểm của cây nhị phân (Binary Tree)
1. Cấu trúc dữ liệu dạng cây là gì? Cây (tree) là một cấu trúc dữ liệu gồm một tập hữu hạn các nút, giữa các nút có một quan hệ phân cấp, gọi là quan hệ “cha – con”. Trong cây, có một nút đặc biệt, không có nút cha, gọi là gốc nút […]
Các thao tác cơ bản trên cây nhị phân (Binary Tree)
1. Biểu diễn cây nhị phân Cây nhị phân là một cấu trúc dữ liệu bao gồm các nút được kết nối với nhau theo quan hệ cha con với mỗi nút cha có tối đa 2 nút con. Mỗi nút của cây nhị phân sẽ lưu các thông tin sau: Giá trị lưu tại […]
Các thao tác trên cây nhị phân tìm kiếm (Binary Search Tree)
1. Đặc điểm của cây nhị phân tìm kiếm Cây nhị phân tìm kiếm (Binary Search Tree) là một cây nhị phân có đặc điểm: Tất cả các nút trong cây con bên trái lưu trữ giá trị nhỏ hơn nút đang xét Tất cả các nút trong cây con bên phải lưu trữ giá […]