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

Рис. 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 -2*1063+1…+2*1063-1

 

 

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

 
 

 

 


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

 
 

 


46,510 = 56,48 = 0,5648 * 82 = 0,5648 * 26

 

Смещенное представление порядка (в формате SINGLE под порядок отводится 8 разрядов):
610 = 68   00000110
2008 + 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 ) = 29 = 512, Sizeof( Picture ) = 2 (байта).

 

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