Cấu Trúc Dữ Liệu và Thuật Toán trong C++ - Phiên Bản Thứ Tư

Tài liệu nghiên cứu Data structures and algorithms in c by drozdek adam, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về .

• Trường học: Trường Đại Học Công Nghệ Thông Tin
• Chuyên ngành: Cấu Trúc Dữ Liệu và Thuật Toán
• Đề tài: Cấu Trúc Dữ Liệu và Thuật Toán trong C++ - Phiên Bản Thứ Tư
• Loại tài liệu: sách
• Năm xuất bản: 2023
• Địa điểm: Hồ Chí Minh

Tóm tắt

I. Khám phá sách Cấu Trúc Dữ Liệu và Thuật Toán C 4th Ed

Cuốn sách “Cấu Trúc Dữ Liệu và Thuật Toán trong C++ - Phiên Bản Thứ Tư” của tác giả Adam Drozdek là một tài liệu học thuật nền tảng, được công nhận rộng rãi trong cộng đồng khoa học máy tính. Đây không chỉ là một giáo trình cấu trúc dữ liệu thông thường, mà còn là một cẩm nang toàn diện, kết nối sâu sắc giữa lý thuyết trừu tượng và ứng dụng thực tiễn thông qua lập trình C++. Phiên bản thứ tư này tiếp tục khẳng định vị thế của mình như một tài liệu học C++ không thể thiếu cho sinh viên và các lập trình viên chuyên nghiệp. Tác giả nhấn mạnh ba khía cạnh cốt lõi: mối liên hệ mật thiết giữa cấu trúc dữ liệu và thuật toán, việc phân tích độ phức tạp của chúng, và cách trình bày chúng trong môi trường hướng đối tượng. Cuốn sách được thiết kế để đáp ứng các yêu cầu của chương trình giảng dạy Khoa học Máy tính 2008, bao gồm các chủ đề quan trọng như Đồ thị và Cây, Đệ quy, Lập trình hướng đối tượng, và Phân tích thuật toán cơ bản. Mỗi chương đều được minh họa bằng các ví dụ code C++ rõ ràng và các nghiên cứu tình huống (case study) thực tế, từ trình thông dịch, tính toán biểu tượng đến xử lý tệp. Điều này giúp người đọc không chỉ hiểu 'cái gì' mà còn hiểu 'tại sao' và 'như thế nào' khi áp dụng từng cấu trúc dữ liệu. Đây là nguồn tài liệu vô giá để giải bài tập cấu trúc dữ liệu C++ và xây dựng một nền tảng vững chắc cho sự nghiệp phát triển phần mềm.

1.1. Về tác giả Adam Drozdek và uy tín của cuốn sách

Tác giả Adam Drozdek là một học giả có uy tín, và cuốn sách của ông đã trở thành một trong những tài liệu tham khảo hàng đầu trong ngành. Sự thành công của cuốn sách C++ cho sinh viên này đến từ cách tiếp cận cân bằng, không quá nặng về lý thuyết toán học nhưng cũng không hời hợt trong việc giải thích các nguyên tắc cơ bản. Lời nói đầu của cuốn sách chỉ rõ: “Việc nghiên cứu cấu trúc dữ liệu, một thành phần cơ bản của giáo dục khoa học máy tính, đóng vai trò là nền tảng cho nhiều lĩnh vực khoa học máy tính khác”. Điều này cho thấy tầm nhìn của tác giả về vai trò trung tâm của môn học. Phiên bản thứ tư được cập nhật với các chủ đề mới như treaps, k-d trees, và generational garbage collection, phản ánh sự phát triển của lĩnh vực và giữ cho nội dung luôn phù hợp với thực tiễn hiện đại.

1.2. Tầm quan trọng của Cấu trúc dữ liệu và giải thuật C

Hiểu biết về cấu trúc dữ liệu và giải thuật C++ là kỹ năng bắt buộc đối với bất kỳ ai muốn làm việc trong lĩnh vực thiết kế, triển khai, kiểm thử hoặc bảo trì hệ thống phần mềm. Các cấu trúc như danh sách liên kết (linked list), ngăn xếp và hàng đợi (stack and queue), hay cây nhị phân (binary tree) là những viên gạch xây dựng nên các ứng dụng phức tạp. Việc lựa chọn đúng cấu trúc dữ liệu có thể ảnh hưởng đáng kể đến hiệu suất của chương trình. Cuốn sách của Drozdek không chỉ giới thiệu các cấu trúc này mà còn tập trung vào việc phân tích hiệu quả của chúng, giúp người đọc đưa ra quyết định tối ưu khi lập trình. Đây là kiến thức cốt lõi giúp phân biệt giữa một lập trình viên và một kỹ sư phần mềm thực thụ.

