Абстрактный тип данных

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

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

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

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

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

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

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

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

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

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

Create Fraction(FRACTION Object);  
    

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

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

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

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

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

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

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

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

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

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

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

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

5.3. Реализация абстрактного типа

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

Утверждения (предусловия, постусловия и инварианты модуля) в модуле определения называют абстрактными утверждениями. Они - суть требования или спецификация модуля как для разработчика, так и для клиента. Все условия, расположенные в модуле реализации, называют утверждениями реализации. Если модуль корректен, то все абстрактные утверждения поддерживаются утверждениями реализации.

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

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

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

Код будет организован в виде двух файлов - заголовка "fraction.h" и файла реализации "fraction.c":

----- файл fraction.h -----
/*******************************************************
Date: 10 January 2013
Description: fraction type
******************************************************/
typedef struct
{
  int numerator;
  int denominator;
} Fraction;
/*******************************************************
* Name : initF
* Purpose : initialize fraction
* Input : num – numerator
* denum – denominator
* Output : none,
* wasErr() can be called after,
* to test whether the result is correct
* Return : initialized fraction
******************************************************/
Fraction initF(int num, int denum);
/*******************************************************
* Name : isNullF
* Purpose : test fraction to be 0
* Input : f – fraction
* Output : none
* Return : 1 – if is f=0, 0 – if f!=0
*
******************************************************/
int isNullF(Fraction f);
/*******************************************************
* Name : compareF
* Purpose : compares two fractions
* Input : f1, f2 – two fractions
* Output : none
* Return : 1 – f1<f2,0 – f1=f2, -1 f1<f2
******************************************************/
int compareF(Fraction f1, Fraction f2);
/*******************************************************
* Name : addF
* Purpose : adds fractions  
* Input : f1, f2 – two fractions
* Output : none
* Return : fraction (sum of f1 and f2)
******************************************************/
Fraction addF(Fraction f1, Fraction f2);
/*******************************************************
* Name : subF
* Purpose : substracts fractions
* Input : f1, f2 – two fractions
* Output : none
* Return : fraction (substruction of f1 and f2)
******************************************************/
Fraction subF(Fraction f1, Fraction f2);
/*******************************************************
* Name : multF
* Purpose : multiplyes fractions
* Input : f1, f2 – two fractions
* Output : none
* Return : fraction (multiplication of f1 and f2)
*****************************************************/
Fraction multF(Fraction f1, Fraction f2);
/*******************************************************
* Name : divF
* Purpose : divedes fractions
* Input : f1, f2 – two fractions
* Output : none,
* wasErr() can be called after,
* to test whether the result is correct
* Return : fraction (division of f1 and f2)
******************************************************/
Fraction divF(Fraction f1, Fraction f2);
/*******************************************************
* Name : convertFromIntF
* Purpose : converts int type to fraction
* Input : num – number to convert
* Output : none
* Return : fraction
******************************************************/
Fraction convertFromIntF(int num);
/*******************************************************
* Name : convertToDoubleF
* Purpose : converts fraction to double type
* Input : f – fraction to convert
* Output : none
* Return : double type number
******************************************************/
double convertToDoubleF(Fraction f);
/*******************************************************
* Name : getNumeratorF
* Purpose : returns fraction numerator
* Input : f – fraction to convert
* Output : none
* Return : numerator
******************************************************/
int getNumeratorF(Fraction f);
/*******************************************************
* Name : getDenomimantor
* Purpose : returns fraction denominator
* Input : f – fraction to convert
* Output : none
* Return : denominator
******************************************************/
int getDenomimantor(Fraction f);
/*******************************************************
* Name : wasErr
* Purpose : test whether previous function
* returned correct result
* WORKS ONLY AFTER initF, divF
* Input : none
* Output : none
* Return : none
******************************************************/
int wasErr();
void printF(Fraction f);
----- файл fraction.h -----
#include "fraction.h"
int wasError;
Fraction initF(int num, int denum)
{
  Fraction f;
  if (denum > 0)
  {
    f.numerator = num;
    f.denominator= denum;
    shorten(f);
    wasError = 0;
  } else
  {
    wasError = 1;
  }
  return f;
}
int isNullF(Fraction f)
{
  if (f.numerator == 0)
  {
    return 1;
  } else
  {
    return 0;
  }
}
int compareF(Fraction f1, Fraction f2)
{
  Fraction f;
  f = subF(f1,f2);
  if (f.numerator > 0)
  {
    return 1;
  } else
  {
    if (f.numerator < 0)
    {
      return -1;
    } else
    {
      return 0;
    }
  }
}
Fraction addF(Fraction f1, Fraction f2)
{
  Fraction res;
  res.numerator = (f1.numerator*f2.denominator) +
      (f2.numerator*f1.denominator);
  res.denominator = f1.denominator*f2.denominator;
  shorten(res);
  return res;
}
Fraction subF(Fraction f1, Fraction f2)
{
  Fraction res;
  res.numerator = (f1.numerator*f2.denominator) -
      (f2.numerator*f1.denominator);
  res.denominator = f1.denominator*f2.denominator;
  return res;
}
Fraction multF(Fraction f1, Fraction f2)
{
  Fraction res;
  res.numerator = f1.numerator*f2.numerator;
  res.denominator = f1.denominator*f2.denominator;
  return res;
}
Fraction divF(Fraction f1, Fraction f2)
{
  Fraction res;
  res.numerator = f1.numerator*f2.denominator;
  res.denominator = f1.denominator*f2.numerator;
  if (res.denominator != 0)
  {
  wasError = 0;
  } else
  {
    wasError = 1;
    res.numerator = 0;
    res.denominator = 1;
  }
  return res;
}
Fraction convertFromIntF(int num)
{
  Fraction res;
  res.numerator = num;
  res.denominator = 1;
  return res;
}
double convertToDoubleF(Fraction f)
{
  return ((double)f.numerator / (double)f.denominator);
}
int getNumeratorF(Fraction f)
{
  return f.numerator;
}
int getDenomimantor(Fraction f)
{
  return f.denominator;
}
long gcd(long a, long b)
{
  a = labs(a);
  b = labs(b);
  while ((a!=0)  (b!=0))
  {
    if (a > b)
  {
    a = a - b;
  } else
    {
      b = b - a;
    }
  }
  if (a!= 0)
  {
    return a;
  } else
  {
    return b;
  }
}
void shorten(Fraction *f)
{
  int div;
  div = (int)gcd((long)(*f).numerator,
        (long)(*f).denominator);
  (*f).numerator = (*f).numerator / div;
  (*f).denominator = (*f).denominator / div;
}
void shortenLong(long num, long denum, long *resNum,
        long *resDenum)
{
  long div;
  div = gcd(num, denum);
  *resNum = num / div;
  *resDenum = denum / div;
}
int wasErr()
{
  return wasError;
}
void printF(Fraction f)
{
  printf("%d/%d",f.numerator, f.denominator);
}
    

