Cấu trúc dữ liệu và thuật toán - Tập 2 (Phân tích và cài đặt trên C/C++)
Trang chủ   |   Đăng nhập  |  Đăng ký  |  
 
Khoa
Login
Tên truy nhập:
Mật khẩu:
Quên mật khẩu ?
Giỏ hàng 0 SP   |  Sơ đồ site
phone1.png 024.3577.2138 (Giờ hành chính)
phone2.png 0916.18.16.54
phone2.png 0904.251.013 
phone1.png 024. 3577.2145
  
Sách
Cấu trúc dữ liệu và thuật toán - Tập 2 (Phân tích và cài đặt trên C/C++)
Cấu trúc dữ liệu và thuật toán - Tập 2 (Phân tích và cài đặt trên C/C++)
Mã sách: 978-604-80-3254-8
Tác giả: Trần Thông Quế
Nhà xuất bản: Thông tin và Truyền thông
Loại sách:
  - Sách in
Giá Bán: 55.000 VNĐ
Giá bìa: 55.000 VNĐ
Số lượng :
giohang
Hướng dẫn thanh toán
Số trang: 165
Kích thước: 16x24
Trọng lượng: 300 gram
Hình thức bìa: Bìa mềm
Năm xuất bản: 2018
Số lượng trong kho: 197
Số lần xem: 268

Cấu trúc dữ liệu và Thuật toán (Data Structure and Algorithms) là môn học bắt buộc không những với mỗi sinh viên ngành Công nghệ Thông tin mà còn là môn học bắt buộc và môn thi quốc gia đầu vào bắt buộc với các nghiên cứu viên của ngành học đó. Nó là một trong các môn học khó của ngành CNTT, đặc biệt càng khó đối với hầu hết các sinh viên khi phải cài đặt một thuật toán hay một bài toán nào đó thuộc môn học này.

Bất cứ sự thành công nào của một dự án Tin học đều là kết quả của việc kết hợp khéo léo giữa Cấu trúc dữ liệu và Thuật toán. Khẳng định này được chứng tỏ trong một công thức rất ngắn gọn mang tính triết lý đương đại nghề nghiệp:

Big Data + Big Community = Big Result

Việc cài đặt các thuật toán cơ bản hoặc nổi tiếng hoặc khó được thực hiện trên các ngôn ngữ chuyên nghiệp đương đại là C/C++ nhằm giải đáp câu hỏi tồn tại trong đầu những người học là: Thực thi các thuật toán ấy trên máy tính điện tử như thế nào và sẽ cho kết quả ra sao?

MỤC LỤC

Lời nhà xuất bản3

Lời nói đầu5

Chương 1: SẮP XẾP NGOÀI7

1.1. Phương pháp xếp trộn các run7

1.1.1. Một số khái niệm cơ bản về run7

1.1.2. Thuật toán xếp trộn hai run7

1.1.3. Thuật toán trộn tự nhiên12

1.2. Thuật toán sắp xếp trộn đa dường cân bằng19

1.2.1. Mô tả ngắn gọn các bước của BMM bằng ngôn ngữ
tự nhiên20

1.2.2. Mô tả chi tiết thuật toán BMM bằng mã giả......................... 21

1.2.3. Cài đặt24

1.3. Thuật toán trộn đa pha24

1.3.1. Mở đầu24

1.3.2. Mô tả thuật toán PMS bằng ngôn ngữ tự nhiên.................... 24

1.3.3. Ví dụ cách cải tiến của PMS nhờ dùng hệ thức (F).............. 25

Chương 2: PHÉP BĂM VÀ BẢNG BĂM26

2.1. Các khái niệm cơ bản26

2.1.1. Phép băm hay hàm băm26

2.1.2. Bảng băm26

2.1.3. Các chỉ tiêu về một hàm băm tốt27

2.1.4. Đụng độ trong bảng băm là gì?27

2.1.5. Một vài loại hàm băm điển hình28

2.2. Các phương pháp giải quyết đụng độ trong bảng băm............... 32

2.2.1. Tạo bảng băm bằng phương pháp kết nối trực tiếp ............. 33

2.2.2. Tạo bảng băm bằng phương pháp kết nối hợp nhất ............ 42

2.2.3. Tạo bảng băm dùng phương pháp dò tuyến tính ................. 51

