Giáo trình Cấu trúc dữ liệu và giải thuật – Đinh Mạnh Tường – Tài liệu VNU

Giáo trình Cấu trúc dữ liệu và giải thuật – Đinh Mạnh Tường

LỜI NÓI ĐẦU

Cuốn sách này trình diễn những yếu tố cơ bản, quan trọng nhất của Cấu trúc dữ liệu ( CTDL ) và thuật toán đã được đề xuất kiến nghị trong IEEE / ACM computing curricula, theo quan điểm tân tiến .
Khi phong cách thiết kế thuật toán để xử lý một yếu tố, tất cả chúng ta cần phải sử dụng những đối tượng người dùng dữ liệu và những phép toán trên những đối tượng người tiêu dùng dữ liệu ở mức độ trừu tượng. Một trong những nội dung chính của sách này là nghiên cứu và điều tra những kiểu dữ liệu trừu tượng ( KDLTT ) và những CTDL để setup những KDLTT. KDLTT quan trọng nhất là tập động ( một tập đối tượng người dùng dữ liệu với những phép toán tìm kiếm, xen, loại, … ), KDLTT này được sử dụng thoáng rộng nhất trong những chương trình ứng dụng. Các KDLTT cơ bản khác sẽ được nghiên cứu và điều tra là : list, ngăn xếp, hàng đợi, hàng ưu tiên, từ điển, …
Giáo trình Cấu trúc dữ liệu và giải thuật – Đinh Mạnh Tường

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

Bạn đang đọc: Giáo trình Cấu trúc dữ liệu và giải thuật – Đinh Mạnh Tường – Tài liệu VNU

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

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

Xem thêm: 5 dấu hiệu thai phát triển tốt và 10 dấu hiệu thai yếu bạn cần biết

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

TẢI TÀI LIỆU XUỐNG

Xem thêm: 7 phương pháp dạy học tiếng việt theo hướng phát triển năng lực hiệu quả – https://thomaygiat.com

4/5 – ( 3 bầu chọn )

Source: https://thomaygiat.com
Category : Kỹ Thuật Số