4.85 Используя АТД, разработанный в упражнении 4.84, модифицируйте профамму вычисления постфиксных выражений из раздела 4.3 так, чтобы она могла вычислять постфиксные выражения, состоящие из целых чисел произвольной точности.

4.86 Напишите клиентскую программу, которая с помощью АТД Полином из упражнения 4.83 вычисляет интсфалы, используя разложение функций в ряды Тейлора и оперируя с ними в символической форме.

4.87 Разработайте АТД, который позволяет клиентским профаммам выполнять алгебраические операции над векторами чисел с плавающей точкой.

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

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

4.90 Напишите реализацию для интерфейса из упражнения 4.89, используя там, где это необходимо строковую библиотеку С++.

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

4.92 Напишите интерфейс и реализацию АТД Множество индексов , в котором обрабатываются множества целых чисел в диапазоне от О до Л/ - 1 (где М - заданная константа) и имеются операции создания множества, объединения двух множеств, пересечения двух множеств, дополнения множества, разности двух множеств и вывода содержимого множества. Для представления каждого множества используйте массив из Л/ - 1 элементов, принимающих значения 0-1.

4.93 Напишите клиентскую программу, которая тестирует АТД, созданный в упражнении 4.92.

4.10 Перспективы

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

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

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

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

Распечатано программой FmePnnt

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

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

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

Рекурсия и деревья

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

Изучение рекурсии неразрывно связно с изучением рекурсивно определяемых структур, называемых деревьями. Деревья используются как для упрощения понимания и анализа рекурсивных программ, так и в качестве явных структур данных. В главе 1 мы уже встречались с применением деревьев (хотя и не рекурсивным). Взаимосвязь между рекурсивными программами и деревьями лежит в основе значительной части материала книги. Деревья используются для упрощения понимания рекурсивных программ; в свою очередь, рекурсивные программы используются для построения деревьев; в конечном итоге, глобальная взаимосвязь между ними (и рекуррентные отношения) применяется при анализе алгоритмов. Рекурсия