Операции над множествами

Пусть S1, S2, S3 : set of byte , Над этими множествами определены следующие специфические операции:

· 1) Объединение множеств: S2+S3. Результатом является множество, содержащее элементы обоих исходных множеств.

· 2) Пересечение множеств: S2*S3. Результатом является множество, содержащее общие элементы обоих исходных множеств.

· 3) Проверка на вхождение элемента в множество: a in S1. Результатом этой операции является значение логического типа - true, если элемент a входит в множество S1, false - в противном случае.

Записи

Логическое и машинное представление записей

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

Пример записи - совокупность сведений о некотором студенте.

Объект "студент" обладает свойствами:

· "личный номер" - характеризуется целым положительным числом,

· "фамилия-имя-отчество" - характеризуется строкой символов и т.д.

Пример: var

rec:record

num :byte; { личный номер студента }

name :string[20]; { Ф.И.О. }

fac, group:string[7]; { факультет, группа }

math,comp,lang :byte; {оценки по математике, выч. }

end; {технике, ин. языку }

В памяти эта структура может быть представлена в одном из двух видов :

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

Рис. 3.10. Представление в памяти переменной типа record в виде последовательности полей

б) в виде связного списка с указателями на значения полей записи. При такой организации имеет место быстрое обращение к элементам, но очень неэкономичный расход памяти для хранения. Структура хранения в памяти связного списка с указателями на элементы приведена на рис. 3.11.

Рис. 3.11. Представление в памяти переменной типа record в виде связного списка.

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

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

Полем записи может быть в свою очередь интегрированная структура данных - вектор, массив или другая запись. В некоторых языках программирования (COBOL, PL/1) при описании вложенных записей указывается уровень вложенности, в других (PASCAL, C) - уровень вложенности определяется автоматически.

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

type rec = record

f1 : integer;

f2 : char[2];

f3 : rec; end;

Как компилятор будет выделять память для такой записи? Для поля f1 будет выделено 2 байта, для поля f2 - 2 байта, а поле f3 - запись, которая в свою очередь состоит из f1 (2 байта), f2 (2 байта) и f3, которое... и т.д. Недаром компилятор C, встретив подобное описание, выдает сообщение о нехватке памяти.

Однако, полем записи вполне может быть указатель на другую такую же запись: размер памяти, занимаемой указателем известен и проблем с выделением памяти не возникает. Этот прием широко используется в программировании для установления связей между однотипными записями (см. главу 5).