1.3. Những cập nhật trong phiên bản thứ tư của giáo trình

Phiên bản thứ tư (Fourth Edition) mở rộng đáng kể so với các phiên bản trước đó bằng cách bổ sung các chủ đề mới đang được quan tâm. Theo lời giới thiệu, các phần bổ sung chính bao gồm: một phần về treaps (6.10) và k-d trees (6.11), một phần về k-d B-trees (7.5), thảo luận về hai phương pháp sắp xếp bổ sung (9.6), một kỹ thuật băm mới (10.1), và một phần về thu gom rác thế hệ (generational garbage collection) (12.4). Những cập nhật này đảm bảo rằng cuốn giáo trình cấu trúc dữ liệu này luôn bắt kịp với những tiến bộ mới nhất, cung cấp cho sinh viên và các chuyên gia những công cụ và kiến thức cần thiết để giải quyết các vấn đề tính toán hiện đại.

II. Thách thức khi học Cấu Trúc Dữ Liệu và Giải Thuật với C

Việc học cấu trúc dữ liệu và giải thuật C++ đặt ra nhiều thách thức không nhỏ. Một trong những khó khăn lớn nhất là việc nắm bắt các khái niệm trừu tượng và mối liên hệ của chúng với mã nguồn cụ thể. Các khái niệm như độ phức tạp thuật toán và ký hiệu Big O notation đòi hỏi một tư duy logic và toán học nhất định, thường gây khó khăn cho người mới bắt đầu. Thêm vào đó, C++ là một ngôn ngữ mạnh mẽ nhưng cũng phức tạp, đặc biệt là trong việc quản lý bộ nhớ thủ công thông qua con trỏ. Việc không xử lý con trỏ đúng cách có thể dẫn đến các lỗi nghiêm trọng như rò rỉ bộ nhớ (memory leak) hoặc tham chiếu lơ lửng (dangling reference). Cuốn sách của Adam Drozdek nhận thức rõ những thách thức này. Thay vì chỉ trình bày lý thuyết suông, sách cung cấp các đoạn code ví dụ C++ chi tiết và giải thích cặn kẽ cách chúng hoạt động. Ví dụ, chương 1 đi sâu vào Lập trình Hướng đối tượng, con trỏ, cấp phát bộ nhớ động và các vấn đề liên quan như hàm tạo sao chép (copy constructor) và hàm hủy (destructor), đặt nền móng vững chắc trước khi đi vào các cấu trúc dữ liệu phức tạp hơn.

2.1. Phân tích độ phức tạp thuật toán và ký hiệu Big O

Một trong những rào cản chính là hiểu và áp dụng phân tích độ phức tạp. Chương 2 của sách, “Complexity Analysis”, được dành riêng để giải quyết vấn đề này. Nó định nghĩa rõ ràng về độ phức tạp tính toán và độ phức tạp tiệm cận (asymptotic complexity). Sách giải thích cặn kẽ các thuộc tính của ký hiệu Big O notation và cung cấp nhiều ví dụ về cách tìm độ phức tạp tiệm cận cho các đoạn mã khác nhau. Quan trọng hơn, sách phân biệt rõ ràng giữa các trường hợp tốt nhất, trung bình và xấu nhất (best, average, and worst cases), một khía cạnh thường bị bỏ qua nhưng lại cực kỳ quan trọng trong thực tế. Việc nắm vững kiến thức này giúp lập trình viên đánh giá và so sánh các thuật toán tìm kiếm và thuật toán sắp xếp khác nhau để chọn ra giải pháp hiệu quả nhất.

2.2. Khó khăn trong việc quản lý con trỏ và bộ nhớ C

