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

Программа 4.10 Клиентская программа для АТД Отношения эквивалентности

АТД из программы 4.9 позволяет отделить алгоритм связности от реализации union-find), тем самым делая его более доступным.

#include <iostream.h> #include <stdlib.h> #include UF.cxx

int main(int argc, char *argv[]) { int p, q, N = atoi(argv[l]) ; UF info(N); while (cin p q) if (!info.find (p, q)) {

info.unite (p, q);

cout p q endl;

Комбинация программ 4.10 и 4.11 с точки зрения функциональности эквивалентна программе 1.3; однако, разбиение программы на две части является более эффективным подходом, так как:

позволяет отделять решение задачи высокого уровня (задачи связности) от решения задачи низкого уровня (задачи union-find) и решать эти две задачи независимо

предоставляет естественный способ сравнения различных алгоритмов и структур данных, применяемых при решении этой задачи

определяет с помощью интерфейса способ проверки ожидаемой работы программного обеспечения

обеспечивает механизм, позволяющий совершенствовать представления (переходить к новым структурам данных и новым алгоритмам) без каких-либо изменений кода клиентских программ

предоставляет абстракцию, которую можно использовать при построении других алгоритмов

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

Программа 4.11 Реализация АТД Отношения эквивалентности

Этот код взвешенного быстрого объединения из главы 1 является реализацией интерфейса из программы 4.9. В данной реализации код упакован в форму, удобную для его использования в других приложениях. Приватная перегруженная функция-член find реализует обход дерева вплоть до его корня.

class UF {

private: int *id, *sz; int find(int x) { while (x != id[x]) x = id[x] ; return x; } public: UF(int N) {

id = new int[N]; sz = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; sz[i] = 1; }

int find(int p, int q)

{ return (find(p) = find(q)); } void unite(int p, int q)

{ int i = find(p) , j = find(q) ; if (i == j) return; if (sz[i] < sz[j])

{ id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; }

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

Создать заголовочный файл с именем, скажем, UF.h, который будет содержать объявление класса, представление данных и объявления функций, но не определения функций. В рассматриваемом примере этот файл будет содержать код программы 4.9, в который также включается представление данных (приватные объявления из программы 4.11). Затем необходимо сохранить определения функций в отдельном файле .схх, который будет также содержать директиву include для файла UF.h (как это имеет место в любой клиентской программе). При таком порядке вещей появляется возможность раздельной компиляции клиентских программ и реализаций. В самом деле, определение любой функции-члена класса можно сохранить в отдельном файле, если только функция-член объявляется в классе, а в определении функции перед ее именем помещается имя класса и знак ::, Например, определение функции find в нашем примере следовало бы записать так:

int UF:: find (int p, int q)

{ return (find(p) == find(q)); }

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

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

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

Абстрактный (abstract) класс - это класс, все члены которого являются чистыми виртуальными функциями. В любом классе, порожденном от абстрактного класса, должны быть определены все функции-члены и любые необходимые приватные данные-члены; таким образом, по нашей терминологии абстрактный класс является интерфейсом, а любой класс. Порожденный от него, является реализацией. Программы-клиенты могут использовать интерфейс, а система С++ может обеспечить соблюдение соглашений между клиентами и реализациями, даже когда клиенты и реализации функций компилируются раздельно. Например, в программе 4.12 показан абстрактный класс uf для отношений эквивалентности; если изменить первую строку программы 4.11 следующим образом:

class UF : ptiblic class uf

TO она будет указывать на то, что класс UF является производным от класса uf и поэтому в нем определены (как минимум) все функции-члены класса uf - т.е. класс UF является реализацией интерфейса uf.