Программа 4.12 Абстрактный класс для АТД отношения эквивалетности

Приведенный ниже код фломирует интерфейс АТД отношения эквивалентности, который обеспечивает полное разделение клиентов и реализаций (см. текст).

class uf {

public:

virtual uf(int) = 0;

virtual int find(int, int) = 0;

virtual void unite(int, int) = 0;

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

Есть еще один способ действий - применить стратегию четырех файлов, при которой приватные части хранятся не в интерфейсе, но в отдельном файле. Например, в класс из программы 4.9 можно было бы добавить в начале строки

private:

tinclude UFprivate.h

после чего поместить строки

int *id, *sz; int find(int);

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

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

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

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

Упражнения

4.29 Модифицируйте программу 4.11 так, чтобы в ней использовалось сжатие пути делением пополам.

4.30 Устраните упоминаемую в тексте неэффективность программы, добавив в профамму 4.9 операцию, которая объединяет операции union и find и соответствующим образом изменив профаммы 4.11 и 4.10.

о 4.31 Модифицируйте интерфейс (программа 4.9) и реализацию (программа 4.11) для отношений эквивалентности так, чтобы в них присутствовала функция, возвращающая количество узлов, связанных с данным.

4.32 Модифицируйте программу 4.11 так, чтобы для представления структуры данных в ней вместо параллельных массивов использовался массив структур.

о 4.33 Используя стек целых чисел (без шаблонов), напишите программу из трех файлов, вычисляющую значение постфиксного выражения. Обеспечьте, чтобы клиентскую программу (аналог профаммы 4.5) можно было компилировать отдельно от реализации стека (аналог программы 4.7).

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

4.35 Создайте полную реализацию АТД Отношения эквивалентности на базе абстрактного класса с виртуальными функциями и сравните производительность полученной программы и программы 4.11 на крупных задачах связности (в стиле таблицы 1.1).

4.6 Очереди FIFO и обобщенные очереди

Очередь с дисциплиной FIFO (First-In, First-Out - Первым пришел, первым ушел) является еще одним фундаментальным АТД, который подобен стеку магазинного типа, но подчиняется противоположному правилу удаления элемента в операции удалить. Из очереди удаляется не последний вставленный элемент, а наоборот - элемент, который был вставлен в очередь раньше всех остальных.

Пожалуй, ящик для входящей корреспонденции нашего занятого профессора должен бы был функционировать как очередь FIFO, поскольку дисциплина первым пришел, первым ушел интуитивно кажется справедливой для обработки входящей корреспонденции. Однако профессор не всегда вовремя отвечал на телефонные звонки и даже позволял себе опаздывать на лекции! В стеке какая-нибудь служебная записка может застрять на дне, но срочные случаи обрабатываться сразу же после появления. В очереди FIFO документы обрабатываются по порядку, и каждый должен ожидать своей очереди.

Программа 4.13 Интерфейс АТД Очередь FIFO

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

template <class Item> class QUEUE {

private:

программный код, завися]ций от реализации ptiblic:

QUEUE(int); int empty () ; void put(Item); Item get() ;

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