2.2.4. Tạo bảng băm dùng phương pháp dò bậc hai ...................... 59

2.2.5. Tạo bảng băm dùng phương pháp băm kép ......................... 63

2.3. So sánh các phương pháp giải quyết đụng độ bằng số bước dò
     và hệ số nạp
l68

Chương 3: CÂY ĐỎ ĐEN69

3.1. Mở đầu69

3.2. Các khái niệm cơ bản về cây đỏ đen69

3.2.1. Định nghĩa69

3.2.2. Các đặc điểm (các luật) của RBT69

3.2.3. Các tính chất của RBT70

3.3. Các thao tác cơ bản trên RBT  72

3.3.1. Phép quay72

3.3.2. Phép chèn74

3.3.3. Phép xóa79

3.4. Cài đặt trên C++86

3.5. Đánh giá hiệu quả của RBT104

Chương 4: CÂY 2-3-4 VÀ B-CÂY106

4.1. Cây 2-3-4106

4.1.1. Mở đầu106

4.1.2. Tổ chức cây 2-3-4106

4.1.3. Các phép biến đổi không làm thay đổi tính chất của
cây 2-3-4108

4.1.4. Mã giả mô tả một số phép cơ bản trên cây 2-3-4 .............. 114

4.1.5. Đánh giá tính hiệu quả của cây 2-3-4121

4.2. Cây đa nhánh tìm kiếm 122

4.2.1. Định nghĩa cây đa nhánh tìm kiếm122

4.2.2. Các tính chất của MST122

4.3. B-Cây124

4.3.1. Nguồn gốc chữ ”B” trong tên gọi B-cây (B-Tree)............. 124

4.3.2. Giới thiệu chung về B-cây124

4.3.3. Định nghĩa B-cây125

4.3.4. Các biến thể (Variants) của B-cây126

4.3.5. Mã mô tả các thao tác trên B-cây126

4.3.6. Cài đặt B-cây trên C++140

4.3.7. Đánh giá hiệu quả của B-cây155

4.3.8. Tính hiệu quả của B-cây với cách đánh giá khác .............. 156

4.3.9. Tệp tin chỉ mục157

4.3.10. Tệp tin chỉ mục trong bộ nhớ158

4.3.11. Đa chỉ mục159

4.3.12. Tệp tin chỉ mục quá lớn đối với bộ nhớ159

4.3.13. Sơ lược về các tiêu chuẩn tìm kiếm phức tạp................... 160

Từ viết tắt161

Tài liệu tham khảo162



Khi chèn các dữ liệu đã có trật tự vào cây tìm kiếm nhị phân (Binary Search Tree-BST) thì các tính chất ưu việt của nó biến mất do tính tự cân bằng (selt-balangsing) của nó bị phá hủy. Để khắc phục nhược điểm này của BST buộc người ta phải nghiên cứu sử dụng một kiểu dữ liệu trừu tượng (ADT) khác. Đó là cây đỏ đen (Red-Black Tree-RBT).

3.2. CÁC KHÁI NIỆM CƠ BẢN VỀ CÂY ĐỎ ĐEN

3.2.1. Định nghĩa

Về thực chất, RBT là cây tìm kiếm nhị phân (BST), song nó được bổ sung thêm các luật dưới đây.

3.2.2. Các đặc điểm (các luật) của RBT

1.  Một nút bất kỳ có màu hoặc đỏ hoặc đen.

2.  Gốc là nút đen. (Tuy nhiên luật này đôi khi bị phớt lờ. Bởi vì nút gốc có thể luôn bị thay đổi từ đỏ sang đen. Nhưng điều ấy cũng chẳng quan trọng gì, bởi vì luật này có hiệu quả rất nhỏ trong việc phân tích cây RBT).

3. Tất cả các lá đều đen. (Còn gọi là các nút NIL (hay nút NULL) và có cùng màu như gốc).

4. Mỗi nút đỏ có 2 nút con đen

5. Mỗi đường đi từ một nút hiện hành đến các hậu duệ của nó đều có cùng một số nút đen. 

Ví dụ về một cây đỏ đen cho ở hình 3.1.

Chiều cao cây = 4

Chiều cao đen của gốc = 3    

Chiều cao đen của nút “X” = 2

Các nút nhỏ dưới cùng là các lá


Họ và tên (*)
Email (*)
Nội dung (*)