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

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

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

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

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

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

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

----- файл fraction.h -----

/*

Date: 10 May 2011

Description: fraction type

*/

typedef struct {

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 May 2011

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.

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