Тип данных описывает множество объектов со схожими свойствами. Все традиционные языки программирования используют набор базовых типов данных (real, integer, string, character). Базовые типы данных подчиняются предопределенному набору операций. Например, базовый тип данных integer позволяет выполнять такие операции, как сложение, вычитание, умножение, деление.

В традиционные языки программирования включаются конструкторы типов, самым распространенным из которых является конструктор record. Например, для записи типа CUSTOMER можно определить поля данных. Запись CUSTOMER будет представлять собой новый тип данных, в котором будет храниться информация о клиенте, можно напрямую получать доступ к этой структуре данных, ссылаясь на имена полей. Над записью можно выполнять такие операции, как WRITE, READ, DELETE, UPDATE. Для базовых типов данных определить новые операции нельзя.

Как и базовые типы данных, абстрактные типы данных (ATD, abstract data types) описывают множество схожих объектов. Есть отличия ATD от традиционного типа данных:

· операции под ATD определяются пользователем;

· ATD не допускают непосредственного доступа к внутреннему представлению данных и реализации методов.

В некоторых ОО-системах (например, Smalltalk) базовые типы данных реализованы как абстрактные.

Для создания абстрактного типа данных необходимо обеспечить:

· имя типа;

· представление данных или переменные экземпляра объекта, принадлежащего ATD; каждая переменная экземпляра имеет тип данных, который может быть либо базовым типом, либо другим ATD;

· операции под ATD и ограничения реализуются с помощью методов.

Определение ATD перестраивает определение класса. В некоторых ОО-системах для различения классов и типов при ссылки на структуры данных и методы класса используется ключевое слово type, а при ссылке на набор экземпляров объекта - ключевой слово class. Тип (type) более статичное понятие, а class связан в основном со временем выполнения. Отличие ОО-класса от ОО-типа можно проиллюстрировать на примере. Предположим, имеется шаблон для конструктора. К шаблону прилагается описание его структуры, а также инструкция по его использованию. Этот шаблон и есть описание типа (type definition). Комплект сделанных с помощью шаблона реальных изделий, каждое из которых имеет уникальный номер (или OID), составляет класс (class).

ATD совместно с наследованием позволяют создавать сложные объекты. Сложный объект (complex object) формируется путем комбинации других объектов, находящихся в сложных взаимосвязях друг с другом. Пример сложного объекта можно найти в системах безопасности, где используются различные типы данных:

1. стандартные (табличные) данные о сотруднике (ФИО, Таб. № и т.д.);

2. битовая карта для хранения фотографии сотрудника;

Возможность относительно просто работать с такой сложной средой данных повышает значение ОО-систем на современном рынке баз данных.

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

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

Рассмотрим реализацию понятия даты с использованием struct для того, чтобы определить представление даты date и множества функций для работы с переменными этого типа:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include
struct date
{
int month; // месяц
int day; // день
int year; // год
};
void set_date(date* f, int d, int m, int y)
{
f->day = d;
f->month = m;
f->year = y;
}
void print_date(date* f)
{
printf("%d.%d.%d" , f->day, f->month, f->year);
}
int main()
{
date today;
set_date(&today, 2, 4, 2014);
print_date(&today);
getchar();
return 0;
}


Результат выполнения

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include
struct date
{
int month; // месяц
int day; // день
int year; // год
void set_date(int d, int m, int y)
{
day = d; month = m; year = y;
}
void print_date(void );
};
void date::print_date(void )
{
printf("%d.%d.%d" , day, month, year);
}
int main()
{
date today;
today.set_date(2, 4, 2014);
today.print_date();
getchar();
return 0;
}

Функции-члены и данные-члены

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

Определение функций-членов может осуществляться двумя способами:

  • описание функции непосредственно при описании структуры;
  • описание функции вне структуры.

Функции-члены, которые определены внутри структуры, являются неявно встроенными (). Как правило, только короткие, часто используемые функции-члены, должны определяться внутри структуры:

