4.2 Прямая адресация; таблицы с прямой адресацией

Прямая адресация применима, если количество возможных ключей невелико. Пусть возможными ключами являются числа из множества U = {0,1,... ,m–1} (число т не очень велико). Предположим также, что ключи всех элементов различны.

Рисунок 4.2 – Реализация динамического множества с помощью таблицы с прямой адресацией

Для хранения множества используется массив Т[0..т – 1], называемый таблицей с прямой адресацией (direct-address table). Каждая позиция, или ячей­ка, (position, slot) соответствует определённому ключу из множества U.

T[k] – место, предназначенное для записи указателя на элемент с ключом k; если элемента с ключом k в таблице нет, то T[k] = NIL). Реализация словарных операций тривиальна:

Листинг 4.1 – Словарные операции при прямой адресации

Каждая из этих операций требует времени O(1).

Иногда можно сэкономить место, записывая в таблицу Т не указатели на элементы множества, а сами эти элементы. Можно обойтись и без отдельного поля «ключ»: ключом служит индекс в массиве. Впрочем, если мы обходимся без ключей и указателей, то надо иметь способ указать, что данная позиция свободна.