Спецификация и реализация АТД

Исходя из сказанного, понятно, что определение абстрактного типа данных должно состоять из двух четко отделенных друг от друга частей:

внешнее описание АТД, доступное клиентам (такое описание называют функциональной спецификацией  или просто спецификацией);

 реализация операций на конкретном языке программирования (или просто реализация), скрытая от клиентов.

Подчеркнем два основных преимущества отделения спецификации от реализации.

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

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

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

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

Один из наиболее распространенных способов описания основан на алгебраическом подходе [17]. Идея состоит в том, что определяется список операций данного АТД, при этом для каждой операции задается множество входных данных (аргументы) и множество выходных значений (результаты). Таким образом, множество значений определяется через множество операций. Для уточнения смысла каждой операции и для определения связей между различными операциями дополнительно задается совокупность формальных правил в виде алгебраических формул (их принято называть аксиомами). Семантику каждой операции можно задать дополнительно, используя так называемые тройки Хоара {Предусловие Операция Постусловие}, где предусловие и постусловие — логические выражения. Такую тройку можно рассматривать как формулу, при этом если предусловие истинно, то после выполнения операции гарантируется истинность постусловия. Более подробную информацию по формальному описанию АТД можно найти в [2].

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

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

Современные языки программирования позволяют реализовать другой подход, получивший название объектно-ориентированного, предоставляя в распоряжение разработчика специальный тип данных — класс (в языке С++ объектно-ориентированный подход может быть реализован и с использованием структур). Классы идеально подходят для реализации АТД, поскольку соединяют данные (поля) и функции их обработки (методы). Различие между структурным и объектно-ориентированным подходом к реализации АТД показано на рис.1.5.

Рис.1.1. Различные подходы к реализации АТД

В действительности объектно-ориентированный подход является развитием структурного подхода, поэтому не следует противопоставлять их друг другу. В примерах данного пособия будет использоваться объектно-ориентированный подход там, где это уместно. Во многих случаях будет использован структурный подход, чтобы привлечь максимум внимания к структурам данных и алгоритмам их обработки.

1.3. Структуры данных

Понятие структуры данных

Наиболее общим и фундаментальным понятием в определении данных является понятие структуры данных.

  Определим структуру данных как совокупность элементов данных, между которыми установлены определенные отношения (связи) [14].

Это определение имеет столь общий характер, что может использоваться в различных случаях, имея несколько разный смысл.   Рассмотренные выше конструируемые типы данных обычно относят к элементарным структурам данных. Возможно, по этой причине конструируемые типы данных часто называют структурированными, а запись в языке С называется структурой. В дальнейшем не будем путать структуры в смысле языка С со структурами данных в широком понимании.

Кроме структурированных типов данных имеется еще ряд структур данных, которые относят к элементарным или базовым, хотя в большинство языков программирования не встроена их явная поддержка. Эти структуры будут подробно рассмотрены в следующих разделах, а затем будут использоваться как элементарные кирпичики при конструировании более сложных структур данных или описании алгоритмов.

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

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

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