Абстрактные типы

Рис. 6. Внутреннее представление вещественного числа 46,5.

Таблица 2. Вещественные типы

Вещественные типы

Таблица 1. Целые типы

Название	Размер элемента хранения, байт	Множество констант
Byte		0…255
ShortInt		-128…127
Word		0…65535
Integer		-32768…32767
LongInt		-2147483648…2147483647

ЛОГИЧЕСКИЙ ТИП. Значениями логического типа может быть одна из предварительно объявленных констант FALSE (ложь) и TRUE (истина).

Power(BOOLEAN) = 2, Sizeof(BOOLEAN) = 1 (байт),

Ord(False) = 0, Ord(True) = 1.

СИМВОЛЬНЫЙ ТИП. Значениями символьного типа является множество всех символов компьютера. Каждому символу приписывается целое число в диапазоне 0..255. Это число служит кодом внутреннего представления символа. Первая половина символов с кодами 0..127 соответствует стандарту ASCII. Вторая половина символов с кодами 128..255 не ограничена жесткими рамками стандарта и может меняться на компьютерах разных типов.

Power(CHAR) = 256, Sizeof(CHAR) = 2 (байта), Ord(‘F’) = 70;

ПОЛЬЗОВАТЕЛЬСКИЙ ПЕРЕЧИСЛИМЫЙ ТИП (обозначим Enum_Type) задает некоторое подмножество целого типа WORD и может рассматриваться как компактное объявление группы N именованных целочисленных констант со значениями 0,1,…65535. Например,

TypeNote= (do, re, mi, fa, sol, la, si).

Так, значение константы с именем fa и соответственно ее порядковый номер в множестве констант типа Note равны 3, т.е. Ord(fa) = 3.

Power (Enum_Type) = N, N <= 65536.

Sizeof(Enum_Type) = 1 + log2(Power (Enum_Type) – 1) DIV 8.

Power(Note) = 7, Sizeof(Note) = 1 (байт).

Для ограничения полного множества значений некоторого порядкового типа используются отрезки типа. ОТРЕЗОК ТИПА ИЛИ ДИАПАЗОН (обозначим Diap_Type) – упорядоченное подмножество полного множества значений любого порядкового типа, исключая диапазон. Тип-диапазон задается границами своих значений (обозначим их MIN и MAX) внутри базового типа:

Type Diap_Type = MIN.. MAX;

MIN = Low (Diap_Type), MAX = High (Diap_Type).

Power (Diap_Type) = MAX - MIN + 1 <= 65536.

Sizeof(Diap_Type) = 1 + log2(Power (Diap_Type) – 1) div 8.

Например,

Type Otr = 10..19;

Low (Otr) = 10, High(Otr) = 19, Ord(15) = 15,

Power(Otr) = 10, Sizeof(Otr) = 1 (байт).

Порядковые типы конечны и счетны, значения их всегда сопоставимы с рядом целых чисел, и, следовательно кодируются абсолютно точно. Множество констант ВЕЩЕСТВЕННЫХ ТИПОВ бесконечно, значения вещественных типов определяются с некоторой конечной точностью, зависящей от внутреннего формата вещественных чисел.

Название	Размер элемента хранения, байт	Количество значащих цифр	Диапазон десятичного порядка
single		7..8	-45…+38
real		11…12	-39…+38
double		15…16	-324…+308
extended		19…20	-4951…+4932
comp		19…20	-210⁶³+1…+210⁶³-1

Элемент хранения вещественного типа имеет следующую структуру:

Здесь s – знаковый разряд числа; e – экспоненциальная часть, содержащая порядок; m – мантисса числа. Мантисса имеет длину от 23 (для SINGLE) до 63 (для EXTENDED) двоичных разрядов, что и обеспечивает точность 7..8 для SINGLE и 19..20 для EXTENDED десятичных цифр. Знак мантиссы определяет знак числа и имеет значения: 0 – для положительных чисел, 1 – для отрицательных чисел. Порядок числа запоминается увеличенным на 200₈(128). Такой способ хранения порядка называется смещенным. Десятичная точка подразумевается перед левым (старшим) разрядом мантиссы, но при действиях с числом ее положение сдвигается влево или вправо в соответствии с двоичным порядком числа, хранящимся в экспоненциальной части, поэтому действия над вещественными числами называются арифметикой с плавающей точкой. На рис. 6 показано внутреннее представление вещественного числа 46,5 в формате SINGLE.

