Level 528 bài
Data Structures
Tự cài các cấu trúc dữ liệu nền tảng bằng con trỏ và cấp phát động.
Chương 21. Linked List
Danh sách đơn, đôi, vòng. Thêm, xóa, tìm, đảo ngược.
- 21.1Node và bố cục bộ nhớKiểu tự tham chiếu, một nút nằm ở đâu trong bộ nhớ, và bảng so sánh đầy đủ với mảng.24 phút
- 21.2Danh sách liên kết đơnStruct gói head, tail, size. Khởi tạo, in, hủy, và những bất biến phải giữ.26 phút
- 21.3Thêm phần tửThêm đầu, thêm cuối, chèn giữa, và vì sao giữ tail biến O(n) thành O(1).26 phút
- 21.4Xóa phần tửXóa đầu, xóa cuối, xóa theo giá trị, và mẹo con trỏ tới con trỏ.28 phút
- 21.5Tìm kiếmTìm theo giá trị, tìm theo vị trí, tìm nút trước, và vì sao danh sách chậm hơn mảng.18 phút
- 21.6Đảo ngược và hai con trỏĐảo ngược tại chỗ bốn bước, đảo bằng đệ quy, tìm nút giữa, phát hiện chu trình.26 phút
- 21.7Danh sách liên kết đôiHai con trỏ mỗi nút, xóa O(1) khi đã có địa chỉ, và mẫu list_head của nhân Linux.26 phút
- 21.8Danh sách vòngNút cuối trỏ về đầu, điều kiện dừng khác hẳn, và bài toán Josephus.22 phút
Chương 22. Stack
Cài bằng mảng và bằng danh sách liên kết, ứng dụng tính biểu thức.
- 22.1Ngăn xếp bằng mảngLIFO, chỉ số top, tràn trên và tràn dưới, và vì sao mọi thao tác là O(1).22 phút
- 22.2Ngăn xếp bằng danh sách liên kếtKhông giới hạn kích thước, đổi lại một lần cấp phát cho mỗi phép push.20 phút
- 22.3Ứng dụng của ngăn xếpKiểm tra ngoặc, đảo chuỗi, hoàn tác, và chuyển đệ quy thành vòng lặp.26 phút
- 22.4Máy tính biểu thứcShunting-yard chuyển trung tố sang hậu tố, rồi tính hậu tố bằng ngăn xếp.30 phút
Chương 23. Queue
Hàng đợi, hàng đợi vòng, deque, hàng đợi ưu tiên.
- 23.1Hàng đợi cơ bảnFIFO, hai con trỏ front và rear, và vì sao thiếu rear thì enqueue thành O(n).22 phút
- 23.2Hàng đợi vòngMảng vòng bằng phép chia dư, phân biệt rỗng với đầy, và ring buffer nhúng.26 phút
- 23.3DequeThêm và lấy ở cả hai đầu, cài bằng danh sách đôi và bằng mảng vòng.20 phút
- 23.4Hàng đợi ưu tiên và heapHeap nhị phân trên mảng, sift up và sift down, và vì sao dựng heap chỉ tốn O(n).30 phút
Chương 24. Tree
Cây nhị phân, bốn kiểu duyệt, cây tìm kiếm nhị phân, AVL.
- 24.1Cây nhị phânThuật ngữ, chiều cao, số nút tối đa, và phân biệt cây đầy với cây cân bằng.22 phút
- 24.2Bốn kiểu duyệt câyTiền, trung, hậu thứ tự và duyệt theo tầng. Vì sao hủy cây bắt buộc hậu thứ tự.28 phút
- 24.3Cây tìm kiếm nhị phânTính chất BST, vì sao trung thứ tự cho dãy đã sắp, và cây suy biến.22 phút
- 24.4Chèn vào BSTBản đệ quy theo mẫu trả về gốc, bản lặp, và cách xử lý khóa trùng.22 phút
- 24.5Tìm trong BSTTìm bằng vòng lặp, tìm nhỏ nhất và lớn nhất, nút kế tiếp và nút liền trước.18 phút
- 24.6Xóa khỏi BSTBa trường hợp, chọn nút thế mạng, và vì sao phải xóa tiếp ở cây con phải.28 phút
- 24.7Cây AVLHệ số cân bằng, bốn kiểu mất cân bằng, và hai phép xoay dựng nên tất cả.32 phút
Chương 25. Hash Table
Hàm băm, va chạm, chaining, open addressing, rehash.
- 25.1Hàm bămBa yêu cầu, djb2 và FNV-1a, và vì sao hàm băm tự nghĩ thường hỏng.24 phút
- 25.2Va chạmNguyên lý chuồng bồ câu, nghịch lý ngày sinh, và hai hướng xử lý.18 phút
- 25.3ChainingMỗi ô là một danh sách. Cài đủ put, get, remove, và quản lý sở hữu khóa.28 phút
- 25.4Open addressingDò tuyến tính, dò bậc hai, băm kép, và bia mộ khi xóa.26 phút
- 25.5Hệ số tải và rehashNgưỡng rehash, chi phí khấu hao, và chọn số bucket.24 phút