void set(int m, int d, int y) {month = m; day = d; year = y;};



Поскольку разные структуры могут иметь функции-члены с одинаковыми именами, при определении функции члена необходимо указывать имя структуры, связывая их с помощью оператора разрешения контекста (двойное двоеточие)::
тип АТД::имя(список аргументов) {
тело функции-члена; }
  • тип — тип возвращаемого значения функции-члена
  • АТД — имя абстрактного типа данных (имя структуры или класса)
  • имя — имя функции-члена

void date::print_date(void )
{ printf("%d.%d.%d" ,day, month, year);}

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

Функции-члены, одной и той же структуры могут быть полиморфными, то есть перегруженными.

Права доступа

Концепция структуры в языке С++ (в отличие от Си) позволяет членам структуры быть общими, частными или защищенными:

  • public – общие;
  • private – частные;
  • protected – защищенные.

Использование ключевого слова protected связано с понятием наследования .

Использование ключевого слова private ограничивает доступ к членам, которые следуют за этой конструкцией. Члены private могут использоваться только несколькими категориями функций, в привилегии которых входит доступ к этим членам. В основном это функции-члены той же структуры.
Ключевое слово public образует интерфейс к объекту структуры.

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

Изменим структуру date так, чтобы скрыть представление данных (инкапсуляция данных):

1
2
3
4
5
6
7
8

struct date
{
private :
int month, day, year;
public :
void set(int , int , int );
void print();
};

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

Все вычислительные системы основаны на уровнях абстракции: определенные физические свойства кремния и других материалов позволяют принять абстрактную модель бита, который может принимать двоичные значения 0-1; затем на динамических свойствах значений определенного набора битов строится абстрактная модель машины; далее, на основе принципа работы машины под управлением программы на машинном языке строится абстрактная модель языка программирования; и, наконец, строится абстрактное понятие алгоритма, реализуемое в виде программы на языке C++. Абстрактные типы данных дают возможность продолжать этот процесс дальше и разрабатывать абстрактные механизмы для определенных вычислительных задач на более высоком уровне, чем это обеспечивается системой C++, разрабатывать абстрактные механизмы , ориентированные на конкретные приложения и подходящие для решения задач в многочисленных прикладных областях, а также создавать абстрактные механизмы более высокого уровня, в которых используются эти базовые конструкции. Абстрактные типы данных предоставляют в наше распоряжение расширяемый до бесконечности набор инструментальных средств для решения все новых и новых задач.

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

Для разработки нового уровня абстракции потребуется (1) определить абстрактные объекты, с которыми необходимо манипулировать, и операции , которые должны выполняться над ними; (2) представить данные в некоторой структуре данных и реализовать операции ; (3) и (самое главное) обеспечить, чтобы эти объекты было удобно использовать для решения прикладных задач. Эти пункты применимы и к простым типам данных, так что базовые механизмы для поддержки типов данных, которые были рассмотрены в "Элементарные структуры данных" , можно адаптировать для наших целей. Однако язык C++ предлагает важное расширение механизма структур, называемое классом ( class ). Классы исключительно полезны при создании уровней абстракции и поэтому рассматриваются в качестве основного инструмента, который используется для этой цели в оставшейся части книги.

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

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

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

В качестве примера рассмотрим интерфейс типа данных для точек ( программа 3.3) из раздела 3.1 "Элементарные структуры данных" . В этом интерфейсе явно объявляется, что точки представлены как структуры, состоящие из пары чисел с плавающей точкой, обозначаемых x и у. Подобное применение типов данных является обычным в больших системах программного обеспечения: мы разрабатываем набор соглашений о представлении данных (а также определяем ряд связанных с ними операций) и делаем эти правила доступными через интерфейс , чтобы ими могли пользоваться клиентские программы, входящие в состав большой системы. Тип данных обеспечивает согласованность всех частей системы с представлением основных общесистемных структур данных. Какой бы хорошей такая стратегия ни была, она имеет один изъян: если необходимо изменить представление данных , то потребуется изменить и все клиентские программы. Программа 3.3 снова дает нам простой пример: одна из причин разработки этого типа данных - удобство работы клиентских программ с точками, и мы ожидаем, что в случае необходимости у клиентов будет доступ к отдельным координатам точки. Но мы не можем перейти к другому представлению данных (скажем, к полярным координатам, или трехмерным координатам, или даже к другим типам данных для отдельных координат) без изменения всех клиентских программ.

