Giáo trình cấu trúc dữ liệu và lời giải – Đinh bạo dạn Tường

LỜI NÓI ĐẦU

Cuốn sách này trình diễn các vấn đề cơ bản, đặc biệt nhất của kết cấu dữ liệu (CTDL) và thuật toán đã được khuyến nghị trong IEEE/ACM computing curricula, theo cách nhìn hiện đại.

Bạn đang xem: Tài liệu cấu trúc dữ liệu và giải thuật

Khi xây đắp thuật toán để xử lý một vấn đề, chúng ta cần phải sử dụng các đối tượng người sử dụng dữ liệu và những phép toán bên trên các đối tượng dữ liệu ở tại 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à phân tích các kiểu dữ liệu trừu tượng (KDLTT) và các CTDL để thiết lập các KDLTT. KDLTT quan trọng đặc biệt nhất là tập đụng (một tập đối tượng dữ liệu với các phép toán search kiếm, xen, loại, …), KDLTT này được sử dụng rộng thoải mái nhất trong số chương trình ứng dụng. Những KDLTT cơ phiên bản khác vẫn được nghiên cứu là : danh sách, chống xếp, sản phẩm đợi, mặt 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 to gan lớn mật Tường

Phần 1. Các cấu tạo dữ liệu cơ bản 12

Chương 1. Sự trừu tượng hoá tài liệu 13

1.1. Trình diễn dữ liệu trong số ngôn ngữ xây dựng 131.2. Sự trừu tượng hoá tài liệu 17

1.3. Kiểu tài liệu trừu tượng 211.3.1. Đặc tả kiểu tài liệu trừu tượng 211.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 vào C 261.5. Triết lý thiết đặt 30

Chương 2. Kiểu tài 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 342.2. Các hàm nguyên tố 36

2.2.1. Hàm kiến tạo và hàm huỷ 362.2.2. Các tham đổi mới của hàm 382.2.3. Định nghĩa lại những phép toán 41

2.3. Trở nên tân tiến lớp thiết lập kiểu dữ liệu trừu tượng 452.4. Lớp khuôn 55

2.4.1. Lớp côngtơnơ 552.4.2. Hàm khuôn 652.4.3. Lớp khuôn 67

2.5. Các kiểu tài liệu trừu tượng quan trọng 74

Chương 3. Sự vượt kế 77

3.1. Các lớp dẫn xuất 773.2. Hàm ảo và tính nhiều hình 843.3. Lớp các đại lý trừu tượng 88

Chương 4. Danh sách

4.1. Kiểu tài liệu trừu tượng danh sách 984.2. Thiết đặt danh sách vì mảng 1014.3. Cài đặt danh sách vày mảng rượu cồn 1094.4. Setup tập động vì chưng danh sách. Tìm kiếm tuần tự và tìm tìm nhị phân 117

4.4.1. Cài đặt bởi list không được sắp. Kiếm tìm kiếm tuần trường đoản cú 1174.4.2. Setup bởi list được sắp. Tìm kiếm kiếm nhị phân 120

4.5. Ứng dụng 126

Chương 5. Danh sách link 137

5.1. Nhỏ trỏ và cấp phép động bộ nhớ 1375.2. Cấu trúc dữ liệu danh sách liên kết 1415.3. Những dạng danh sách link khác 148

5.3.1. Danh sách links vòng tròn 1485.3.2. Danh sách liên kết có đầu trả 1505.3.3. Danh sách liên kết kép 151

5.4. Cài đặt danh sách vày danh sách links 1545.5. đối chiếu hai cách thức cài đặt list 1625.6. Setup tập động do danh sách link 164

Chương 6. Ngăn xếp 168

6.1. Kiểu dữ liệu trừu tượng chống xếp 1686.2. Thiết lập ngăn xếp vị mảng 1696.3. Thiết đặt ngăn xếp bởi vì danh sách liên kết 1726.4. Biểu thức vết ngoặc tương xứng 1766.5. Đánh giá chỉ biểu thức số học 178

6.5.1. Đánh giá bán biểu thức postfix 1786.5.2. đưa biểu thức infix thành postfix 1806.6. Phòng xếp với đệ quy 183

Chương 7. Hàng chờ 187

7.1. Kiểu tài liệu trừu tượng hàng hóng 1877.2. Thiết lập hàng đợi vì mảng 1887.3. Thiết đặt hàng đợi bởi danh sách liên kết 1947.4. Mô rộp hệ sắp đến hàng 298

Chương 8. Cây 203

8.1. Các khái niệm cơ bản 2048.2. Chú tâm cây 2098.3. Cây nhị phân 2138.4. Cây kiếm tìm kiếm nhị phân 220

8.4.1. Cây tìm kiếm nhị phân 2208.4.2. Các phép toán tập hễ trên cây kiếm tìm kiếm nhị phân 223