C++ cho phép lập trình viên kiểm soát trực tiếp bộ nhớ, nhưng đây cũng là con dao hai lưỡi. Sách nhấn mạnh các vấn đề tiềm ẩn khi làm việc với con trỏ. Phần “Pointers and Copy Constructors” (1.2) và “Pointers and Destructors” (1.3) chỉ ra rằng việc sao chép đối tượng mặc định của trình biên dịch có thể gây ra lỗi khi các thành viên dữ liệu là con trỏ. Sách giải thích: “Nếu thiếu hàm tạo sao chép do người dùng định nghĩa, trình biên dịch sẽ tự động tạo ra một hàm thực hiện sao chép theo từng thành viên”. Điều này dẫn đến việc hai con trỏ cùng trỏ đến một vùng nhớ, gây ra các hiệu ứng phụ không mong muốn. Sách cung cấp giải pháp bằng cách hướng dẫn cách viết hàm tạo sao chép và toán tử gán đúng cách, một kỹ năng thiết yếu trong lập trình C++.

III. Hướng dẫn các Cấu Trúc Dữ Liệu và Thuật Toán C nền tảng

Cuốn sách của Adam Drozdek xây dựng kiến thức một cách có hệ thống, bắt đầu từ những cấu trúc dữ liệu tuyến tính cơ bản nhất. Đây là phương pháp sư phạm hiệu quả, giúp người đọc xây dựng nền tảng vững chắc trước khi tiếp cận các chủ đề phức tạp hơn. Các chương đầu tiên tập trung vào những khái niệm cốt lõi trong cấu trúc dữ liệu và giải thuật C++, bao gồm danh sách liên kết, ngăn xếp và hàng đợi. Mỗi cấu trúc dữ liệu không chỉ được định nghĩa về mặt lý thuyết mà còn được trình bày chi tiết về cách cài đặt bằng lập trình C++, sử dụng con trỏ và lập trình hướng đối tượng. Cuốn sách cũng giới thiệu cách Thư viện Mẫu Chuẩn (STL) của C++ cung cấp các triển khai sẵn có cho những cấu trúc này, giúp người học kết nối kiến thức học thuật với các công cụ lập trình hiện đại. Ví dụ, Chương 3 về danh sách liên kết (linked list) không chỉ dừng lại ở danh sách liên kết đơn và đôi mà còn khám phá các biến thể như danh sách tự tổ chức (self-organizing lists). Tương tự, Chương 4 trình bày chi tiết về ngăn xếp và hàng đợi (stack and queue) cùng các ứng dụng thực tế của chúng, chẳng hạn như bài toán tìm đường thoát khỏi mê cung (exiting a maze).

3.1. Làm chủ danh sách liên kết linked list trong C

Chương 3 đi sâu vào danh sách liên kết (linked list), một cấu trúc dữ liệu động cơ bản. Sách trình bày chi tiết về danh sách liên kết đơn (Singly Linked Lists) và danh sách liên kết đôi (Doubly Linked Lists). Mỗi loại đều được phân tích ưu nhược điểm và đi kèm với code ví dụ C++ cho các thao tác cơ bản như thêm, xóa, tìm kiếm phần tử. Một điểm nổi bật là phần thảo luận về danh sách tự tổ chức (self-organizing lists), một kỹ thuật tối ưu hóa giúp di chuyển các phần tử được truy cập thường xuyên lên đầu danh sách để giảm thời gian tìm kiếm trung bình. Sách cũng giới thiệu về std::list trong STL, cho thấy cách thư viện chuẩn cung cấp một giải pháp mạnh mẽ và đã được kiểm thử cho việc quản lý danh sách liên kết.

3.2. Tìm hiểu ngăn xếp và hàng đợi stack and queue

Chương 4 tập trung vào ngăn xếp và hàng đợi (stack and queue), hai cấu trúc dữ liệu trừu tượng với các quy tắc truy cập đặc biệt (LIFO và FIFO). Sách giải thích cách triển khai chúng bằng mảng hoặc danh sách liên kết. Ngoài các cấu trúc cơ bản, chương này còn giới thiệu các biến thể quan trọng trong STL như hàng đợi ưu tiên (priority_queue) và hàng đợi hai đầu (deque). Case study “Exiting a Maze” là một ví dụ tuyệt vời về ứng dụng của ngăn xếp trong thuật toán quay lui (backtracking) để giải quyết một bài toán thực tế. Việc hiểu rõ các cấu trúc này là rất quan trọng vì chúng là nền tảng cho nhiều thuật toán phức tạp hơn, chẳng hạn như duyệt đồ thị hay quản lý lời gọi hàm trong đệ quy.

