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

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

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

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

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

На рис. 4.9 проиллюстрирована работа модифицированного АТД “ Стек без повторяющихся элементов” для случая, показанного на рис. 4.1; на рис.4.10 приведен результат аналогичных изменений для очереди FIFO.

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

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

Имеется важный частный случай, для которого существует простое решение; его иллюстрирует программа 4.16 для АТД “ Стек магазинного типа”. В этой реализации предполагается, что элементы являются целыми числами в диапазоне от нуля до М–1. Далее, чтобы определять, имеется ли уже в стеке некоторый элемент, в реализации используется второй массив, индексами которого являются сами элементы стека. При вставке в стек элемента I выполняется также установка в 1 i-того элемента второго массива, а при удалении из стека I i-ый элемент второго массива устанавливается в 0. Во всем остальном для вставки и удаления элементов применяется тот же код с одной дополнительной проверкой: перед вставкой элемента выполняется проверка, нет ли в стеке такого элемента. Если есть, операция занесения элемента игнорируется. Это решение не зависит от используемого представления стека – на базе массива, связного списка или чего-нибудь еще. Для реализации принципа “ Удалять старый элемент” требуется большой объем работы.

Суммируя изложенное выше, можно сказать, что один из способов реализации стека без повторяющихся элементов, функционирующего по принципу “игнорировать новый элемент”, состоит в поддержке двух структур данных. Первая, как и прежде, содержит элементы стека и позволяет отслеживать порядок, в котором были вставлены элементы стека. Вторая структура является массивом, позволяющим отслеживать, какие элементы находятся в стеке; индексами этого массива являются элементы стека. Такое использование массива рассматривается как частный случай реализации таблицы символов, которая обсуждается в разделе 12.2. Когда известно, что элементы представляют собой целые числа в диапазоне от 0 до М-1, эту же методику можно применять по отношению к любой обобщенной очереди.

Программа 4.16. Стек индексных элементов, в котором запрещены повторяющиеся элементы.

В этой реализации стека магазинного типа предполагается, что класс Item имеет тип int, который возвращает целые числа в диапазоне от 0 до max N-1, так что он может поддерживать массив t, где каждому элементу стека соответствует отличное от нуля значение. Этот массив дает возможность функции push быстро проверять, не находится ли уже в стеке ее аргумент, и если так, то не предпринимать никаких действий. В каждом элементе массива t используется только один бит, поэтому при желании можно сэкономить оперативную память, используя вместо целых чисел символы или биты.

template <class Item>

Дата добавления: 2015-07-08