8.5. Thiết đặt tập động bởi cây kiếm tìm kiếm nhị phân 2318.6. Thời gian thực hiện các phép toán tập cồn trên cây kiếm tìm kiếm nhị phân 237

Chương 9. Bảng băm 242

9.1. Cách thức băm 2429.2. Những hàm băm 245

9.2.1. Cách thức chia 2459.2.2. Cách thức nhân 2469.2.3. Hàm băm cho các giá trị khoá là xâu ký tự 246

9.3. Các cách thức giải quyết va va 248

9.3.1. Cách thức định showroom mở 2489.3.2. Cách thức tạo dây chuyền sản xuất 253

9.4. Thiết đặt bảng băm showroom mở 2549.5. Thiết lập bảng băm dây chuyền sản xuất 2609.6. Tác dụng của cách thức băm 265

Chương 10. Mặt hàng ưu tiên 269

10.1. Kiểu dữ liệu trừu tượng mặt hàng ưu tiên 26910.2. Các cách thức đơn giản cài đặt hàng ưu tiên 270

10.2.1. Thiết đặt hàng ưu tiên bởi danh sách 27010.2.2. Cài đặt hàng ưu tiên bởi cây kiếm tìm kiếm nhị phân 271

10.3. Cây trang bị tự phần tử 272

10.3.1.Các phép toán sản phẩm ưu tiên bên trên cây máy tự bộ phận 27310.3.2. Xây đắp cây thứ tự phần tử 278

10.4. Cài đặt hàng ưu tiên vì cây máy tự phần tử 28210.5. Nén tài liệu và mã Huffman 287

Phần 2. Các cấu tạo 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. Những phép xoay 29711.2. Cây AVL 298

11.2.1.Các phép toán tập rượu cồn trên cây AVL 30111.2.2.Cài để tập động vì cây AVL 309

11.3. Cây đỏ – black 31511.4. Cấu trúc dữ liệu tự điều chỉnh 32711.5. Phân tích mua trả góp 32811.6. Cây tán loe 330

11.6.1.Các phép toán tập cồn trên cây tán loe 33611.6.2.Phân tích mua trả góp 338

Chương 12. Mặt hàng ưu tiên cùng với phép toán hợp độc nhất vô nhị 341

12.1. Mặt hàng ưu tiên với phép toán hợp độc nhất 34112.2. Những phép toán hợp nhất và sút khoá trên cây trang bị tự thành phần 34212.3. Cây nghiêng 342

12.3.1.Các phép toán mặt hàng ưu tiên trên cây nghiêng 34312.3.2.Phân tích trả dần 348

Chương 13. Họ những tập không giảm nhau 352

13.1. Kiểu dữ liệu trừu tượng họ các tập không cắt nhau 35213.2. Setup đơn giản 35313.3. Setup bởi cây 354

13.3.1.Phép hòa hợp theo trọng số 35713.3.2.Phép search với nén mặt đường 360

13.4. Ứng dụng 362

13.4.1.Vấn đề tương tự 36313.4.2.Tạo ra mê lộ 364

Chương 14. Các kết cấu dữ liệu đa chiều 367

14.1. Các phép toán trên các dữ liệu nhiều chiều 36714.2. Cây k – chiều 368

14.2.1.Cây 2 – chiều 36914.2.2.Cây k – chiều 377

14.3. Cây tứ phân 37814.4. Cây tứ phân MX 382

Phần 3. Thuật toán 388

Chương 15. So với thuật toán 389

15.1. Thuật toán và các vấn đề tương quan 38915.2. Tính công dụng của thuật toán 39115.3. Ký hiệu ô lớn và biểu diễn thời gian chạy vì chưng ký hiệu ô mập 394

15.3.1.Định nghĩa ký hiệu ô lớn 39415.3.2.Biểu diễn thời hạn chạy của thuật toán 395

15.4. Đánh giá thời hạn chạy của thuật toán 398

15.4.1.Luật tổng 39815.4.2.Thời gian chạy của những lệnh 399

15.5. Phân tích các hàm đệ quy 402

Chương 16. Các chiến lược kiến tạo thuật toán 409

16.1. Chia – nhằm – trị 409

16.1.1.Phương pháp thông thường 40916.1.1.Tìm max và min 411

16.2. Thuật toán đệ quy 41316.3. Quy hoạch hễ 418

16.3.1.Phương pháp tầm thường 41816.3.2.Bài toán sắp tới xếp các đồ đồ gia dụng vào balô 41916.3.3.Tìm dãy bé chung của hai dãy số 421

16.4. Quay lui 422

16.4.1.Tìm tìm vét can 42216.4.2.Quay lui 42416.4.3.Kỹ thuật cù lui để giải bài toán tối ưu 430

16.5. Kế hoạch tham nạp năng lượng 432

