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

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

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

Упражнения

> 4.63 Перегрузите операции + и += для работы с комплексными числами (профаммы 4.18 и 4.19).

4.64. Преобразуйте АТД Отношения эквивалентности (из раздела 4.5) в тип данных первого класса.

4.65 Создайте АТД первого класса для использования в программах, оперирующих с игральными картами.

4.66 Используя АТД из упражнения 4.65, напишите программу, которая опытным путем определит вероятность раздачи различных наборов карт при игре в покер.

о 4.67 Разработайте реализацию для АТД Комплексное число на базе представления комплексных чисел в полярных координатах (т.е. в форме ге).

4.68 Воспользуйтесь тождеством е = cosO + i sinO для доказательства того, что е = 1, а yv комплексных корней ТУ-ой степени из единицы равны

+ /sm

27Zk

для А: = О, 1, ... , N- 1.

4.69 Перечислите корни N-oVi степени из единицы для значений от 2 до 8.

4.70 С использованием precision и setw из файла iostream.h создайте реализацию перегруженной операции для программы 4.19, которая выдаст выходные данные, показанные на рис. 4.12 для программы 4.17.

> 4.71 Опишите точно, что происходит в результате запуска программы 4.20 моделирования очереди, используя такую простую реализацию, как программа 4.14 или 4.15.

4.72 Разработайте реализацию данного в тексте АТД первого класса Очередь FIFO (программа 4.21), в которой в качестве базовой структуры данных используется массив.

> 4.73 Напишите интерфейс АТД первого класса для стека.

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

4.75 Разработайте реализацию АТД первого класса для стека из упражнения 4.73, которая в качестве базовой структуры данных использует связный список.

о 4.76 Используя приведенные ранее АТД первого класса для комплексных чисел (программы 4.18 и 4.19), модифицируйте программу вычисления постфиксных выражений из раздела 4.3 таким образом, чтобы она вычисляла постфиксные выражения, состоящие из комплексных чисел с целыми коэффициентами. Для простоты считайте, что все комплексные числа имеют ненулевые целые коэффициенты как для вещественной, так и для мнимой частей, и записываются без пробелов. Например, для исходного выражения

l+2i 0+li + l-2i * 3+4i + .

программа должна вывести результат 8+41.

4.77 Выполните математический анализ процесса моделирования очереди в программе 4.20, чтобы определить вероятность (как функцию аргументов N п М) того, что очередь, выбранная для Л-ой операции get, будет пустой, а также ожидаемое количество элементов в этих очередях после N итераций цикла for.

4.9 Пример использования АТД в приложении

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

2 х 2х х х

X X 1-jc+---

2 6

(l + x + x +х)= 1 +

-+---

2 3 3

Кроме того, необходима возможность вычислять полиномы для заданного значения X. Для X = 0.5 обе стороны приведенного выше уравнения имеют значение 1.1328125. Операции умножения, сложения и вычисления полиномов являются центральными операциями в огромном числе математических вычислений. Программа 4.23 - это простой пример, в котором выполняются символические операции, соответствующие полиномиальным уравнениям

(х+ 1) = х + 2;с+ 1,

(л;+ Ifx + Зх+ Зх+ 1,

(х+ 1) = х +4;с + 6х+4х+ 1,

(х+ 1) = х +5х + Юх + \0х+ 5х+ 1,

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

Программа 4.23 Клиентская программа для АТД Полином

(биномиальные коэффициенты)

Эта клиентская программа использует АТД Полином , определенный в интерфейсе (программа 4.24), для выполнения алгебраических операций над полиномами с целыми коэффициентами. В программу из командной строки вводится целое число N и число с плавающей точкой р. Затем она вычисляет (х + 1) и проверяет результат, вычисляя значение результирующего полинома для х ~ р.

finclude <iostreeua.h> finclude <stdlib.h> #include POLY.схх int main(int argc, char *argv[]) { int N = atoi(argv[l]); float p = atof(argv[2]);

cout Binomial coefficients endl;

POLY<int> x(l,l), one(l,0), t = x + one, у = t;

for (int i = 0; i < N; i++) { у = y*t; cout у endl; }

cout y.eval(p) endl;

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

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