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

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

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

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

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

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

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

В отличие от этого, программа 4.1 содержит реализацию абстрактного типа данных, соответствующего типу данных из профаммы 3.3. В этой реализации используется класс языка С++, в котором сразу определены как данные, так и связанные с ними операции. Программа 4.2 является клиентской программой, работающей с упомянутым типом данных. Эти две профаммы выполняют те же самые вычисления, что и программы 3.3 и 3.8. Они иллюстрируют ряд основных свойств классов, которые сейчас будут рассматриваться.

Программа 4.1 Реализация класса POINT (точка)

В этом классе определен тип данных, который состоит из набора значений, представляющих собой пары чисел с плавающей точкой (предполагается, что они интерпретируются как точки на декартовой плоскости), а также две функции-члена, определенные для всех экземпляров класса POINT: функция POINT(), которая является конструктором, инициализирующим координаты случайными значениями от О до 1, и функция distance(POINT), вычисляющая расстояние до другой точки. Представление данных является приватным (private), и обращаться к нему или модифицировать его могут только функции-члены. В свою очередь, функции-члены являются общедоступными (public) и доступны для любого клиента. Код можно сохранить, например, в файле с именем POINT.cxx.

#include <math.h> class POINT {

private: float X, у;

public: POINT()

{ X = 1.0*rand()/RAND MAX;

у = 1.0*rand()/RAND MAX; } float distance(POINT a)

{ float dx = x-a.x, dy = у-а.у;

return sqrt(dx*dx + dy*dy); }

Когда мы записываем в программе определение наподобие int i, мы даем системе команду зарезервировать область памяти для данных (встроенного) типа int, на которую будем ссылаться по имени i. В языке С++ такая сущность называется объектом. При записи в программе такого определения, как POINT р, говорят, что создается объект класса POINT, ссылка на который осуществляется по имени р. В нашем примере каждый объект имеет два элемента данных, которые называются х и у. Так же как и в случае структур, на них ссылаются по именам, подобным р.у.

Элементы данных х и у называются данными-членами класса. В классе могут быть также определены функции-члены, которые реализуют операции, связанные с этим типом данных. Например, класс, определенный в программе 4.1, имеет две функции-члена, которые называются POINT и distance.

Клиентские программы, такие как программа 4.2, могут обращаться к функциям-членам, связанным с объектом, ссылаясь на них по именам точно так же, как они ссылаются на данные, находящиеся в какой-нибудь структуре struct. Например, выражение p.distance(q) вычисляет расстояние между точками р и q (это же самое расстояние даст и выражение q.distance(p)). Функция POINT(), первая функция в программе 4.1, является особой функцией-членом, называемой конструктором: у нее такое же имя, как и у класса, и она вызывается тогда, когда требуется создать объект этого класса. Определение POINT р в программе-клиенте приводит к распределению области памяти под новый объект и затем (посредством функции POINT()) к присвоению каждому из двух его элементов данных случайного значения в диапазоне от О до 1.

Программа 4.2 Программа-клиент для класса POINT (нахождение ближайшей точки)

Эта версия программы 3.8 Т)вляется клиентом, который использует АТД POINT, определенный в программе 4.3. Оператор new[] создает массив объектов абстрактного типа POINT (вызывая конструктор POINT() для инициализации каждого объекта случайными значениями координат). Оператор a[i].distance(a[j]) вызывает для объекта a[i] функцию-член distance с аргументом аЦ].

#include <iostreani.h> #include <stdlib.h> #include POINT.схх int main(int argc, char *argvt]) { float d = atof(argvt2]) ; int i, cnt = 0, N = atoi (argv[1]) ; POINT *a = new POINT [N] ; for (i = 0; i < N; i++)

for (int j = i+1; j < N; j++)

if (a[i].distance(a[j]) < d) cnt++; cout cnt pairs within d endl;