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

Метод, который применяется в языке С++ для реализации типов данных первого класса, применим к любому классу: в частности, он применим к обобщенным очередям и, таким образом, обеспечивает возможность создания программ, которые оперируют со стеками и очередями FIFO во многом так же, как и с другими типами данных С++. При изучении алгоритмов эта возможность достаточно важна, поскольку она предоставляет естественный способ выражения высокоуровневых операций, относящихся к таким АТД. Например, вполне уместно говорить об операциях соединения двух очередей - т.е. создании из них одной очереди. Далее будут рассматриваться алгоритмы, которые реализуют такие операции для АТД Очередь по приоритету (глава 9) и Таблица символов (глава 12).

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

Программа 4.17 Драйвер комплексных чисел (корни из единицы)

Эта клиентская программа выполняет вычисления над комплексными числами с использованием АТД, который позволяет проводить вычисления непосредственно с интересующей нас абстракцией. В этой связи объявляются переменные типа Complex и задействуются в арифметических выражениях с перегруженными операциями. Данная программа проверяет реализацию ЛТД, вычисляя корни из единицы в различных степенях. При помощи соответствующего определения перегруженной операции << (см. упр. 4.70) производится вывод таблицы, показанной на рис. 4.12.

#include <iostreain.h> #include <stdlib.h> #include <math.h> #include COMPLEX.cxx int main(int argc, char *argv[]) { int N = atoi(argv[l]); cout N complex roots of unity endl; for (int к = 0; к < N; k++) { float theta = 2 . 0*3 .14159*]c/N;

Complex t(cos(theta) , sin(theta)), x = t; cout к : t ; for (int j = 0; j < N-l; j++) x *= t; cout X endl;

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

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

Число / = ./Zy называется мнимым числом. Хотя как вещественное число не имеет смысла, мы называем его / и выполняем над / алгебраические операции, заменяя на - 1 всякий раз, когда его встречаем. Комплексное число состоит из двух частей: вещественной и мнимой - комплексные числа можно записывать в виде а + Ы, где а и b - вещественные числа. Для умножения комплексных чисел применяются обычные алгебраические правила, при этом всякий раз заменяется на -1. Например:

(а + Ы){с + di) = ас + bci + adi + bdi = (ас - bd) + (ad + bc)i.

При умножении комплексных чисел вещественные или мнимые части могут сокращаться (принимать значения 0), например: (1 - 0(1 -0 = 1-/-/+/ = -2/, (1 +/У = 4/ = -4, (1 + if = 16.

Разделив обе части последнего уравнения на 16 = {-Jlf, мы находим, что

/ 1 . \8

42 42

= 1.

Вообще говоря, имеется много комплексных чисел, которые при возведении в степень дают 1. Они называются комплексными корнями из единицы. Действительно, для каждого имеется ровно N комплексных чисел z, для которых справедливо г = 1. Легко можно показать, что этим свойством обладают числа

/sin

для А: = о, 1, ... , A-l (см. упр. 4.68). Например, если в этой формуле взять А: = 1 и N = S, получим корень восьмой степени из единицы, который мы только что нашли.

Программа 4.17 вычисляет все корни Л-ой степени из единицы для любого данного и затем возводит их в Л-ую степень, используя операцию *=, определенную в данном АТД. Выходные данные программы показаны на рис. 4.12. При этом ожи-

дается, что каждое из этих чисел, возведенное в N-ую степень, дает один и тот же результат - 1 или 1 + О/. Полученные мнимые части не равны строго нулю из-за ограниченной точности вычислений. Интерес к этой программе объясняется тем, что она использует класс Complex точно так же, как встроенный тип данных. Далее будет подробно показано, почему это возможно.

Даже в этом простом примере важно, чтобы тип данных был абстрактным, поскольку имеется еще одно стандартное представление, которым можно было бы воспользоваться - полярные координаты (см. упр. 4.67). Программа 4.18 - это интерфейс, который может использоваться такими клиентами, как программа 4.17; а программа 4.19 - это реализация, в которой используется стандартное представление данных (одно число типа float для вещественной части и другое - для мнимой).

Программа 4.18 Интерфейс АТД первого класса для комплексных чисел

Этот интерфейс для комплексных чисел позволяет реализациям создавать объекты типа Complex (инициализированные двумя значениями типа float), обеспечивает доступ к вещественной и мнимой частям и использование операции *=. Хотя это и не задано явно, стандартные системные механизмы, действующие для всех классов, позволяют использовать объекты класса Complex в операторах присваивания, а также в аргументах и возвращаемых значениях функций.

class Солф1ех

private:

программный код,

зависящий оф реализации public:

Complex(float, float);

float Re() const;

float Im() const;

Complexfi operator*=(Complexfi);

Когда в программе 4.17 мы полагаем х = t, где X и t являются объектами класса Complex, система распределяет память для нового объекта и копирует в новый объект значения, относящиеся к объекту t. Если использовать объект класса Complex как аргумент или возвращаемое значение функции, процесс будет таким же. Кроме того, когда объект выходит за пределы области видимости, система освобождает связанную с ним память. Например, в профамме 4.17 система освобождает память, связанную с объектами t и х класса Complex, после цикла for так же, как и память, связанную с переменной г типа float. Коротко говоря, класс Complex используется подобно встроенным типам данных, т.е. он относится к типам данных первого класса.

0 1,000 0.000 1.000 0.000

1 0.707 0.707 1.000 0.000

2 0.000 1.000 1.000 0.000

3 -0.707 0.707 1.000 0.000 4-1.000 0,000 1.000 0.000

5 -0,707 -0,707 1.000 0.000

6 0.000 -1,000 1,000 0.000

7 0.707 -0.707 1.000 0.000

РИСУНОК 4.12 КОМПЛЕКСНЫЕ КОРНИ ИЗ ЕДИНИЦЫ

Эта таблица содержит выходные данные программы 4.17, когда она вызывается с параметрами а.оШ 8, а реализация перегруженной операции выполняет соответствующее форматирование выходных данных (см. упр. 4.70). Восемь комплексных корней из единицы равны: ±\,±iu

2 2

(два левых столбца). При возведении в восьмую степень все эти восемь чисел дают в результате 1 + О/ (два левых столбца).