UBND THÀNH PHỐ HẢI PHÒNG
TRƯỜNG ĐẠI HỌC HẢI PHÒNG
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Mã số: GT.CN.2023.03
Chủ biên: TS. Đào Thị Hường
Các thành viên: ThS. Nguyễn Văn Quang, ThS. Vũ Thị Sơn, ThS.
Hoàng Văn Lâm
Đơn vị: Khoa Công nghệ thông tin
Hải Phòng, năm 2023
ii
MỤC LỤC
MỤC LỤC .................................................................................................................. ii
DANH MỤC HÌNH VẼ ............................................................................................ v
DANH MỤC BẢNG BIỂU ................................................................................... viii
LỜI NÓI ĐẦU ........................................................................................................... x
Chương 1. TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ........... 1
1.1. TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU .............................................. 1
1.1.1. Dữ liệu và cấu trúc dữ liệu .............................................................. 1
1.1.2. Phân loại các kiểu cấu trúc dữ liệu .................................................. 5
1.1.3. Kiểu dữ liệu và kiểu dữ liệu trừu tượng .......................................... 8
1.1.4. Các ứng dụng của cấu trúc dữ liệu .................................................. 9
1.2. KHÁI QUÁT VỀ ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT 10
1.2.1. Giải thuật và độ phức tạp của thuật toán ....................................... 10
1.2.2. Phân tích thuật toán ....................................................................... 13
1.2.2. Một số quy tắc đánh giá độ phức tạp của thuật toán ..................... 16
1.3. CÂU HỎI VÀ BÀI TẬP CHƯƠNG 1 ................................................... 19
Chương 2. THUẬT TOÁN ĐỆ QUY ..................................................................... 20
2.1. CƠ SỞ LÝ THUYẾT VỀ ĐỆ QUY ..................................................... 20
2.1.1. Thuật toán đệ quy (Recursive Algorithm) .................................... 20
2.1.2. Cơ chế hoạt động của hàm đệ quy ................................................ 22
2.2. VÍ DỤ MINH HOẠ THUẬT TOÁN ĐỆ QUY ..................................... 24
2.2.1. Bài toán con thỏ trên mặt trăng (dãy số Fibonaci) ........................ 24
2.2.2. Bài toán tháp Hà Nội ..................................................................... 25
2.3. CÂU HỎI VÀ BÀI TẬP CHƯƠNG 2 ................................................... 29
Chương 3. MỘT SỐ CẤU TRÚC DỮ LIỆU CƠ BẢN ........................................ 30
3.1. DANH SÁCH ........................................................................................... 30
3.1.1. Khái niệm danh sách ...................................................................... 30
3.1.2. Các phép toán trên danh sách ........................................................ 30
3.2. MẢNG ...................................................................................................... 31
3.2.1. Định nghĩa mảng............................................................................ 31
3.2.2. Các phép toán đối với mảng .......................................................... 34
3.2.3. Đánh giá cấu trúc dữ liệu kiểu mảng ............................................. 37
3.3. DANH SÁCH NỐI ĐƠN ......................................................................... 37
3.3.1. Khái niệm danh sách nối đơn ........................................................ 37
iii
3.3.2. Các phép toán cơ bản với danh sách nối đơn ................................ 39
3.4. DANH SÁCH NỐI KÉP ......................................................................... 48
3.4.1. Giới thiệu danh sách nối kép ......................................................... 48
3.4.2. Các phép toán cơ bản với danh sách nối kép ................................. 50
3.5. NGĂN XẾP (STACK) ............................................................................. 53
3.5.1. Giới thiệu ngăn xếp........................................................................ 53
3.5.2. Các phép toán cơ bản của ngăn xếp ............................................... 54
3.5.3. Cài đặt Stack bằng mảng. .............................................................. 54
3.5.4. Cái đặt Stack bằng danh sách nối đơn ........................................... 59
3.5.5. Ứng dụng của ngăn xếp ................................................................. 62
3.6. HÀNG ĐỢI (QUEUE) ............................................................................. 63
3.6.1. Giới thiệu hàng đợi ........................................................................ 63
3.6.2. Cài đặt Queue bằng mảng .............................................................. 63
3.6.3. Cái đặt Queue bằng danh sách liên kết đơn. .................................. 67
3.6.4. Ứng dụng của Queue. .................................................................... 69
3.7. CÂU HỎI VÀ BÀI TẬP CHƯƠNG 3 ................................................... 71
Chương 4. SẮP XẾP VÀ TÌM KIẾM .................................................................... 74
4.1. SẮP XẾP................................................................................................... 74
4.1.1.Mở đầu về sắp xếp .......................................................................... 74
4.1.2.Một số thuật toán sắp xếp ............................................................... 75
4.2. TÌM KIẾM ............................................................................................... 89
4.2.1. Mở đầu về tìm kiếm .............................................................................. 89
4.2.2. Một số phương pháp tìm kiếm ....................................................... 89
4.3. CÂU HỎI VÀ BÀI TẬP CHƯƠNG 4 ................................................... 94
Chương 5. CÂY (TREE) ......................................................................................... 95
5.1. CÁC KHÁI NIỆM ................................................................................... 95
5.2. CÁC PHÉP TOÁN CƠ BẢN TRÊN CÂY ............................................ 97
5.3. CÁC PHƯƠNG PHÁP CÀI ĐẶT CÂY .............................................. 100
5.4. CÂY NHỊ PHÂN ................................................................................... 102
5.4.1. Tổng quan về cây nhị phân .......................................................... 102
5.4.2. Cây nhị phân tìm kiếm. ................................................................ 110
5.5. CÂY NHỊ PHÂN CÂN BẰNG ( AVL TREE) .................................... 119
5.5.1. Cây nhị phân cân bằng hoàn toàn ................................................ 119
5.5.2. Cây nhị phân cân bằng tổng quát ................................................. 120
iv
5.5.3. Các thao tác cân bằng lại cây ....................................................... 122
5.5.4. Tạo cây nhị phân cân bằng AVL ................................................. 137
5.6. CÂU HỎI VÀ BÀI TẬP CHƯƠNG 5 ................................................. 139
Chương 6. ĐỒ THỊ
(
GRAPH
)
.............................................................................. 141
6.1. ĐỊNH NGHĨA VỀ ĐỒ THỊ ................................................................. 141
6.1.1. Các khái niệm về đồ thị ............................................................... 141
6.1.2. Các khái niệm trên đồ thị vô hướng ............................................ 142
6.1.3. Một số thuật ngữ trên đồ thị có hướng......................................... 142
6.1.4. Một số loại đồ thị đặc biệt ........................................................... 143
6.2. CÁC PHƯƠNG PHÁP BIỂU DIỄN ĐỒ THỊ .................................... 144
6.2.1. Biểu diễn đồ thị bằng ma trận kề ................................................. 144
6.2.3. Biểu diễn đồ thị bằng danh sách cạnh.......................................... 146
6.2.3. Biểu diễn đồ thị bằng danh sách kề ............................................. 147
6.2.4. Biểu diễn đồ thị bằng danh sách kề dựa vào danh sách liên kết .. 148
6.3. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ ............................ 150
6.3.1. Thuật toán tìm kiếm theo chiều sâu (Depth First Search)............ 151
6.3.2. Thuật toán tìm kiếm theo chiều rộng (BFS-Breadth First
Search) ........................................................................................ 155
6.4. ỨNG DỤNG CỦA CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ
THỊ ...................................................................................................... 160
6.5. CÂU HỎI VÀ BÀI TẬP ÔN TẬP CHƯƠNG 6 ................................ 161
TÀI LIỆU THAM KHẢO .................................................................................... 162
TÀI LIỆU THAM KHẢO TIẾNG VIỆT ................................................... 162
TÀI LIỆU THAM KHẢO TIẾNG ANH .................................................... 162
CÁC TRANG WEB ...................................................................................... 162
v
DANH MỤC HÌNH VẼ
Hình 1-1: Minh hoạ các mục dữ liệu ................................................................ 1
Hình 1-2: Phân loại cấu trúc dữ liệu trong máy tính ......................................... 6
Hình 2-1: Minh hoạ khái niệm đệ quy ............................................................ 20
Hình 2-2: Minh hoạ cơ chế tính n! đối với hàm đệ quy .................................. 23
Hình 2-3: Bài toán con thỏ trên mặt trăng ...................................................... 24
Hình 2-4: Bài toán tháp Hà Nội ...................................................................... 26
Hình 2-5: Minh hoạ thực hiện bài toán tháp Hà Nội với số lượng đĩa là 3 .... 28
Hình 3-1: Minh hoạ cấu trúc dữ liệu kiểu mảng một chiều ............................ 32
Hình 3-2: Minh hoạ mảng hai chiều ............................................................... 33
Hình 3-3: Minh hoạ phép toán chèn một phần tử vào trong mảng đã sắp xếp 35
Hình 3-4: Minh hoạ phép toán loại bỏ một phần tử khỏi mảng ...................... 35
Hình 3-5: Minh hoạ thuật toán trộn hai mảng đã có thứ tự ............................ 37
Hình 3-6: Một node của danh sách liên kết .................................................... 38
Hình 3-7: Danh sách liên kết ........................................................................... 38
Hình 3-8: Hình ảnh danh sách liên kết đơn được trỏ bởi con trỏ P ................ 41
Hình 3-9: Minh hoạ chèn nút mới q vào đầu danh sách liên kết .................... 41
Hình 3-10: Hình ảnh con trỏ phụ m tìm tới nút cuối cùng ............................. 42
Hình 3-11: Hình ảnh bổ sung nút mới q vào sau nút cuối cùng ..................... 42
Hình 3-12: Hình ảnh danh sách liên kết có R trỏ vào nút bất kỳ .................... 44
Hình 3-13: Hình ảnh cho con trỏ phụ m tìm tới nút trước nút R .................... 44
Hình 3-14: Hình ảnh bổ sung nút mới q vào trước nút bất kỳ R .................... 44
Hình 3-15: Hình ảnh tìm nút có giá trị trường khóa của info bằng x ............. 47
Hình 3-16: Phần tử trong danh sách nối kép ................................................... 48
Hình 3-17: Hình ảnh danh sách nối kép .......................................................... 49
Hình 3-18: Hình ảnh chèn nút mới q vào sau nút cuối của danh sách nối kép
......................................................................................................................... 51
Hình 3-19: Đẩy một phần tử vào trong ngăn xếp ........................................... 53
Hình 3-20: Lấy một phần tử ra khỏi ngăn xếp ................................................ 53