CTDL GT1
MỤC LỤC
Phần 1. Các cấu trúc dữ liệu cơ bản 12
Chương 1. Sự trừu tượng hoá dữ liệu 13
1.1. Biểu diễn dữ liệu trong các ngôn ngữ lập trình 13
1.2. Sự trừu tượng hoá dữ liệu 17
1.3. Kiểu dữ liệu trừu tượng 21
1.3.1. Đặc tả kiểu dữ liệu trừu tượng 21
1.3.2. Cài đặt kiểu dữ liệu trừu tượng 23
1.4. Cài đặt kiểu dữ liệu trừu tượng trong C 26
1.5. Triết lý cài đặt 30
Chương 2. Kiểu dữ liệu trừu tượng và các lớp C ++ 34
2.1. Lớp và các thành phần của lớp 34
2.2. Các hàm thành phần 36
2.2.1. Hàm kiến tạo và hàm huỷ 36
2.2.2. Các tham biến của hàm 38
2.2.3. Định nghĩa lại các phép toán 41
2.3. Phát triển lớp cài đặt kiểu dữ liệu trừu tượng 45
2.4. Lớp khuôn 55
2.4.1. Lớp côngtơnơ 55
2.4.2. Hàm khuôn 65
2.4.3. Lớp khuôn 67
2.5. Các kiểu dữ liệu trừu tượng quan trọng 74
Chương 3. Sự thừa kế 77
3.1. Các lớp dẫn xuất 77
3.2. Hàm ảo và tính đa hình 84
3.3. Lớp cơ sở trừu tượng 88
Chương 4. Danh sách 98
4.1. Kiểu dữ liệu trừu tượng danh sách 98
4.2. Cài đặt danh sách bởi mảng 101
4.3. Cài đặt danh sách bởi mảng động 109
4.4. Cài đặt tập động bởi danh sách. Tìm kiếm tuần tự và tìm kiếm nhị phân 117
4.4.1. Cài đặt bởi danh sách không được sắp.
Tìm kiếm tuần tự 117
4.4.2. Cài đặt bởi danh sách được sắp. Tìm kiếm nhị phân 120
4.5. Ứng dụng 126
Chương 5. Danh sách liên kết 137
5.1. Con trỏ và cấp phát động bộ nhớ 137
5.2. Cấu trúc dữ liệu danh sách liên kết 141
5.3. Các dạng danh sách liên kết khác 148
5.3.1. Danh sách liên kết vòng tròn 148
5.3.2. Danh sách liên kết có đầu giả 150
5.3.3. Danh sách liên kết kép 151
5.4. Cài đặt danh sách bởi danh sách liên kết 154
5.5. So sánh hai phương pháp cài đặt danh sách 162
5.6. Cài đặt tập động bởi danh sách liên kết 164
Chương 6. Ngăn xếp 168
6.1. Kiểu dữ liệu trừu tượng ngăn xếp 168
6.2. Cài đặt ngăn xếp bởi mảng 169
6.3. Cài đặt ngăn xếp bởi danh sách liên kết 172
6.4. Biểu thức dấu ngoặc cân xứng 176
6.5. Đánh giá biểu thức số học 178
6.5.1. Đánh giá biểu thức postfix 178
6.5.2. Chuyển biểu thức infix thành postfix 180
6.6. Ngăn xếp và đệ quy 183
Chương 7. Hàng đợi 187
7.1. Kiểu dữ liệu trừu tượng hàng đợi 187
7.2. Cài đặt hàng đợi bởi mảng 188
7.3. Cài đặt hàng đợi bởi danh sách liên kết 194
7.4. Mô phỏng hệ sắp hàng 298
Chương 8. Cây 203
8.1. Các khái niệm cơ bản 204
8.2. Duyệt cây 209
8.3. Cây nhị phân 213
8.4. Cây tìm kiếm nhị phân 220
8.4.1. Cây tìm kiếm nhị phân 220
8.4.2. Các phép toán tập động trên cây tìm kiếm nhị phân 223
8.5. Cài đặt tập động bởi cây tìm kiếm nhị phân 231
8.6. Thời gian thực hiện các phép toán tập động trên cây tìm kiếm nhị phân 237
Chương 9. Bảng băm 242
9.1. Phương pháp băm 242
9.2. Các hàm băm 245
9.2.1. Phương pháp chia 245
9.2.2. Phương pháp nhân 246
9.2.3. Hàm băm cho các giá trị khoá là xâu ký tự 246
9.3. Các phương pháp giải quyết va chạm 248
9.3.1. Phương pháp định địa chỉ mở 248
9.3.2. Phương pháp tạo dây chuyền 253
9.4. Cài đặt bảng băm địa chỉ mở 254
9.5. Cài đặt bảng băm dây chuyền 260
9.6. Hiệu quả của phương pháp băm 265
Chương 10. Hàng ưu tiên 269
10.1. Kiểu dữ liệu trừu tượng hàng ưu tiên 269
10.2. Các phương pháp đơn giản cài đặt hàng ưu tiên 270
10.2.1 . Cài đặt hàng ưu tiên bởi danh sách 270
10.2.2 . Cài đặt hàng ưu tiên bởi cây tìm kiếm nhị phân 271
10.3. Cây thứ tự bộ phận 272
10.3.1.Các phép toán hàng ưu tiên trên cây thứ tự bộ phận 273
10.3.2. Xây dựng cây thứ tự bộ phận 278
10.4. Cài đặt hàng ưu tiên bởi cây thứ tự bộ phận 282
10.5. Nén dữ liệu và mã Huffman 287
Phần 2. Các cấu trúc dữ liệu cao cấp 296
Chương 11. Các cây tìm kiếm cân bằng 297
11.1. Các phép quay 297
11.2. Cây AVL 298
11.2.1.Các phép toán tập động trên cây AVL 301
11.2.2.Cài đặt tập động bởi cây AVL 309
11.3. Cây đỏ - đen 315
11.4. Cấu trúc dữ liệu tự điều chỉnh 327
11.5. Phân tích trả góp 328
11.6. Cây tán loe 330
11.6.1.Các phép toán tập động trên cây tán loe 336
11.6.2.Phân tích trả góp 338
Chương 12. Hàng ưu tiên với phép toán hợp nhất 341
12.1. Hàng ưu tiên với phép toán hợp nhất 341
12.2. Các phép toán hợp nhất và giảm khoá
trên cây thứ tự bộ phận 342
12.3. Cây nghiêng 342
12.3.1.Các phép toán hàng ưu tiên trên cây nghiêng 343
12.3.2.Phân tích trả góp 348
Chương 13. Họ các tập không cắt nhau 352
13.1. Kiểu dữ liệu trừu tượng họ các tập không cắt nhau 352
13.2. Cài đặt đơn giản 353
13.3. Cài đặt bởi cây 354
13.3.1.Phép hợp theo trọng số 357
13.3.2.Phép tìm với nén đường 360
13.4. Ứng dụng 362
13.4.1.Vấn đề tương đương 363
13.4.2.Tạo ra mê lộ 364
Chương 14. Các cấu trúc dữ liệu đa chiều 367
14.1. Các phép toán trên các dữ liệu đa chiều 367
14.2. Cây k - chiều 368
14.2.1.Cây 2 - chiều 369
14.2.2.Cây k - chiều 377
14.3. Cây tứ phân 378
14.4. Cây tứ phân MX 382
Phần 3. Thuật toán 388
Chương 15. Phân tích thuật toán 389
15.1. Thuật toán và các vấn đề liên quan 389
15.2. Tính hiệu quả của thuật toán 391
15.3. Ký hiệu ô lớn và biểu diễn thời gian chạy bởi ký hiệu ô lớn 394
15.3.1.Định nghĩa ký hiệu ô lớn 394
15.3.2.Biểu diễn thời gian chạy của thuật toán 395
15.4. Đánh giá thời gian chạy của thuật toán 398
15.4.1.Luật tổng 398
15.4.2.Thời gian chạy của các lệnh 399
15.5. Phân tích các hàm đệ quy 402
Chương 16. Các chiến lược thiết kế thuật toán 409
16.1. Chia - để - trị 409
16.1.1.Phương pháp chung 409
16.1.1.Tìm max và min 411
16.2. Thuật toán đệ quy 413
16.3. Quy hoạch động 418
16.3.1.Phương pháp chung 418
16.3.2.Bài toán sắp xếp các đồ vật vào balô 419
16.3.3.Tìm dãy con chung của hai dãy số 421
16.4. Quay lui 422
16.4.1.Tìm kiếm vét can 422
16.4.2.Quay lui 424
16.4.3.Kỹ thuật quay lui để giải bài toán tối ưu 430
16.5. Chiến lược tham ăn 432
16.5.1.Phương pháp chung 432
16.5.2.Thuật toán tham ăn cho bài toán người bán hàng 433
16.5.3.Thuật toán tham ăn cho bài toán balô 434
16.6. Thuật toán ngẫu nhiên 435
Chương 17. Sắp xếp 443
17.1. Các thuật toán sắp xếp đơn giản 444
17.1.1.Sắp xếp lựa chọn 444
17.1.2.Sắp xếp xen vào 446
17.1.3.Sắp xếp nổi bọt 447
17.2. Sắp xếp hoà nhập 448
17.3. Sắp xếp nhanh 452
17.4. Sắp xếp sử dụng cây thứ tự bộ phận 459
Chương 18. Các thuật toán đồ thị 464
18.1. Một số khái niệm cơ bản 464
18.2. Biểu diễn đồ thị 466
18.2.1.Biểu diễn đồ thị bởi ma trận kề 466
18.2.2.Biểu diễn đồ thị bởi danh sách kề 468
18.3. Đi qua đồ thị 469
18.3.1.Đi qua đồ thị theo bề rộng 469
18.3.2. Đi qu đồ thị theo độ sâu 472
18.4. Đồ thị định hướng không có chu trình và sắp xếp topo 477
18.5. Đường đi ngắn nhất 480
18.5.1.Đường đi ngắn nhất từ một đỉnh nguồn 480
18.5.2. Đường đi ngắn nhất giữa mọi cặp đỉnh 485
18.6. Cây bao trùm ngắn nhất 488
18.6.1.Thuật toán Prim 489
18.6.2.Thuật toán Kruskal 493
Chương 19. Các bài toán NP – khó và NP - đầy đủ 501
19.1. Thuật toán không đơn định 502
19.2. Các bài toán NP – khó và NP - đầy đủ 506
19.3. Một số bài toán NP – khó 509
Bạn đang đọc truyện trên: Truyen2U.Com