|
Абстрактные типы данных (АТД) конструируются в программе на основе встроенных и ранее сконструированных абстрактных типов. Если конструирование осуществляется путем агрегирования, т.е. объединения свойств составляющих типов, полученный тип является структурированным типом или агрегатом. Если при конструировании объединяются разнородные свойства, получается новый тип – ЗАПИСЬ (обозначим 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 бит, соответствующий ее порядковому номеру в базовом типе.
Константа базового типа с порядковым номером К в элементе хранения объекта множественного типа представлена битом с номером
BitNumber = K mod 8
в байте с номером
ByteNumber = ( K div 8 ) – ( MIN div 8 ), где
MIN = Low( Base_Type ).
Ord( cyan ) = 8, BitNumber( cyan ) = 0, ByteNumber( cyan ) = 1.
Операции над множествами определяются как теоретико-множественные операции над их характеристическими функциями.
ФАЙЛ – это либо именованная область внешней памяти (жесткого диска, дискеты, компакт-диска, электронного “виртуального” диска), либо логическое устройство – потенциальный источник или приемник информации. С логическими устройствами связаны стандартные аппаратные средства, такие как клавиатура, экран дисплея, принтер. В PASCAL существуют три вида файлов в зависимости от способа хранения информации в них: типизированные (обозначим File_Type), текстовые (тип TEXT) и нетипизированные (тип FILE). С каждым файлом связана специальная структура, называемая дескриптором (описателем), в которой хранится имя файла, дата создания, размер файла, атрибут доступа к файлу и т.п. При описании в программе объекта файлового типа в оперативной памяти создается элемент хранения, в котором размещается дескриптор файла. Размер дескриптора файла фиксирован для файла любого вида (128 байт) и никак не связан с размером файла во внешней памяти.
|
