Операции над статическими структурами

Таблицы

Begin

Type

Begin

Var

Type

Записи

Type

Var

Type

Type

Множества

Множествомназывается неупорядоченная совокупность элементов порядкового типа, элементами которого могут быть величины типов ShortInt, Byte, Char, а также интервального и перечисляемого. Элементы множества могут принимать все значения базового типа, их количество не должно превышать 256. В табл. 4.6 перечислены операции, которые определены над множествами S, S1, S2.

Табл. 4.6. Операции над множествами.

В языке Паскаль для задания типа-множества есть зарезервированные слова set и of с помощью которых следует указать элементы множества в виде перечисления или диапазона:

< имя > = set of < тип >;

где

< имя > – идентификатор типа множества;

< тип > – идентификатор или определение типа элементов.

Примеры определения множеств:

TNumber = set of 0..9;

TOperation = set of (Plus, Minus, Mult, Divide);

TSymbols = set of Char;

Тип множества может быть определен и при объявлении переменных:

Symbols: TSymbols;

Operation: TOperation;

Digits: set of 0..9;

Значением переменной-множества может быть любое сочетание элементов, заданных ее типом. Чаще всего значение переменной-множества задается конструктором множества, т.е. перечислением его элементов в квадратных скобках:

Digits:=[1, 3, 5, 7, 9]; { нечетные цифры }

Symbols:=[‘A’..’Z’, ‘a’..’z’]; { латинский алфавит }

Символьные множества хранятся в памяти также как и числовые. Разница лишь в том, что хранятся не числа, а коды ASCII символов. Множество может быть пустым, т.е. не иметь ни одного элемента: Symbols:= [ ].

Множество в памяти хранится как массив битов, в котором каждый бит указывает, является ли элемент принадлежащим объявленному множеству или нет. Число байтов, выделяемых для данных типа множество, вычисляется по формуле:

ByteSize = (max div 8)-(min div 8)+1

где max и min – верхняя и нижняя границы базового типа данного множества.

Номер байта для элемента Е вычисляется по формуле:

ByteNumber = (E div 8)-(min div 8)

а номер бита внутри байта по формуле:

BitNumber = E mod 8

Например, переменная следующего типа:

TVideo = (MDA,CGA,HGC,EGA,EGAm,VGA,VGAm,SVGA,PGA,XGA);

в памяти будет занимать:

ByteSize = (9 div 8)-(0 div 8)+1 = 2 байта

Запись– конечное упорядоченное множество полей, характеризующихся различным типом данных. Записи являются удобным средством представления программных моделей реальных объектов предметной области, и, как правило, каждый такой объект обладает набором свойств (полей данных), характеризуемых данными различных типов.

Поля записи могут иметь простой или структурный тип. Приведем примеры записей:

{ комплексное число }

Complex = record

Re, Im: Real;

end;

{ календарная дата }

TDate = record

Day: 1..31;

Month: (Jan, Feb, Mar, Apr,May, Jun, Jul, Aug, Sep, Oct, Nov, Dec);

Year: Word;

end;

и затем объявим переменные соответствующего типа:

Z: Complex;

Date: TDate;

Основная операция над записями – доступ к выбранному полю (операция квалификации). Практически во всех языках обозначение этой операции имеет вид:

< имя переменной-записи >.< имя поля >

Например, полям записи Z можно присвоить значения:

Z.Re:=5.2;

Z.Im:=-8.4;

При неоднократном обращении к одному и тому же полю записи или к различным полям одной записи удобно использовать оператор доступа:

with < имя переменной типа запись > do < оператор >

В этом случае можно не указывать имя записи, а только имена полей. С использованием оператора with можно записать:

with Date do

Day:=18;

Month:=Jan;

Year:=2000;

end;

Большинство языков поддерживает операции, работающие с записью, как с единым целым, а не с отдельными ее полями: операция присваивания одной записи значения другой однотипной записи и сравнения двух однотипных записей на равенство/неравенство. Это позволяет обрабатывать в одной структуре данные разных типов. Например, если переменные A и B представляют собой записи одного типа, то можно использовать присваивание A:=B. При этом поля записи A получат значения соответствующих полей записи B.

