Если несколько компонент записи умещаются в одном слове памяти, то может идтп речь об упаковке (см. рис. 1.8). faK же как для массива, желательность упаковки можно указать в описании с помощью слова packed перед словом j-ecord. Поскольку смещения компонент вычисляются при .трансляции, смещение компоненты внутри слова также мо-

выравнявание

Рис. 1.8. Представление упакованной записи.

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

1.10.3. Представление множеств

Множество S наилучшим образом представляется в памяти машины с помощью характеристической функции C(s). Характеристическая функция - это массив логических значений, i-я компонента которого означает наличие или отсутствие i-ro значения базового типа в множестве s. Размер этого массива равен кардинальному числу базового типа множества:

C{si) = {iins) (1.39)

Например, множество небольших целых чисел

s-[l. 4, 8, 9]

представляется последовательностью логических значений f (false) и 7(true)

C{s) = (PTFFTFFFTT)

если базовый тип множества s - целые числа, принадлежа-ч^ие диапазону 0..9. В памяти машины последовательность логических значений изображается так называемой строкой разрядов (см. рис. 1.9).

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

0 1 0 0 1 0 0 0 1 1

4 -9

Рис. 1.9. Предстайление мнол{ества в виде разрядной строки.

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

jcin[c Cg, .... с„]

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

(д: = с,) V (д: = Са) V ... V {х=с„)

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

1.11. ПОСЛЕДОВАТЕЛЬНЫЙ ФАЙЛ

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

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

I in (х+у) s (/ in х) V (i in у)

i in (х*у) s (i in л) Л (/ in у) (1.40)

I in (x-y) = (i in X) Л in y)

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

ретствующее представление легко находится для любой {числительной машины.

Большинство так называемых усложненных структур: последовательности, деревья, графы и т. д. - характеризуются тем, что их кардинальные числа бесконечны. Это отличие от-базовых структур с конечными кардинальными числами очень важно и имеет существенные практические следствия. Например, определим последовательную структуру следующим образом.

Последовательность с базовым типом Го -это либо пустая последовательность, либо конкатенация последовательности (с базовым типом Tq) и значения типа Го.

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

Аналогичные рассуждения применимы ко всем другим усложненным структурам данных. Из этого прежде всего следует, что объем памяти, необходимый для размещения структуры усложненного типа, неизвестен во время трансляции и может изменяться во время выполнения программы. Это требует динамического распределения памяти, при котором память занимается, если соответствующие значения растут , и, возможно, освобождается, когда они убывают . Поэтому проблема представления усложненных структур - чрезвычайно тонкая и сложная, и ее решение существенно-влияет на эффективность работы и экономию памяти. Здесь можно принимать решения только с учетом того, какие простейшие операции и насколько часто должны выполняться на данной структуре. Поскольку эта информация неизвестна разработчику языка и транслятора, ему приходится исключать усложненные структуры из языка (универсального). Отсюда также следует, что программист должен избегать использования таких структур, если при решении задачи можно ограничиться фундаментальными структурами данных.

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