ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
PHẠM ANH PHƯƠNG (CHỦ BIÊN)
NGUYỄN ĐÌNH LẦU, TRẦN VĂN HƯNG, QUÁCH HẢI THỌ
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
ĐÀ NẴNG 12/2022
MỤC LỤC
LỜI MỞ ĐẦU ...................................................................................................................... 5
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ................... 7
1.1. CÁC KHÁI NIỆM ........................................................................................................ 7
1.1.1. Dữ liệu ................................................................................................................ 7
1.1.2. Cấu trúc lưu trữ ................................................................................................... 7
1.1.3. Lựa chọn cấu trúc dữ liệu cho bài toán .............................................................. 7
1.2. GIẢI THUẬT ................................................................................................................ 8
1.2.1. Khái niệm về giải thuật....................................................................................... 8
1.2.2. Các tính chất của giải thuật ................................................................................ 8
1.2.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật ................................................. 9
1.3. NGÔN NGỮ BIỂU DIỄN GIẢI THUẬT .................................................................. 10
1.3.1. Ngôn ngữ tự nhiên ............................................................................................ 10
1.3.2. Giả mã .............................................................................................................. 10
1.3.3. Lưu đồ ............................................................................................................... 11
1.4. PHÂN TÍCH VÀ ĐÁNH GIÁ GIẢI THUẬT ............................................................ 13
1.4.1. Đặt vấn đề ......................................................................................................... 13
1.4.2. Độ phức tạp tính toán của giải thuật ................................................................. 14
1.4.3. Độ phức tạp của một số giải thuật thông dụng ................................................. 15
BÀI TẬP CHƯƠNG 1 ....................................................................................................... 16
CHƯƠNG 2: GIẢI THUẬT ĐỆ QUY .............................................................................. 18
2.1. ĐỊNH NGHĨA ĐỆ QUY ............................................................................................. 18
2.2. CẤU TRÚC CỦA GIẢI THUẬT ĐỆ QUY ............................................................... 19
2.3. PHƯƠNG PHÁP XÂY DỰNG GIẢI THUẬT ĐỆ QUY .......................................... 19
2.4. ƯU VÀ NHƯỢC ĐIỂM CỦA ĐỆ QUY.................................................................... 22
2.4.1. Ưu điểm ............................................................................................................ 22
2.4.2. Nhược điểm ...................................................................................................... 22
2.5. PHÂN LOẠI ĐỆ QUY ............................................................................................... 22
2.5.1. Đơn đệ quy ....................................................................................................... 22
2.5.2. Đa đệ quy .......................................................................................................... 23
2.5.3. Đệ quy chéo ...................................................................................................... 23
2.5.4. Đệ quy chồng .................................................................................................... 24
2.5.5. Đệ quy đuôi ...................................................................................................... 24
2.6. GIẢI THUẬT QUAY LUI ......................................................................................... 25
BÀI TẬP CHƯƠNG 2 ....................................................................................................... 29
CHƯƠNG 3: DANH SÁCH ĐẶC ................................................................................... 31
3.1. KHÁI NIỆM DANH SÁCH ....................................................................................... 31
3.2. CÁC THAO TÁC TRÊN DANH SÁCH ĐẶC .......................................................... 31
3.2.1. Duyệt danh sách ............................................................................................... 31
3.2.2. Chèn một phần tử vào danh sách ...................................................................... 31
3.2.3. Xóa một phần tử ra khỏi danh sách .................................................................. 32
3.2.4. Ưu và nhược điểm khi dùng danh sách đặc...................................................... 32
3.3. CÁC THUẬT TOÁN SẮP XẾP ................................................................................. 34
3.3.1. Sắp xếp nổi bọt (Bubble sort) ........................................................................... 34
3.3.2. Sắp xếp chọn (Selection sort) ........................................................................... 35
3.3.3. Sắp xếp chèn (Insertion Sort) ........................................................................... 37
3.3.4. Sắp xếp nhanh (Quick Sort) ............................................................................. 38
3.3.5.Sắp xếp trộn (Merge Sort) ................................................................................. 42
3.3.6. Sắp xếp vun đống (Heap sort) .......................................................................... 45
3.4. THUẬT TOÁN TÌM KIẾM ....................................................................................... 49
3.4.1. Tìm kiếm tuần tự .............................................................................................. 49
3.4.2. Tìm kiếm nhị phân ............................................................................................ 49
BÀI TẬP CHƯƠNG 3 ....................................................................................................... 50
CHƯƠNG 4: DANH SÁCH LIÊN KẾT ........................................................................... 56
4.1. GIỚI THIỆU ............................................................................................................... 56
4.2. DANH SÁCH LIÊN KẾT ĐƠN ................................................................................. 57
4.2.1. Định nghĩa và khai báo ..................................................................................... 57
4.2.2. Các thao tác trên danh sách liên kết đơn .......................................................... 58
4.2.3. Danh sách liên kết đơn nối vòng ...................................................................... 68
4.3. DANH SÁCH LIÊN KẾT KÉP .................................................................................. 74
4.3.1. Định nghĩa ........................................................................................................ 74
4.3.2. Các thao tác trên danh sách liên kết kép .......................................................... 75
BÀI TẬP CHƯƠNG 4 ....................................................................................................... 79
CHƯƠNG 5: DANH SÁCH HẠN CHẾ ........................................................................... 84
5.1. ĐẶT VẤN ĐỀ ............................................................................................................ 84
5.2. NGĂN XẾP ................................................................................................................ 84
5.2.1. Định nghĩa ngăn xếp ......................................................................................... 84
5.2.2. Các thao tác trên ngăn xếp................................................................................ 85
5.2.3. Cài đặt ngăn xếp ............................................................................................... 85
5.2.4. Ứng dụng của ngăn xếp .................................................................................... 88
5.3. HÀNG ĐỢI ................................................................................................................. 93
5.3.1. Định nghĩa ........................................................................................................ 93
5.3.2. Các phép toán trên hàng đợi ............................................................................. 93
5.3.3. Cài đặt hàng đợi ................................................................................................ 93
5.3.4. Ứng dụng của hàng đợi .................................................................................... 98
BÀI TẬP CHƯƠNG 5 ....................................................................................................... 98
CHƯƠNG 6: ĐỒ THỊ ...................................................................................................... 100
6.1. CÁC KHÁI NIỆM CƠ BẢN .................................................................................... 100
6.1.1. Các định nghĩa ................................................................................................ 100
6.1.2. Một số dạng đồ thị đặc biệt ............................................................................ 102
6.1.3. Đường đi, chu trình và đồ thị liên thông ........................................................ 103
6.2. BIỂU DIỄN ĐỒ THỊ ................................................................................................ 104
6.2.1. Ma trận kề, ma trận trọng số ........................................................................... 104
6.2.2. Danh sách kề ................................................................................................... 106
6.3. CÁC PHƯƠNG PHÁP DUYỆT ĐỒ THỊ ................................................................ 107
6.3.1. Duyệt theo chiều sâu ...................................................................................... 107
6.3.2. Duyệt theo chiều rộng .................................................................................... 108
6.3.3. Tìm đường đi và kiểm tra tính liên thông của đồ thị ...................................... 110
6.4. MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ ....................................................... 111
6.4.1. Bài toán tìm đường đi ngắn nhất .................................................................... 111
6.4.2. Bài toán tìm cây khung nhỏ nhất .................................................................... 116
BÀI TẬP CHƯƠNG 6 ..................................................................................................... 121
CHƯƠNG 7: CÂY ........................................................................................................... 123
7.1. GIỚI THIỆU ............................................................................................................. 123
7.2. ĐỊNH NGHĨA VÀ MỘT SỐ KHÁI NIỆM.............................................................. 124
7.2.1. Định nghĩa ...................................................................................................... 124
7.2.2. Các khái niệm ................................................................................................. 125
7.3. CÂY NHỊ PHÂN ...................................................................................................... 126
7.3.1. Định nghĩa ...................................................................................................... 126
7.3.2. Các khái niệm bổ sung ................................................................................... 126
7.3.3. Tổ chức lưu trữ cây nhị phân.......................................................................... 128
7.3.4. Các phép duyệt trên cây nhị phân .................................................................. 130
7.4. CÂY BIỂU THỨC .................................................................................................... 132
7.5. CÂY TÌM KIẾM NHỊ PHÂN .................................................................................. 136
7.5.1. Định nghĩa ...................................................................................................... 136
7.5.2. Các thao tác trên cây BST .............................................................................. 136
7.6. CÂY TÌM KIẾM NHỊ PHÂN CÂN BẰNG ............................................................. 140
7.6.1. Định nghĩa ...................................................................................................... 140
7.6.2. Thuật toán cân bằng đơn giản ........................................................................ 141
7.6.3. Các phép xoay để cân bằng cây BST ............................................................. 143
7.7. CÂY AVL ................................................................................................................. 146
7.7.1. Chèn một nút mới vào cây AVL .................................................................... 147
7.7.2. Xóa một nút khỏi cây AVL ............................................................................ 147
BÀI TẬP CHƯƠNG 7 ..................................................................................................... 148
CHƯƠNG 8: BẢNG BĂM .............................................................................................. 152
8.1. GIỚI THIỆU ............................................................................................................. 152
8.2. HÀM BĂM ............................................................................................................... 152
8.2.1. Hàm băm chia ................................................................................................. 154
8.2.2. Hàm băm xếp .................................................................................................. 155
8.2.3. Các hàm băm khác .......................................................................................... 156
8.3. XỬ LÝ VA CHẠM .................................................................................................. 156
8.3.1. Xử lý va chạm bằng địa chỉ mở ...................................................................... 157
8.3.2. Các yếu tố ảnh hưởng đến hiệu suất tìm kiếm ............................................... 157
8.3.3. Xử lý va chạm bằng Phương pháp chuỗi ....................................................... 158
8.4. XÓA PHẦN TỬ TRONG BẢNG BĂM .................................................................. 158
BÀI TẬP CHƯƠNG 8 ..................................................................................................... 159
PHỤ LỤC A: CÀI ĐẶT CÁC THAO TÁC TRÊN DANH SÁCH LIÊN KẾT ............. 162
A1. DANH SÁCH LIÊN KẾT ĐƠN ............................................................................... 162
A2. DANH SÁCH LIÊN KẾT ĐƠN NỐI VÒNG .......................................................... 166
A3. DANH SÁCH LIÊN KẾT KÉP ................................................................................ 170
PHỤ LỤC B: CÀI ĐẶT STACK .................................................................................... 175
B1. CÀI ĐẶT STACK BẰNG DANH SÁCH LIÊN KẾT ............................................. 175
B2. TÍNH GIÁ TRỊ BIỂU THỨC SỐ HỌC .................................................................... 177
PHỤ LỤC C. CÀI ĐẶT HÀNG ĐỢI .............................................................................. 182
C1. CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG .................................................................... 182
C2. CÀI ĐẶT HÀNG ĐỢI BẰNG DANH SÁCH LIÊN KẾT ĐƠN ............................. 184
C3. CÀI ĐẶT HÀNG ĐỢI BẰNG DANH SÁCH LIÊN KẾT KÉP .............................. 186
TÀI LIỆU THAM KHẢO ............................................................................................... 189
Giáo trình Cấu trúc dữ liệu và giải thuật
5
LỜI MỞ ĐẦU
Theo khung chương trình đào tạo ngành Công nghệ Thông tin ở các hệ Đại học và Cao
đẳng, Cấu trúc dữ liệu và giải thuật là khối kiến thức cơ sở ngành, hỗ trợ nâng cao kỹ năng
lập trình cho người học.
Giáo trình này trang bị cho bạn đọc các nguyên lý thiết kế các cấu trúc dữ liệu cơ bản
cùng với các phép toán (thao tác) trên các cấu trúc dữ liệu đó: danh sách đặc (các thuật toán
tìm kiếm, sắp xếp,…); danh sách liên kết (với các thao tác: khởi tạo, bổ sung, xóa, duyệt,…);
danh sách hạn chế: ngăn xếp, hàng đợi (với các thao tác: khởi tạo, push, pop,...); đồ thị (các
phép duyệt đồ thị, các thuật toán tối ưu trên đồ thị); cây nhị phân, cây tìm kiếm nhị phân (với
các thao tác: khởi tạo, duyệt, bổ sung, xóa nút…); bảng băm.
Nội dung của giáo trình này được chia thành 8 chương, đầu mỗi chương đều có tóm tắt
chương để bạn đọc nắm khái quát về nội dung chương, sau đó là nội dung chương được trình
bày ngắn gọn từ các kiến thức cơ bản về cách xây dựng cấu trúc dữ liệu đến xây dựng giải thuật
và cài đặt mã lệnh. Cuối mỗi chương đều có hệ thống bài tập thực hành từ dễ đến khó, đối với
các bài tập khó đều có gợi ý về cách giải. Các mã nguồn trong giáo trình được viết theo phong
cách hướng đối tượng, tương thích với trình biên dịch Dev C++ 5.X, đây cũng là một trong
những công cụ hỗ trợ lập trình gọn nhẹ, biên dịch được trên cả hai hệ điều hành Windows lẫn
Linux và được sử dụng khá phổ biến trong việc học tập và giảng dạy tại các trường học cũng
như trong các kỳ thi Olympic Tin học sinh viên và ACM/ICPC Quốc tế.
Chúng tôi đã cố gắng đúc kết để biên soạn cuốn sách Giáo trình Cấu trúc dữ liệu và
giải thuật một cách cô đọng, súc tích nhằm đáp ứng nhu cầu học tập và nghiên cứu của học
sinh, sinh viên và những bạn đọc quan tâm đến lĩnh vực lập trình, giúp bạn đọc có một tài liệu
tham khảo tốt khi tìm hiểu sâu về lĩnh vực lập trình.
Chân thành cảm ơn các đồng nghiệp ở các trường Đại học Sư phạm - Đại học Đà Nẵng,
Đại học Bách Khoa - Đại học Đà Nẵng, Đại học Công nghệ Thông tin và Truyền thông Việt-
Hàn, Đại học Duy Tân, Đại học Khoa học - Đại học Huế đã giúp đỡ, đóng góp nhiều ý kiến
quý báu để chúng tôi hoàn thiện nội dung giáo trình này.
Nhóm tác giả cũng hy vọng sớm nhận được các ý kiến đóng góp, phê bình của bạn đọc
về nội dung, chất lượng và hình thức trình bày để giáo trình ngày một hoàn thiện hơn.