Программа 12.5 Таблица символов (упорядоченная) с использованием массива

Подобно программе 12.4, в этой реализации используется массив элементов, но для нее не обязательно, чтобы ключи были небольшими целыми числами. Поддержание упорядоченности массива обеспечивается тем, что при вставке нового элемента большие элементы смещаются с целью освобождения места, как это делается при сортировке вставками. В этом случае функция search может выполнять в массиве поиск элемента с указанным ключом, возвращая значение nullltem при обнаружении элемента с большим ключом. Реализация функций select и sort тривиальны, а реализация функции remove оставляется на самостоятельную проработку (см. упражнение 12.16).

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

private:

Item nullltem, *st; int N; public:

ST(int maxN)

{ st = new Item[maxN+l] ; N = 0; } int count()

{ return N; } void insert(Item x)

{ int i = N++; Key v = x. key () ;

while (i > 0 && V < st[i-1].key())

{ st[i] = st[i-l]; i-; } st[i] = x;

Item search (Key v) (

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

if (! (st[i] .key 0 < v)) break; if (v == st[i].key()) return st[i]; return nullltem;

Item select(int k)

{ return st[k]; } void show(ostream& os)

{ int i = 0;

while (i < N) st[i++].show(os); }

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

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

Этот подход характеризуется тем, что операция insert выполняется быстро, а операции select и sort требуют значительно большего объема работы (для выполнения каждой из них требуется реализация одного из методов, описанных в главах 7-10). Удаление {remove) элемента с указанным ключом можно выполнить, отыскав его, а затем переместив последний элемент массива в позицию удаляемого элемента и уменьшив размер массива на 1; удаление всех элементов с заданным ключом реализуется путем повторения этой операции. Если доступен дескриптор, предоставляющий индекс элемента в массиве, поиск не требуется и операция remove выполняется за постоянное время.

Еще одна простая реализация таблицы символов - использование связного списка. В этом случае можно также хранить список в упорядоченном виде с целью, урощения поддержки операции sort л\\Ьо оставить его неупорядоченным для ускорения операции insert. Программа 12.6 демонстрирует второй подход. Как обычно, преимущество применения связных списков по сравнению с массивами состоит в том, что вовсе не обязательно заранее точно определять максимальный размер таблицы, а недостаток - в необходимости расхода дополнительного объема памяти (под ссылки) и невозможности эффективной поддержки операции select.

Программа 12.6 Таблица символов (неупорядоченная) с использованием связного списка

в этой реализации операций construct, count, search и insert используется односвяз-ный список, каждый узел которого содержит элемент с ключом и ссылкой. Функция insert помещает новый элемент в начало списка и выполняется за постоянное время. Функция-член search использует приватную рекурсивную функцию searchR для просмотра списка.

Поскольку список не упорядочен, реализации операций sort и select опущены.

#include <stdlib.h> template <class Item, class Key> class ST {

private:

Item nullltem; struct node { Item item; node* next; node(Item x, node* t)

{ item = x; next = t; }

typedef node *link; int N; link head;

Item searchR (link t, Key v) { if (t == 0) return nullltem;

if (t->item.key 0 - v) return t->item; return searchR(t->next, v);

public:

ST(int maxN)

{ head = 0; N = 0; } int count ()

{ return N; } Item search(Key v)

{ return searchR(head, v); } void insert(Item x)

{ head = new node(x, head); N++; }

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

Сохранение элементов в упорядоченном виде - иллюстрация идеи, что в о общем случае в реализациях таблиц символов ключи используются для определенной структуризации данных в целях ускорения поиска. Структура может допускать быстрые реализации и ряда других операций, но при этом следует учитывать затраты на поддержку структуры, которые могут приводить к замедлению других операций. Мы встретимся с многими примерами упомянутого явления. Например, в приложении, где функция 5orf требуется часто, нужно было бы выбрать упорядоченное представление (с использованием массива или списка), поскольку такая структура таблицы делает реализацию функции sort тривиальной, в отличие от необходимости полной реализации сортировки. В приложении, в котором заведомо потребуется частое выполнение операции select, нужно было бы использовать представление с использованием упорядоченного массива, поскольку при такой структуре таблицы затрачиваемое на выполнение упомянутой операции время постоянно. И напротив, время выполнения операции select в связном списке линейно зависит от количества элементов, даже если список упорядочен.

Чтобы подробнее проанализировать последовательный поиск произвольных ключей, начнем с рассмотрения затрат на вставку новых ключей и отдельно рассмотрим случаи успешного и неуспешного поиска. Первый часто называют попаданием при поиске, а второй - промахом при поиске. Нас интересуют затраты как при попаданиях, так и при промахах в среднем и худшем случаях. Строго говоря, в реализации с использованием упорядоченного массива (см. программу 12.5) для каждого исследуемого элемента используются две операции сравнения (== и <). При анализе в главах 12-16 каждую из таких пар мы будем считать одной операцией сравнения, поскольку обычно для эффективного их объединения можно выполнить низкоуровневую оптимизацию.

Лемма 12.2 При последовательном поиске в таблице символов с N элементами для выявления попаданий при поиске требуется выполнение около N/2 сравнений (в среднем).

См. лемму 2.1. Доказательство применимо к массивам или связным спискам, упорядоченным или неупорядоченным.

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

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