В отличие от этого, программа 4.1 содержит реализацию абстрактного типа данных, соответствующего типу данных из программы 3.3, но с использованием класса языка C++, в котором сразу определены как данные, так и связанные с ними операции . Программа 4.2 является клиентской программой, работающей с этим типом данных. Эти две программы выполняют те же самые вычисления, что и программы 3.3 и 3.8. Они иллюстрируют ряд основных свойств классов, которые мы сейчас рассмотрим.

Когда мы пишем в программе определение наподобие int i, мы указываем системе зарезервировать область памяти для данных (встроенного) типа int , к которой можно обращаться по имени i. В языке C++ для подобных сущностей имеется термин объект . При записи в программе такого определения, как POINT p, говорят, что создается объект класса POINT , к которому можно обращаться по имени p. В нашем примере каждый объект содержит два элемента данных, с именами x и у. Как и в случае структур, к ним можно обращаться по именам вроде p.y.

Элементы данных x и у называются данными-членами класса. В классе могут быть также определены функции-члены, которые реализуют операции , связанные с этим типом данных. Например, класс , определенный в программе 4.1, имеет две функции-члена с именами POINT и distance .

Клиентские программы, такие как программа 4.2, могут вызывать функции-члены, связанные с объектом, указывая их имена точно так же, как и имена данных, находящихся в какой-нибудь структуре struct. Например, выражение p.distance(q) вычисляет расстояние между точками p и q (такое же расстояние должен возвращать и вызов q.distance(p) ). Функция POINT() - первая функция в программе 4.1 - является особой функцией-членом, называемой конструктором: у нее такое же имя, как и у класса, и она вызывается тогда, когда требуется создать объект этого класса.

Программа 4.1. Реализация класса POINT (точка)

В этом классе определен тип данных , который состоит из набора значений, представляющих собой "пары чисел с плавающей точкой" (предполагается, что они интерпретируются как точки на декартовой плоскости), а также две функции-члена, определенные для всех экземпляров класса POINT : функция POINT() , которая является конструктором, инициализирующим координаты случайными значениями от 0 до 1, и функция distance(POINT) , вычисляющая расстояние до другой точки. Представление данных является приватным ( private ), и обращаться к нему или модифицировать его могут только функции-члены. Сами функции-члены являются общедоступными ( public ) и доступны для любого клиента. Код можно сохранить, например, в файле с именем POINT .cxx.

#include class POINT { private: float x, у; public: POINT() { x = 1.0*rand()/RAND_MAX; у = 1.0*rand()/RAND_MAX; } float distance(POINT a) { float dx = x-a.x, dy = y-a.y; return sqrt(dx*dx + dy*dy); } };

Программа 4.2. Программа-клиент для класса POINT (нахождение ближайшей точки)

Эта версия программы 3.8 является клиентом, который использует АТД POINT , определенный в программе 4.3. Операция new создает массив объектов POINT (вызывая конструктор POINT () для инициализации каждого объекта случайными значениями координат). Выражение a[i].distance(a[j]) вызывает для объекта a[i] функцию-член distance с аргументом a[j] .

#include #include #include "POINT.cxx" int main(int argc, char *argv) { float d = atof(argv); int i, cnt = 0, N = atoi(argv); POINT *a = new POINT[N]; for (i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (a[i].distance(a[j]) < d) cnt+ + ; cout << cnt << " пар в радиусе " << d << endl; }

Определение POINT p в программе-клиенте приводит к выделению области памяти под новый объект и затем (с помощью функции POINT() ) к присвоению каждому из двух его элементов данных случайного значения в диапазоне от 0 до 1.