3.3. Khám phá sức mạnh của đệ quy và ứng dụng

Đệ quy là một khái niệm mạnh mẽ nhưng thường khó nắm bắt. Chương 5 của cuốn giáo trình cấu trúc dữ liệu này dành riêng để làm sáng tỏ chủ đề này. Tác giả Adam Drozdek giải thích rằng “đệ quy có thể được giải thích tốt nhất nếu xem xét đến ngăn xếp thời gian chạy (run-time stack)”. Sách minh họa chi tiết cách các lời gọi hàm đệ quy được quản lý trên ngăn xếp hệ thống, giúp người đọc hình dung rõ ràng quá trình hoạt động. Sách cũng phân tích các loại đệ quy khác nhau và mổ xẻ một lời gọi đệ quy để hiểu sâu hơn về cơ chế hoạt động. Case study về một trình thông dịch đệ quy (recursive descent interpreter) cho thấy sức mạnh của đệ quy trong việc giải quyết các bài toán phân tích cú pháp phức tạp.

IV. Phương pháp tiếp cận Cấu Trúc Dữ Liệu C phi tuyến tính

Sau khi đã nắm vững các cấu trúc tuyến tính, cuốn “Cấu Trúc Dữ Liệu và Thuật Toán trong C++” chuyển sang các cấu trúc phi tuyến tính phức tạp hơn như cây và đồ thị. Đây là những cấu trúc dữ liệu có khả năng mô hình hóa các mối quan hệ phức tạp trong thế giới thực, từ hệ thống phân cấp tổ chức, mạng máy tính đến các mối quan hệ xã hội. Chương 6 tập trung hoàn toàn vào cây nhị phân (binary tree) và các biến thể của nó như cây tìm kiếm nhị phân, cây AVL, và heap. Sách không chỉ trình bày cách triển khai và các thao tác cơ bản (thêm, xóa, tìm kiếm) mà còn đi sâu vào các thuật toán duyệt cây (pre-order, in-order, post-order) và các thuật toán cân bằng cây như DSW. Chương 8 mở rộng sang đồ thị (graph), một cấu trúc tổng quát hơn, bao gồm các thuật toán kinh điển như tìm đường đi ngắn nhất, cây khung nhỏ nhất và các bài toán NP-complete. Cách trình bày của sách giúp người đọc xây dựng một mô hình tư duy vững chắc để giải quyết các bài toán sử dụng các cấu trúc dữ liệu nâng cao này.

4.1. Chinh phục cây nhị phân binary tree và cây cân bằng

Chương 6 cung cấp một cái nhìn toàn diện về cây nhị phân (binary tree). Sách bắt đầu với các định nghĩa cơ bản về cây, cây nhị phân và cây tìm kiếm nhị phân (BST). Nội dung bao gồm các phương pháp duyệt cây theo chiều rộng (Breadth-First Traversal) và chiều sâu (Depth-First Traversal), kể cả phiên bản duyệt không dùng ngăn xếp (stackless). Một phần quan trọng của chương này là thảo luận về các thuật toán xóa nút trong BST, bao gồm xóa bằng cách hợp nhất (Deletion by Merging) và xóa bằng cách sao chép (Deletion by Copying). Để giải quyết vấn đề hiệu suất của BST trong trường hợp xấu nhất, sách giới thiệu các kỹ thuật cân bằng cây như thuật toán DSW và cây tự điều chỉnh (self-adjusting trees). Cuối cùng, heap được giới thiệu như một ứng dụng của cây để triển khai hàng đợi ưu tiên hiệu quả.

4.2. Khám phá bảng băm hash table và kỹ thuật băm

Tìm kiếm hiệu quả là một yêu cầu cốt lõi trong nhiều ứng dụng. Chương 10 trình bày về bảng băm (hash table), một trong những cấu trúc dữ liệu quan trọng nhất cho việc tìm kiếm với thời gian trung bình O(1). Sách khám phá các khía cạnh khác nhau của kỹ thuật băm, bao gồm việc thiết kế các hàm băm tốt (ví dụ: mid-square, universal hash functions) và các phương pháp giải quyết xung đột (collision resolution). Ngoài ra, sách còn giới thiệu các kỹ thuật nâng cao như băm hoàn hảo (perfect hashing) và băm cuckoo (cuckoo hashing). Case study “Hashing with Buckets” cung cấp một ví dụ thực tế về cách triển khai và sử dụng bảng băm để quản lý dữ liệu hiệu quả, cho thấy sức mạnh của cấu trúc này trong các ứng dụng thực tế.

