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

Как и в случае с сортировкой, мы рассмотрим методы без определения типов обрабатываемых элементов. Столь же подробно, как в разделе 6.8, будут исследоваться реализации, использующие интерфейс, который определяет Item и основные абстрактные операции с данными. Мы рассмотрим методы как с использованием сравнения, так и с использованием корня, использующие в качестве индексов ключи или фрагменты ключей. Чтобы разделить роли, выполняемые при поиске элементами и ключами, понятие Item (элемент), использованное в главах 6-11, расширяется до элементов, содержащих ключи типа Key. Поскольку требуется несколько больше элементов, чем было необходимо для ознакомления с алгоритмами сортировки, будем считать, что они объединены в пакеты абстрактных типов данных, реализованные с помощью классов С++, как показано в программе 12.1. Функция-член кеу() будет применяться для извлечения ключей из элементов, а перегруженная операция operator== - для проверки равенства двух ключей. В этой главе и главе 13 также перегружается operator< для сравнения значений двух ключей, что помогает при поиске; алгоритмы поиска, описанные в главах 14 и 15, основываются на извлечении фрагментов ключей за счет использования базовых операций с корнями, которые использовались в главе 10. Кроме того предполагается, что элементы инициализируются нулевыми значениями (null), и что клиенты имеют доступ к функции null(), которая может проверять, является ли элемент нулевым. Нулевые элементы используются для поддержки возвращаемого значения в том случае, когда ни один элемент в таблице символов не имеет искомого ключа. В некоторых реализациях предполагается, что нулевые элементы имеют служебный ключ.

Программа 12.1 Пример реализации АТД элемента

Это определение класса элементов, представляющих собой небольшие записи, состоящие из целочисленных ключей и связанной с ними информации в виде значений с плавающей точкой, иллюстрирует основные соглашения в отношении элементов таблиц символов. Наши реализации таблиц символов - клиентские программы, в которых операции == и < используются для сравнения ключей, а функции-члены кеуО и пи11() - соответственно для получения доступа к ключам и проверки, являются ли элементы нулевыми.

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

#include <stdlib.h> #include <iostreaiii.h> static int maxKey - 1000; typedef int Key ; class Item {

private:

Key keyval; float info; pviblic: I tern 0

{ keyval = msucKey; } Key keyO

{ return keyval; } int nulK)

{ return keyval = maxKey; } void randO

{ keyval = 1000*::rand()/RAND MAX; info = 1.0*::rand()/RAND MAX; } int scan(istreeua& is - cin)

{ return (is keyval info) != 0; } void show (ostream& os cout)

{ os keyval info endl;

ostream& operator (ostreaua& os, Item& x) { x.show(os); return os; }

Чтобы использовать при поиске интерфейсы и реализации для чисел с плавающей точкой, строк и более сложных элементов, описанных в разделах 6.8 и 6.9, нужно только убедиться, что в Key присутствуют определения кеу(), niill(), operator== и operator<, а также изменить rand, scan и show, сделав их функциями-членами, которые ссылаются на ключи соответствующим образом.

Программа 12.2 - интерфейс, который определяет базовые операции таблицы символов (за исключением операции объединить (join). Этот интерфейс будет использоваться в клиентских программах и всех реализациях поиска в этой и нескольких следующих главах. Абстрактный тип данных первого класса не применяется в том смысле, как это принималось в разделе 4.8 (см. упражнение 12.6), поскольку в больишнстве программ используется только одна таблица, а добавление конструкторов копирования, перегруженных операций присваивания и деструкторов, хоть и несложная задача в большинстве реализаций, но все же она отвлекала бы от важных характеристик алгоритмов. В программе 12.2 можно было бы также определить версию интерфейса для манипулирования дескрипторами элементов подобно программе 9.8 (см. упражнение 12.7), но это излишне усложняет программу в типичной ситуации, когда достаточно манипулировать элементом посредством ключа. Интерфейс не задает способ определения элемента, который должен бьггь удален. В большинстве реализаций используется интерпретация удалить элемент с ключом, равным данному элементу , при этом подразумевается предварительный поиск. В других реализациях, которые предоставляют дескрипторы и могут выполнять проверку идентичности элемента, необходимость поиска перед удалением исключается, и поэтому для них допустимы более быстрые алгоритмы. Кроме того, при рассмотрении алгоритмов для операции объединить, предполагающих наличие приложений, которые обрабатывают несколько таблиц символов, можно использовать реализации АТД первого класса таблицы символов, которые сводят к минимуму напрасную трату времени и расход памяти (см. раздел 12.9).

Программа 12.2 АТД таблицы символов

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

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

private:

Код, зависящий от реализации public:

ST(int);

int count 0;

Item search(Key) ;

void insert(Item) ;

void remove(Item);

Item select(int);

void show(ostream&);

В некоторых алгоритмах не предполагается наличие какого-либо определенного порядка ключей, и поэтому для сравнения ключей в них используется только operator== (а не operator<), однако во многих реализациях таблиц символов используется упорядоченная организация ключей, применяемых в operator< для структурирования данных и управления поиском. Кроме того, абстрактные операции select (выбор) и sort (сортировка) явно ссылаются на порядок ключей. Функция sort объединяется в пакет в виде функции, которая отправляет все элементы в выходной поток по порядку без необязательной перекомпоновки. Реализации sort можно легко обобш,ить с целью получения функции, которая посещает элементы в порядке их ключей, возможно, применяя к каждому из них процедуру, переданную в аргументе. Используемые функции sort для таблиц символов мы назвали show, поскольку приведенные реализации обеспечивают отображение содержимого таблицы символов отсортированным по порядку. Для алгоритмов, в которых operator< не используется, нет необходимости, чтобы ключи были сравнимы друг с другом, поэтому такие алгоритмы необязательно поддерживают операции select и sort.

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

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