Kiểu dữ liệu trừu tượng (ABSTRACT DATA TYPE -ADT)

Khái niệm trừu tượng hóa

Trong tin học, trừu tượng hóa nghĩa là đơn giản hóa, làm cho nó sáng sủa hơn và dễ hiểu hơn. Cụ thể trừu tượng hóa là che đi những chi tiết, làm nổi bật cái tổng thể. Trừu tượng hóa có thể thực hiện trên hai khía cạnh là trừu tượng hóa dữ liệu và trừu tượng hóa chương trình.

Trừu tượng hóa chương trình

Trừu tượng hóa chương trình là sự định nghĩa các chương trình con để tạo ra các phép toán trừu tượng (sự tổng quát hóa của các phép toán nguyên thủy). Chẳng hạn ta có thể tạo ra một chương trình con Matrix_Mult để thực hiện phép toán nhân hai ma trận. Sau khi Matrix_mult đã được tạo ra, ta có thể dùng nó như một phép toán nguyên thủy (chẳng hạn phép cộng hai số).

Trừu tượng hóa chương trình cho phép phân chia chương trình thành các chương trình con. Sự phân chia này sẽ che dấu tất cả các lệnh cài đặt chi tiết trong các chương trình con. Ở cấp độ chương trình chính, ta chỉ thấy lời gọi các chương trình con và điều này được gọi là sự bao gói.

Ví dụ như một chương trình quản lý sinh viên được viết bằng trừu tượng hóa có thể là:

void Main() {

Nhap( Lop);

Xu_ly (Lop);

Xuat (Lop);

}

Trong chương trình trên, Nhap, Xu_ly, Xuat là các phép toán trừu tượng. Chúng che dấu bên trong rất nhiều lệnh phức tạp mà ở cấp độ chương trình chính ta không nhìn thấy được. Còn Lop là một biến thuộc kiểu dữ liệu trừu tượng mà ta sẽ xét sau.

Trừu tượng hóa dữ liệu

Trừu tượng hóa dữ liệu là định nghĩa các kiểu dữ liệu trừu tượng

Một kiểu dữ liệu trừu tượng là một mô hình toán học cùng với một tập hợp các phép toán (operator) trừu tượng được định nghĩa trên mô hình đó. Ví dụ tập hợp số nguyên cùng với các phép toán hợp, giao, hiệu là một kiểu dữ liệu trừu tượng.

Trong một ADT các phép toán có thể thực hiện trên các đối tượng (toán hạng) không chỉ thuộc ADT đó, cũng như kết quả không nhất thiết phải thuộc ADT. Tuy nhiên phải có ít nhất một toán hạng hoặc kết quả phải thuộc ADT đang xét.

ADT là sự tổng quát hoá của các kiểu dữ liệu nguyên thuỷ.

Để minh hoạ ta có thể xét bản phác thảo cuối cùng của thủ tục GREEDY. Ta đã dùng một danh sách (LIST) các số nguyên và các phép toán trên danh sách newclr là:

• Tạo một danh sách rỗng.
• Lấy phần tử đầu tiên trong danh sách và trả về giá trị null nếu danh sách rỗng.
• Lấy phần tử kế tiếp trong danh sách và trả về giá trị null nếu không còn phần tử kế tiếp.
• Thêm một số nguyên vào danh sách.

Nếu chúng ta viết các chương trình con thực hiện các phép toán này, thì ta dễ dàng thay các mệnh đề hình thức trong giải thuật bằng các câu lệnh đơn giản

Điều này cho thấy sự thuận lợi của ADT, đó là ta có thể định nghĩa một kiểu dữ liệu tuỳ ý cùng với các phép toán cần thiết trên nó rồi chúng ta dùng như là các đối tượng nguyên thuỷ. Hơn nữa chúng ta có thể cài đặt một ADT bằng bất kỳ cách nào, chương trình dùng chúng cũng không thay đổi, chỉ có các chương trình con biểu diễn cho các phép toán của ADT là thay đổi.

Cài đặt ADT là sự thể hiện các phép toán mong muốn (các phép toán trừu tượng) thành các câu lệnh của ngôn ngữ lập trình, bao gồm các khai báo thích hợp và các thủ tục thực hiện các phép toán trừu tượng. Để cài đặt ta chọn một cấu trúc dữ liệu thích hợp có trong ngôn ngữ lập trình hoặc là một cấu trúc dữ liệu phức hợp được xây dựng lên từ các kiểu dữ liệu cơ bản của ngôn ngữ lập trình.