чтобы, интерпретируя ее как последовательность операций над деком в смысле упр. 4.41, получить вторую последовательность.

> 4.43 Запишите интерфейс для АТД Дек .

4.44 Для интерфейса дека (упр. 4.43) запишите реализацию, в которой в качестве базовой структуры данных используется массив.

4.45 Для интерфейса дека (упр.4.43) запишите реализацию, в которой в качестве базовой структуры данных используется двухсвязный список.

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

4.47 Напишите программу-клиент, которая проверяет полученный АТД Дек (упр. 4.43), считывая с командной строки в качестве первого аргумента строку команд подобную приведенной в упр. 4.40, после чего выполняет указанные операции. В интерфейс и реализации добавьте функцию-член dump и распечатывайте содержимое дека после каждой операции, как это сделано на рис. 4.6.

о 4.48 Создайте АТД Неупорядоченная очередь (напишите интерфейс и реализацию), в котором в качестве базовой структуры данных используется массив. Обеспечьте для каждой операции постоянное время выполнения.

4.49 Создайте АТД Неупорядоченная очередь (напишите интерфейс и реализацию), в котором в качестве базовой сфуктуры данных используется связный список. Напишите как можно более эффективные реализации операций insert и remove и проанализируйте связанные с ними издержки для наихудшего случая их выполнения.

> 4.50 Напишите программу-клиент, которая выбирает для лотереи числа следующим образом: заносит в неупорядоченную очередь числа от 1 до 99, а затем удаляет пять из них и выводит результат.

4.51 Напишите программу-клиент, которая считывает с командной строки в качестве первого аргумента целое число N, а затем распечатывает результат раздачи в покере карт на N ифоков. Для этого она должна заносить в неупорядоченную очередь N элементов (см. упр. 4.7) и затем вьщавать результат выбора из этой очереди пяти карт за один раз.

4.52 Напишите профамму, которая решает задачу связности. Для этого она должна вставлять все пары в неупорядоченную очередь, а затем с помощью алгоритма взвешенного быстрого поиска (программа 1.3) извлекает их из очереди.

4.7 Повторяющиеся и индексные элементы

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

Например, компании, поддерживающей список рассылки по адресам покупателей, может потребоваться расширить этот список информацией из других списков, собранных с различных источников. Это выполняется с помощью соответствующих операций insert. При этом, по-видимому, не требуется заносить информацию о покупателях, адреса которых уже присутствуют в списке. Далее можно будет увидеть, что тот же принцип применим в самых разнообразных приложениях. В качестве еще одного примера рассмотрим задачу маршрутизации сообщений в сложной сети передачи данных. Можно попытаться передать сообщение одновременно по нескольким маршрутам, однако каждому отдельно взятому узлу сети необходима только одна копия этого сообщения в свои внутренние структуры данных.

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

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

На рис. 4.9 проиллюстрирована работа модифицированного АТД Стек без повторяющихся элементов для

РИСУНОК 4.9 СТЕК МАГАЗИННОГО ТИПА БЕЗ ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ

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

R S Т

случая, показанного на рис. 4.1; на рис. 4.10 приведен результат аналогичных изменений для очереди FIFO.

Вообще говоря, решение относительно повторяющихся элементов приходится принимать тогда, когда профамма-клиент делает запрос на занесение элемента, уже имеющегося в структуре данных. Как следует поступить в такой ситуации? Продолжать работу так, как будто запроса вообще не было? Или удалить старый элемент и занести новый? Это решение влияет на порядок, в котором, в конечном счете, будут обрабатываться элементы в АТД наподобие стеков и очередей FIFO (см. рис. 4.11); упомянутое различие очень существенно для клиентских программ. Например, компания, использующая подобный АТД для списка рассылки, могла бы предпочесть занесение нового элемента на место старого (вероятно, предполагая, что он содержит более свежую информацию о клиенте); а коммутационный центр, использующий такой АТД, мог бы предпочесть проигнорировать новый элемент (вероятно, он уже предпринял соответствующие шаги и отправил сообщение). Более того, выбор того или иного принципа влияет на реализации: как правило, принцип удалить старый элемент более труден в реализации, нежели принцип игнорировать новый элемент , поскольку связан с модификацией структуры данных.

Для реализации обобщенных очередей без повторяющихся элементов необходимо иметь абстрактную операцию, проверяющую равенство элементов (как это рассматривалось в разделе 4.1). Помимо такой операции необходимо иметь возможность определять, существует ли уже в структуре данных новый вставляемый элемент. Этот общий случай предполагает необходимость реализации АТД Таблица символов , поэтому он рассматривается в контексте реализаций, в главах с 12 по 15.

Имеется важный частный случай, для которого существует простое решение; его иллюстрирует профамма 4.16 для АТД Стек магазинного типа . В этой реализации предполагается, что элементы являются целыми числами в диапазоне от О до Л/ - 1. Далее, чтобы определять, имеется ли уже в стеке некоторый элемент, в реализации используется второй массив, индексами которого являются сами элементы стека. При вставке в стек элемента / выполняется также установка в 1 /-ого элемента второго массива, а при удалении из стека элемента / i-ый элемент второго массива устанавливается в 0. Во всем остальном для вставки и уда-

N F R

т о и

F I R FIRS

I R S

I R S Т

R S Т

R S Т I

R S Т I N

S Т I N

Т I N

I N F

1 N F

N F R

N F R S

F R S

R S S

S Т Т

т о и

т о и

о и и

РИСУНОК 4.10 ОЧЕРЕДЬ FIFO БЕЗ ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ.

ФУНКЦИОНИРУЮЩАЯ ПО ПРИНЦИПУ ИГНОРИРОВАТЬ НОВЫЙ ЭЛЕМЕНТ

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