Các khái niệm cơ BẢN

1.1. Khái niệm về cấu trúc dữ liệu. 1
1.2. Các kiểu dữ liệu 1
1.1.1 Kiểu nguyên 2
1.1.2 Kiểu số thực (kiểu số dấu phẩy động) 2
1.1.3 Kiểu ký tự. 3
1.1.4 Các kiểu dữ liệu có cấu trúc. 3
Khái niệm 5
Khai báo 5
Khai báo theo mảng 5
Vừa khai báo vừa gán giá trị 6
Các thao tác trên chuỗi ký tự. 6
Nhập chuỗi từ bàn phím 6
Xuất chuỗi lên màn hình 6
*Biến con trỏ 7
Khai báo biến con trỏ 7
Cách truy xuất 8
Ví dụ 8
* Cấp phát và thu hồi vùng nhớ 9
a. Cấp phát: 9
Sử dụng 9
b. Thu hồi và kiểm tra vùng nhớ còn lại 10
*Truyền địa chỉ sang hàm 10
1.3 Thuật toán và đánh giá độ phức tạp của thuật toán 11
1.3.1. Thuật toán. 11
1.3.2. Đánh giá độ phức tạp của giải thuật. 13
1.4. Đệ quy 16
1.4.1. Khái niệm đệ quy 16
1.4.2. Đệ quy và lặp 17
Chương 2: DANH SÁCH 20
2.1. Khái niệm danh sách. 20
2.2. Danh sách đặc. 20
2.2.1. Định nghĩa. 20
2.2.2. Tổ chức cấu trúc dữ liệu. 20
2.2.3. Các phép toán trên danh sách: 20
2.2.4. Ưu nhược điểm và ứng dụng. 21
2.3. Danh sách hạn chế. 21
2.3.1. Ngăn xếp (Stack). 21
2.3.2. Hàng đợi (Queue) 28
2.4. Danh sách liên kết 33
2.4.1. Định nghĩa. 33
2.4.2. Danh sách liên kết đơn. 33
Chương 3: CÂY (TREE) 44
3.1. Các khái niệm cơ bản. 44
3.1.1. Cây. 44
3.1.2. Bậc của nút và bậc của cây (Degree) 44
3.1.3. Nút lá (leaf nodes) và nút nhánh (Branch nodes). 44
3.1.4. Mức của một nút (depth) và Độ cao (height) của cây 44
3.1.5. Nút cha và nút con. 44
3.1.6. Cây có thứ tự. 44
3.2. Cây nhị phân tìm kiếm. 44
3.2.1. Định nghĩa, tính chất. 45
3.2.2 Biểu diễn cây nhị phân. 45
3.2.3. Các phép duyệt cây. 47
CHƯƠNG 4: SẮP XẾP VÀ TÌM KIẾM 60
4.1. Đặt vấn đề. 60
4.2. Sắp xếp. 60
4.2.1. Các phương pháp sắp xếp cơ bản. 60
4.2.3. Sắp xếp theo phương pháp Nổi bọt (Buble Sort). 64
4.2.2.Các phương pháp sắp xếp nâng cao. 68
a.Ý tưởng: 70
b. Ðịnh nghĩa Heap: 72
c. Các tính chất của Heap: 72
d. Giải thuật Heapsort : 72
Cài đặt: 74
Ðánh giá giải thuật 76
4.3.3. Sắp xếp theo phương pháp Hoà nhập (Merge Sort). 76
4.3. Tìm Kiếm. 78
4.3.1. Tìm kiếm tuần tự. 78
4.3.2. Tìm kiếm nhị phân. 80
TÀI LIỆU THAM KHẢO 81

Hình 1.1 Sơ đồ mô tả các kiểu dữ liệu cơ bản 1
Hình 3.2 Cấu trúc của một cây 44
Hình 3.3 Cây nhị phân tìm kiếm 45
Hình 3.4 Các biểu diễn cây nhị phân tìm kiếm 46
Hình 3.5 Mô tả cây nhị phân tìm kiếm lưu trữ 47
Hình 3.6 Sơ đồ cây nhị phân tìm kiếm móc nối 47
Hình 3.7 Mô phỏng xóa 1 nút lá 53
Hình 3.8 Mô phỏng xóa 1 nút có chứa cây con bên trái hoặc bên phải 53
Hình 3.9 Mô phỏng xóa 1 nút có chứa cây con bên trái và bên phải 54
Hình 3.10 Mô phỏng xóa 1 nút cực trái của cây con bên phải 54
Hình 3.11 Mô phỏng xóa 1 nút cực trái của cây con bên phải 54
Hình 3.12 Mô phỏng xóa 1 nút cực trái của cây con bên phải 55
Hình 4.13 Mô phỏng các bước sắp xếp bằng phương pháp lựa chọn trực tiếp 61
Hình 4.14 Mô phỏng các bước sắp xếp bằng phương pháp chèn 63
Hình 4.15 Mô phỏng các bước sắp xếp bằng phương pháp nổi bọt 67