4.3. Tìm hiểu về Đồ thị graph và các bài toán liên quan

Chương 8 giới thiệu về đồ thị (graph), một cấu trúc dữ liệu cực kỳ linh hoạt dùng để mô hình hóa các mối quan hệ nhiều-nhiều. Nội dung bao gồm các thuật toán cơ bản như tìm đường đi ngắn nhất cho tất cả các cặp đỉnh (All-to-All Shortest Path), bài toán Union-Find, và kiểm tra tính liên thông. Sách cũng đi sâu vào các chủ đề nâng cao hơn như luồng cực đại (maximum flow), cặp ghép ổn định (stable matching), và chu trình Eulerian/Hamiltonian. Một phần đặc biệt thú vị là thảo luận về các bài toán NP-complete trong lý thuyết đồ thị, chẳng hạn như bài toán Clique, 3-Colorability, và Vertex Cover. Việc hiểu về đồ thị và các thuật toán liên quan là rất cần thiết cho các lĩnh vực như mạng máy tính, trí tuệ nhân tạo và tối ưu hóa vận hành.

V. Bí quyết ứng dụng Cấu Trúc Dữ Liệu và Thuật Toán C

Điểm mạnh của cuốn “Cấu Trúc Dữ Liệu và Thuật Toán trong C++” không chỉ nằm ở việc trình bày lý thuyết mà còn ở khả năng kết nối lý thuyết đó với các ứng dụng thực tế. Cuốn sách này là một tài liệu học C++ tuyệt vời vì nó chỉ ra cách các cấu trúc dữ liệu và thuật toán được sử dụng để giải quyết các vấn đề cụ thể. Các chương cuối của sách tập trung vào các lĩnh vực ứng dụng quan trọng như sắp xếp, nén dữ liệu, quản lý bộ nhớ và đối sánh chuỗi. Mỗi chương đều phân tích chi tiết các phương pháp khác nhau, so sánh hiệu quả của chúng dựa trên độ phức tạp thuật toán, và cung cấp code ví dụ C++ để minh họa. Ví dụ, Chương 9 về Sắp xếp không chỉ giới thiệu các thuật toán sắp xếp cơ bản như Bubble Sort mà còn đi sâu vào các thuật toán hiệu quả như Quicksort, Mergesort và Heapsort. Sách cũng hướng dẫn cách sử dụng các hàm sắp xếp có sẵn trong STL, giúp lập trình viên tiết kiệm thời gian và đảm bảo hiệu suất. Việc giải bài tập cấu trúc dữ liệu C++ ở cuối mỗi chương giúp củng cố kiến thức và rèn luyện kỹ năng giải quyết vấn đề.

5.1. Các thuật toán sắp xếp và thuật toán tìm kiếm hiệu quả

Chương 9 cung cấp một phân tích chi tiết về các thuật toán sắp xếp. Sách phân loại chúng thành hai nhóm: thuật toán sắp xếp cơ bản (Elementary Sorting Algorithms) và thuật toán sắp xếp hiệu quả (Efficient Sorting Algorithms). Mỗi thuật toán được phân tích về độ phức tạp thời gian trong các trường hợp tốt nhất, trung bình và xấu nhất. Sách không chỉ dừng lại ở việc mô tả thuật toán mà còn đi kèm với các đoạn mã C++ rõ ràng. Phần “Sorting in the Standard Template Library” (9.4) rất hữu ích, nó chỉ ra cách tận dụng std::sort và các hàm liên quan để thực hiện sắp xếp một cách nhanh chóng và hiệu quả. Các thuật toán tìm kiếm cũng được tích hợp trong các chương về cấu trúc dữ liệu tương ứng, chẳng hạn như tìm kiếm nhị phân trong cây tìm kiếm nhị phân.

5.2. Các Case Study thực tế và code ví dụ C chi tiết

