Cuốn sách này sẽ giới thiệu đến bạn các vấn đề cơ bản và quan trọng nhất của Cấu trúc dữ liệu và giải thuật. Đây là những kiến thức được đề xuất theo quan điểm hiện đại trong IEEE/ACM computing curricula.
Contents
Lời giới thiệu
Cuốn sách này sẽ trình bày các khái niệm và phương pháp thiết kế thuật toán cần thiết để giải quyết các vấn đề. Khi thiết kế một thuật toán, chúng ta cần sử dụng các đối tượng dữ liệu và các phép toán trên đối tượng dữ liệu ở mức độ trừu tượng. Cuốn sách này tập trung vào nghiên cứu các kiểu dữ liệu trừu tượng (KDLTT) và các cấu trúc dữ liệu (CTDL) để cài đặt các KDLTT. Trong đó, tập động là một KDLTT quan trọng nhất, được sử dụng rộng rãi trong các chương trình ứng dụng. Bên cạnh đó, cuốn sách cũng giới thiệu các CTDL khác như danh sách, ngăn xếp, hàng đợi, hàng ưu tiên, từ điển, …
Phần 1: Các cấu trúc dữ liệu cơ bản
Chương 1: Sự trừu tượng hóa dữ liệu
Trong chương này, cuốn sách trình bày về việc biểu diễn dữ liệu trong các ngôn ngữ lập trình và sự trừu tượng hóa dữ liệu. Ngoài ra, cuốn sách cũng giới thiệu các kiểu dữ liệu trừu tượng (KDLTT) và cách cài đặt chúng trong ngôn ngữ lập trình C.
Chương 2: Kiểu dữ liệu trừu tượng và các lớp C++
Chương này tập trung vào giới thiệu về lớp và các thành phần của lớp trong ngôn ngữ lập trình C++. Cuốn sách cũng trình bày về các hàm thành phần, phát triển lớp cài đặt kiểu dữ liệu trừu tượng và lớp khuôn.
Chương 3: Sự thừa kế
Chương này giới thiệu về các lớp dẫn xuất, hàm ảo và tính đa hình cũng như lớp cơ sở trừu tượng.
Chương 4: Danh sách
Chương này tập trung vào kiểu dữ liệu trừu tượng danh sách và các phương pháp cài đặt danh sách bằng mảng và danh sách liên kết. Cuốn sách cũng giới thiệu về ứng dụng của danh sách.
Chương 5: Danh sách liên kết
Chương này giới thiệu về con trỏ và cấp phát động bộ nhớ, cấu trúc dữ liệu danh sách liên kết và các dạng danh sách liên kết khác nhau. Cuốn sách cũng trình bày về cách cài đặt danh sách bằng danh sách liên kết.
Chương 6: Ngăn xếp
Chương này giới thiệu về kiểu dữ liệu trừu tượng ngăn xếp và cách cài đặt ngăn xếp bằng mảng và danh sách liên kết. Cuốn sách cũng trình bày về cách đánh giá biểu thức dấu ngoặc cân xứng và đánh giá biểu thức số học.
Chương 7: Hàng đợi
Chương này giới thiệu về kiểu dữ liệu trừu tượng hàng đợi và cách cài đặt hàng đợi bằng mảng và danh sách liên kết. Cuốn sách cũng trình bày về cách mô phỏng hệ sắp hàng.
Chương 8: Cây
Chương này giới thiệu các khái niệm cơ bản về cây, cách duyệt cây và cách cài đặt tập động bằng cây tìm kiếm nhị phân.
Chương 9: Bảng băm
Chương này giới thiệu về phương pháp băm, các hàm băm và các phương pháp giải quyết va chạm. Cuốn sách cũng trình bày về cách cài đặt bảng băm bằng phương pháp địa chỉ mở và phương pháp tạo dây chuyền.
Chương 10: Hàng ưu tiên
Chương này giới thiệu về kiểu dữ liệu trừu tượng hàng ưu tiên và cách cài đặt hàng ưu tiên bằng danh sách và cây tìm kiếm nhị phân. Cuốn sách cũng trình bày về nén dữ liệu và mã Huffman.
Phần 2: Các cấu trúc dữ liệu cao cấp
Chương 11: Các cây tìm kiếm cân bằng
Chương này giới thiệu về các phép quay, cây AVL, cây đỏ-đen, cấu trúc dữ liệu tự điều chỉnh và cây tán loe.
Chương 12: Hàng ưu tiên với phép toán hợp nhất
Chương này giới thiệu về hàng ưu tiên với phép toán hợp nhất, cây nghiêng và chiến lược thiết kế thuật toán.
Chương 13: Họ các tập không cắt nhau
Chương này giới thiệu về kiểu dữ liệu trừu tượng họ các tập không cắt nhau và cách cài đặt chúng bằng danh sách và cây. Cuốn sách cũng giới thiệu ứng dụng của họ các tập không cắt nhau.
Chương 14: Các cấu trúc dữ liệu đa chiều
Chương này giới thiệu về các phép toán trên các dữ liệu đa chiều và các cấu trúc dữ liệu như cây k-chiều và cây tứ phân.
Phần 3: Thuật toán
Chương 15: Phân tích thuật toán
Chương này giới thiệu về thuật toán và các vấn đề liên quan, tính hiệu quả của thuật toán và cách đánh giá thời gian chạy thuật toán.
Chương 16: Các chiến lược thiết kế thuật toán
Chương này giới thiệu về các chiến lược thiết kế thuật toán như chia-để-trị, thuật toán đệ quy, quy hoạch động, quay lui, chiến lược tham ăn và thuật toán ngẫu nhiên.
Chương 17: Sắp xếp
Chương này giới thiệu về các thuật toán sắp xếp đơn giản như sắp xếp lựa chọn, sắp xếp xen vào, sắp xếp nổi bọt cũng như các thuật toán sắp xếp khác.
Chương 18: Các thuật toán đồ thị
Chương này giới thiệu về một số khái niệm cơ bản trong đồ thị, biểu diễn đồ thị và các thuật toán đi qua đồ thị, đường đi ngắn nhất và cây bao trùm ngắn nhất.
Chương 19: Các bài toán NP-khó và NP-đầy đủ
Chương này giới thiệu về thuật toán không đơn định và các bài toán NP-khó và NP-đầy đủ.
Với cuốn sách này, bạn sẽ có kiến thức cơ bản và nâng cao về Cấu trúc dữ liệu và giải thuật. Nó sẽ là một nguồn tài liệu hữu ích cho người học và nghiên cứu trong lĩnh vực này.