Рис. 11.6 Тот же список, что на рис. 11.3а и 11.5, реализованный на базе единственного массива А. Каждой записи соответствует тройка идущих подряд элементов массива. Полям key, next и prev соответствуют сдвиги 0, 1 и 2. Указатель на запись - индекс первого из отведённых для неё элементов. Светлосерые записи входят в список; стрелками изображено действие указателей.

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

При реализации записей на базе массива можно воспользоваться той же стратегией. Рассмотрим один-единственный массив А. Каждая запись будет занимать в нём непрерывный участок A[j .. к]. Указатель на запись - это индекс j; каждому полю записи соответствует число из интервала [0 .. к - j] - сдвиг. Например, при представлении всё того же списка, что и на рис. 11.3а и 11.5, можно решить, что полям key, next и prev соответствуют сдвиги 0, 1 и 2. Тогда значение prev[i], где г - указатель (= индекс в массиве А), есть не что иное, как А[г + 2] (см. рис. 11.6).

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

Выделение и освобождение памяти

При добавлении нового элемента в список надо отвести под него место в памяти. Стало быть, необходимо вести учёт использования адресов. В некоторых системах этим ведает специальная подпрограмма - сборщик мусора (garbage collector), которая определяет, какие участки памяти более не используются, и возвращает их для повторного использования. Во многих случаях, однако, можно возложить обязанности по выделению и освобождению памяти на саму структуру данных. В этом разделе мы покажем, как это делается; в качестве примера рассмотрим двусторонне связанный список, представленный с помощью нескольких массивов.

Пусть массивы, с помощью которых мы представляем наш спи-

Рис. 11.7 Работа процедур allocate-object и Free-Object, (а) Тот же список, что на рис. 11.5 (светло-серый) и список свободных позиций (тёмно-серый). Структура списка свободных позиций изображена с помощью стрелок, (б) Вот что получится после вызова allocate-OBJECT0 (возвращает значение 4), присваивания &еу[4] <- 25 и вызова LlST-lNSERT(L, 4). Новый список свободных позиций начинается с 8 (таково было значение пеж£[4]). (в) Теперь мы вызвали LlST-delete(L, 5), а затем Free-Object(5). Позиция 5 - голова нового списка свободных позиций, за ней следует 8.

сок, имеют длину то, и пусть в данный момент в списке содержится п то элементов. Остальные п - то мест (позиций) в массиве свободны (free).

Мы будем хранить свободные позиции в односторонне связанном списке, называемом списком свободных позиций (free list). Этот список использует только массив next: именно, next[i] содержит индекс свободной позиции, следующей за свободной позицией г. Голова списка хранится в переменной free. Список свободных позиций хранится вперемежку со списком L (рис. 11.7). Обратите внимание, что каждому числу из отрезка [1;то] отвечает элемент либо списка L, либо списка свободных мест.

Список свободных позиций ведёт себя как стек: из всех свободных участков памяти под новую запись выделяется тот, который был освобождён последним. Поэтому для выделения и освобождения памяти можно воспользоваться реализацией стековых операций Push и Pop на базе списка. В приводимых ниже процедурах Allocate-Object (выделить место) и Free-Object (освободить место) подразумевается, что в глобальной переменной free записан индекс первой (в списке) свободной позиции.

Рис. 11.8 Списки L\ (светло-серый) и L2 (тёмно-серый), а также список свободных мест (черный) хранятся в одной тройке массивов.

Free-0biect(2;)

1next[x] <- free

2free <- x

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

Часто один список свободных позиций обслуживает сразу несколько динамических множеств (рис. 11.8).

Описанные процедуры выделения и освобождения памяти просты и удобны (работают за время 0(1)). Их можно приспособить для хранения однотипных записей любого вида, отведя одно из полей записи под хранение индекса next (в свободных позициях).

Упражнения

11.3-1 Следуя образцу рис. 11.5, изобразите представление последовательности (13,4,8,19,5,11) в виде двусторонне связанного списка, реализованного с помощью трех массивов; по образцу рис. 11.6 изобразите тот же список, реализованный с помощью одного массива.

11.3-2 Напишите процедуры Allocate-Obiect и Free-Obiect для случая однотипных записей, хранящихся в одном массиве.

11.3-3 Почему в процедурах Allocate-Obiect и Free-Obiect никак не фигурирует поле prev?

11.3-4 Часто (например, при страничной организации виртуальной памяти) бывает полезно хранить элементы списка в непрерыв-

Allocate-Obiect() 1 if free = nil