Một trong những điểm giá trị nhất của cuốn sách là việc tích hợp các Case Study (nghiên cứu tình huống) vào cuối hầu hết các chương. Tác giả khẳng định: “Những case study này được chọn từ các lĩnh vực khác nhau của khoa học máy tính như trình thông dịch, tính toán biểu tượng, và xử lý tệp, để chỉ ra phạm vi ứng dụng rộng rãi của các chủ đề đang được thảo luận”. Ví dụ, case study về một trình kiểm tra chính tả (Spell Checker) trong chương 7 (Multiway Trees) hay tính toán tần suất từ (Computing Word Frequencies) trong chương 6 (Binary Trees) là những ví dụ điển hình. Các case study này đi kèm với mã nguồn hoàn chỉnh, giúp người đọc thấy được cách các mảnh ghép lý thuyết kết hợp lại để tạo thành một ứng dụng hoàn chỉnh.

VI. Đánh giá sách Cấu Trúc Dữ Liệu và Thuật Toán C của Drozdek

Tổng kết lại, “Cấu Trúc Dữ Liệu và Thuật Toán trong C++ - Phiên Bản Thứ Tư” của Adam Drozdek là một giáo trình cấu trúc dữ liệu xuất sắc và toàn diện. Cuốn sách thành công trong việc tạo ra sự cân bằng hoàn hảo giữa chiều sâu lý thuyết và tính ứng dụng thực tiễn. Đây là một sách C++ cho sinh viên không thể thiếu, đồng thời cũng là một tài liệu tham khảo quý giá cho các lập trình viên muốn củng cố và nâng cao kiến thức nền tảng. Với cách trình bày rõ ràng, các ví dụ code C++ minh họa chi tiết, và các case study thực tế, sách giúp người đọc vượt qua những thách thức phổ biến khi học về cấu trúc dữ liệu và giải thuật C++. Các bài tập và dự án lập trình ở cuối mỗi chương cung cấp cơ hội tuyệt vời để thực hành và áp dụng kiến thức đã học. Phiên bản thứ tư, với những cập nhật về các chủ đề mới, đảm bảo rằng nội dung của sách luôn phù hợp và có giá trị trong bối cảnh công nghệ không ngừng phát triển. Đây chắc chắn là một khoản đầu tư xứng đáng cho bất kỳ ai nghiêm túc với sự nghiệp lập trình C++ và phát triển phần mềm.

6.1. Tại sao đây là sách C cho sinh viên không thể bỏ qua

Đối với sinh viên ngành Công nghệ thông tin và Khoa học máy tính, cuốn sách này cung cấp một lộ trình học tập có cấu trúc và bài bản. Nó bao quát toàn bộ các chủ đề cốt lõi được yêu cầu trong chương trình học, từ cơ bản đến nâng cao. Ngôn ngữ trình bày mạch lạc, kết hợp với các sơ đồ và hình minh họa trực quan, giúp các khái niệm trừu tượng trở nên dễ hiểu hơn. Đặc biệt, việc tích hợp Thư viện Mẫu Chuẩn (STL) vào các chương giúp sinh viên làm quen với các công cụ lập trình C++ hiện đại, thu hẹp khoảng cách giữa môi trường học thuật và công nghiệp. Việc có một nguồn tài liệu học C++ đáng tin cậy như thế này sẽ là một lợi thế lớn trong quá trình học tập và chuẩn bị cho các kỳ thi hay phỏng vấn kỹ thuật.

6.2. Giá trị của cuốn giáo trình cấu trúc dữ liệu này mang lại

Giá trị lớn nhất của cuốn giáo trình cấu trúc dữ liệu này nằm ở cách tiếp cận toàn diện. Nó không chỉ dạy cách triển khai một cây nhị phân hay một bảng băm, mà còn giải thích khi nào và tại sao nên sử dụng chúng. Việc nhấn mạnh vào phân tích độ phức tạp thuật toán và Big O notation trang bị cho người đọc khả năng tư duy phản biện về hiệu suất mã nguồn. Các case study đa dạng cho thấy tính ứng dụng rộng rãi của kiến thức, truyền cảm hứng cho người học khám phá các lĩnh vực khác nhau của khoa học máy tính. Tóm lại, cuốn sách không chỉ cung cấp kiến thức, mà còn xây dựng tư duy của một kỹ sư phần mềm, một kỹ năng sẽ tồn tại lâu dài trong sự nghiệp của họ.

