Операции абстрактного типа данных

При проектировании абстрактного типа данных всегда необходимо решить две задачи

- определить представление и множество значений, и

- множество операций типа.

Абстрактный тип может описывать достаточно сложный объект реального мира и все его значения представляют собой домен множеств возможных значений, который проще задавать в терминах отдельных элементов. Например, для абстрактного типа «Студент», необходимо задать множество возможных значений его имени, его фамилии, номера группы, номера зачётки. Здесь имя, фамилия, номер группы и номер зачётки – представляют собой элементы объекта «Студент». Задав длины элементов и наборы символов, из которых эти элементы могут составляться, можно говорить о том, что задано множество значений абстрактного типа «Студент».

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

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

- конструкторы (порождают все множество возможных значений типа),

- операции инициализации (начальные конструкторы, которым безразлично исходное значение объекта),

- создания, удаления (позволяют занять или освободить память объекта);

- операции копирования значения типа;

- операции селекторы (обеспечивают доступ к частям объекта);

- операции сравнения значений;

- операции преобразования типов;

- операции ввода/вывода.

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

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

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

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

В нашем случае, можно определить операцию создания

Create_Fraction(FRACTION Object);

в функции которой бы вменялось бы инициализировать и числитель и знаменатель дроби. Причём, числитель (Numerator) обнуляется, а знаменатель (Denominator) устанавливается в единицу. Таким образом, операция создания может одновременно рассматриваться как начальный конструктор.

В свою очередь, часто бывают нужны операции доступа к значению числителя или знаменателя дроби по-отдельности. Это типичные операции селекторы, которые, в свою очередь, можно ещё и рассматривать как преобразователи типа. Так как они из дроби получают целое число.

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

Операции преобразования типов абсолютно необходимы в языках программирования со строгой типизацией. Однако и в любом абстрактном типе эти операции полезны, т.к. дают прогнозируемый результат. При проектировании операций преобразования не нужно стремиться охватить все типы. Например, для дроби может потребоваться только операция проверки знака, приводящая дробь к логическому значению (0, 1) или типу BOOL (TRUE, FALSE).

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

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

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

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

При проектировании набора операций очень важно сохранять взаимосвязь проектируемых операций со свойствами самого абстрактного объекта. Например, в случае «Студент», вполне осуществимой операцией может быть прибавление числа к номеру зачётки, однако такая операция не согласуется с абстракцией типа «Студент». А прибавление единицы к числителю дроби (FRACTION) может быть вполне оправдано.

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

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

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

- Должна быть обеспечена возможность проверки предусловий каждой
экспортируемой операции.

- Следует оценить целесообразность включения в АТД следующих операций:

• операции создания;

• операции инициализации;

• операции перемещения (копирования структуры);

• операции проверки;

• операции преобразования типов;

• операции ввода-вывода;

• операции копирования (значений);

• операции-селекторы;

• операции уничтожения.

- Старайтесь свести число операция к минимуму. Простой АТД проще понять.

- Поддерживайте связь операций с выбранной абстракцией типа.

Дата добавления: 2014-12-26