46,5₁₀ = 56,4₈ = 0,564₈ * 8² = 0,564₈* 2⁶

Смещенное представление порядка (в формате SINGLE под порядок отводится 8 разрядов):
6₁₀ = 6₈		00000110
200₈	+	10000000
порядок	=	10000110

Абстрактные типы данных (АТД) конструируются в программе на основе встроенных и ранее сконструированных абстрактных типов. Если конструирование осуществляется путем агрегирования, т.е. объединения свойств составляющих типов, полученный тип является структурированным типом или агрегатом. Если при конструировании объединяются разнородные свойства, получается новый тип – ЗАПИСЬ (обозначим Rec_Type). Пусть Тип Rec_Type строится на основе типов Type1, Type2,… Type N.

Type Rec_Type = record

< Имя свойства 1 >: Type1;

< Имя свойства 2 >: Type2;

...

< Имя свойства N >: Type N;

end;

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

Power(Rec_Type) = Power(Type1) * Power(Type2) * … * Power(TypeN),

Sizeof(Rec_Type) = Sizeof(Type1) + Sizeof(Type2) + … + Sizeof(TypeN).

Например,

Type Rec = record

X: 0..9; Y: 0..9

end;

Множество констант этого типа включает 100 пар значений (0,0), (0,1),…(0,10), (1,0), (1,1), …, (1,10), (10,0), …(10,10).

Power(Rec) = Power(X) * Power(Y) = 10 * 10 = 100,

Sizeof(Rec) = Sizeof(X) + Sizeof(Y) = 1 + 1 = 2 (байта).

Если при конструировании типа объединяются однородные свойства, получается новый тип - МАССИВ (обозначим Array_Type). Массив – это агрегат, составленный из однородных свойств. Пусть тип Array_Type формируется из N элементов типа Type1:

Const N = …; { N – количество элементов массива }

Type Array_Type = array [1..N ] of Type1;

Power(Array_Type) = Power(Type1)^N,

Sizeof(Array_Type) = N * Sizeof(Type1).

На базе типа с ограниченным множеством значений (обозначим Base_Type) можно построить тип с более широким спектром значений – тип МНОЖЕСТВО (обозначим Set_Type). Множество определяется как набор всевозможных комбинаций однотипных логически связанных объектов некоторого базового типа. Мощность базового типа не дожна превышать 256 констант. Пусть в качестве базового типа для построения АТД КАРТИНА используется перечисление цветов

Type Colour = (white, black, red, green, blue, yellow, gray, magenta, cyan);

Type Picture = Set of Colour;

Примеры множественных констант:

[ ], [ red ], [ green, blue, red ], … [ green, black ], …[ white.. cyan ].

Power(Set_Type) = 2 ^{Power(Base_Type)},

Sizeof(Set_Type) = 1 + (Power(Base_Type) – 1) div 8 или

Sizeof(Set_Type) = (MAX div 8) – (MIN div 8) + 1, где

MIN = Low(Base_Type), MAX = High(Base_Type).

Power(Colour) = 9, Sizeof(Colour) = 1 (байт),

Power(Picture) = 2⁹ = 512, Sizeof(Picture) = 2 (байта).

Элемент хранения объекта множественного типа должен допускать размещение 2 ^{Power(Base_Type)} значений. В качестве представления объекта множественного типа используется характеристическая функция, являющаяся массивом логических значений, i–я компонента которого означает наличие или отсутствие i-й константы базового типа в множестве. Каждая константа базового типа в представлении константы множественного типа имеет сопоставимый номер и занимает 1 бит, соответствующий ее порядковому номеру в базовом типе. Например, представление объекта [white, red, green, gray, cyan] в его элементе хранения выглядит следующим образом (рис.7):