Trích đoạn nội dung tài liệu

Data Structures and Algorithms in C++ Fourth Edition Adam Drozdek Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. This is an electronic version of the print textbook. Due to electronic rights restrictions, some third party content may be suppressed.

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. The publisher reserves the right to remove content from this title at any time if subsequent rights restrictions require it. For valuable information on pricing, previous editions, changes to current editions, and alternate formats, please visit www.com/highered to search by ISBN#, author, title, or keyword for materials in your areas of interest. Copyright 2012 Cengage Learning.

All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience.

Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Data Structures and © 2013 Cengage Learning Algorithms in C++, ALL RIGHTS RESERVED. No part of this work covered by the copyright herein Fourth Edition may be reproduced, transmitted, stored or used in any form or by any means by Adam Drozdek graphic, electronic, or mechanical, including but not limited to photocopying, Executive Editor: Marie Lee recording, scanning, digitizing, taping, Web distribution, information networks, or information storage and retrieval systems, except as permitted under Senior Product Manager: Section 107 or 108 of the 1976 United States Copyright Act, without the prior Alyssa Pratt written permission of the publisher. Associate Product Manager: Stephanie Lorenz For product information and technology assistance, contact us at Content Project Manager: Cengage Learning Customer & Sales Support, www.com/support Matthew Hutchinson For permission to use material from this text or product, submit all Art Director: Cheryl Pearl requests online at www.com/permissions Further permissions questions can be emailed to Print Buyer: Julio Esperas [e-mail] Compositor: PreMediaGlobal Proofreader: Andrea Schein Library of Congress Control Number: 2012942244 Indexer: Sharon Hilgenberg ISBN-13: 978-1-133-60842-4 ISBN-10: 1-133-60842-6 Cengage Learning 20 Channel Center Street Boston, MA 02210 USA Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil and Japan.

Locate your local office at: www.com/global Cengage Learning products are represented in Canada by Nelson Education, Ltd. To learn more about Cengage Learning, visit www.com Purchase any of our products at your local college store or at our preferred online store www.com Some of the product names and company names used in this book have been used for identification purposes only and may be trademarks or registered trademarks of their respective manufacturers and sellers. Any fictional data related to persons or companies or URLs used throughout this book is intended for instructional purposes only. At the time this book was printed, any such data was fictional and not belonging to any real persons or companies.

Cengage Learning reserves the right to revise this publication and make changes from time to time in its content without notice. The programs in this book are for instructional purposes only. They have been tested with care, but are not guaranteed for any particular intent beyond educational purposes. The author and the publisher do not offer any warranties or repre- sentations, nor do they accept any liabilities with respect to the programs.

Printed in the United States of America 1 2 3 4 5 6 7 18 17 16 15 14 13 12 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. To my daughters, Justyna and Kasia Copyright 2012 Cengage Learning. All Rights Reserved.

May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Contents 1 Object-Oriented Programming Using C++ 1 1.1 Abstract Data Types 1 1.1 Pointers and Arrays 12 1.2 Pointers and Copy Constructors 14 1.3 Pointers and Destructors 16 1.4 Pointers and Reference Variables 17 1.5 Pointers to Functions 20 1.6 C++ and Object-Oriented Programming 23 1.7 The Standard Template Library 24 1.8 Vectors in the Standard Template Library 28 1.9 Data Structures and Object-Oriented Programming 35 1.10 Case Study: Random Access File 35 1.12 Programming Assignments   48 Bibliography   50 Copyright 2012 Cengage Learning. All Rights Reserved.

May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

