Подобная организация удобна в некоторых приложениях, поскольку все элементы с данным искомым ключом возвращаются в результате выполнения одной операции search (поиск) или могут быть удалены одной операцией remove (удаление). С точки зрения реализации, эта организация эквивалентна предоставлению управления дублированными ключами клиенту. Вторая возможность - оставление элементов с одинаковыми ключами в главной структуре данных поиска и возврат в результате поиска любого элемента с данным ключом. Это соглащение проще для приложений, которые обрабатывают элементы по одному, когда порядок обработки элементов с одинаковыми ключами не важен. Однако, это может оказаться неудобным с точки зрения разработки алгоритма, поскольку может потребоваться расширение интерфейса за счет включения в него механизма для получения всех элементов с данным ключом или для вызова указанной функции для каждого элемента с конкретным ключом. Третья возможность - принять, что каждый элемент имеет уникальный идентификатор (кроме ключа) и потребовать, чтобы функция search отыскивала элемент с данным идентификатором при заданном ключе. Разумеется, может потребоваться и какой-либо более сложный механизм. Эти рассуждения применимы ко всем операциям на таблицах символов при наличии дублированных ключей. Нужно ли удалить все элементы с данным ключом, любой элемент с ключом или конкретный элемент (для чего требуется реализация, поддерживающая дескрипторы элементов)? При описании реализаций таблиц символов мы неформально указываем возможный наиболее удобный способ обработки элементов с одинаковыми ключами, не обязательно рассматривая каждый механизм для каждой реализации.

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

Программа 12.3 Пример клиента для таблицы символов

В этой программе таблица символов используется для поиска отдельных ключей в произвольно сгенерированной или считанной со стандартного ввода последовательности. Для каждого ключа операция search используется для проверки того, просматривался ли ключ раньше. Если ранее ключ не просматривался, функция вставляет элемент с этим ключом в таблицу символов. Типы ключей и элементов, а также абстрактные операции с ними определены в item.cxx (см., например, программу 12.1).

#include <ios*ream.h> #include <stdlib.h> #include Item.cxx #include ST.cxx int main(int argc, char *argv[]) { int N, maxN = atoi (argv[l]) , sw = atoi (argv[2]) ; SKI tern, Key> st(maxN) ; for (N = 0; N < itiaxN; N++) { Item v;

if (sw) v.randO; else if (v.scanO) break; if (! (St. search (v.keyO )) .null ()) continue; St.insert(v);

St. show (cout) ; cout endl; cout N keys endl;

cout St. count 0 distinct keys endl;

Как обычно, следует иметь в виду, что различные реализации операций на таблицах символов обладают различными характеристиками производительности, которые могут зависеть от конкретного набора операций. В одном приложении операция insert может использоваться сравнительно редко (возможно, для построения таблицы) при огромном количестве выполняемых операций search; в другом, в сравнительно небольших таблицах, может выполняться офомное количество операций insert и remove, перемежаемое операциями search. Не все реализации будут поддерживать все операции, и некоторые из них могут обеспечивать эффективную поддержку определенных функций за счет других; при этом явно предполагается, что менее эффективные функции выполняются редко. Каждая из базовых операций в интерфейсе таблицы символов находит важные применения, поэтому для обеспечения эффективного использования различных комбинаций операций пре1и1агается множество базовых вариантов реализации. В этой и нескольких следующих главах основное внимание будет уделено реализациям базовых функций construct, insert и search с приведением некоторых пояснений относительно функций remove, select, sort и join, когда в этом возникнет необходимость. Широкое множество алгоритмов, требующих рассмотрения, обусловлено различием характеристик производительности различных комбинаций базовых операций, а также ограничениями, накладываемыми на значения ключей, размерами элементов и другими факторами.

В этой главе мы встретимся с реализациями, в которых среднее время выполнения операций search, insert, remove и select для произвольных ключей пропорционально логарифму количества элементов в словаре, а время выполнения операции sort линейно зависит от количества элементов. В главе 13 мы исследуем способы обеспечения этого уровня производительности; кроме того, в разделе 12.2 будет приведена одна, а в главах 14 и 15 - несколько реализаций, производительность которых при определенных условиях остается постоянной.

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

Упражнения

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

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

О 12.3 Используя программу 12.2 АТД таблицы символов, создать реализации АТД стека и очереди.

\> 12.4 Используй АТД таблицы символов, определенный программой интерфейса 12.2, создать реализацию АТД очереди по приоритету, который поддерживает операции удаления как максимального, так и минимального элементов.

12.5 Используя АТД таблицы символов, определенный программой интерфейса 12.2, создать реализацию сортировки массива, совместимой с реализациями, описанными в главах 6-10,

[> 12.6 Добавьте в профамму 12.2 объявления деструктора, конструктора копирования и перегруженной операции присваивания, чтобы преобразовать ее в АТД первого класса (см. разделы 4.8 и 9.5).

12.7 Определите интерфейс АТД таблицы символов, который позволяет клиентским программам удалять конкретные элементы с использованием дескрипторов и изменять ключи (см. разделы 4.8 и 9.5).

[> 12.8 Приведите интерфейс типа элемента и реализацию элементов с двумя полями: 16-битным целочисленным ключом и строкой С, которая содержит информацию, связанную с этим ключом.

12.9 Укажите среднее количество отдельных ключей, которые профамма-драйвер (программа 12.3) будет находить среди произвольных целых чисел, меньших 1000, для = 10, 10, 10, 10 * и 10 Определите свой ответ эмпирически, аналитически или обоими методами.

12.2 Поиск с использованием индексации по ключам

предположим, что значения ключей - отдельные небольшие числа. В этом случае простейший алгоритм поиска основывается на сохранении элементов в массиве, индексированном по ключам, как сделано в реализации, приведенной в программе 12,4. Код весьма прост: оператор new[] инициализирует все записи значением nuUItem, затем мы вставляем {insert) элемент со значением ключа к, просто сохраняя его в массиве st[k], и выполняем поиск {search) элемента со значением ключа к, отыскивая его в st[k]. Для удаления {remove) элемента со значением ключа к значение nullltem помещается в st[k]. Реализации операций выбора {select), сортировки {sort) и подсчета {count) в профамме 12.4 используют линейный просмотр массива с пропуском нулевых элементов. Реализация предоставляет клиенту решать задачи обработки элементов с дублированными ключами и проверки таких условий, как указание операции remove для ключа, отсутствующего в таблице.

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

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