4.5 Используя представление на базе связного списка, подобное тому, что в программе 3.14, преобразуйте интерфейс обработки списка (list-processing interface) из раздела 3.4 (программа 3.12) в реализацию АТД на базе классов. Протестируйте полученный интерфейс, модифицируя клиентскую программу (программу 3,13) так, чтобы она использовала этот интерфейс; затем перейдите к реализации на базе массивов (см. упражнение 3.52).

4.1 Абстрактные объекты и коллекции объектов

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

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

В разделе 3.1, в котором обсуждалось применение простых типов данных для написания программ, не зависящих от типов объектов, для задания типов элементов данных использовался typedef. Этот подход позволяет использовать один и тот же код для, скажем, целых чисел и чисел с плавающей точкой за счет простого изменения typedef При использовании указателей типы объектов могут быть сколь угодно сложными. При таком подходе часто приходится делать неявные предположения относительно операций, выполняемых над объектами (например, в профамме 3.2 предполагается, что для объектов типа Number определены операции сложения, умножения и приведения к типу float) и, кроме того, мы не скрываем представление данных от клиентских программ. Абстрактные типы данных позволяют делать явными любые предположения относительно операций, выполняемых над объектами данных.

В оставшейся части данной главы рассматривается несколько примеров использования классов С++ с целью построения АТД для обобщенных объектов данных. Будет продемонстрировано создание АТД для обобщенных объектов типа Item, позволяющие записывать клиентские программы, в которых объекты Item используются точно так же, как и встроенные типы данных. Там, где это необходимо, в классе Item явно определяются операции, которые должны выполняться над обобщенными

объектами с помощью наших алгоритмов. Все эти характеристики объектов определяются вместе с сокрытием от клиентских программ любой информации о представлении данных.

После реализации класса Item для обобщенных объектов (либо принятия решения использовать встроенный класс), воспользуемся механизмом шаблонов языка С++ для написания кода, который является обобщенным относительно типов объектов. Например, операцию обмена для обобщенных элементов можно определить следующим образом:

template <class Item>

void exch(Item &x. Item &y)

{ Item t = x; X = y; у = t; }

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

Разобравшись с классами обобщенных объектов, можно перейти к рассмотрению коллекций (collection) объектов. Многие структуры данных и алгоритмы применяются для реализации фундаментальных АТД, представляющих собой коллекции абстрактных объектов и создаваемых на основе двух следующих операций:

вставить новый объект в коллекцию.

удалить объект из коллекции.

Такие АТД называются обобщенными очередями (generalized queues). Как правило, для удобства в них также явно включаются следующие операции: создать (construct) структуру данных (конструкторы), подсчитать (count) количество объектов в структуре данных (или просто проверить, не пуста ли она). Могут потребоваться и операции, наподобие уничтожить (destroy) структуру данных (деструкторы) и копировать (сору) структуру данных (конструкторы копирования); эти операции обсуждаются в разделе 4.8.

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

Мы рассматриваем некоторые из этих фундаментальных структур данных, их свойства и примеры применения; в то же самое время мы используем их в качестве примеров, чтобы проиллюстрировать основные механизмы, используемые для разработки АТД. В разделе 4.2 исследуется стек магазинного типа (pushdown stack), в котором для удаления объектов используется следующее правило: всегда удаляется объект,

добавленный последним. В разделе 4.3 рассматриваются различные применения стеков, а в разделе 4.4 - реализации стеков, придерживаясь при этом того подхода, что реализации должны быть отделены от приложений. После обсуждения стеков мы вернемся к предыдущему материалу и рассмотрим процесс создания нового АТД в контексте абстракции union-find для задачи связности, которая исследовалась в главе 1. После этого мы вернемся к коллекциям абстрактных объектов и рассмотрим очереди FIFO (которые на данном уровне абстракции отличаются от стеков только тем, что в них применяется другое правило удаления элементов), а также обобщенные очереди, где запрещены повторяющиеся элементы.

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

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

В языке С+-+- классы, реализующие коллекции абстрактных объектов, называются контейнерными классами (container classes). Некоторые из обсуждаемых структур данных реализованы в библиотеке языка С++ или ее расширениях (стандартной библиотеке шаблонов - Standard Template Library). Во избежание путаницы, мы будем редко ссылаться на эти классы, и материал книги представляется, начиная с самых основ.

Упражнения

1> 4.6 Дайте определение для класса Item, в котором для проверки равенства чисел с плавающей точкой используется перефуженная операция ==. Считайте два числа с плавающей точкой равными, если абсолютная величина их разности, деленная на большее (по абсолютной величине) из двух чисел, меньше чем 10~.