vi ■ Contents 2 Complexity Analysis 51 2.1 Computational and Asymptotic Complexity 51 2.3 Properties of Big-O Notation 54 2.6 Examples of Complexities 57 2.7 Finding Asymptotic Complexity: Examples 59 2.8 The Best, Average, and Worst Cases 61 2.11 Exercises   71 Bibliography   74 3 Linked Lists 75 3.1 Singly Linked Lists 75 3.2 Doubly Linked Lists 90 3.5 Self-Organizing Lists 101 3.7 Lists in the Standard Template Library 109 3.9 Case Study: A Library 114 3.11 Programming Assignments   127 Bibliography   130 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Contents ■ vii 4 Stacks and Queues 131 4.4 Stacks in the Standard Template Library 149 4.5 Queues in the Standard Template Library 149 4.6 Priority Queues in the Standard Template Library 151 4.7 Deques in the Standard Template Library 153 4.8 Case Study: Exiting a Maze 158 4.10 Programming Assignments   166 Bibliography   168 5 Recursion 169 5.2 Function Calls and Recursion Implementation 172 5.3 Anatomy of a Recursive Call 174 5.11 Case Study: A Recursive Descent Interpreter 198 5.13 Programming Assignments   210 Bibliography   213 6 Binary Trees 214 6.1 Trees, Binary Trees, and Binary Search Trees 214 6.2 Implementing Binary Trees 219 6.3 Searching a Binary Search Tree 222 Copyright 2012 Cengage Learning. All Rights Reserved.

May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.1 Breadth-First Traversal 225 6.2 Depth-First Traversal 226 6.3 Stackless Depth-First Traversal 233 6.1 Deletion by Merging 244 6.2 Deletion by Copying 246 6.1 The DSW Algorithm 253 6.8 Self-Adjusting Trees 261 6.1 Self-Restructuring Trees 262 6.1 Heaps as Priority Queues 270 6.2 Organizing Arrays as Heaps 271 6.12 Polish Notation and Expression Trees 286 6.1 Operations on Expression Trees 287 6.13 Case Study: Computing Word Frequencies 290 6.15 Programming Assignments   302 Bibliography   306 7 Multiway Trees 309 7.1 The Family of B-Trees 310 7.9 Sets and Multisets in the Standard Template Library 353 7.10 Maps and Multimaps in the Standard Template Library 359 Copyright 2012 Cengage Learning.

All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience.

Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.4 Case Study: Spell Checker 373 7.6 Programming Assignments   385 Bibliography   389 8 Graphs 391 8.1 All-to-All Shortest Path Problem 405 8.1 Union-Find Problem 409 8.1 Connectivity in Undirected Graphs 415 8.2 Connectivity in Directed Graphs 418 8.2 Maximum Flows of Minimum Cost 433 8.1 Stable Matching Problem 442 8.3 Matching in Nonbipartite Graphs 447 8.10 Eulerian and Hamiltonian Graphs 449 8.12 NP-Complete Problems in Graph Theory 462 8.1 The Clique Problem 462 8.2 The 3-Colorability Problem 463 8.3 The Vertex Cover Problem 465 8.4 The Hamiltonian Cycle Problem 466 8.13 Case Study: Distinct Representatives 467 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.15 Programming Assignments   486 Bibliography   487 9 Sorting 491 9.1 Elementary Sorting Algorithms 492 9.3 Efficient Sorting Algorithms 505 9.4 Sorting in the Standard Template Library 528 9.6 Case Study: Adding Polynomials 534 9.8 Programming Assignments   543 Bibliography   545 10 Hashing 548 10.3 Mid-Square Function 550 10.6 Universal Hash Functions 551 10.3 Deletion 561 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.4 Perfect Hash Functions 562 10.2 The FHCD Algorithm 566 10.1 The Cuckoo Hashing 568 10.6 Hash Functions for Extendible Files 571 10.7 Case Study: Hashing with Buckets 576 10.9 Programming Assignments   587 Bibliography   588 11 Data Compression 590 11.1 Conditions for Data Compression 590 11.1 Adaptive Huffman Coding 601 11.3 Run-Length Encoding 606 11.4 Ziv-Lempel Code 607 11.5 Case Study: Huffman Method with Run-Length Encoding 610 11.7 Programming Assignments   622 Bibliography   624 12 Memory Management 625 12.1 The Sequential-Fit Methods 626 12.2 The Nonsequential-Fit Methods 627 12.1 Mark-and-Sweep 637 12.3 Incremental Garbage Collection 646 12.4 Generational Garbage Collection 653 12.5 Case Study: An In-Place Garbage Collector 658 Copyright 2012 Cengage Learning. All Rights Reserved.

May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.7 Programming Assignments   668 Bibliography   671 13 String Matching 674 13.1 Exact String Matching 674 13.2 The Knuth-Morris-Pratt Algorithm 677 13.3 The Boyer-Moore Algorithm 685 13.