Многоуровневые записи

Type

Type

Var

Общая характеристика записей и способы описания в Delphi

Записи

Рандомизированные алгоритмы

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

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

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

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

Приведенные примеры показывают, что рандомизированные алгоритмы являются весьма полезными для решения практических задач.

Запись (record) - это структура данных, представляющая собой конечное множество эле­ментов, называемых полями записи или просто полями. Поля записи в общем случае имеют различные типы. Обычно данные типа «запись» используются в качестве элементов структур, называемых таблицами.

Запись, хранящаяся в оперативной памяти, относится к классу оперативных последовательных структур, поскольку

а) в течение всего времени существования запись занимает сплошной участок памяти, в котором хотя могут находиться «пустоты», обусловленные выравниванием, однако между слотами её полей недопустимо существование слотов других данных;

б) поля в физической памяти располагаются в той последовательности, в которой они перечисляются при объявлении типа Record;

в) адресом всей записи в целом является адрес слота ее начального поля.

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

<имя переменной>: Record

<список имен полей 1>: <тип 1>;

× × ×

<список имен полей m>: <тип m>;

End;

Однако с точки зрения хорошего стиля описание переменной типа «запись» следует начинать с явного объявления ее типа, которое (объявление типа) выглядит следующим образом:

<имя типа> = Record

<список имен полей 1>: <тип 1>;

× × ×

<список имен полей m>: <тип m>;

End;

Var <имя переменной>: <имя типа>;

Пример объявления типа «запись» и переменной-записи, содержащей сведения о студенте, приводится ниже:

TStud = Record

Fam, Name, Par: String[35];

Year: 1950..2000;

Sex: (Male, Female);

Group: String[7]

End;

Var StudFITR, StudMSF: TStud;

Доступ к любому элементу записи осуществляется с помощью имени, называемого селектором поля записи.Селектор состоитиз имени переменной типаRecord, и по­слеточки записываетсяимя поля, например,StudFITR.Fam,где StudFITR - имяпеременной, Fam - имя поля.

Логическую структуру записи часто изображают в виде прямоугольника, разделенного горизонтальными и вертикальными линиями на более мелкие прямоугольники, соответствующие отдельным полям. При этом размеры внутренних прямоугольников никак не сопоставляются с физическими размерами полей в байтах. Рядом с прямоугольниками указываются идентификаторы соответствующих полей, а внутри - их значения, называемые метками. Пример логической структуры записи типа TStud приводится на рисунке 4.1.

Рисунок 4.1 – Логическая структура записи типа TStud

Обычно любой физической структуре ставится в соответствие дескриптор (description - описание, приметы)или заголовок, который содержит общие сведения о физической структуре. Дескриптор является записью, в которой количество, размеры и содержимое полей зави­сят от той структуры, которой поставлен в соответствие дескриптор. Например, дескриптор записи может содержать:

- код структуры (Record),

- имя записи,

- число входящих в нее полей,

- имена, типы и длины полей,

- адреса (указатели) слотов полей.

В записи некоторые поля сами могут представлять собой записи. Например, дополним объявление типа TStud объявлением следующего типа:

TStudent = Record

SelfStud: TStud;

Faculty: (FITR, MSF, ATF, MTF);

Military: Boolean;

End;

где поля Faculty и Military предназначены для хранения соответственно названия факультета, на котором обучается студент, и признака «служил в армии / не служил». Пусть к тому же переменная Student имеет тип TStudent. Тогда в селекторах некоторых полей может появиться третья компонента, например,

Student.SelfStud.Fam:= ’Иванов’;

Student.SelfStud.Group:= ’107312’;

Student.Military:= True;

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