MỤC LỤC
CHƢƠNG 1. CÁC KHÁI NIỆM MỞ ĐẦU .............................................................................. 1
1.1. Giải thuật và cấu trúc dữ liệu. ......................................................................................... 1
1.2. Cấu trúc dữ liệu và các vấn đề liên quan. ....................................................................... 1
1.3. Ngôn ngữ diễn đạt giải thuật. .......................................................................................... 2
1.4. Kiểu dữ liệu, cấu trúc dữ liệu, kiểu dữ liệu trừu tƣợng ................................................... 3
CHƢƠNG 2. CÁC KIỂU DỮ LIỆU TRỪU TƢỢNG CƠ BẢN ............................................... 6
2. 1. Ngăn xếp - Stack ............................................................................................................ 6
2.1.1 Khái niệm .................................................................................................................. 6
2.1.2 Các thao tác của ngăn xếp ......................................................................................... 6
2.1.3 Ví dụ về hoạt động của một stack ............................................................................. 7
2.1.4 Cài đặt stack bằng mảng ............................................................................................ 7
2.1.5 Ứng dụng của stack ................................................................................................. 10
2.2. Hàng đợi - Queue .......................................................................................................... 12
2.2.1 Khái niệm ................................................................................................................ 12
2.2.2 Các thao tác cơ bản của một hàng đợi ..................................................................... 13
2.2.3 Cài đặt hàng đợi sử dụng mảng ............................................................................... 13
2.2.4 Ví dụ về hoạt động của hàng đợi với cài đặt bằng mảng vòng tròn ........................ 16
2.2.5 Ứng dụng của hàng đợi ........................................................................................... 16
2.3. Danh sách liên kết – Linked list .................................................................................... 17
2.3.1 Định nghĩa ............................................................................................................... 17
2.3.2 Các thao tác trên danh sách liên kết. ....................................................................... 17
2.3.3 Cài đặt danh sách liên kết sử dụng con trỏ .............................................................. 18
2.3.4 Các kiểu danh sách liên kết khác ............................................................................. 25
2.3.5 Một số ví dụ sƣ̉ dụng cấu trúc danh sách liên kết .................................................... 26
2.3.6. Cài đặt stack và queue bằng con trỏ ....................................................................... 26
2.4. Bài tập áp dụng ............................................................................................................. 26
CHƢƠNG 3. CÂY (TREE). ..................................................................................................... 28
3.1. Định nghĩa ..................................................................................................................... 28
3.1.1. Đồ thị (Graph) ........................................................................................................ 28
3.1.2. Cây (tree) ................................................................................................................ 29
3.3. Cây tìm kiếm nhị phân (Binary Search Tree - BST) .................................................... 31
3.3.1. Định nghĩa .............................................................................................................. 31
3.3.2. Khởi tạo cây rỗng ................................................................................................... 32
3.3.3. Chèn thêm một nút mới vào cây ............................................................................. 32
3.3.4. Xóa bỏ khỏi cây một nút ........................................................................................ 33
3.3.5. Tìm kiếm trên cây ................................................................................................... 34
3.3.6. Duyệt cây ................................................................................................................ 35
3.3.7. Cài đặt cây BST ...................................................................................................... 36
3.4.Cây cân bằng – AVL ..................................................................................................... 39
CHƢƠNG 4. BẢNG BĂM (HASH TABLE) .......................................................................... 54
4. 1. Định nghĩa bảng băm ................................................................................................... 54
4.1.1.Định nghĩa : ............................................................................................................. 54
4.1.2.Kích thƣớc của bảng băm : ...................................................................................... 55
4.1.3. Phân loại : ............................................................................................................... 55
4.1.4.Các phép toán trên bảng băm : ................................................................................ 57
4.2.Hàm băm và các loại hàm băm : .................................................................................... 57
4.2.1.Hàm băm (Hash Function): ..................................................................................... 57
4.2.2.Một số loại hàm băm : ............................................................................................. 58
ii
4.3.Xung đột và cách xử lý xung đột ................................................................................... 61
4.3.1. Định nghĩa : ............................................................................................................ 61
4.3.2.Hệ số tải (Load Factor - ) : .................................................................................... 61
4.3.3.Một số phƣơng pháp xử lý xung đột : ..................................................................... 61
4.3.4. Đánh giá : ............................................................................................................... 71
4.4.4.Kết luận : ..................................................................................................................... 72
4.5. Bài tập áp dụng ............................................................................................................. 72
TÀI LIỆU THAM KHẢO. ....................................................................................................... 75