Таблицы

Когда речь шла о записях, было отмечено, что полями записи

могут быть интегрированные структуры данных - векторы, массивы,

другие записи. Аналогично и элементами векторов и массивов могут

быть также интегрированные структуры. Одна из таких сложных

структур - таблица. С физической точки зрения таблица представля-

ет собой вектор, элементами которого являются записи. Характерной

логической особенностью таблиц, которая и определила их рассмот-

рение в отдельном разделе, является то, что доступ к элементам

таблицы производится не по номеру (индексу), а по ключу - по зна-

чению одного из свойств объекта, описываемого записью-элементом

таблицы. Ключ - это свойство, идентифицирующее данную запись во

множестве однотипных записей. Как правило, к ключу предъявляется

требование уникальности в данной таблице. Ключ может включаться в

состав записи и быть одним из ее полей, но может и не включаться

в запись, а вычисляться по положению записи. Таблица может иметь

один или несколько ключей. Например, при интеграции в таблицу за-

писей о студентах (описание записи приведено в п.3.5.1) выборка

может производиться как по личному номеру студента, так и по фа-

милии.

Основной операцией при работе с таблицами является операция

доступа к записи по ключу. Она реализуется процедурой поиска.

Поскольку поиск может быть значительно более эффективным в табли-

цах, упорядоченных по значениям ключей, довольно часто над табли-

цами необходимо выполнять операции сортировки. Эти операции расс-

матриваются в следующих разделах данной главы.

Иногда различают таблицы с фиксированной и с переменной дли-

ной записи. Очевидно, что таблицы, объединяющие записи совершенно

идентичных типов, будут иметь фиксированные длины записей. Необ-

ходимость в переменной длине может возникнуть в задачах, подобных

тем, которые рассматривались для записей с вариантами. Как прави-

ло таблицы для таких задач и составляются из записей с варианта-

ми, т.е. сводятся к фиксированной (максимальной) длине записи.

Значительно реже встречаются таблицы с действительно переменной

длиной записи. Хотя в таких таблицах и экономится память, но воз-

можности работы с такими таблицами ограничены, так как по номеру

записи невозможно определить ее адрес. Таблицы с записями пере-

менной длины обрабатываются только последовательно - в порядке

возрастания номеров записей. Доступ к элементу такой таблицы

обычно осуществляется в два шага. На первом шаге выбирается пос-

тоянная часть записи, в которой содержится - в явном или неявном

виде - длина записи. На втором шаге выбирается переменная часть

записи в соответствии с ее длиной. Прибавив к адресу текущей за-

писи ее длину, получают адрес следующей записи.

Так таблица с записями переменной длины может, например,

рассматриваться в некоторых задачах программируемых в машинных

кодах. Каждая машинная команда - запись, состоит из одного или

нескольких байт. Первый байт - всегда код операции, количество и

формат остальных байтов определяется типом команды. Процессор вы-

бирает байт по адресу, задаваемому программным счетчиком, и опре-

деляет тип команды. По типу команды процессор определяет ее длину

и выбирает остальные ее байты. Содержимое программного счетчика

увеличивается на длину команды.