Этот стиль программирования, который иногда называется объектно-ориентированным программированием, полностью поддерживается конструкцией class языка C++. Класс можно считать расширением понятия структуры, где не только объединяются данные, но и определяются операции с этими данными. Может существовать много разных объектов, принадлежащих одному классу, но все они подобны в том, что их данные-члены могут принимать один и тот же набор значений, и с этими данными-чле-нами может выполняться одна и та же совокупность операций - в общем, это экземпляры одного и того же типа данных. В объектно-ориентированном программировании объекты предназначены для обработки своих данных-членов (в отличие от использования независимых функций для обработки данных, хранимых в объектах).

Мы рассматриваем описанный выше пример небольшого класса просто чтобы познакомиться с основными чертами классов; поэтому он далеко не полон. В реальном коде для класса точки у нас будет намного больше операций. Например, в программе 4.1 отсутствуют даже операции , позволяющие узнавать значения координат x и y . Как мы увидим, добавление этих и других операций - довольно простая задача. В части 5 мы более подробно рассмотрим классы для точки и других геометрических абстракций, например, линий и многоугольников.

В языке C++ (но не в С) у структур также могут быть связанные с ними функции. Ключевое различие между классами и структурами связано с доступом к информации, который характеризуется ключевыми словами

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

Абстрактный тип данных (АТД) определяется независимо от способа его реализации:

    множеством возможных значений этого типа,

    и набором операций со значениями этого типа.

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

    способ представления значений этого типа,

    и реализацию операций со значениями этого типа.

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

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

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

В исследованиях по абстрактным типам данных уже на раннем этапе была осознана важная роль понятия «параметризация типа ». Действительно, например АТД «Стек» не зависит от типа элементов стека, но реализовать этот АТД указанием на «элементы какого-то одинакового типа» невозможно. В язык программирования Ada соответствующие средства конструирования параметризованных типов данных были включены изначально, а в современных «практических языках программирования» какие средства появились только со времен появления разработки по STL-библиотеке . На сегодня понятие «обобщенное программирование» занимает значимое положение в практическом программировании благодаря включению в «практические языки программирования» средств конструирования параметризованных типов данных (шаблоны, template , generic) .

Всё вышесказанное означает, что с методологической и теоретической точки зрения необходимо более детальное точное определение понятия «абстрактный тип данных». В теории понятие «абстрактный тип данных» обычно определяется как многосортная (многоосновная) алгебраическая система , в которой дополнительно к множеству возможных значений (носителю) и набору операций над такими значениями выделены понятия:

    Сорт и сигнатура – эти понятия позволяют расклассифицировать и элементы носителя и операции с ними по их типам (для операций - по типам их аргументов и возвращаемого значения).

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

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

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

Но все же мы будем различать эти два понятия, учитывая:

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

    Структура данных - скорее некоторая схема организации данных и управления ими, которая предполагает соответствующие конкретизации при ее использовании в конкретных ситуациях при решении конкретных задач.

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

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

Абстрактный тип данных (АТД) определяется независимо от способа его реализации:

§ множеством возможных значений этого типа,

§ и набором операций со значениями этого типа.

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

§ способ представления значений этого типа,

§ и реализацию операций со значениями этого типа.

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

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

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



В исследованиях по абстрактным типам данных уже на раннем этапе была осознана важная роль понятия «параметризация типа ». Действительно, например АТД «Стек» не зависит от типа элементов стека, но реализовать этот АТД указанием на «элементы какого-то одинакового типа» невозможно. В язык программирования Ada соответствующие средства конструирования параметризованных типов данных были включены изначально, а в современных «практических языках программирования» какие средства появились только со времен появления разработки по STL-библиотеке . На сегодня понятие «обобщенное программирование» занимает значимое положение в практическом программировании благодаря включению в «практические языки программирования» средств конструирования параметризованных типов данных (шаблоны, template , generic) .

