Giới thiệu cấu trúc dữ liệu

Giới thiệu Kiểu dữ liệu trừu tượng (ADT)

Trong khoa học máy tính, một kiểu dữ liệu trừu tượng (ADT-Abatract Data Type) là một mô hình toán học cho các kiểu dữ liệu. Một kiểu dữ liệu trừu tượng được xác định theo hành vi của nó (ngữ nghĩa) từ quan điểm của người dùng, của dữ liệu, cụ thể về giá trị có thể có, các hoạt động có thể có trên dữ liệu thuộc loại này và hành vi của các hoạt động này. Mô hình toán học này tương phản với cấu trúc dữ liệu, là những đại diện cụ thể của dữ liệu và là quan điểm của người triển khai, không phải người dùng.

Về mặt hình thức, ADT có thể được định nghĩa là một “lớp đối tượng có hành vi logic được xác định bởi một tập hợp các giá trị và một tập hợp các phép toán”; điều này tương tự như một cấu trúc đại số trong toán học. Ý nghĩa của “hành vi” khác nhau tùy theo tác giả, với hai loại đặc tả chính thức cho hành vi là đặc tả tiên đề (đại số) và mô hình trừu tượng; chúng tương ứng với ngữ nghĩa tiên đề và ngữ nghĩa hoạt động của một máy trừu tượng. Một số tác giả cũng bao gồm độ phức tạp tính toán (“chi phí”), cả về thời gian (cho các hoạt động tính toán) và không gian (để biểu diễn các giá trị). Trong thực tế, nhiều kiểu dữ liệu phổ biến không phải là ADT, vì tính trừu tượng không hoàn hảo và người dùng phải nhận thức được các vấn đề như tràn số học do biểu diễn. Ví dụ: các số nguyên thường được lưu trữ dưới dạng các giá trị có độ rộng cố định (số nhị phân 32 bit hoặc 64 bit) và do đó gặp phải hiện tượng tràn số nguyên nếu giá trị lớn nhất bị vượt quá.

Bạn đang xem: Giới thiệu cấu trúc dữ liệu

Xem thêm : "Bền Vững" trong Tiếng Anh là gì: Định Nghĩa, Ví Dụ Anh Việt

ADT là một khái niệm lý thuyết, trong khoa học máy tính, được sử dụng trong thiết kế và phân tích các thuật toán, cấu trúc dữ liệu và hệ thống phần mềm, và không tương ứng với các tính năng cụ thể của ngôn ngữ máy tính — các ngôn ngữ máy tính chính thống không hỗ trợ trực tiếp các ADT được chỉ định chính thức. Tuy nhiên, các đặc điểm ngôn ngữ khác nhau tương ứng với các khía cạnh nhất định của ADT và dễ bị nhầm lẫn với ADT thích hợp; chúng bao gồm các kiểu trừu tượng, kiểu dữ liệu không rõ ràng, giao thức và thiết kế theo ràng buộc. ADT lần đầu tiên được đề xuất bởi Barbara Liskov và Stephen N. Zilles vào năm 1974, như một phần của sự phát triển của ngôn ngữ CLU.

Kiểu dữ liệu trừu tượng là các thực thể lý thuyết thuần túy, được sử dụng (trong số những thứ khác) để đơn giản hóa việc mô tả các thuật toán trừu tượng, để phân loại và đánh giá cấu trúc dữ liệu, và để mô tả chính thức kiểu hệ thống của ngôn ngữ lập trình. Tuy nhiên, một ADT có thể được thực hiện bởi các kiểu dữ liệu hoặc cấu trúc dữ liệu cụ thể, theo nhiều cách và trong nhiều ngôn ngữ lập trình; hoặc được mô tả bằng ngôn ngữ đặc tả chính thức. ADT thường được thực hiện dưới dạng mô-đun: giao diện của mô-đun khai báo các thủ tục tương ứng với các hoạt động ADT, đôi khi có các chú thích mô tả các ràng buộc. Chiến lược che giấu thông tin này cho phép thay đổi việc triển khai mô-đun mà không làm ảnh hưởng đến các chương trình khách.

Xem thêm : Phân tích nhân vật chị Dậu trong đoạn trích Tức nước vỡ bờ

Thuật ngữ kiểu dữ liệu trừu tượng cũng có thể được coi là một cách tiếp cận tổng quát của một số cấu trúc đại số, chẳng hạn như mạng, nhóm và vòng. Khái niệm về kiểu dữ liệu trừu tượng có liên quan đến khái niệm trừu tượng hóa dữ liệu, quan trọng trong lập trình hướng đối tượng và thiết kế theo phương pháp hợp đồng để phát triển phần mềm.

Định nghĩa của ADT chỉ đề cập đến những thao tác nào sẽ được thực hiện chứ không đề cập đến cách những hoạt động này sẽ được thực hiện. Nó không chỉ định cách dữ liệu sẽ được tổ chức trong bộ nhớ và những thuật toán nào sẽ được sử dụng để thực hiện các hoạt động. Nó được gọi là “trừu tượng” vì nó cung cấp một chế độ xem độc lập với việc triển khai. Quá trình chỉ cung cấp các yếu tố cần thiết và ẩn các chi tiết được gọi là trừu tượng hóa.

Sử dụng kiểu dữ liệu không cần biết kiểu dữ liệu đó được triển khai như thế nào, ví dụ: chúng ta đang sử dụng các giá trị Nguyên thủy như kiểu dữ liệu int, float, char chỉ với kiến thức rằng kiểu dữ liệu này có thể hoạt động và được thực hiện mà không cần bất kỳ giá trị nào. ý tưởng về cách chúng được thực hiện. Vì vậy, người dùng chỉ cần biết kiểu dữ liệu có thể làm gì chứ không cần biết nó sẽ được triển khai như thế nào. Hãy coi ADT như một hộp đen ẩn cấu trúc và thiết kế bên trong của kiểu dữ liệu.

Nguồn: https://thcshongthaiad.edu.vn
Danh mục: Tra Cứu