16.5.1.Phương pháp phổ biến 43216.5.2.Thuật toán tham ăn uống cho câu hỏi người bán sản phẩm 43316.5.3.Thuật toán tham nạp năng lượng cho vấn đề balô 434

16.6. Thuật toán đột nhiên 435

Chương 17. Bố trí 443

17.1. Các thuật toán sắp tới xếp đơn giản dễ dàng 444

17.1.1.Sắp xếp lựa chọn 44417.1.2.Sắp xếp xen vào 44617.1.3.Sắp xếp nổi bọt bong bóng 447

17.2. Thu xếp hoà nhập 44817.3. Bố trí nhanh 45217.4. Sắp xếp sử dụng cây đồ vật tự phần tử 459

Chương 18. Các thuật toán vật dụng thị 464

18.1. Một số khái niệm cơ phiên bản 46418.2. Màn biểu diễn đồ thị 466

18.2.1.Biểu diễn đồ gia dụng thị bởi vì ma trận kề 46618.2.2.Biểu diễn trang bị thị bởi danh sách kề 468

18.3. Đi qua đồ gia dụng thị 469

18.3.1.Đi qua vật dụng thị theo bề rộng 46918.3.2. Đi qu vật thị theo độ sâu 472

18.4. Đồ thị triết lý không có quy trình và thu xếp topo 47718.5. Đường đi ngắn nhất 480

18.5.1.Đường đi ngắn nhất xuất phát điểm từ 1 đỉnh nguồn 48018.5.2. Đường đi ngắn duy nhất giữa các cặp đỉnh 485

18.6. Cây bao phủ ngắn duy nhất 488

18.6.1.Thuật toán Prim 48918.6.2.Thuật toán Kruskal 493

Chương 19. Các bài toán NP – khó khăn và NP – không thiếu thốn 501

19.1. Thuật toán không solo định 50219.2. Những bài toán NP – cạnh tranh và NP – vừa đủ 50619.3. Một trong những bài toán NP – khó 509

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

Hello anh em, mình đã bước đầu gia nhập Amazon dưới vai trò Thực tập sinh nghệ thuật Phát triển ứng dụng trong 6 tháng tính từ lúc tháng 2 năm 2021. Trong nội dung bài viết này, bản thân sẽ chia sẻ tất cả những tài nguyên đặc biệt quan trọng mà mình đã theo học tập về kết cấu dữ liệu và giải thuật (CTDL>) trong thời gian qua.

Đầu tiên thì là những trang web. Những trang mà lại mình follow bao gồm có:

Leet
Code— Trang web rất tốt để thực hành thực tế các câu hỏi CTDL>, giao diện người tiêu dùng tốt, phần trao đổi tuyệt vời.

Geeksfor
Geeks— quá đỉnh cho chúng ta sinh viên kỹ thuật Máy tính, bạn cũng có thể nhận được tất cả các thắc mắc với các chiến thuật khả thi cùng cũng có thể thực hành trên đây.

Techie
Delight— Một website đơn giản giành cho việc học CTDL>.

Một số website khác mà chúng ta có thể tham khảo là Interview
Bit với Educative.io.

*

Từ tởm nghiệm bản thân, tôi khuyên răn bạn không nên quá nhồi nhét quá, chỉ việc tìm hiểu những khái niệm và áp dụng chúng cho các câu hỏi, đồng thời nâng cao kiến thức của công ty về CTDL>. “Bạn càng thực hành nhiều, các bạn càng học được không ít hơn.” nếu bạn không thể làm được thắc mắc nào trong các nguồn tôi hỗ trợ hoặc ở ngẫu nhiên đâu, đừng dễ dàng bỏ cuộc, ít nhất hãy dành 1-2 giờ động não và ngay cả khi bạn không thể giải quyết được thì cũng đừng quá lo lắng. Chúng ta có thể dễ dàng search thấy một số đoạn clip trên Youtube với các giải thích cực dễ nắm bắt và chúng ta có thể tham khảo phần bàn bạc trong Leet
Code hoặc tham khảo Geeksfor
Geeks. Dần dần dần, bạn sẽ hình thành được tư duy với tự mình xử lý được vấn đề.

Để nghiên cứu các chủ đề thiết yếu về Khoa học máy tính như Hệ làm chủ cơ sở dữ liệu (Database Management System-DBMS), Hệ điều hành và Mạng trang bị tính, hãy tham khảoKnowledge GateandGate Smashers,Geeksfor
Geeks.

Về OOP, chúng ta có thể tham khảoSaurabh Shukla’s sir, C++ playlist.

Xem thêm: Full Bộ Tài Liệu Học Bằng Lái Xe Máy A1 Kèm Hướng Dẫn Học Hiệu Quả

Ngoài ra, hãy nhớ là ghi chú lại toàn bộ những điều chúng ta đã học, nó sẽ giúp bạn ôn tập nhanh chóng bất cứ khi nào bạn muốn.