Абстрактный тип данных (Abstract data type)

Абстрактный тип данных (АТД) — это модель, в рамках которой некоторый класс объектов определяется со стороны операций, возможных для объектов этого класса. В данном случае «класс» следует понимать как набор или группу сходных объектов.

An abstract data type defines a class of abstract objects which is completely characterized by the operations available on those objects. This means that an abstract data type can be defined by defining the characterizing operations for that type.^[1]

При использовании абстрактного типа данных, разработчик концентрируется только на его поведении. Поведение же определяется набором операций заданных в абстрактном типе данных. Определить набор операций означает задать соотношения между этими операциями.

для примера рассмотрим абстрактный тип данных пара. Пара определяется через четыре операции:

• set1(a) — установить первый элемент пары
• get1() — получить первый элемент пары
• set2(b) — установить второй элемент пары
• get2() — получить второй элемент пары

Операция get1 всегда вернёт тот элемент который был передан при последнем вызове set1, аналогично работают get2 и set2. Таким образом определяется соотношение между операциями пары, а значит и поведение этого абстрактного типа данных. Абстрактный тип данных пара может использоваться, например, для реализации двухмерной точки или комплексного числа. Особенно важно, что не определяется реализация методов — пара может быть реализована через различные структуры данных: массив, запись и др.

Польза от использовании абстрактного типа данных заключается в возможности декомпозировать задачу.

Стандартные типы данных языков программирования, такие как Integer или String, в определенном смысле, тоже являются абстрактными типами данных. Пользователь языка программирования знает только набор операций для работы с типом: числа можно перемножать и складывать, а строки соединять. Реализация, внутреннее устройство, типа данных скрыто за компилятором или интерпретатором: порядок байт в числе, способ хранения строки в памяти и другие. В то же время, абстрактными типами данных часто называют не просто стандартные типы данных ЯП, а более высокоуровневые объекты которых может не быть в стандартной библиотеке. Часто применяются следующие АТД:

• Список
• Множество
• Стек
• Очередь

Ссылки на эту заметку

• Абстракция (Abstraction)
• Абстракция данных
• Абстракция и декомпозиция
• Множество (АТД)
• Отношение между структурами данных и абстрактными типами данных
• Очередь (Queue)
• Простые и составные типы данных
• Селектор элементов массив и списков
• Список (АТД)
• Стек

Эта заметка на GitHub

Обсудить на форуме

---

1. Programming with abstract data types. Barbara Liskov. 1974. The Meaning of Abstraction ↩︎