Пример использования:

/******************************************************
date: 10 January 2013
description: string reading and encoding sample
******************************************************/
#include <stdio.h>
#include "fraction.h"
int main()
{
  Fraction f1, f2, f3;
  f1 = initF(8,16);
  f2 = initF(2,1);
  f3 = addF(f1,f2);
  printf("f1: ");
  printF(f1);
  printf("\n");
  printf("f2: ");
  printF(f2);
  printf("\n");
  printf("f3: ");
  printF(f3);
  printf("\n");
  printf("f1 compare to f2: %d\n", compareF(f1,f2));
  printf("To double: %f\n",convertToDoubleF(f3));
  printf("Ended.");
  return 0;
}
/* Output:
f1: 1/2
f2: 2/1
f3: 1/1
f1 compare to f2: -1
To double: 1.000000
Ended. */
    

Для сокращения дроби в модуле реализована отдельная функция shorten, которая не указана в заголовочном файле fraction.h и является недоступной импортеру. Она используется только внутри самого модуля.

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

(MAXINT / 2 ) * (2 / MAXINT)  
    

дает результат 1/ 1, что не выходит за границы int, но в промежуточных вычислениях вполне возможно получение значения 2*MAXINT, не укладывающееся в int (здесь MAXINT - максимальное значение, которое может храниться в int).

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

(MAXINT / 3) + ((MAXINT + 1) / 3) = (2*MAXINT + 1) / 3  
    

