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

Cuốn sách này trình bày các vấn đề 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 trong IEEE/ACM computing curricula, theo quan điểm hiện đại. Khi thiết kế thuật toán để giải quyết một vấn đề, chúng ta cần phải sử dụng các đối tượng dữ liệu và các phép toán trên các đối tượng dữ liệu ở mức độ trừu tượng. Một trong các nội dung chính của sách này là nghiên cứu các kiểu dữ liệu trừu tượng (KDLTT) và các CTDL để cài đặt các KDLTT. KDLTT quan trọng nhất là tập động (một tập đối tượng dữ liệu với các phép toán tìm kiếm, xen, loại, …), KDLTT này được sử dụng rộng rãi nhất trong các chương trình ứng dụng. Các KDLTT cơ bản khác sẽ được nghiên cứu là : danh sách, ngăn xếp, hàng đợi, hàng ưu tiên, từ điển, …
Chúng ta sẽ cài đặt các KDLTT bởi các lớp C + +. Sự cài đặt các KDLTT bởi các lớp C + + cho phép ta có thể biểu diễn các đối tượng dữ liệu và các phép toán trên các đối tượng dữ liệu trong các chương trình ứng dụng một cách toán học, ngắn gọn và dễ hiểu, tương tự như khi ta sử dụng các số nguyên, số thực trong chương trình. Một ưu điểm quan trọng khác là, nó cho phép khi thiết kế và cài đặt phần mềm, chúng ta có thể làm việc ở mức độ quan niệm cao, có thể thực hành được các nguyên lý lập trình. Với mỗi KDLTT, chúng ta sẽ nghiên cứu các cách cài đặt bởi các CTDL khác nhau. Hiệu quả của các phép toán trong mỗi cách cài đặt sẽ được đánh giá. Sự đánh giá so sánh các cách cài đặt sẽ giúp cho người sử dụng có sự lựa chọn thích hợp cho từng chương trình ứng dụng. Thông qua sự cài đặt các lớp C + + cho mỗi KDLTT và các chương trình ứng dụng chúng, độc giả sẽ được cung cấp thêm nhiều kỹ thuật lập trình hữu ích. Sự nghiên cứu mỗi KDLTT sẽ được tiến hành qua các bước sau đây.
• Đặc tả KDLTT. Chúng ta sẽ mô tả các đối tượng dữ liệu bằng cách sử dụng các ký hiệu, các khái niệm toán học và logic. Các phép toán trên các đối tượng dữ liệu sẽ được mô tả bởi các hàm toán học.
• Lựa chọn CTDL thích hợp để cài đặt đối tượng dữ liệu
• Thiết kế và cài đặt lớp C + +.
• Phân tích hiệu quả của các phép toán.
• Các ví dụ ứng dụng.
Nội dung của cuốn sách được tổ chức thành ba phần. Phần 1 sẽ nghiên cứu các CTDL cơ bản được sử dụng để cài đặt các KDLTT, đó là danh sách liên kết (DSLK), cây tìm kiếm nhị phân (TKNP), cây thứ tự bộ phận (heap), bảng băm. Danh sách, ngăn xếp, hàng đợi sẽ được cài đặt bởi mảng hoặc bởi DSLK. Cây TKNP được sử dụng để cài đặt tập động. Hàng ưu tiên được cài đặt hiệu quả bởi heap. Bảng băm là CTDL rất thích hợp để cài đặt từ điển. Trong phần 2 chúng ta sẽ nghiên cứu các CTDL cao cấp. Các CTDL này có đặc điểm chung là sự tổ chức dữ liệu và các phép toán trên các CTDL này là khá phức tạp, song bù lại thời gian thực hiện các phép toán lại hiệu quả hơn. Chúng ta sẽ nghiên cứu các loại cây tìm kiếm cân bằng, các CTDL tự điều chỉnh, các CTDL đa chiều, … Đặc biệt, chúng ta sẽ đưa vào kỹ thuật phân tích trả góp, đây là kỹ thuật phân tích hoàn toàn mới, được sử dụng để đánh giá thời gian chạy của một dãy phép toán trên các CTDL tự điều chỉnh. Phần 3 dành để nói về thuật toán. Chúng ta sẽ trình bày phương pháp đánh giá thời gian chạy của thuật toán bằng ký hiệu ô lớn, và các kỹ thuật để phân tích, đánh giá thời gian chạy của thuật toán. Một nội dung quan trọng của phần này là nghiên cứu các chiến lược thiết kế thuật toán. Chúng ta sẽ trình bày các chiến lược thiết kế thuật toán hay được sử dụng là : chia – để – trị, quy hoạch động, quay lui, … Các thuật toán sắp xếp, các thuật toán đồ thị cũng sẽ được nghiên cứu. Cuối cùng chúng ta trình bày một vấn đề có tính chất lý thuyết, đó là các bài toán NP – khó và NP – đầy đủ.

Nguồn	: Internet
Tác giả	: Đinh Mạnh Tường
Kiểu tập tin	: DOC
Độ lớn tập tin	: 647.98 KB