public: POINT();

float distance(POINT) const;

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

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

Применение классов языка С++ для реализации абстрактных типов данных с соблюдением общепринятого правила, гласящего, что интерфейс состоит из определений общедоступных функций, не является идеальным вариантом, поскольку интерфейс и реализация разделяются не полностью. Когда мы изменяем реализацию, нам приходится перекомпилировать профаммы-клиенты. Некоторые альтернативные варианты рассматриваются в разделе 4,5.

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

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

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

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

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

числа, можно, скажем, выполняя цикл, в котором некоторое целое число умножается на два до тех пор, пока не появится сообщение об ощибке переполнения.

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

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

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

Упражнения

> 4.1 Предположим, необходимо подсчитать количество пар точек, находящихся внутри квадрата со стороной d. Чтобы решить эту задачу, сделайте две разные версии программы-клиента и реализации: во-первых, модифицируйте соответствующим образом функцию-член distance; во-вторых, замените функцию-член distance функциями-членами X и Y.

4.2 В программе 4.3 к классу точки добавьте функцию-член, которая возвращает расстояние до начала координат.

о 4.3 В программе 4.3 модифицируйте реализацию АТД Point таким образом, чтобы точки были представлены полярными координатами.

о 4.4 Напишите клиентскую программу, которая считывает из командной строки целое число Ли заполняет массив Лточками, среди которых нет двух равных друг другу. Для проверки равенства или неравенства точек используйте перефуженную операцию ==, описанную в тексте настоящей главы.