если int занимает 4 байта, MAXINT = 2147483647. Это число не делится на 3, и дробь (MAXINT / 3) является сокращенной. Число 2147483648 (2147483647 + 1) тоже не делится на 3, и дробь ((MAXINT + 1) / 3) также является сокращенной. Однако дробь (2*MAXINT + 1) / 3 может быть сокращена, так как (2*MAXINT + 1) = 4294967295 делится на 3. При этом результат деления умещается в int.

Пример реализации, лишенной этой проблемы, может быть следующим:

Fraction addF2(Fraction f1, Fraction f2)
{
  Fraction res;
  long num, resNum;
  long denum, resDenum;
  num = (f1.numerator*f2.denominator) + (f2.numerator*f1.denominator);
  denum = f1.denominator*f2.denominator;
  shortenLong(num, denum, resNum, resDenum);
  res.numerator = (int) resNum;
  res.denominator = (int) resDenum;
  if ((res.numerator == resNum)  (res.denominator == resDenum))
  {
  wasError = 0;
  } else
  {
  wasError = 1;
  res.numerator = 0;
  res.denominator = 1;
  }
  return res;
}
void shortenLong (long num, long denum, long *resNum,
long *resDenum)
{
  long div;
  div = gcd(num, denum);
  *resNum = num / div;
  *resDenum = denum / div;
}  
    

Для сокращения значений увеличенной точности реализована отдельная функция shortenLong.

В модуле определяется переменная wasError, которая после каждой операции выставляется в 0, если операция выполнена корректно (т.е. получен ожидаемый результат), и wasError = 1, если операция не привела к ожидаемому результату или в ходе ее выполнения произошла ошибка. Например, при попытке деления дроби на нулевую дробь wasError выставляется в 1, а результирующая дробь равна 0/1.

5.4. Проблемы абстрактных типов данных

Модульное проектирование в совокупности с выделением абстрактных типов данных приводит к централизации управления типом в модуле и, как следствие, к более структурированному коду основной программы. Например, в программной системе требуется реализовать операции со стеком, т.е. с абстрактной структурой типа "список" с ограничением доступа (включение и извлечение) только на одном конце. Иногда такую процедуру обслуживания называют LIFO (Last In First Out).

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

Две основные операции PUSH и POP (включить и извлечь), очевидно, могут быть определены как void Push_Stack(char Item) и void Pop_Stack(char *ltem). Такое определение подчеркивает для программиста тот факт, что обе процедуры изменяют состояние стека.

Если процедуру извлечения определить как функцию char Pop_Stack (), то изменение стека (удаление из него верхнего элемента) скорее придется рассматривать как побочный эффект. Т.е., кроме прямого результата - вычисления значения, функция производит еще что- то, возможно, влияющее на ее глобальное окружение. С другой стороны, для вспомогательной функции просмотра элемента вершины стека форма char Check_Top () достаточно очевидна, так как измене-ние состояния стека при ее выполнении не происходит.

Полезно определить пару функций проверки (вычисления) предусловий для операций со стеком. int Is_Stack_Empty() - функция проверки пустого стека, int Is_Stack_Full() - функция проверки полностью заполненного стека.

Is_Stack_Empty () будет являться средством проверки возможности извлечь элемент из стека или обратиться к его верхнему элементу. Истинность этой функции запрещает применение операций Check_Top и Pop_Stack. В свою очередь, истинность функции Is_Stack_Full не разрешает применять операцию включения Push_Stack.

Проводя анализ введенных пяти операций рассматриваемого абстрактного типа, можно сделать вывод, что мы имеем операции-конструкторы: Push_Stack, Pop_Stack, которые можно рассматривать одновременно и как селекторы. "Чистый" селектор - Check_Top. Но и его можно еще рассматривать как преобразователь типа "стек" в "символ", что будет не совсем верно, так как сам стек не является в явном виде параметром операции. Кроме того, имеются типичные операции проверки предусловий Is_Stack_Empty и Is_Stack_Full.

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

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

По итогам наших рассуждений h-файл для модуля Char_Stack (char_stack.h) выглядит так:

----- файл char_stack.h -----
void Push_Stack(char Item);
/*====================================================
Операция записи символа в стек.
Предусловие Is_Stack_Full() == 0
Если предусловие нарушено,
состояние стека не изменяется.
=====================================================*/
void Pop_Stack(char *Item);
/*====================================================
Операция извлечения символа из стека.
Предусловие Is_Stack_Emty() == 0
Если предусловие нарушено,
состояние параметра не изменяется.
=====================================================*/
char Check_Top();
/*====================================================
Операция проверки символа, находящегося в вершине стека.
Предусловие Is_Stack_Emty() == 0
Если предусловие нарушено,
возвращается символ с кодом '/0'.
=====================================================*/
int Is_Stack_Empty();
/*====================================================
Операция проверки пустого стека.
Is_Stack_Emty() == 1, если в стеке нет ни одного элемента.
=====================================================*/
int Is_Stack_Full();
/*====================================================
Операция проверки пустого стека.
Is_Stack_Full() == 1, если стек заполнен полностью.
=====================================================*/  
    

Программный код самого модуля char_stack.c может выглядеть следующим образом:

----- файл char_stack.c -----
#include "char_stack.h"
define MAX_ITEM_NUMBER 20
char Stack[MAX_ITEM_NUMBER];
int Top = 0;     /* Изначально стек пуст */
void Push_Stack(char Item);
/*====================================================
Операция записи символа в стек.
=====================================================*/
{
  if (Is_Stack_Full() == 0) /* Если стек не полон */
  {       /* Включить элемент в стек */
    Stack[Top++] = Item;
  }
}
void Pop_Stack(char *Item);
/*====================================================
Операция извлечения символа из стека.
=====================================================*/
{
  if (Is_Stack_Emty() == 0) /* Если стек не пуст */
  { /* Извлечь элемент из стека */
    Item* = Stack[--Top];
  }
}
char Check_Top();
/*====================================================
Операция копирования символа из вершины стека.
=====================================================*/
{
  if (Is_Stack_Emty() == 0) /* Если стек не пуст */
  {       /* Копировать вершину стека */
    return( Stack[Top - 1]);
  }
  else     /* Если стек пуст */
  { /* Вернуть символ с нулевым кодом */
    return( '\0' );
  }
}
int   Is_Stack_Empty();
/*====================================================
Операция проверки пустого стека.
=====================================================*/
{
  return ( Top == 0 );
}
  int Is_Stack_Full();
/*====================================================
Операция проверки пустого стека.
=====================================================*/
{
  return ( Top == MAX_ITEM_NUMBER );
}  
    

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

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

Определение размера стека через константу MAX_ITEM_NUMBER позволяет упростить при необходимости изменение его размера. А применение операций Top++ при записи в стек и --Top при извлечении верхнего элемента обеспечивает компактность записи без потери наглядности.

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

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

Создание стека - установка указателя на его головной элемент. Пустому стеку соответствует значение указателя NILL. Включение нового элемента - создание структуры: значение, указатель на следующий; копирование включаемого значения в созданный элемент и подключение нового элемента в качестве вершины стека.

Что является отличительной чертой такого способа реализации АТД?

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

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

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

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

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

А=В;  
    

выглядит понятнее, чем

fraction_copy(A,B);  
    

Рассмотрим еще один пример реализации и использования абстрактного типа данных - множество. В некоторых языках программирования, например Modula-2, множество является стандартным типом данных, но в Си такой тип отсутствует. Для примера рассмотрим множество символов расширенной таблицы ASCII, т.е. элемен-тами множества могут быть любые символы char. Для хранения такого множества можно использовать массив с длиной, равной количеству всех значений char, т.е. 256 элементов. Для символов, принадлежащих конкретному множеству, значение элемента с номером, соответствующим ASCII-коду символа, устанавливается в единицу. Остальные элементы массива равны нулю.

Перед использованием множества следует обнулить массив, чтобы получить пустое множество. Далее путем добавления нужных элементов можно получить требуемое множество.

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

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

