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

Абстрактные типы данных (АТД) конструируются в программе на основе встроенных и ранее сконструированных абстрактных типов. Если конструирование осуществляется путем агрегирования, т.е. объединения свойств составляющих типов, полученный тип является структурированным типом или агрегатом. Если при конструировании объединяются разнородные свойства, получается новый тип – ЗАПИСЬ (обозначим 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):

Рис. 7. Внутреннее представление объекта множественного типа

Константа базового типа с порядковым номером К в элементе хранения объекта множественного типа представлена битом с номером

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 байт) и никак не связан с размером файла во внешней памяти.

TypeFile_Type = File of <Name_Type>,

где <Name_Type> - любой тип, кроме файлового.

Sizeof(File_Type) = 128.

Для того чтобы описать совокупность операций, производимых над объектом, пользователь может сконструировать АТД – ПРОЦЕДУРНЫЙ ТИП (обозначим Proc_Type). Любой процедурный тип определяет:

множество возможных действий,

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

Например, процедурный тип

Type DST = PROCEDURE (var P: Point);

определяет возможные действия над объектами типа ТОЧКА. Любая процедура, описание которой совпадает с объявлением типа DST, может рассматриваться как объект типа DST. Например, процедуры

Init(var P: Point);	{ инициализировать }
Show(var P: Point);	{ отобразить }
Hide (var P: Point);	{ стереть }
Move(var P: Point);	{ переместить }

являются объектами типа DST. В элементах хранения оьъектов процедурного типа размещаются адреса точек входа в соответствующие процедуры (точки запуска – активации процедур). Поэтому множество констант процедурного типа является подмножеством множества адресов оперативной памяти, т.е. подмножеством типа УКАЗАТЕЛЬ (обозначим Pointer_Type), а размер элемента хранения процедурного типа определяется размером элемента хранения типа указатель (см. 2.2.2).

Sizeof(Proc_Type) = Sizeof(Pointer_Type).

Объявление и реализация АТД обычно помещаются в модуль. Рассмотрим абстрактный тип данных ВРЕМЯ. Значение каждого момента времени состоит из 3 атрибутов: старших, средних и младших единиц временной шкалы (например, сутки:часы:минуты) (рис. 8).

Рис. 8. Элемент хранения АТД “ВРЕМЯ”

UNIT Time;

{ Раздел объявлений АТД ВРЕМЯ }

Interface

{ Описание атрибутов }

TTimer =record

hour, minute, second: word

end;

{ Описание действий по обработке объектов типа ВРЕМЯ }

{ Инициализация атрибутов объекта типа ВРЕМЯ }

Procedure Init (var t: TTimer);

{ Приращение значения времени }

Procedure Add (var t: Ttimer; dt: word);

{ Преобразование значения времени во внутреннее представление }

Procedure TtoReal (t: Ttimer; var r: real);

{ Преобразование значения времени из внутреннего представления }

Procedure RealtoT (r: real; var t: TTimer);

{ Раздел реализации действий по обработке объектов типа ВРЕМЯ }

Implementation

Procedure Init (var t: TTimer);

begin

...

end;

...

end.

Использование модуля Time:

UNIT Main;

uses Time;

var t1,t2: Ttimer; r: real;

begin

Init (t1); Add(t1,10); TtoReal(t1,.r);...

end.

2. идентификация объектов

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

именование

указание.