tailieunhanh - Chương 1: Sự trừu tượng hoá dữ liệu

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 | Do vậy, khi cài đặt KDLTT chúng ta cần tạo ra một giao diện (interface) giữa chương trình áp dụng và sự cài đặt KDLTT. Giao diện này bao gồm các phép toán đã xác định trong KDLTT. Người sử dụng chỉ được phép giao tiếp với sự cài đặt KDLTT thông qua giao diện này. Nói một cách hình ảnh thì cách cài đặt KDLTT cần phải sao cho tạo thành bức tường giữa chương trình áp dụng và sự cài đặt KDLTT. Bức tường này che chắn CTDL, chỉ có thể truy cập tới CTDL thông qua các phép toán đã đặc tả trong KDLTT (hình ). Nếu thực hiện được sự cài đặt KDLTT như thế, thì khi ta thay đổi CTDL biểu diễn đối tượng dữ liệu và thay đổi cách cài đặt các hàm cũng không ảnh hưởng gì đến chương trình áp dụng sử dụng KDLTT này. Điều này tương tự như khi ta sử dụng máy bán nước giải khát tự động. Thiết kế bên ngoài và các chỉ dẫn sẽ cho phép người sử dụng mua được loại nước mà mình mong muốn. Chẳng hạn, có ba nút ấn: cam, côca, cà phê. Bỏ 5 xu vào lỗ dưới nút cam và ấn nút cam, người sử dụng sẽ nhận được cốc cam , Người sử dụng không cần biết đến cấu tạo bên trong của ta có thể thay đổi cấu tạo bên trong của máy, miễn là nó vẫn đáp ứng được mong muốn của người sử dụng khi họ thực hiện các thao tác theo chỉ dẫn.