Всё вышесказанное означает, что с методологической и теоретической точки зрения необходимо более детальное точное определение понятия «абстрактный тип данных». В теории понятие «абстрактный тип данных» обычно определяется как многосортная (многоосновная) алгебраическая система , в которой дополнительно к множеству возможных значений (носителю) и набору операций над такими значениями выделены понятия:

§ Сорт и сигнатура – эти понятия позволяют расклассифицировать и элементы носителя и операции с ними по их типам (для операций - по типам их аргументов и возвращаемого значения).

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

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

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

Но все же мы будем различать эти два понятия, учитывая:

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

§ Структура данных - скорее некоторая схема организации данных и управления ими, которая предполагает соответствующие конкретизации при ее использовании в конкретных ситуациях при решении конкретных задач.

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

2.1. Последовательность (Sequence).

Бесконечная (конечная) последовательность формально определяется как функция, областью определения которой является множество положительных целых чисел: f(i)= , . Во многих случаях индексирование последовательности более удобно начинать с нуля; тогда областью определения / будет множество целых неотрицательных чисел. Аналогично определим конечную последовательность или список как функцию, областью определения которой является множество {1, 2, ..., }.

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

¨ Множество возможных значений – конечные последовательности элементов одинакового типа.

¨ Набор операций:

§ Вставить элемент в последовательность.

§ Удалить элемент из последовательности.

§ Посмотреть – функция, возвращающая значение элемента последовательности.

Разновидности этого вида АТД различаются способом доступа к элементам последовательности и ограничениями на место вставки и удаления элементов.

Для АТД этого вида стек (stack) , очередь (queue) и дек (deque от Double Ended Queue - двусторонняя очередь) характерно разрушающее чтение , т.к. доступ к элементам (для всех трех операций) ограничен одним из концов последовательности и операцию «посмотреть другой элемент» можно выполнить, только удалив мешающие этому элементы. Для АТД вектор(array, vector),файл (file) и линейный список (linear list) ограничения на доступ обеспечивают неразрушающее чтение , поэтому особое значение имеет (производная) операция просмотра последовательности .

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

Понятия «номер» и «позиция» элемента – близкие, но могут не совпадать:

§ Номер - это собственно порядковый номер элемента в последовательности. Но порядковый номер элемента изменяется в результате выполнения операций вставки и удаления предшествующих элементов, это создает ряд неудобств в идентификации элементов последовательности.

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

Для АТД «Последовательность» представляют интерес дополнительные операции вида: сцепить две последовательности, расцепить на две последовательности. Например, в АТД строка(string) такого вида операции фактически являются основными.

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

2.2. Множество (Set).

¨ Множество возможных значений – конечные множества элементов одинакового типа.

¨ Набор операций:

§ Вставить элемент во множество.

§ Удалить элемент из множества.

§ Принадлежать – функция, возвращающая значение true, если элемент принадлежит множеству.

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

Специализированные расширения АТД «Множество» рассматриваются в различных направлениях:

§ Близким к понятию «множество» является понятие «набор». Набор (Bag, MultiSet) – также как и множество является семейством элементов, безотносительно к тому задано ли на элементах отношение порядка, но элементы в наборе могут повторяться по значению. Вообще говоря, набор можно представить множеством, например, элементы которого являются парами [значение элемента, количество вхождений в набор].

§ В практических приложениях часто элементы множеств идентифицируются, т.е. элемент является парой [ключ элемента, собственно значение элемента], АТД «Словарь» - пример такого специализированного расширения АТД «Множество». Предпочтительный случай, когда ключ элемента – уникальный , т.е. множество не может содержать двух элементов с одинаковым ключом. Но возможно, что используемый ключ неуникальный, т.е. неоднозначно идентифицирущий собственно значение элемента. Вообще говоря, множество (и набор) с неуникальным ключом можно представить множеством с уникальным ключом, усложнив тип значения элемента, например, рассматривая в качестве значения элемента множество значений предыдущего типа (с одинаковым ключом).

