BAN CƠ YẾU CHÍNH PHỦ
HỌC VIỆN KỸ THUẬT MẬT MÃ
ThS. NGUYỄN VĂN PHÁC
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Hà Nội, 2025
i
BAN CƠ YẾU CHÍNH PHỦ
HỌC VIỆN KỸ THUẬT MẬT MÃ
ThS. NGUYỄN VĂN PHÁC
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Hà Nội, 2025
ii
MỤC LỤC
LỜI NÓI ĐẦU ................................................................................................. xi
CHƯƠNG 1 ................................................................................................... 2
GIỚI THIỆU CHUNG ...................................................................................... 2
1.1. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật..................................... 2
1.2. Cấu trúc dữ liệu và các vấn đề liên quan ............................................... 3
1.2.1. Việc lựa chọn và nghiên cứu các cấu trúc dữ liệu .......................... 3
1.2.2. Cấu trúc dữ liệu và các phép toán ................................................... 3
1.2.3. Cấu trúc dữ liệu và cấu trúc lưu trữ ................................................ 4
1.2.4. Cấu trúc dữ liệu trong các ngôn ngữ lập trình bậc cao ................... 4
1.3. Ngôn ngữ diễn đạt giải thuật .................................................................. 5
Câu hỏi chương 1 .......................................................................................... 7
CHƯƠNG 2 ................................................................................................... 8
ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY ............................................................. 8
(Recursive algorithm) ........................................................................................ 8
2.1. Khái niệm đệ quy ................................................................................... 8
2.2. Giải thuật đệ quy .................................................................................... 8
2.3. Thiết kế một số giải thuật đệ quy ......................................................... 11
2.3.1. Hàm tính n! ................................................................................... 11
2.3.2. Dãy số FIBONACCI ..................................................................... 12
2.3.3. Bài toán “Tháp Hà Nội” (Tower of Hanoi) .................................. 13
2.4. Hiệu lực của đệ quy .............................................................................. 16
2.5. Đệ quy và quy nạp toán học ................................................................. 19
Bài tập chương 2 ......................................................................................... 21
CHƯƠNG 3 ................................................................................................. 23
MẢNG VÀ DANH SÁCH .............................................................................. 23
3.1. Mảng ..................................................................................................... 23
3.1.1. Định nghĩa mảng ........................................................................... 23
iii
3.1.2. Cấu trúc lưu trữ của mảng ............................................................. 23
3.2. Danh sách ............................................................................................. 24
3.2.1. Định nghĩa danh sách .................................................................... 24
3.2.2. Cài đặt danh sách bằng mảng ........................................................ 25
3.3. Ngăn xếp (Stack) .................................................................................. 25
3.3.1. Định nghĩa ..................................................................................... 25
3.3.2. Cài đặt ngăn xếp bằng mảng ......................................................... 26
3.3.3. Một số ví dụ về ứng dụng của ngăn xếp ....................................... 28
3.3.3.1. Biểu thức dấu ngoặc cân xứng ................................................... 28
3.3.3.2. Định giá biểu thức số học .......................................................... 30
3.3.3.3. Chuyển đổi biểu thức dạng trung tố sang dạng hậu tố ............... 33
3.3.4. Ngăn xếp và việc cài đặt hàm đệ quy ........................................... 36
3.4. Hàng đợi (Queue) ................................................................................. 41
3.4.1. Định nghĩa ..................................................................................... 41
3.4.2. Cài đặt hàng đợi bằng mảng.......................................................... 42
3.5. Danh sách móc nối đơn (singly linked list) ......................................... 44
3.5.1. Nguyên tắc .................................................................................... 44
3.5.2. Một số phép toán ........................................................................... 45
3.5.2.1. Bổ sung một nút mới vào danh sách móc nối đơn ..................... 45
3.5.2.2. Loại bỏ một nút ra khỏi danh sách móc nối đơn........................ 46
3.5.2.3. Ghép hai danh sách móc nối đơn ............................................... 47
3.5.3. Ví dụ áp dụng ................................................................................ 48
3.5.3.1. Biểu diễn đa thức ....................................................................... 48
3.5.3.2. Giải thuật cộng đa thức .............................................................. 49
3.6. Danh sách móc nối vòng (circularly linked list) .................................. 51
3.7. Danh sách móc nối kép (Doubly linked list) ....................................... 52
3.8. Ngăn xếp và hàng đợi móc nối ............................................................ 55
Bài tập chương 3 ......................................................................................... 56
iv
CHƯƠNG 4 ................................................................................................. 60
CÂY ................................................................................................. 60
4.1. Định nghĩa và các khái niệm ................................................................ 60
4.2. Cây nhị phân (Binary tree) ................................................................... 63
4.2.1. Định nghĩa và tính chất ................................................................. 63
4.2.2. Cài đặt cây nhị phân ...................................................................... 65
4.2.2.1. Cài đặt cây nhị phân bằng mảng ................................................ 65
4.2.2.2. Cài đặt cây nhị phân bằng móc nối ............................................ 66
4.2.3. Phép duyệt cây nhị phân (traversing binary tree) ......................... 67
Bài tập chương 4 ......................................................................................... 72
CHƯƠNG 5 ................................................................................................. 75
PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT .................................................. 75
5.1. Phân tích giải thuật ............................................................................... 75
5.1.1. Đặt vấn đề ..................................................................................... 75
5.1.2. Phân tích thời gian thực hiện giải thuật ........................................ 75
5.1.2.1. Độ phức tạp tính toán của giải thuật .......................................... 76
5.1.2.2. Xác định độ phức tạp tính toán .................................................. 77
5.1.2.3. Thời gian chạy của các câu lệnh ................................................ 78
5.2. Các phương pháp thiết kế giải thuật .................................................... 83
5.2.1. Phương pháp chia để trị ................................................................ 84
5.2.2. Phương pháp quy hoạch động ....................................................... 87
5.2.3. Phương pháp quay lui ................................................................... 90
5.3.4. Phương pháp nhánh cận (Branch and Bound) .............................. 96
5.2.5. Phương pháp tham ăn (Greedy strategy) .................................... 101
5.2.6. Phương pháp Top - Down ........................................................... 102
5.2.7. Phương pháp tinh chỉnh từng bước (Stepwise refinement) ........ 104
Câu hỏi và bài tập chương 5 ...................................................................... 112
CHƯƠNG 6 ............................................................................................... 114