----- файл set.h -----
/*******************************************************
date: 10 January 2013
description: Set type
******************************************************/
/* Definition of the Set type */
typedef struct
{
  int elems[255];
} Set;
/*******************************************************
* Name : initSet
* Purpose : prepares the Set to work with
* (should be called before using Set variable)
* Input : s – new set
* Output : s – set prepared to work with
* Return : none
******************************************************/
void initSet(Set *s);
/*******************************************************
* Name : initFromStringSet
* Purpose : prepares the Set to work with
* (can be called instead of initSet(…) )
* Input : s – new set,
* str – string with elements to add to the set
* Output : s – set prepared to work with,
* containing elements from string str
* Return : none
******************************************************/
void initFromStringSet(Set *s, char *str)
/*******************************************************
* Name : addElemSet
* Purpose : adds the element to the set
* (if element already exists – does nothing)
* Input : s – set, elem – element to add
* Output : s – set with added element
* Return : none
******************************************************/
void addElemSet(Set *s, char elem);
/*******************************************************
* Name : removeElemSet
* Purpose : removes the element from the set
* (if element already exists – does nothing)
* Input : s – set, elem – element to delete
* Output : s – set with no element elem
* Return : none
******************************************************/
void removeElemSet(Set *s, char elem);
/*******************************************************
* Name : isInSet
* Purpose : check whether the element is in the set
* Input : s – set
* Output : none
* Return :
*   -1 is in set
*   0 is not in set
******************************************************/
int isInSet(Set s, char elem);
/*******************************************************
* Name : unionSet
* Purpose : unions two sets
* Input : s1 – set one, s2 – set two
* Output : s1 – union result
* Return : none
******************************************************/
void unionSet(Set *s1, Set s2);
// deducts set s2 from set s1
// input: s1 – set one, s2 – set two
// output: s1 – deduct result
void substrSet(Set *s1, Set s2);
/*******************************************************
* Name : intersectSet
* Purpose : intersects two sets
* Input : s1 – set one, s2 – set two
* Output : s1 – intersection result
* Return : none
******************************************************/
void intersectSet(Set *s1, Set s2);
/*******************************************************
* Name : isEqualSet
* Purpose : compares two sets
* Input : s1 – set one, s2 – set two
* Output : none
* Return :
*   1 sets are equal
*   0 not equal
******************************************************/
int isEqualSet(Set s1, Set s2);
/*******************************************************
* Name : copySet
* Purpose : copies set s1 to set s2
* Input : s1 – set one, s2 – set two
* Output : s1 – copy of s2
* Return : none
******************************************************/
void copySet(Set *s1, Set s2);
/*******************************************************
* Name : isEmptySet
* Purpose : check whether the set is empty
* Input : s1 – set one, s2 – set two
* Output : none
* Return :
*   1 set is empty
*   0 not empty
******************************************************/
int isEmptySet(Set s);
/*******************************************************
* Name : printSet
* Purpose : prints set
* Input : s1 – set to print
* Output : prints set on th screen (standard output)
* Return : none
******************************************************/
void printSet(Set s);
----- файл set.c -----
//
// author: O.
// date: 10 January 2013
// description: Set type
//
#include "set.h"
#include <stdio.h>
void initSet(Set *s)
{
  int i;
  for (i = 0; i < 255; i++)
  {
    (*s).elems[i] = 0;
  }
}
void initFromStringSet(Set *s, char *str)
{
  int i;
  while(*str != '\0')
  {
    i = (int)*str;
    (*s).elems[i] = 1;
    str++;
  }
}
void addElemSet(Set *s, char elem)
{
  int i;
  i = (int)elem;
  (*s).elems[i] = 1;
}
void removeElemSet(Set *s, char elem)
{
  int i;
  i = (int)elem;
  (*s).elems[i] = 0;
}
int isInSet(Set s, char elem)
{
  int i;
  i = (int)elem;
  if (s.elems[i] == 1)
  {
    return 1;
  } else
  {
    return 0;
  }
}
void unionSet(Set *s1, Set s2)
{
  int i;
  for (i=0; i < 255; i++)
  {
    (*s1).elems[i] = ((*s1).elems[i] | s2.elems[i]);
  }
}
void substrSet(Set *s1, Set s2)
{
  int i;
  for (i=0; i < 255; i++)
  {
    (*s1).elems[i] = ((*s1).elems[i] - s2.elems[i]);
    if ( (*s1).elems[i] < 0 )
    {
      (*s1).elems[i] = 0;
    }
  }
}
void intersectSet(Set *s1, Set s2)
{
  int i;
  for (i=0; i < 255; i++)
  {
    (*s1).elems[i] = ((*s1).elems[i]  s2.elems[i]);
  }
}
int isEqualSet(Set s1, Set s2)
{
  int i;
  for (i=0; i < 255; i++)
  {
    if (s1.elems[i] != s2.elems[i] )
    {
      return 0;
    }
  }
  return 1;
}
void copySet(Set *s1, Set s2)
{
  int i;
  for (i=0; i < 255; i++)
  {
    (*s1).elems[i] = s2.elems[i];
  }
}
int isEmptySet(Set s)
{
  int i;
  for (i=0; i < 255; i++)
  {
    if (s.elems[i] == 1 )
    {
      return 0;
    }
  }  
  return 1;
}
void printSet(Set s)
{
  int i;
  for (i=0; i < 255; i++)
  {
    if (s.elems[i] == 1 )
    {
      printf("%c",(char)i);
    }
  }
}  
    