§ Естественным представляется задание на множестве отношения порядка, частичного или линейного, АТД «Очередь с приоритетом» - пример такого специализированного расширения АТД «Множество». Аналогично в предметной области решаемой задачи могут представлять интерес и другие отношения на множестве .

§ Фундаментальное положение в математике занимает понятие отношение эквивалентности и соответственно – понятие разбиение множества на классы эквивалентности. Естественно, что это понятие широко используется и в практических разработках моделей решения задач предметных областей. АТД «Семейство непересекающихся множеств» (Disjoint Sets, Partitions, Разбиения) - пример соответствующего специализированного расширения АТД «Множество».

Для специализированных расширений АТД «Множество» естественно соответствующим образом уточняются вышеотмеченные операции и появляются свои новые операции, представляющие интерес.

2.3. Словарь (Dictionary, Map), другое название – ассоциативный массив .

¨ Множество возможных значений – конечные множества элементов одинакового типа, вида , где Key – уникальный ключ элемента, Value - собственно значение.

¨ Набор операций:

§ Вставить элемент (с ключом) во множество.

§ Удалить элемент (заданный ключом) из множества.

§ Найти элемент – функция, возвращающая по ключу значение элемента или «пустое» значение, если элемента с таким ключом нет во множестве.

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

2.4. Очередь с приоритетом (Priority queue).

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

Отметим, что такое множество возможных значений можно трактовать и как множество последовательностей (с перечислением её элементов в заданном линейном порядке).

¨ Набор операций:

§ Вставить элемент в (линейно упорядоченное) множество.

§ Удалить минимальный элемент из множества.

§ Найти минимальный – функция, возвращающая значение минимального элемента во множестве.

Рассматриваются также (существенные) вариации этого АТД с дополнительными операциями:

§ Расцепить очередь на две по заданному значению (приоритету) элемента – на очередь элементов с меньшим приоритетом и очередь остальных.

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

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

§ Уменьшить значение (приоритет) заданного элемента.

§ Удалить (произвольно) заданный элемент из множества.

2.5. Непересекающиеся множества (Disjoint Sets, Partitions, Разбиения) .

¨ Множество возможных значений – конечные множества (семейства) непересекающихся конечных множеств. Элементы семейства идентифицированы, т.е. каждое множество из семейства имеет (уникальное) имя.

¨ Набор операций:

§ Объединить(А,В) – операция вида А:= А È В без сохранения исходных объединяемых множеств (а значит новое значение семейства останется семейством непересекающихся множеств, причем их количество уменьшится).

§ Найти множество – функция, возвращающая для заданного х имя такого множества Х в семействе, что х Î Х.

2.6. Деревья, графы и отношения общего вида.

В дискретной математике особое внимание уделяется (конечным) отношениям вида - дерево, граф и сеть (мультиграф, гиперграф), имеющим определенно выраженную геометрическую трактовку:

¨ Граф – (конечное) бинарное отношение (симметричное – в случае неориентированных графов), E Í V 2 , где V – множество вершин, а E – множество ребер графа.

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

¨ Дерево – это бинарное отношение (строгого) частичного порядка, дополнительно удовлетворяющее требованиям (иерархичности, древесности):

§ из того, что х<у,z следует, что у и z сравнимы, т.е. либо у£z либо z£у (х<у трактуется как: х встречается раньше у в пути к корню дерева, х – потомок, у - предок);

§ во множестве V (вершин дерева) существует наибольший элемент (корень дерева).

Деревья можно различать, если порядок сыновей (хотя бы для одной) вершины дерева различен. Упорядоченное дерево – дерево, в котором для каждой вершины задан порядок на множестве дочерних вершин, т.е. детей можно определить как первый, второй и т.д.

¨ Сеть – это отношение общего вида, которое можно трактовать как обобщение – E Í VÈV 2 È...V k , а можно – как отношение (E Í V k) с множеством элементов V, имеющим «пустой» (фиктивный) элемент.

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

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