Методы сортировки и поиска

Абстрактные (определяемые пользователями) типы данных


На самом деле, оба термина, употребленные в названии раздела, плохо отражают суть соответствующего понятия. Термин "абстрактные типы" плох тем, что реально ничего абстрактного в этой категории типов нет. Термин "определяемые пользователями типы" не точно отражает специфику, поскольку все типы, обсуждавшиеся выше, кроме встроенных в языки программирования, так или иначе определяются пользователями. Тем не менее, в силу привычки, мы будем использовать в этом разделе словосочетание "абстрактные типы данных" (АТД).

Не обращая больше внимания на ущербность терминологии, займемся содержанием понятия АТД. Как мы видели, наличие перечисляемых, уточняемых и конструируемых типов данных в сочетании со средствами выделения динамической памяти позволяет конструировать и использовать структуры данных, достаточные для создания произвольно сложных программ. Ограниченность этих средств состоит в том, что при определении типов и создании структур невозможно зафиксировать правила их использования. Например, если определен структурный тип с полями salary, commissions и total в предположении, что для любой переменной этого типа поле total всегда будет содержать общую сумму выплат, то ничто не мешает по ошибке нарушить это условие (с точки зрения компилятора никакой ошибки нет) и получить неверные результаты работы программы.

Основной идеей АТД является то, что при его определении специфицируется не только структура значений типа, но и набор допустимых операций над переменными и значениями этого типа. В наиболее сильном случае доступ к внутренней структуре типа доступен только через его операции. В число операций обязаны входить один или несколько конструкторов значений типа.

Имеется много разновидностей языков с АТД, языковые средства которых весьма различаются. Кроме того, к этому семейству языков примыкают языки объектно-ориентированного программирования. По поводу них одни авторы (к числу которых относится и автор этой книги) полагают, что для них термин "язык объектно-ориентированного программирования" является модной заменой старого термина "язык с АТД". Другие находят между этими языковыми семействами много тонких отличий, часть которых считают серьезными. Мы не будем глубоко анализировать эти дискуссии, а обсудим некоторые базовые концепции, общие для обоих семейств.

Содержание раздела