ся в стеке) при отсутствии быстрого доступа к любому элементу (в реализации на базе связных списков).

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

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

Этот факт является непосредственным следствием внимательного изучения профамм 4.7 и 4.8.

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

Реализация на базе связного списка создает впечатление стека, который может увеличиваться неограниченно. Однако в практических условиях такой стек невозможен: рано или поздно, когда запрос на выделение еще некоторого объема памяти не сможет быть удовлетворен, new сгенерирует исключение. Можно также организовать стек на базе массива, который будет увеличиваться и уменьшаться динамически: когда стек заполняется наполовину, размер массива увеличивается в два раза, а когда стек становится наполовину пустым, размер массива уменьшается в два раза. Детали реализации упомянутой стратегии мы оставляем в качестве упражнения в главе 14, где этот процесс подробно рассматривается для более сложных применений.

Упражнения

> 4.21 Определите содержимое элементов s[0], ... , s[4] после выполнения с помощью программы 4.7 операций, показанных на рис. 4.1.

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

4.23 Измените реализацию стека магазинного типа на базе массива (программа 4.7) так, чтобы она вызывала функцию-член еггог(), если клиентская программа пытается выполнить операцию вытолкнуть, когда стек пуст, или операцию затолкнуть, когда стек переполнен.

4.24 Измените реализацию стека магазинного типа на базе связного списка (программа 4.8) таким образом, чтобы она вызывала функцию-член еггогО, если кли-

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

4.25 Измените реализацию стека магазинного типа на базе связного списка (профамма 4.8) так, чтобы для создания списка она использовала массив индексов (см. рис. 3.4).

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

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

4.28 Реализуйте функцию вычисления инфиксных выражений, состояших из целых чисел. Она должна включать программы 4.5 и 4.6, а также использовать АТД из упражнения 4.27. Примечание: пофебуется рассмотреть случай, когда оба стека содержат элементы одного и того же типа.

4.5 Создание нового АТД

Разделы с 4.2 по 4.4 содержат пример полного кода программы на С++ для одной из наиболее важных абстракций: стека магазинного типа. В интерфейсе из раздела 4.2 определены основные операции; клиентские программы из раздела 4.3 могут использовать эти операции независимо от их реализации, а вот реализация из раздела 4.4 обеспечивает конкретное представление и программный код ATD.

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

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

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

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

В программе 4.9 определен интерфейс, включающий две операции (в дополнение к операции создать (construct)). Похоже, что эти операции описывают алгоритмы связности, рассмотренные в главе 1, на высоком уровне абстракции. Какие бы базовые алгоритмы и структуры данных не лежали в основе, необходимо иметь возможность проверки связности двух узлов, а также описания, что конкретные два узла являются связанными.

Программа 4.9 Интерфейс АТД Отношения эквивалентности

Интерфейс АТД построен так, чтобы было удобно записывать код, в точности соответствующий принятому решению рассматривать алгоритм связности в виде класса, поддерживающего три абстрактных операции: инициализировать (initialize) абстрактную структуру данных для отслеживания связей между заданным числом узлов; на11ти (find), являются ли два узла связанными; и соединить (unite) два данных узла и считать их с этого момента связанными.

class UF {

private:

программный код, зависяирт оф реализации public: UF(int);

int find(int, int); void unite(int, int);

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

Программа 4.11 является реализацией интерфейса union-find, который определен в программе 4.9. В этой реализации (см. раздел 1.3) применяется бор деревьев, в основе которого лежат два массива, представляющие известную информацию о связях. В разных алгоритмах, рассмотренных в главе 1, используются различные реализации АТД, причем их можно тестировать независимо друг от друга, не изменяя клиентскую программу.

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