В случаях, когда такие операции не поддерживаются языком явно (язык C), они могут выполняться над отдельными полями или записи могут копироваться и сравниваться как неструктурированные области памяти.

Поля записи в свою очередь могут быть записями, т.е. записи могут быть вложенными на несколько уровней. Для доступа к внутренним полям необходимо удлинять составное имя через точку (каждая точка раскрывает один уровень), либо использовать последовательно несколько операторов доступа with.

Пусть определена запись, описывающая некоторый объект:

{ сведения об объекте }

TItem = record

Name: string[20];

Tested: Boolean;

Date: TDate;

end;

Определим переменную типа TItem:

var Item: TItem;

Тогда дата проверки объекта задается составным именем:

Item.Date.Day:=18;

Item.Date.Month:=Jan;

Item.Date.Year:=2000;

или с использованием двух операторов with:

with Item do

with Date do

Day:=18;

Month:=Jan;

Year:=2000;

end;

Упакованные записи. Доступ к отдельному полю записи эффективен, т.к. величина смещения каждого поля от начала записи постоянна и известна во время компиляции. Так как для поля иногда нужен объем памяти, не кратный размеру слова (или двойного слова), компилятор может «увеличить» запись так, чтобы каждое поле было выровнено по границе слова (или двойного слова), поскольку доступ к невыровненному полю по границе слова (или двойного слова) менее эффективен.

Например, объявление следующего типа:

TSomeStruct = record

c1: Char; { 1 байт, пропустить 1 байт }

w1: Word; { 2 байта }

c2: Char; { 1 байт, пропустить 1 байт }

w2: Word; { 2 байта }

end;

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

TSomeStruct = record

w1: Word; { 2 байта }

w2: Word; { 2 байта }

c1: Char; { 1 байт, пропустить 1 байт }

c2: Char; { 1 байт, пропустить 1 байт }

end;

По умолчанию для быстрого доступа элементы массива и поля записей выравниваются по границе слова или двойного слова. Для устранения такого выравнивания можно использовать зарезервированное слово packed перед словом record или array. Это приведет к снижению скорости доступа, но одновременно уменьшит объем занимаемой структурой места в памяти.

Полем записи может быть другая запись, но не такая же, что связано, прежде всего, с тем, что компилятор должен выделить для размещения записи память.

Пусть, определена запись вида:

Rec = record

f1: Word;

f2: Char;

f3: Rec;

end;

Для поля f1 будет выделено 2 байта, для поля f2 – 1 байт, а поле f3 – запись, которая в свою очередь состоит из f1 (2 байта), f2 (1 байт) и f3 и т.д. Компилятор, встретив подобное описание, выдает сообщение о нехватке памяти. Однако полем записи вполне может быть указатель на другую такую же запись: размер памяти, занимаемый указателем известен, и проблем с выделением памяти не возникает. Подобный прием широко используется для установления связей между однотипными записями.

PRec = ^Rec

Rec = record

f1: Word;

f2: Char;

f3: PRec;

end;

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

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

Для задач подобного рода некоторые языки программирования (C, PASCAL) предоставляют записи с вариантами. Запись с вариантами состоит из двух частей. В первой части описываются поля, общие для всех групп объектов, моделируемых записью. Среди полей обычно бывает поле, значение которого позволяет идентифицировать группу, к которой данный объект принадлежит и, следовательно, какой из вариантов второй части записи должен быть использован при обработке.

Вторая часть записи содержит описания непересекающихся свойств – для каждого подмножества таких свойств – отдельное описание. Язык программирования может требовать, чтобы имена полей-свойств не повторялись в разных вариантах (PASCAL), или же требовать именования каждого варианта (C). В первом случае идентификация поля, находящегося в вариантной части записи при обращении к нему ничем не отличается от случая простой записи:

< имя переменной-записи >.< имя поля >

Во втором случае идентификация немного усложняется:

< имя переменной-записи >.< имя варианта >.< имя поля >

Рассмотрим использование записей с вариантами. Пусть требуется размещать на экране простые геометрические фигуры – круги, прямоугольники, треугольники. Для «базы данных», которая будет описывать состояние экрана, удобно представлять все фигуры однотипными записями.

Для любой фигуры описание должно включать координаты некоторой опорной точки (центра, правого верхнего угла, одной из вершин) и код цвета. Другие параметры построения будут разными для разных фигур: для круга – радиус; для прямоугольника – длины непараллельных сторон; для треугольника – координаты двух других вершин. Запись с вариантами для такой задачи в языке PASCAL выглядит так:

figure = record

ftype : Char; { тип фигуры }

x0, y0 : Word; { координаты опорной точки }

color : Byte; { цвет }

case fig_t: Char of

'C': (radius: Word); { радиус окружности }

'R': (len1, len2: Word); { длины сторон прямоугольника }

'T': (x1,y1,x2,y2: Word); { координаты двух вершин }

end;

Если определена переменная fig1 типа figure, в которой хранится описание окружности, то обращение к радиусу этой окружности будет иметь вид: fig1.radius. Поле с именем fig_type введено для представления идентификатора вида фигуры, который, например, может кодироваться символами: «C» – окружность или «R» – прямоугольник, или «T» – треугольник.

Выделение памяти для записи с вариантами показано на рис. 4.1. Под запись с вариантами выделяется объем памяти, достаточный для размещения самого большого варианта. Если выделенная память используется для меньшего варианта, часть ее остается неиспользуемой. Общая для всех вариантов часть записи размещается так, чтобы смещения всех полей относительно начала записи были одинаковыми для всех вариантов.

Наиболее просто это достигается размещением общих полей в начале записи, но это не строго обязательно. Вариантная часть может и «вклиниваться» между полями общей части. Поскольку в любом случае вариантная часть имеет фиксированный (максимальный) размер, смещения полей общей части также останутся фиксированными.

Рис. 4.1. Выделение памяти для записи с вариантами.

В предыдущем разделе было отмечено, что полями записи могут быть интегрированные структуры – векторы, массивы, другие записи. Аналогично элементами векторов и массивов могут быть также интегрированные структуры. Одна из таких структур – таблица. С логической точки зрения таблица представляет вектор, элементами которого являются записи. Таблицы не имеют стандартного типа данных в языке Паскаль.

В таблицах доступ к элементам производится не по номеру (индексу), а по ключу – значению одного из свойств объекта, описываемого записью-элементом таблицы. Ключ идентифицирует данную запись во множестве однотипных. К ключу предъявляется требование уникальности в данной таблице. Ключ может включаться в состав записи и быть одним из ее полей, но может и не включаться, а вычисляться по положению записи. Таблица может иметь один или несколько ключей. Например, при интеграции в таблицу записей о студентах выборка может производиться как по личному номеру студента, так и по фамилии.

Основной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Поскольку поиск может быть значительно более эффективным в таблицах, упорядоченных по значениям ключей, довольно часто над таблицами необходимо выполнять операции сортировки. Такие операции рассматриваются в разделе 4.6.

Различают таблицы с фиксированной и переменной длиной записи. Очевидно, что таблицы, объединяющие записи идентичных типов, будут иметь фиксированные длины записей. Необходимость в переменной длине может возникнуть в задачах, подобных тем, которые рассматривались для записей с вариантами. Как правило, таблицы для таких задач и составляются из записей с вариантами, т.е. сводятся к фиксированной (максимальной) длине записи.

Значительно реже встречаются таблицы с действительно переменной длиной записи. Хотя в таких таблицах и экономится память, но возможности работы с такими таблицами ограничены, т.к. по номеру записи невозможно определить ее адрес. Таблицы с записями переменной длины обрабатываются только последовательно – в порядке возрастания номеров записей.

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