С этого шага мы начнем рассматривать создание и использование структур данных.

"Если вы пришли к выводу, что ваша программа работает недостаточно быстро, первое, что надо сделать, это убедиться, что вы решаете задачу, пользуясь наилучшими алгоритмами и представлениями данных. Замена примитивного или неадекватного алгоритма более подходящим может ускорить выполнение вашей программы на порядок и более. Так что если вы проведете несколько дней, штудируя знаменитые книги Кнута [1-3] или Седжуика [4] (в надежде подобрать алгоритм, до которого вряд ли додумались бы сами), - будьте уверены: вы сделали выгодное вложение своего драгоценного времени.

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

    Рей Дункан. "PC Magazine", 1,1992, с.102

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

    Этот термин появился в 1974 г. в статье Б.Лисков и С.Зиллеса [5], посвященной принципам разрабатывавшегося ими языка программирования CLU. Термин быстро распространился среди системных программистов и теоретиков программирования и стал у них не только популярным, но настолько модным, что им стали называть понятия, весьма далекие от того, о чем шла речь у его авторов. Прилагательное "абстрактный" может ввести в заблуждение (особенно математика), так как абстрактные типы не более абстрактны, чем многие другие варианты понятия типа, к которым это прилагательное не "прилагают". На самом деле речь идет прежде всего о повышении уровня абстракции по отношению к языкам императивного программирования.

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

    В языках программирования АТД - это конструкция (кластер, модуль, класс), состоящая из двух частей:

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

      В некоторых экспериментальных языках, например в Альфарде [6,с.149], языковая конструкция, соответствующая АТД, содержит, кроме двух упомянутых, еще две части:

• абстрактное описание средствами более высокого уровня, включая непроцедурные;
• описание корректности представления, определяющее, в каком смысле конкретное описание правильно представляет абстрактное описание.

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

    К формальной записи абстрактных типов данных можно применить алгебраический подход [7, с.11-12]. Он проявляется в том, что задается множество операций над данными. Данные определяются как структуры, порождаемые этими операциями. Использование выразительных средств алгебры связано с возможностью применения к данным математических методов, в частности с перспективами применения к данным теории ассоциативных и коммутативных групп.

Если АТД воспринимается многими программистами с напряжением и внутренним сопротивлением, тогда как математики видят и создают алгебраические системы чуть ли не на каждом шагу, то это отчасти объясняется младенческим возрастом программирования по сравнению с математикой.

    В.Н.Агафонов [6]

    В качестве примера рассмотрим тип данных "список". В качестве операций над списками возьмем операцию создания списков CONS, операции декомпозиции списков CAR и CDR, операцию NULL, дающую возможность определить, пуст список или нет, а также операцию NIL, задающую пустой список.

    Эти операции записываются следующим образом:

   DATA_TYPE LIST (X) IS
      OPERATIONS:
         NIL : --> LIST(X)
         CONS: X x LIST(X) --> LIST(X)
         CAR : LIST(X) --> X
         CDR : LIST(X) --> LIST(X)
         NULL: LIST(X) --> BOOLEAN
   END LIST

    Символом X в приведенных выше выражениях обозначается тип данных для каждого непустого элемента списка. Тип данных "список" называют полиморфным типом данных, поскольку он содержит внутри себя переменные для типов, как, например, X.

    Если использовать только эти определения, то остаются неясными связи между операциями CONS, CAR и CDR, а также вид выражения NULL. Поэтому помимо задания операций записываются выражения (называемые обычно аксиомами), которым должны удовлетворять эти операции. Имеются три аксиомы списков:

   DATA_TYPE LIST(X) IS
      AXIOMS:
         VAR Y: X,
             L: LIST(X)
         CONS (CAR (L), CDR (L)) = L
         NULL (NIL) = TRUE
         NULL (CONS (X,L)) = FALSE
   END LIST

    С помощью определенных таким образом операций и аксиом формально определяется абстрактный тип данных: "список". Создание конкретных списков осуществляется таким образом, чтобы удовлетворить этим правилам.

    Тип данных является полным, если он обеспечивает достаточно операций для того, чтобы все требующиеся пользователю работы с объектами могли быть проделаны с приемлемой эффективностью. Строгое определение полноты дать невозможно, хотя существуют пределы относительно того, насколько мало операций может иметь тип, оставаясь при этом приемлемым.

    Полнота типа зависит от контекста использования. Если тип предполагается использовать в ограниченном контексте (таком, как, например, одна программа), то должно быть обеспечено достаточно операций для этого контекста. Если тип предназначен для общего использования, желательно иметь богатый набор операций [8, с.98].

    Операции абстракции данных распадаются на 4 класса [8, c.97].

1. Примитивные конструкторы.

Эти операции создают объекты соответствующего типа, не используя никаких объектов в качестве аргумента (например, создание пустого списка). Обычно примитивные конструкторы создают не все, а только некоторые объекты. Другие объекты создаются конструкторами или модификаторами.

2. Конструкторы.

Эти операции используют в качестве аргументов объекты соответствующего им типа и создают другие объекты такого же типа.

3. Модификаторы.

Эти операции модифицируют объекты соответствующего им типа (например, операции вставка и удаление).

4. Наблюдатели (селекторы).

Эти операции используют в качестве аргументов объекты соответствующего им типа и возвращают результат другого типа. Они используются для получения информации об объектах. Иногда наблюдатели комбинируются с конструкторами или модификаторами.

    В общем случае абстракция данных должна иметь операции по крайней мере трех из четырех рассмотренных ранее классов. Она должна иметь примитивные конструкторы, наблюдатели и либо конструкторы (если она неизменяемая), либо модификаторы (если изменяемая) [8, с.98].

    На следующем шаге мы рассмотрим создание и использование массивов.

Предыдущий шаг Содержание Следующий шаг