следует выбирать метод поиска с использованием индексации по ключам, поскольку операции search и insert трудно реализовать эффективнее.

Если элементы вообще отсутствуют (имеются только ключи), можно использовать таблицу бит. В этом случае таблица символов называется таблицей существования (existence table), поскольку А:-ый разряд можно считать признаком существования к в наборе ключей таблицы. Например, на 32-разрядном компьютере этот метод можно было бы использовать для быстрого выяснения того, используется ли уже конкретный 4-значный номер телефонного коммутатора, используя таблицу из 313 слов.

Лемма 12.1 Если значения ключей - положительные целые числа меньшие М, и элементы имеют различные ключи, то тип данных таблицы символов может быть реализован посредством индексированных по ключам массивов элементов так, чтобы для выполнения операций insert, search и remove требовалось постоянное время; время для выполнения операций initialize, select и sort пропорционально М всегда, когда любая из операций выполняется по отношению к таблице, состоящей из N-элементов.

Это свойство становится очевидным после ознакомления с кодом. Обратите внимание, что на ключи накладывается условие N < М.

Программа 12.4 не обрабатывает дублированные ключи и в ней предполагается, что значения ключей лежат в пределах между О и М-1. Для хранения любых элементов с одинаковыми ключами можно было бы использовать связные списки или один из подходов, упомянутых в разделе 12.1, а перед использованием ключей в качестве индексов можно было бы выполнить их простые преобразования (см. упражнение 12.13). Но мы отложим подробное рассмотрение таких случаев вплоть до главы 14, в которой рассматривается хеширование, при котором Для реализации таблиц символов для общих ключей используется этот же подход, заключающийся в преобразовании Ю1ючей из потенциально широкого диапазона в узкий с дополнительными действиями для элементов с дублированными ключами. Пока будем предполагать, что старым элементом со значением ключа, равным ключу вставляемого элемента, можно молча пренебречь (как в программе 12.4), или же считать это условием ошибки (см. упражнение 12.10).

Программа 12.4 Таблица символов, основывающаяся на индексированном по ключам массиве

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

template <class Item, class Кеу> class ST {

private:

Item nullltem, *st;

int M; public:

ST(int maxN)

{ М = nullltem.key О ; st = new Item[M] ; } int count0

{ int N = 0;

for (int i = 0; i < M; i++)

if (!st[i] .nullO ) N++; return N;

void insert(Item x)

{ sttx.keyO] = x; } Item search(Key v)

{ return st[v]; } void remove (Item x)

{ st[x.key()] = nullltem; } Item select(int k)

{ for (int i = 0; i < M; i++) if (!st[i]-nullO)

if (k-- = 0) return st[i]; return nullltem;

void show(ostream& os)

{ for (int i = 0; i < M; i++)

if (!st[i] .nullO ) st[i] .show(os) ; }

Реализация операции count в программе 12.4 - пример ленивого подхода, когда действия выполняются только при вызове функции count. Альтернативный ( энергичный ) подход заключается в поддержке локальной переменной счетчика непустых позиций таблицы с увеличением значения переменной, когда вставка (insert) выполняется в позицию таблицы, содержащую nullltem, и с уменьщением значения счетчика, если удаление (remove) выполняется по отношению к позиции таблицы, не содержащей nullltem (см. упражнение 12.11). Ленивый подход предпочтительнее, если операция count используется редко (или вообще не используется), а количество возможных значений ключей мало; энергичный подход предпочтительнее, если операция count используется часто или если количество возможных значений ключей очень велико. Для подпрограммы библиотеки общего назначения энергичный подход предпочтительней, поскольку он обеспечивает оптимальную производительность для наихудшего случая при небольшом постоянном коэффициенте увеличения затрат на выполнение операций insert и remove. Для внутреннего цикла в приложении с очень большим количеством операций insert и remove, но незначительным количеством операций count ленивый подход оказывается предпочтительней, поскольку обеспечивает наиболее быструю реализацию часто выполняемых операций. Как мы уже неоднократно убеждались, подобная дилемма типична для разработки АТД, которые должны поддерживать различные наборы операций.

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

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

Упражнения

12.10 Реализуйте АТД таблицы символов первого класса (см. упражнение 12.6), используя динамически распределяемые массивы, индексированные по ключам.

> 12.11 Измените реализацию, представленную в программе 12.4, чтобы обеспечить энергичную реализацию функции count (путем отслеживания количества ненулевых записей).

t> 12.12 Измените реализацию, созданную в упражнении 12.10, чтобы обеспечить энергичную реализацию функции count (см. упражнение 12.11).

12.13 Разработайте версию профаммы 12.4, в которой используется функция h(Key), преобразующая ключи в неотрицательные целые числа меньшие М так, чтобы никакие два ключа не отображались одним и тем же целым числом. (Это усовершенствование делает реализацию полезной, когда ключи относятся к узкому диапазону (не обязательно начинающемуся с 0) и в других простых случаях.)

12.14 Разработайте версию профаммы 12.4 для случая, когда элементы представляют собой ключи, являющиеся положительными целыми числами меньшими М (без какой-либо связанной информации). В реализации используйте динамически распределенный массив, состоящий приблизительно из M/bitword слов, где bitword - количество бит в одном слове в используемой компьютерной системе.

12.15 Используйте реализацию, созданную в упражнении 12.14, для экспериментального определения среднего и стандартного отклонений количества отдельных целых чисел в произвольной последовательности Л неофинательных целых чисел меньших Лдля Л близкого к объему памяти, доступному программе в используемом компьютере и выраженному в битах (см. профамму 12.3)

12.3 Последовательный поиск

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