Пример использования множества показан далее. Он будет помещен в отдельный файл "setexample.c", в который будет импортироваться реализованный тип данных путем включения заголовочного файла "set.h".

----- файл setexample.c -----
/******************************************************
date: 10 January 2013
description: Set type
*******************************************************/
#include <stdio.h>
#include "set.h"
int main()
{
  Set s1, s2;
/* Do not forget to do it! */
  initFromStringSet(s1, "abcde");
  initSet(s2);
  addElemSet(s2,'a');
  addElemSet(s2,'b');
  printf("\n s1: ");
  printSet(s1);
  printf("\n s2: ");
  printSet(s2);
  removeElemSet(s1,'a');
  printf("\n s1: ");
  printSet(s1);
  unionSet(s1, s2);
  printf("\n s1: ");
  printSet(s1);
  substrSet(s1, s2);
  printf("\n s1: ");
  printSet(s1);
  addElemSet(s1,'a');
  intersectSet(s1, s2);
  printf("\n s1: ");
  printSet(s1);
  return 0;
}  
    

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

Во-первых, это необходимость в импортере всегда использовать операцию создания, которая в примере реализована функцией initSet и функцией initFromStringSet. Так как массив в Си не инициализируется по умолчанию, то если в основной программе перед работой со множеством не вызвать initSet (или initFromStringSet), во множестве могут оказаться "лишние" элементы. При этом компилятор сам не может отследить корректность использования функций создания. Это целиком задача программиста.

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

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

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

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

0 1 2 3 4 5 6 7 8 9 A B C D E F

и все символы строки должны принадлежать этому алфавиту (множеству).

/* sample code - how Set can be used */
Set s3;
char str[100];
int i;
initFromStringSet(s3,"0123456789ABCDEF");
printf("\nEnter HEX number: ");
scanf("%s", str);
i = 0;
while(str[i] != '\0')
{
  if (isInSet(s3, str[i]) == 0)
  {
    printf("You entered not a HEX number!");
    break;
  }
  i++;
}  
    

5.5. Инкапсуляция

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

Использование скрытых типов имеет следующие преимущества:

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

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

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

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

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

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

  /* file: person.h */
  struct PEROBJ;
  typedef struct PEROBJ *PERSON;
  void createPerson(PERSON *p);
  void setAge(PERSON p, int newAge);
  int getAge(PERSON p);
  void deletePerson(PERSON *p);  
    

Мы задали тип как PERSON, который является указателем на PEROBJ. Описание и структура PEROBJ не раскрывается, поэтому из заголовочного файла нельзя увидеть структуру типа, а значит, из импортера не удастся работать с ней напрямую. Сразу определить тип как

typedef struct PERSON;  
    

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

В типе PERSON заданы операции создания и удаления. Они необходимы при выделении памяти под указатель и при ее высвобождении. Для всех скрытых типов приходится реализовывать такие операции. Более того, как уже было сказано, их необходимо обязательно использовать в импортере, иначе возникнет ошибка работы с указателем, для хранения значений которого не выделена память. К сожалению, большинство структурных языков программирования высокого уровня, и Си в том числе, не обладают никакими средствами помощи и контроля для создания/удаления переменных пользовательских типов. Это является одним из недостатков скрытых типов, который решается лишь в объектно-ориентированных языках.

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

Реализация типа помещается в с-файл, который может иметь вид:

/* file: person.c */
#include "person.h"
#include <malloc.h>
struct PEROBJ
{
  int age;
};
void createPerson(PERSON *p)
{
  *p = malloc(sizeof(struct PEROBJ));
}
void setAge(PERSON p, int newAge)
{
  (*p).age = newAge;
}
int getAge(PERSON p)
{
  return (*p).age;
}
void deletePerson(PERSON *p)
{
  free(*p);
}  
    

Здесь приводится описание типа PEROBJ, с которым происходит реальная работа и реализация указанных в h-файле функций. Чтобы работать с полями PERSON, приходится использовать конструкцию (*p).age, так как тип реализован указателем на структуру.

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

/* file: test.c */
#include <stdio.h>
#include "person.h"
int main()
{
PERSON p1;
createPerson(p1);
setAge(p1, 23);
printf("Hi, %d\n", getAge(p1));
deletePerson(p1);
return 0;
}  
    

Саму переменную age из импортирующего модуля изменить нельзя - она недоступна. Это позволяет сохранять целостность типа. В импортере нельзя написать

(*р1).age = -10;  
    

и сделать переменную р1 некорректной.

В рассмотренном примере возраст хранится как количество лет. А что если понадобится знать дату рождения и уметь рассчитывать возраст в зависимости от текущего года? Здесь проявляется одно из важнейших свойств скрытого типа - простота модификации. Чтобы сохранить дату рождения, можно добавить новые поля - день месяца, месяц и год рождения. При этом поле age больше будет не нужно и даже вредно, так как может запутать. Новые изменения приведут к следующему коду.

В h-файл добавим два прототипа новых функций:

void setBirthDay(PERSON p, int day, int month, int year);
int getBirthDay(PERSON p);  
    

В c-файле изменим реализацию setAge и getAge и добавим две новых функции:

#include "person.h"
#include <malloc.h>
#include <time.h>
struct PEROBJ
{
  int day; /* 1-31 */
  int month; /* 1-12 */
  int year; /*1800 – 2100 */
};
void createPerson(PERSON *p)
{
  *p = malloc(sizeof(struct PEROBJ));
}
void setAge(PERSON p, int newAge)
{
  /* get current date in C format */
  time_t timer = time(NULL);
  /* convert our date to structure */
  struct tm *t = localtime(timer);
  /* set current day */
  (*p).day = (*t).tm_mday;
  /* set current month (C format:0-11, our is:1-12)*/
  (*p).month = (*t).tm_mon+1;
  /* set birth year */
  /*(curent – newAge, */
  /*C format for year is: years from 1900) */
  (*p).year = (*t).tm_year+1900-newAge;
}
int getAge(PERSON p)
{
  /* get current date in C format */
  time_t timer = time(NULL);
  /* convert our date to structure */
  struct tm *t = localtime(timer);
  return ((*t).tm_year+1900)-(*p).year;
}
void setBirthDay(PERSON p, int day, int month, int year)
{
  (*p).day = day;
  (*p).month = month;
  (*p).year = year;
}
int getBirthYear(PERSON p)
{
  return (*p).year;
}
void deletePerson(PERSON *p)
{
  free(*p);
}  
    

Интерпретация переменной age изменена, а ранее реализованные методы setAge и getAge по-прежнему возвращают возраст в годах. Все ранее написанные программы, которые использовали наш скрытый тип PERSON, продолжают работать, как и работали, никаких изменений в них не требуется. А все новые программы могут использовать дополнительные методы setBirthDay и getBirthYear.

Пример основной программы, работающей с новым модулем:

/* file: test2.c */
#include <stdio.h>
#include "person.h"
int main()
{
  PERSON p1;
  createPerson(p1);
  setAge(p1, 23);
  printf("Hi, %d\n", getAge(p1));
  setBirthDay(p1, 23,05,1982);
  printf("Hi, %d\n", getAge(p1));
  printf("Hi, %d\n", getBirthYear(p1));
  deletePerson(p1);
}  
    

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

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

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

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

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

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

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

Чаще всего головная программа самостоятельно управляет выводом, и чтобы написать процедуру вывода значения переменной скрытого типа, надо учесть в ней все возможные особенности вывода (шрифт, цвет, положение и т.д.), которые использует головная программа. Обычно они заранее неизвестны.

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

5.6. Уровни абстракции

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

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

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

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

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

Внимание!

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

Вопросы и задачи для самостоятельного решения