Абстрактные типы данных

#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 = y-a.y;
  return sqrt(dx*dx + dy*dy); }
 };
      

  #include <iostream.h>
  #include <stdlib.h>
  #include "POINT.cxx"
  int main(int argc, char *argv[])
    { float d = atof(argv[2]);
      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 << " пар в радиусе " << d << endl;
    }
      

static float distance(POINT a, POINT b)
  {
    float dx = a.x  -  b.x, dy = a.y  -  b.y;
    return sqrt(dx*dx + dy*dy);
  }
      

friend float distance(POINT, POINT);
      

Дружественная (friend) функция - это функция, которая, не будучи членом класса, имеет доступ к его приватным членам.

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

float X() const { return x; }
float Y() const { return y; }
      

Эти функции объявлены с ключевым словом const, так как они не модифицируют данные-члены объекта, для которого вызываются. Мы часто включаем в классы языка C++ подобные функции. Обратите внимание, что если бы использовалось другое представление данных, например, полярные координаты, то реализовать эти функции было бы труднее, но эта трудность была бы прозрачной для клиента. Преимущества подобной гибкости можно также задействовать в функциях-членах - если в реализации функции distance из программы 4.1 вместо обращений a.x использовать обращения a.X() , то этот код не придется переписывать при изменении представления данных. Помещая эти функции в приватную часть класса, можно обеспечить такую гибкость даже в тех классах, где не требуется доступ клиента к данным.

Во многих приложениях главная цель в создании класса - определение нового типа данных, наиболее соответствующего потребностям приложения. В таких ситуациях часто требуется использовать этот тип данных таким же образом, как и встроенные типы данных языка C++, например, int или float. Эта тема рассматривается более подробно в разделе 4.8. Один важный инструмент в языке С++, помогающий нам достичь этой цели, называется перегрузкой операций (operator overloading) - она позволяет указать, что к объекту класса могут применяться фундаментальные операции, и что в точности эти операции должны делать. Например, предположим, что требуется считать две точки совпадающими, если расстояние между ними меньше чем 0,001. Добавив в класс код

friend int operator==(POINT a, POINT b)
  { return distance(a, b) < .001; }
      

можно с помощью операции == проверять, равны ли две точки (согласно приведенному определению).

Другой операцией, для которой обычно желательна перегрузка, является операция << из класса ostream. При программировании на языке C++ обычно предполагается, что эту операцию можно использовать для вывода значений любого объекта; в действительности же так можно делать, только если в классе определена перегруженная операция <<. В классе POINT это можно сделать следующим образом:

ostream operator<<(ostream t, POINT p)
  {
    cout << "(" << p.X() << "," << P.Y() << ")";
    return t;
  }
      

Эта операция не является ни функцией-членом, ни даже дружественной: для доступа к данным она использует общедоступные функции-члены X() и Y() .

Как понятие класса языка C++ соотносится с моделью "клиент-интерфейс-реализация" и абстрактными типами данных? Оно обеспечивает непосредственную языковую поддержку, но очень часто для этого существует несколько различных подходов. Общепринято следующее правило: объявления общедоступных функций в классе образуют его интерфейс. Другими словами, представление данных хранится в приватной части класса, где оно недоступно для программ, использующих класс (клиентских программ). Все, что клиентские программы "знают" о классе - это общедоступная информация о его функциях-членах (имя, тип возвращаемого значения и типы аргументов). Чтобы подчеркнуть важность интерфейса (определяемого посредством класса), мы в этой книге сначала рассматриваем интерфейс (наподобие программы 4.3), и уже затем рассматриваем реализацию - в данном случае это программа 4.1. Дело в том, что такой порядок упрощает анализ других реализаций, с другими представлениями данных и другими реализациями функций, а также тестирование и сравнение реализаций, позволяя делать это без каких-либо изменений клиентских программ.

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

Программа 4.3. Интерфейс абстрактного типа данных POINT

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

class POINT
  {
    private:
      // Программный код, зависящий от реализации 
    public:
      POINT();
      float distance(POINT) const;
  };
      

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

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

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

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

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

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

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

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

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

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

Упражнения

4.1. Предположим, что необходимо подсчитать количество пар точек, находящихся внутри квадрата со стороной d. Для решения этой задачи напишите две разные версии клиента и реализации: (1) модифицируйте соответствующим образом функцию-член distance; (2) замените функцию-член distance функциями-членами X и Y.

4.2. Добавьте в класс точки (программа 4.3) функцию-член, которая возвращает расстояние до начала координат.

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

4.4. Напишите клиентскую программу, которая считывает из командной строки целое число N и заполняет массив N точками, среди которых нет двух равных друг другу. Для проверки равенства или неравенства точек используйте перегруженную операцию ==, описанную в тексте настоящей главы.

4.5. Используя представление на базе связного списка, наподобие программы 3.14, преобразуйте интерфейс обработки списков из раздела 3.4 (программа 3.12) в реализацию АТД на базе классов. Протестируйте полученный интерфейс, изменив клиентскую программу (программа 3.13) так, чтобы она использовала этот интерфейс; затем перейдите к реализации на базе массивов (см. упражнение 3.52).

Абстрактные объекты и коллекции объектов

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

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

В разделе 3.1 , в котором обсуждалось применение простых типов данных для написания программ, не зависящих от типов объектов, для указания типов элементов данных использовалось описание typedef. Этот подход позволяет использовать один и тот же код для, скажем, целых чисел и чисел с плавающей точкой за счет простого изменения typedef. При использовании указателей типы объектов могут быть сколь угодно сложными. При таком подходе часто приходится делать неявные предположения относительно операций, выполняемых с объектами (например, в программе 3.2 предполагается, что для объектов типа Number определены операции сложения, умножения и приведения к типу float), и, кроме того, представление данных не скрывается от клиентских программ. Абстрактные типы данных позволяют сделать явными любые предположения относительно операций, выполняемых с объектами данных.

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

После реализации класса Item для обобщенных объектов (либо выбора подходящего встроенного класса) мы будем пользоваться механизмом шаблонов языка С++ для написания кода, который является обобщенным относительно типов объектов. Например, операцию обмена для обобщенных элементов можно определить следующим образом:

template <class Item>
void exch(Item x, Item y)
  { Item t = x; x = y; y = t; }
        

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

Разобравшись с классами обобщенных объектов, можно перейти к рассмотрению коллекций (collection) объектов. Многие структуры данных и алгоритмы, которые будут рассмотрены в данной книге, применяются для реализации фундаментальных АТД, представляющих собой коллекции абстрактных объектов и создаваемых с помощью двух следующих операций:

вставить новый объект в коллекцию.

удалить объект из коллекции.

Такие АТД называются обобщенными очередями (generalized queue). Как правило, для удобства в них также явно включаются следующие операции: создать (construct) структуру данных (конструктор) и подсчитать (count) количество объектов в структуре данных (или просто проверить, пуста ли она). Могут также потребоваться операции уничтожить (destroy) структуру данных (деструктор) и копировать (copy) структуру данных (конструктор копирования); эти операции будут рассмотрены в разделе 4.8.

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

Мы рассмотрим некоторые из этих фундаментальных структур данных, их свойства и примеры применения; в то же самое время мы используем их в качестве примеров, чтобы проиллюстрировать основные механизмы, используемые для разработки АТД. В разделе 4.2 будет рассмотрен стек магазинного типа (pushdown stack), в котором для удаления объектов используется следующее правило: всегда удаляется объект, вставленный последним. В разделе 4.3 будут описаны различные применения стеков, а в разделе 4.4 - реализации стеков, при этом реализации будут отделены от приложений. После обсуждения стеков мы вернемся к процессу создания нового АТД в контексте абстракции объединение-поиск для задачи связности, которая была рассмотрена в . А затем мы вернемся к коллекциям абстрактных объектов и рассмотрим очереди FIFO и обобщенные очереди (которые на данном уровне абстракции отличаются от стеков только правилом удаления элементов), а также обобщенные очереди без повторяющихся элементов.

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

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

В языке C++ классы, реализующие коллекции абстрактных объектов, называются контейнерными классами (container class). Некоторые из структур данных, которые будут рассмотрены ниже, реализованы в библиотеке языка C++ или ее расширениях (стандартной библиотеке шаблонов - Standard Template Library). Во избежание путаницы мы будем редко ссылаться на эти классы, и излагать материал, начиная с самых основ.

Упражнения

4.6. Дайте определение для класса Item, в котором для проверки равенства чисел с плавающей точкой используется перегруженная операция ==. Считайте два числа с плавающей точкой равными, если абсолютная величина их разности, деленная на большее (по абсолютной величине) из двух чисел, меньше чем 10-6.

4.7. Дайте определение класса Item и перегрузите операции == и << так, чтобы их можно было использовать в программе обработки игральных карт.

4.8. Перепишите программу 3.1 так, чтобы в ней использовался класс обобщенных объектов Item. Ваша программа должна работать для любого типа объектов класса Item, которые могут выводиться при помощи операции <<, генерироваться случайным образом статической функцией-членом rand(), и для которых определены операции + и /.

АТД для стека магазинного типа

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

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

Определение 4.2. Стек магазинного типа - это АТД, который включает две основные операции: вставить, или втолкнуть (push), новый элемент и удалить, или вытолкнуть (pop), элемент, вставленный последним.

Когда мы говорим об АТД стека магазинного типа, мы считаем, что существует достаточно хорошее описание операций втолкнуть и вытолкнуть, чтобы клиентская программа могла их использовать, а также некоторая реализация этих операций в соответствии с правилом удаления элементов такого стека: последним пришел, первым ушел (last-in, first-out, сокращенно LIFO).

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

(рис 4.1) Пример стека магазинного типа (очереди LIFO)

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

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

Первая строка кода интерфейса для АТД стека в программе 4.4 добавляет в этот класс шаблон C+ + , позволяющий клиентским программам указывать вид объектов, которые могут заноситься в стек.

Объявление

STACK<int> save(N) указывает, что элементы стека save должны быть типа int (и что стек может вместить не более N элементов). Программа-клиент может создавать стеки, содержащие объекты типа float, или char, или любого другого типа (даже типа STACK) - для этого необходимо просто изменить параметр шаблона в угловых скобках. Мы можем считать, что указанный класс замещает в реализации класс Item везде, где он встречается.

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

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

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

Программа 4.4. Интерфейс АТД стека

Используя то же соглашение, что и в программе 4.3, мы определяем АТД стека через объявление общедоступных функций. При этом предполагается, что представление стека и любой другой код, зависящий от реализации, являются приватными, чтобы можно было изменять реализации, не изменяя код клиентских программ. Кроме того, в этом интерфейсе применяется шаблон, что позволяет программам-клиентам использовать стеки, содержащие объекты любых классов (см. программы 4.5 и 4.6), а в реализациях для обозначения типа объектов стека использовать ключевое слово Item (см. программы 4.7 и 4.8). Аргумент конструктора STACK задает максимальное количество элементов, которые можно поместить в стек.

template <class Item>
class STACK
  {
    private:
      // Программный код, зависящий от реализации
    public:
      STACK(int);
      int empty() const;
      void push(Item item);
      Item pop();
  };
        

Упражнения

4.9. В последовательности

E A S * Y * Q U E * * * S T * * * I O * N * * *

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

4.10. Используя те же соглашения, что и в упражнении 4.9, вставьте звездочки в последовательность E A S Y таким образом, чтобы последовательность значений, возвращаемых операциями вытолкнуть, была следующей: (1) E A S Y; (2) Y S A E; (3) A S Y E; (4) A Y E S; либо докажите, что такая последовательность невозможна.

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

Примеры клиентов, использующих ATД стека

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

5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 )

При вычислении необходимо сохранять промежуточные результаты: например, если сначала вычисляется 9 + 8, придется сохранить результат 17 на время вычисления 4*6. Стек магазинного типа представляет собой идеальный механизм для сохранения промежуточных результатов в таких вычислениях.

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

5 9 8 + 4 6 * * 7 + *

Форма записи, обратная постфиксной, называется префиксной или польской записью (так как ее придумал польский логик Лукашевич).

При инфиксной записи чтобы отличить, например, выражение

5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 )

от выражения

( ( 5 * 9 ) + 8 ) * ( ( 4 * 6 ) + 7 )

требуются скобки; но в постфиксной (или префиксной) записи скобки не нужны. Чтобы понять, почему это так, можно рассмотреть следующий процесс преобразования постфиксного выражения в инфиксное: все группы из двух операндов со следующим за ними знаком операции заменяются их инфиксными эквивалентами и заключаются в круглые скобки - они означают, что этот результат может рассматриваться как операнд. То есть, группы a b * и a b + заменяются соответственно на группы (a * b) и (a + b). Затем то же самое преобразование выполняется с полученным выражением, и весь процесс продолжается до тех пор, пока не будут обработаны все операции. Вот шаги преобразования для нашего случая:

5 9 8 + 4 6 * * 7 + *

5 ( 9 + 8 ) ( 4 * 6 ) * 7 + *

5 ( ( 9 + 8 ) * ( 4 * 6 ) ) 7 + *

5 ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 ) *

( 5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 ) )

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

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

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

Примером такого языка является язык PostScript, с помощью которого напечатана данная книга. Это завершенный язык программирования, в котором программы пишутся в постфиксном виде и интерпретируются с помощью внутреннего стека, в точности как в программе 4.5. Мы не можем осветить здесь все аспекты этого языка (см. раздел ссылок), но он достаточно прост, чтобы мы рассмотрели некоторые реальные программы и оценили полезность постфиксной записи и абстракции стека магазинного типа. Например, строка 5 9 8 add 4 6 mul mul 7 add mul является PostScript-программой! Программа на языке PostScript состоит из операций (таких, как add и mul) и операндов (например, целые числа). Программа на этом языке интерпретируется так же, как в программе 4.5 - слева направо. Если встречается операнд, он заносится в стек; если встречается знак операции, из стека извлекаются операнды для этой операции (если они нужны), а затем результат (если он есть) заносится в стек.

(рис 4.2) Вычисление постфиксного выражения

Эта последовательность операций демонстрирует использование стека для вычисления постфиксного выражения 5 9 8 + 4 6 * * 7 + *. Выражение обрабатывается слева направо и если встречается число, оно заносится в стек; если же встречается знак операции, то эта операция выполняется с двумя верхними числами стека, и результат опять заносится в стек.

Программа 4.5. Вычисление постфиксного выражения

Эта программа-клиент для стека магазинного типа считывает любое постфиксное выражение с операциями умножения и сложения целых чисел, затем вычисляет это выражение и выводит полученный результат. Промежуточные результаты она хранит в стеке целых чисел; при этом предполагается, что интерфейс из программы 4.4 реализован в файле STACK.cxx как шаблон класса.

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

В программе неявно предполагается, что целые числа и знаки операций ограничены какими-нибудь другими символами (скажем, пробелами), но программа не проверяет корректность входных данных. Последний оператор if и цикл while выполняют вычисление наподобие функции atoi языка C++, которая преобразует строки в коде ASCII в целые числа, пригодные для вычислений. Когда встречается новая цифра, накопленный результат умножается на 10, и к нему прибавляется эта цифра.

#include <iostream.h>
#include <string.h>
#include "STACK.cxx"
int main(int argc, char *argv[])
  { char *a = argv[1]; int N = strlen(a);
    STACK<int> save(N);
    for (int i = 0; i < N; i++)
      {
        if (a[i] == '+')
          save.push(save.pop() + save.pop());
        if (a[i] == '*')
          save.push(save.pop() * save.pop());
        if ((a[i] >= '0')  (a[i] <= '9'))
          save.push(0);
        while ((a[i] >= '0')  (a[i] <= '9'))
          save.push(10*save.pop() + (a[i++]-'0'));
      }
    cout << save.pop() << endl;
  }
        

Таким образом, на рис 4.2 полностью описан процесс выполнения этой программы: после выполнения программы в стеке остается число 2 07 5.

В языке PostScript имеется несколько примитивных функций, которые служат инструкциями для абстрактного графопостроителя; а кроме них, можно определять и собственные функции. Эти функции вызываются с аргументами, расположенными в стеке, таким же способом, как и любые другие функции. Например, следующий код на языке PostScript 0 0 moveto 144 hill 0 72 moveto 72 hill stroke соответствует последовательности действий "вызвать функцию moveto с аргументами 0 и 0, затем вызвать функцию hill с аргументом 144" и т.д. Некоторые операции относятся непосредственно к самому стеку.

Например, операция dup дублирует элемент в верхушке стека; поэтому, например, код 144 dup 0 rlineto 60 rotate dup 0 rlineto означает следующую последовательность действий: вызвать функцию rlineto с аргументами 144 и 0, затем вызвать функцию rotate с аргументом 60, затем вызвать функцию rlineto с аргументами 144 и 0 и т.д. В PostScript-программе, показанной на рис 4.3, определяется и используется функция hill. Функции в языке PostScript подобны макросам: строка показан пример PostScript-программы, в которой определяется функция и вычерчивается простая диаграмма.

(рис 4.3) Простая программа на языке PostScript

В верхней части рисунка приведена диаграмма, а в нижней - PostScript-программа, формирующая эту диаграмму. Программа является постфиксным выражением, в котором используются встроенные функции moveto, rlineto, rotate, stroke и dup, а также определяемая пользователем функция hill (см. текст). Графические команды являются инструкциями графопостроителю: команда moveto устанавливает перо в заданную позицию страницы (координаты даются в пунктах, равных 1/72 дюйма); команда rlineto перемещает перо в новую позицию, координаты которой задаются относительно текущей позиции (тем самым к пройденному пути добавляется очередной участок); команда rotate изменяет направление движения пера (поворачивает влево на заданное число градусов); а команда stroke вычерчивает пройденный путь.

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

(рис 4.4) Преобразование инфиксного выражения в постфиксное

Данная последовательность демонстрирует использование стека для преобразования инфиксного выражения (5*(((9+8)*(4*6))+7)) в постфиксную форму 5 9 8 + 4 6 * * 7 + *. Выражение обрабатывается слева направо: если встречается число, оно записывается в выходной поток; если встречается левая скобка, она игнорируется; если встречается знак операции, он заносится в стек; и если встречается правая скобка, то в выходной поток выталкивается знак операции, находящийся на верхушке стека.

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

Программа 4.6 представляет собой реализацию этого процесса. Обратите внимание, что аргументы в постфиксном выражении расположены в том же самом порядке, что и в инфиксном выражении. Любопытно, что левые скобки в инфиксном выражении не нужны. Однако они необходимы, если существуют операции, имеющие разное количество операндов (см. упражнение 4.14).

Программа 4.6. Преобразование из инфиксной формы в постфиксную

Эта программа является еще одним примером программы-клиента для стека магазинного типа. В данном случае стек содержит символы. Для преобразования (A+B) в постфиксную форму A B + левая скобка игнорируется, символ A записывается в выходной поток, знак + запоминается в стеке, символ B записывается в выходной поток, а затем при обнаружении правой скобки знак + извлекается из стека и записывается в выходной поток.

#include <iostream.h>
#include <string.h>
#include "STACK.cxx"
int main(int argc, char *argv[])
  { char *a = argv[1]; int N = strlen(a);
    STACK<char> ops(N);
    for (int i = 0; i < N; i++)
      {
        if (a[i] == ')')
          cout << ops.pop() << " ";
        if ((a[i] == '+') || (a[i] == '*'))
          ops.push(a[i]);
        if ((a[i] >= '0')  (a[i] <= '9'))
          cout << a[i] << " ";
      }
    cout << endl;
  }
        

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

Это приложение также демонстрирует достоинства абстрактных типов данных и шаблонов C++ . Здесь не просто используются два разных стека: один из них содержит объекты типа char (знаки операций), а другой - объекты типа int (операнды). С помощью АТД в виде шаблона класса, определенного в программе 4.4, можно даже объединить две рассмотренных клиентских программы в одну (см. упражнение 4.19). Несмотря на привлекательность этого решения, учтите, что оно может и не быть оптимальным: ведь различные реализации могут отличаться своей производительностью, так что не стоит априори считать, что одна и та же реализация будет хорошо работать в обоих случаях. Вообще-то наш главный интерес - реализации и их производительность, и сейчас мы приступим к рассмотрению этих вопросов применительно к стеку магазинного типа.

Упражнения

4.12. Преобразуйте в постфиксное выражение

( 5 * ( ( 9 * 8 ) + ( 7 * ( 4 + 6 ) ) ) ) .

4.13. Таким же способом, как на рис 4.2, покажите содержимое стека при вычислении программой 4.5 выражения

59*8746+*213*+*+*.

4.14. Расширьте программы 4.5 и 4.6 таким образом, чтобы они обрабатывали операции - (вычитание) и / (деление).

4.15. Расширьте решение упражнения 4.14 таким образом, чтобы оно включало унарные операции - (смена знака) и $ (извлечение квадратного корня). Кроме того, измените механизм абстрактного стека в программе 4.5 так, чтобы можно было использовать числа с плавающей точкой. Например, имея в качестве исходного выражение

(-(-1) + $((-1) * (-1)-(4 * (-1)))) / 2 программа должна выдать число 1.618034.

4.16. Напишите на языке PostScript программу которая вычерчивает следующую фигуру:

4.17. Методом индукции докажите, что программа 4.5 правильно вычисляет любое постфиксное выражение.

4.18. Напишите программу, которая преобразует постфиксное выражение в инфиксное, используя стек магазинного типа.

4.19. Объедините программы 4.5 и 4.6 в один модуль, в котором будут использоваться два разных АТД: стек целых чисел и стек (знаков) операций.

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

(x = 1)

(y = (x + 1))

(((x + y) * 3) + (4 * x))

программа должна вывести число 13.

Реализации АТД стека

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

Если для представления стека применяется массив, то все функции, объявленные в программе 4.4, реализуются очень просто - см. программу 4.7. Элементы заносятся в массив в точности так, как показано на рис 4.1, при этом отслеживается индекс верхушки стека. Выполнение операции втолкнуть означает запоминание элемента в позиции массива, указываемой индексом верхушки стека, а затем увеличение этого индекса на единицу; выполнение операции вытолкнуть означает уменьшение индекса на единицу и извлечение элемента, обозначенного этим индексом.

Программа 4.7. Реализация стека магазинного типа на базе массива

В этой реализации N элементов стека хранятся как элементы массива: s[0], ..., s[N-1], начиная с первого занесенного элемента и завершая последним. Верхушкой стека (позицией, в которую будет занесен следующий элемент стека) является элемент s[N]. Максимальное количество элементов, которое может вмещать стек, программа-клиент передает в виде аргумента в конструктор STACK, размещающий в памяти массив заданного размера. Однако код не проверяет такие ошибки, как помещение элемента в заполненный стек (или выталкивание элемента из пустого стека).

template <class Item>
class STACK
  {
    private:
      Item *s; int N;
    public:
      STACK(int maxN)
        { s = new Item[maxN]; N = 0; }
      int empty() const
        { return N == 0; }
      void push(Item item)
        { s[N++] = item; }
      Item pop()
        { return s[ - N]; }
  };
        

Операция создать (конструктор) выполняет выделение памяти под массив указанного размера, а операция проверить, пуст ли стек проверяет, равен ли индекс нулю. Скомпилированная вместе с клиентской программой (такой, как программа 4.5 или 4.6), эта реализация обеспечивает эффективный стек магазинного типа.

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

Например, чтобы стек мог свободно увеличиваться и уменьшаться, можно отдать предпочтение связному списку, как в программе 4.8. В таком стеке элементы будут храниться в обратном порядке по сравнению с реализацией на базе массива - начиная с последнего занесенного элемента и завершая первым (см. рис 4.5). Это позволяет более просто реализовать базовые стековые операции. Чтобы вытолкнуть элемент, удаляется узел из начала списка, и из него извлекается элемент; чтобы втолкнуть элемент, создается новый узел и добавляется в начало списка. Поскольку все операции связного списка выполняются в начале списка, ведущий узел не нужен.

(рис 4.5) Стек магазинного типа на базе связного списка

Стек представлен указателем head, который указывает на первый (последний вставленный) элемент. Чтобы вытолкнуть элемент из стека (вверху), удаляется элемент из начала списка, а в head заносится ссылка из этого элемента. Чтобы втолкнуть в стек новый элемент (внизу), он присоединяется в начало списка: в его поле ссылки заносится значение head, а в head - указатель на этот новый элемент.

Программа 4.8. Реализация стека магазинного типа на базе связного списка

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

template <class Item>
class STACK 
  {
    private:
      struct node
{ Item item; node* next;
  node(Item x, node* t)
    { item = x; next = t; }
};
      typedef node *link;
      link head;
    public:
      STACK(int)
{ head = 0; }
      int empty() const
{ return head == 0; }
      void push(Item x)
{ head = new node(x, head); }
      Item pop()
{ Item v = head->item; link t = head->next;
  delete head; head = t; return v; }
  };

Программа 4.8 не проверяет такие ошибки, как попытка извлечения элемента из пустого стека, занесение элемента в переполненный стек или нехватка памяти. В отношении двух последних условий имеются две возможности. Их можно трактовать как не связанные между собой ошибки и отслеживать количество элементов в списке, а при каждом занесении в стек проверять, что счетчик не превышает значение, переданное конструктору в качестве аргумента, и что операция new выполнена успешно. Но можно выбрать позицию, когда не требуется заранее знать максимальный размер стека, и, игнорируя аргумент конструктора, сообщать о переполнении стека только при отказе операции new (см. упражнение 4.24).

Программы 4.7 и 4.8 представляют две различные реализации одно и того же АТД. Можно заменять одну реализацию другой, не делая никаких изменений в клиентских программах, подобных тем, которые рассматривались в разделе 4.3. Они отличаются только производительностью. Реализация на базе массива использует объем памяти, необходимый для размещения максимального числа элементов, которые может вместить стек в процессе вычислений; реализация на базе списка использует объем памяти, пропорциональный количеству элементов, но при этом всегда расходует дополнительную память для одной ссылки на каждый элемент, а также дополнительное время на выделение памяти при каждой операции втолкнуть и освобождение памяти при каждой операции вытолкнуть. Если требуется стек больших размеров, который обычно заполняется практически полностью, то, по-видимому, предпочтение стоит отдать реализации на базе массива. Если же размер стека варьируется в широких пределах, и имеются другие структуры данных, которые могут занимать память тогда, когда в стеке находятся лишь несколько элементов, лучше воспользоваться реализацией на базе связного списка.

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

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

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

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

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

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

Упражнения

4.21. Определите содержимое элементов .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

class UF
  {
    private:
      // Программный код, зависящий от реализации
    public:
      UF(int);
      int find(int, int);
      void unite(int, int);
  };
        

Программа 4.10. Клиент для АТД отношений эквивалентности

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

#include <iostream.h>
#include <stdlib.h>
#include "UF.cxx"
int main(int argc, char *argv[])
  { int p, q, N = atoi(argv[1]);
    UF info(N);
    while (cin >> p >> q)
      if (!info.find(p, q))
        {
          info.unite(p, q);
          cout << " " << p << " " << q << endl;
        }
  }
        

Программа 4.11. Реализация АТД отношений эквивалентности

Этот код взвешенного быстрого объединения из является реализацией интерфейса из программы 4.9 в форме, удобной для его использования в других приложениях. Перегруженная приватная функция-член find реализует обход дерева вплоть до его корня.

class UF 
  {
    private:
      int *id, *sz;
      int find(int x)
        { while (x != id[x]) x = id[x];
return x; }
    public:
      UF(int N)
{
  id = new int[N]; sz = new int[N];
  for (int i = 0; i < N; i++)
    { id[i] = i; sz[i] = 1; }
}
      int find(int p, int q)
{ return (find(p) == find(q)); }
      void unite(int p, int q)
{ int i = find(p), j = find(q);
  if (i == j) return;
  if (sz[i] < sz[j])
    { id[i] = j; sz[j] += sz[i]; }
  else
    { id[j] = i; sz[i] += sz[j]; }
}
 };

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

Сочетание программ 4.10 и 4.11 функционально эквивалентно программе 1.3, однако разбиение программы на две части более эффективно, так как:

позволяет отделить решение задачи высокого уровня (задачи связности) от решения задачи низкого уровня (задачи объединение-поиск) и решать эти две задачи независимо

предоставляет естественный способ сравнения различных алгоритмов и структур данных, применяемых при решении этой задачи

определяет с помощью интерфейса способ проверки, что программа работает как задумано

обеспечивает механизм, позволяющий переходить к новым представлениям (к новым структурам данных или новым алгоритмам) без каких-либо изменений кода клиентских программ

предоставляет абстракцию, с помощью которой можно конструировать другие алгоритмы

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

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

Создается заголовочный файл - скажем, с именем UF.h - который будет содержать объявление класса, представление данных и объявления функций, но не определения функций. В рассматриваемом примере этот файл будет содержать код программы 4.9, в который также включается представление данных (приватные объявления из программы 4.11). Определения функций необходимо сохранить в отдельном файле .cxx, который (как и все клиенты) будет также содержать директиву include для файла UF.h. В этом случае появляется возможность раздельной компиляции клиентских программ и реализаций. Вообще-то определение любой функции-члена класса можно поместить в отдельный файл, если эта функция-член объявлена в классе, а в определении функции перед ее именем находится имя класса и знак ::. Например, определение функции find в нашем примере следовало бы записать так:

int UF::find(int p, int q)
  { return (find(p) == find(q)); }
        

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

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

В языке C++ имеется механизм, специально предназначенный для того, чтобы писать программы с хорошо определенным интерфейсом, который позволяет полностью отделять клиентские программы от реализаций. Этот механизм базируется на понятии производных (derived) классов, посредством которых можно дополнять или переопределять некоторые члены существующего класса. Включение ключевого слова virtual в объявление функции-члена означает, что эта функция может быть переопределена в производном классе; добавление последовательности символов = 0 в конце объявления функции-члена указывает, что данная функция является чисто виртуальной (pure virtual) функцией, которая должна быть переопределена в любом производном классе. Производные классы обеспечивают удобный способ создания программ на основе работ других программистов и являются важным компонентом объектно-ориентированных систем программирования.

Абстрактный (abstract) класс - это класс, все члены которого являются чисто виртуальными функциями. В любом классе, порожденном от абстрактного класса, должны быть определены все функции-члены и любые необходимые приватные данные-члены - таким образом, согласно нашей терминологии, абстрактный класс является интерфейсом, а любой класс, порожденный от него, является реализацией. Программы-клиенты могут использовать интерфейс, а система C++ может обеспечить соблюдение соглашений между клиентами и реализациями, даже когда клиенты и реализации функций компилируются раздельно. Например, в программе 4.12 показан абстрактный класс uf для отношений эквивалентности; если изменить первую строку программы 4.11 следующим образом:

class UF : public class uf
        

то она будет указывать, что класс UF является производным от класса uf, и поэтому в нем определены (как минимум) все функции-члены класса uf - т.е. класс UF является реализацией интерфейса uf.

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

Есть еще один способ - применение четырех файлов, когда приватные части хранятся не в интерфейсе, а в отдельном файле. Например, в начало класса из программы 4.9 можно было бы добавить строки

private:
#include "UFprivate.h"
и поместить в файл UFprivate.h строки
int *id, *sz;
int find(int);
        

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

Программа 4.12. Абстрактный класс для АТД отношения эквивалентности

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

class uf 
  {
    public:
      virtual uf(int) = 0;
      virtual int find(int, int) = 0;
      virtual void unite(int, int) = 0;
  };
        

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

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

Упражнения

4.29. Измените программу 4.11 так, чтобы в ней использовалось сжатие пути делением пополам.

4.30. Устраните упоминаемую в тексте неэффективность программы, добавив в программу 4.9 операцию, которая объединяет операции объединение и поиск, и соответствующим образом изменив программы 4.11 и 4.10.

4.31. Измените интерфейс (программа 4.9) и реализацию (программа 4.11) для отношений эквивалентности так, чтобы в них присутствовала функция, возвращающая количество узлов, которые связаны с данным.

4.32. Измените программу 4.11 так, чтобы для представления структуры данных в ней вместо параллельных массивов использовался массив структур.

4.33. Напишите программу из трех файлов (без шаблонов), вычисляющую значение постфиксного выражения с помощью стека целых чисел. Обеспечьте, чтобы клиентскую программу (аналог программы 4.5) можно было компилировать отдельно от реализации стека (аналог программы 4.7).

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

4.35. Создайте полную реализацию АТД отношения эквивалентности на базе абстрактного класса с виртуальными функциями и сравните производительность полученной программы и программы 4.11 на крупных задачах связности (в стиле таблицы 1.1).

Очереди FIFO и обобщенные очереди

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

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

Очереди FIFO часто встречаются в повседневной жизни. Когда мы стоим в цепочке людей, чтобы посмотреть кинокартину или купить продукты, нас обслуживают в порядке FIFO. Аналогично этому в вычислительных системах очереди FIFO часто используются для обслуживания задач, которые необходимо выполнять по принципу "первым пришел, первым обслужен". Другим примером, иллюстрирующим различие между стеками и очередями FIFO, может служить отношение к скоропортящимся продуктам в магазине. Если продавец выкладывает новые товары на переднюю часть полки, и покупатели берут товары также с передней части полки, получается стек. У продавца могут возникнуть неприятности, поскольку товар на задней части полки может стоять очень долго и попросту испортиться. Выкладывая новые товары на заднюю часть полки, продавец гарантирует, что время, в течение которого товар находится на полке, ограничивается временем, необходимым покупателям для приобретения всех товаров, выставляемых на полку. Этот же базовый принцип применяется во множестве подобных ситуаций.

Определение 4.3. Очередь FIFO - это АТД, который содержит две базовых операции: вставить (put - занести) новый элемент и удалить (get - извлечь) элемент, который был вставлен раньше всех остальных.

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

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

(рис 4.6) Пример очереди FIFO

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

Программа 4.13. Интерфейс АТД очереди FIFO

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

template <class Item>
class QUEUE 
  {
    private:
     // Программный код, зависящий от реализации 
    public:
      QUEUE(int); 
      int empty(); 
      void put(Item);
      Item get();
  };
        

В случае реализации АТД очереди FIFO с помощью связного списка, элементы списка хранятся в порядке от первого вставленного до последнего вставленного элемента (см. рис 4.6). Такой порядок является обратным по отношению к порядку, который применяется в реализации стека; именно такой порядок позволяет создавать эффективные реализации операций с очередями. Как показано на рис 4.7 и в программе 4.14 (реализация), требуются два указателя на этот список: один на начало списка (для извлечения первого элемента) и второй на его конец (для занесения в очередь нового элемента).

Программа 4.14. Реализация очереди FIFO на базе связного списка

Различие между очередью FIFO и стеком магазинного типа (программа 4.8) состоит в том, что новые элементы вставляются в конец списка, а не в его начало. Поэтому в данном классе хранится указатель tail на последний узел списка, чтобы функция put могла добавлять в список новый узел: этот узел связывается с узлом, на который указывает указатель tail, а затем указатель tail изменяется так, чтобы он указывал уже на новый узел. Функции QUEUE, get и empty повторяют аналогичные функции в реализации стека магазинного типа на базе связного списка из программы 4.8. Поскольку новые узлы всегда вставляются в конец списка, конструктор узлов может обнулять поле указателя каждого нового узла и поэтому принимать только один аргумент.

template <class Item>
class QUEUE
  {
    private:
      struct node
        { Item item; node* next;
node(Item x)
  { item = x; next = 0; }
        };
      typedef node *link;
      link head, tail;
    public:
      QUEUE(int)
        { head = 0; }
      int empty() const
        { return head == 0; }
      void put(Item x)
        { link t = tail;
tail = new node(x);
if (head == 0)
  head = tail;
else
  t->next = tail;
        }
      Item get()
        { Item v = head->item;
link t = head->next;
delete head;
head = t;
return v; }
    };
        

(рис 4.7) Очередь на базе связного списка

В представлении очереди в виде связного списка новые элементы вставляются в конец списка, поэтому элементы связного списка располагаются от первого вставленного элемента (в начале) до последнего (в конце). Очередь представляется двумя указателями: ). Чтобы занести в очередь новый элемент, в поле ссылки узла, на который ссылается указатель tail, заносится указатель на новый элемент (в середине рисунка), а затем изменяется указатель tail (внизу).

Для реализации очереди FIFO можно использовать и массив, однако при этом необходимо соблюдать осторожность и обеспечить, чтобы время выполнения как операции занести, так и операции извлечь было постоянным. Это условие запрещает пересылать элементы очереди внутри массива, как это можно было бы предположить при буквальной интерпретации рис 4.6. Поэтому, как и в реализации на базе связного списка, нам потребуются два индекса массива: для начала очереди и для конца. Содержимым очереди считаются элементы между этими двумя индексами. Чтобы извлечь элемент, он удаляется из начала очереди, после чего индекс , в результате выполнения последовательности операций занести и извлечь все выглядит так, будто очередь движется по массиву. При достижении конца массива выполняется переход к его началу. Соответствующая реализация приведена в коде программы 4.15.

Лемма 4.2. Для АТД очереди FIFO можно реализовать операции извлечь и занести с постоянным временем выполнения, используя либо массивы, либо связные списки.

Это понятно из анализа кода программ 4.14 и 4.15. $$$\blacksquare$$$

(рис 4.8) Пример очереди FIFO, реализованной на базе массива

Здесь приведена последовательность операций с данными для абстрактного представления очереди из рис 4.6. Очередь реализована за счет запоминания ее элементов в массиве, сохранения индексов начала и конца очереди и возврата индексов на начало массива при достижении его конца. В данном примере индекс tail возвращается на начало массива, когда вставляется второй символ T, а индекс head - когда удаляется второй символ S.

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

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

Программа 4.15. Реализация очереди FIFO на базе массива

К содержимому очереди относятся все элементы массива, расположенные между индексами head и tail, учитывая возврат к 0 с конца массива. Если индексы head и tail равны, очередь считается пустой, однако если они стали равными в результате выполнения операции put, очередь считается полной. Как обычно, проверка на такие ошибочные ситуации не выполняется, но размер массива задается на 1 больше максимального количества элементов очереди, ожидаемое клиентом. При необходимости программу можно расширить, включив в нее такие проверки.

template <class Item>
class QUEUE
  {
    private:
      Item *q; int N, head, tail;
    public:
      QUEUE(int maxN)
        { q = new Item[maxN+1];
N = maxN+1; head = N; tail = 0; }
        int empty() const
{ return head % N == tail; }
        void put(Item item)
{ q[tail++] = item; tail = tail % N; }
        Item get()
{ head = head % N; return q[head++]; }
  };
        

И стеки магазинного типа, и очереди FIFO являются частными случаями более общего АТД: обобщенной (generalized) очереди. Частные случаи обобщенных очередей различаются только правилами удаления элементов. Для стеков это правило "удалить элемент, который был вставлен последним", для очередей FIFO - правило "удалить элемент, который был вставлен первым"; существует и множество других вариантов.

Простым, но, тем не менее, мощным вариантом является неупорядоченная очередь (random queue) с правилом "удалить случайный элемент" - программа-клиент может ожидать, что она с одинаковой вероятностью получит любой из элементов очереди. Используя представление на базе массива (см. упражнение 4.48), для неупорядоченной очереди можно реализовать операции с постоянным временем выполнения. Это представление на базе массива требует, как для стеков и очередей FIFO, предварительного выделения оперативной памяти. Однако в данном случае альтернативное представление на базе связного списка менее удобно, чем в случае стеков и очередей FIFO, поскольку эффективная реализация как операции вставки, так и операции удаления является очень трудной задачей (см. упражнение 4.49). На базе неупорядоченных очередей можно создавать рандомизированные алгоритмы, которые с высокой степенью вероятности позволяют избежать вариантов наихудшей производительности (см. раздел 2.7 ).

В нашем описании стеков и очередей FIFO элементы упорядочены по времени вставки в очередь. Но можно рассмотреть более абстрактную концепцию - последовательный ряд упорядоченных элементов с базовыми операциями вставки и удаления элементов и в начале, и в конце списка. Если элементы вставляются в конец списка и удаляются также с конца, получается стек (как в реализации на базе массива); если элементы вставляются в начало и удаляются в начале, тоже получается стек (как в реализации на базе связного списка). Если же элементы вставляются в конец, а удаляются в начале, то получается очередь FIFO (как в реализации на базе связного списка). Если элементы вставляются в начало, а удаляются с конца, также получается очередь FIFO (этот вариант не соответствует ни одной из реализаций - для его точной реализации можно было бы изменить представление на базе массива, а вот представление на базе связного списка для этой цели не подойдет, т.к. в случае удалении элементов в конце очереди придется сохранять указатель на конец очереди). Эта точка зрения приводит нас к абстрактному типу данных дека (deque - double-ended queue, двухсторонняя очередь), в котором и вставки, и удаления возможны с обеих сторон. Его реализацию мы оставляем в качестве упражнений (см. упражнения 4.43 - 4.47); заметим, что реализация на базе массива окажется простым расширением программы 4.15, а для реализации на базе связного списка потребуется двухсвязный список, иначе удалять элементы дека можно будет только с одной стороны.

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

В главах с 12 по 16 будут рассмотрены таблицы символов (symbol table). Это обобщенные очереди, в которых элементы имеют ключи, а правило удаления элементов имеет вид "удалить элемент, ключ которого равен данному, если таковой элемент существует". Этот АТД, пожалуй, самый важный из изучаемых, и мы изучим десятки его реализаций.

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

Упражнения

4.36. Найдите содержимое элементов , равно 10.

4.37. В последовательности

a S * Y * Q U E * * * S T * * * I O * N * * *

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

4.38. Измените приведенную в тексте реализацию очереди FIFO на базе массива (программа 4.15) так, чтобы в ней вызывалась функция error(), если клиент пытается выполнить операцию извлечь, когда очередь пуста, или операцию занести, когда очередь заполнена.

4.39. Измените приведенную в тексте реализацию очереди FIFO на базе связного списка (программа 4.14) так, чтобы в ней вызывалась функция error(), если клиент пытается выполнить операцию извлечь, когда очередь пуста, или если при выполнении new для операции занести отсутствует доступная память.

4.40. В последовательности

E A s + Y + Q U E * * + s t + * + I O * n + + *

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

4.41. При тех же условиях, что и в упр. 4.40, расставьте в последовательности E a s Y плюсы и звездочки так, чтобы операции извлечь возвращали следующую последовательность символов: (1) E s a Y, (2) Y a s E, (3) a Y s E, (4) a s Y E; либо в каждом случае докажите, что такая последовательность невозможна.

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

4.43. Напишите интерфейс для АТД дека.

4.44. Напишите реализацию для интерфейса дека (упр. 4.43), в которой в качестве базовой структуры данных используется массив.

4.45. Напишите реализацию для интерфейса дека (упр. 4.43), в которой в качестве базовой структуры данных используется двухсвязный список.

4.46. Напишите реализацию для приведенного в тексте интерфейса очереди FIFO (программа 4.13), в которой в качестве базовой структуры данных используется циклический список.

4.47. Напишите программу-клиент для тестирования АТД дека (упр. 4.43), которая считывает из командной строки в качестве первого аргумента строку команд, подобную приведенной в упр. 4.40, после чего выполняет указанные операции. В интерфейс и реализации добавьте функцию-член dump и выводите содержимое дека после каждой операции, как это сделано на рис 4.6.

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

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

4.50. Напишите программу-клиент, которая выбирает для лотереи числа следующим образом: заносит в неупорядоченную очередь числа от 1 до 99, а затем выводит результат удаления пяти чисел.

4.51. Напишите программу-клиент, которая принимает из первого аргумента командной строки целое число N, а затем выводит результат раздачи карт на N игроков в покер. Для этого она должна занести в неупорядоченную очередь N элементов (см. упр. 4.7) и затем выдавать результат выбора из этой очереди по пять карт за один раз.

4.52. Напишите программу решения задачи связности. Для этого она должна вставлять все пары в неупорядоченную очередь, а затем извлекать их из очереди с помощью алгоритма взвешенного быстрого поиска (программа 1.3).

Повторяющиеся и индексные элементы

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

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

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

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

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

(рис 4.9) Стек магазинного типа без дубликатов

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

(рис 4.10) Очередь FIFO без дубликатов, с правилом игнорирования нового элемента

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

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

(рис 4.11)

Очередь FIFO без дубликатов, с правилом удаления старого элемента Здесь показан результат выполнения тех же операций, что и на рис 4.10. Однако тут используется другой, более сложный дляреа-лизации принцип: новый элемент всегда добавляется в конец очереди. Если в очереди уже имеется такой же элемент, он удаляется.

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

Имеется важный частный случай, для которого существует простое решение, приведенное в программе 4.16 для АТД стека магазинного типа. В этой реализации предполагается, что элементы являются целыми числами в диапазоне от 0 до М - 1. Для определения, имеется ли уже в стеке некоторый элемент, в реализации используется второй массив, индексами которого являются сами элементы стека. Когда в стек заносится элемент i, в i-й элемент второго массива заносится 1, а при удалении из стека элемента i туда заносится 0. Во всем остальном для вставки и удаления элементов применяется тот же код, но перед вставкой элемента выполняется проверка, нет ли в стеке такого элемента. Если есть, операция занесения элемента игнорируется. Это решение не зависит от используемого представления стека - на базе массива, связного списка или чего-нибудь еще. Реализация принципа "удалять старый элемент" требует большего объема работы (см. упражнение 4.57).

Итак, один из способов реализации стека без повторяющихся элементов, функционирующего по принципу "игнорировать новый элемент", состоит в использовании двух структур данных. Первая, как и прежде, содержит элементы стека и позволяет отслеживать порядок, в котором были вставлены элементы стека. Вторая структура является массивом, позволяющим определять, какие элементы находятся в стеке; индексами этого массива являются элементы стека. Такое использование массива является частным случаем реализации таблицы символов, которая будет рассмотрена в разделе 12.2 . Если известно, что элементы представляют собой целые числа в диапазоне от 0 до М - 1, эту технику можно применять по отношению к любой обобщенной очереди.

Этот частный случай встречается довольно часто. Его наиболее важный пример - когда элементы структуры данных сами являются индексами массива, поэтому такие элементы называются индексными элементами (index item). Обычно имеется набор из М объектов, хранимых в каком-то другом массиве, и в каком-то более сложном алгоритме необходимо передавать эти объекты через структуру обобщенной очереди. Объекты заносятся в очередь по индексам и обрабатываются при удалении, причем каждый объект должен обрабатываться только один раз. Очередь без дубликатов, в которой используются индексы массива, позволяет непосредственно достичь этой цели.

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

Программа 4.16. Стек индексных элементов без дубликатов

В этой реализации стека магазинного типа предполагается, что класс Item приводим к типу int, который возвращает целые числа в диапазоне от 0 до maxN-1. Поэтому в нем используется массив t, где каждому элементу стека соответствует отличное от нуля значение. Этот массив дает возможность функции push быстро проверять наличие в стеке ее аргумента, и не выполнять занесение, если он там есть. Для каждого элемента массива t достаточно одного бита, поэтому при желании можно сэкономить память, используя вместо целых чисел символы или биты (см. упр. 12.12).

template <class Item>
class STACK
  {
    private:
      Item *s, *t; int N;
    public:
      STACK(int maxN)
        {
s = new Item[maxN]; N = 0;
t = new Item[maxN];
for (int i = 0; i < maxN; i++) t[i] = 0;
        }
        int empty() const
{ return N == 0; }
        void push(Item item)
{
  if (t[item] == 1) return;
  s[N++] = item; t[item] = 1;
}
Item pop()
  { t[s[--N]] = 0; return s[N]; }
  };
        

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

Упражнения

4.53. Нарисуйте рисунок, аналогичный рис 4.9, для стека без дубликатов, работающего по правилу "удалять старый элемент".

4.54. Измените стандартную реализацию стека на базе массива из раздела 4.4 (программа 4.7), чтобы в ней были запрещены дубликаты по правилу "игнорировать новый элемент". Используйте простейший метод, выполняющий просмотр всего стека.

4.55. Измените стандартную реализацию стека на базе массива из раздела 4.4 (программа 4.7), чтобы в ней были запрещены дубликаты по правилу "удалять старый элемент". Используйте простейший метод, выполняющий просмотр всего стека и перемещение его элементов.

4.56. Выполните упражнения 4.54 и 4.55 для реализации стека на базе связного списка из раздела 4.4 (программа 4.8).

4.57. Разработайте реализацию стека магазинного типа с запретом дубликатов по правилу "удалять старый элемент". Элементами стека являются целые числа в диапазоне от 0 до М - 1, а операции втолкнуть и вытолкнуть должны иметь постоянное время выполнения. Подсказка: возьмите представление стека на базе двухсвязного списка и храните в массиве индексных значений указатели на узлы этого списка, а не значения 0-1.

4.58. Выполните упражнения 4.54 и 4.55 для очереди FIFO.

4.59. Выполните упражнение 4.56 для очереди FIFO.

4.60. Выполните упражнение 4.57 для очереди FIFO.

4.61. Выполните упражнения 4.54 и 4.55 для рандомизированной очереди.

4.62. Напишите клиентскую программу для АТД, полученного в упражнении 4.61, в которой используется рандомизированная очередь без повторяющихся элементов.

АТД первого класса

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

Однако если такие типы данных использовать в программах аналогично встроенным типам данных, например, int или float, то возможны неприятности. В данном разделе мы научимся конструировать АТД, с которыми можно работать так же, как и со встроенными типами данных, и все-таки скрывать от клиентов детали реализации.

Определение 4.4. Тип данных первого класса - это тип данных, который можно использовать в программах таким же образом, как и встроенные типы данных.

Например, типы данных первого класса можно использовать в объявлениях переменных, в операторах присваивания, в аргументах и возвращаемых значениях функций. В этом определении, равно как и в других, относящихся к типам данных, нельзя достигнуть точности, не углубившись в сложные вопросы семантики операций. Как будет показано, одно дело требовать, чтобы можно было написать a = b, где a и b - объекты определенного пользователем класса, и совсем другое дело точно определить, что означает эта запись.

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

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

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

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

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

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

Число $$$i=\sqrt{-1})$$$ i = V-1 является мнимым числом. Хотя $$$\sqrt{-1}$$$ как вещественное число не имеет смысла, мы называем его i и выполняем над ним алгебраические операции, заменяя каждый раз i² на - 1. Комплексное число состоит из двух частей, вещественной и мнимой, и записывается в виде a + bi, где а и b - вещественные числа. Для умножения комплексных чисел применяются обычные алгебраические правила, только i² всякий раз заменяется на -1. Например:

(а + bi)(c + di) = ac + bci + adi + bdi2 = (ac - bd) + (ad + bc)i .

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

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

#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include "COMPLEX.cxx"
int main(int argc, char *argv[])
    { int N = atoi(argv[1]);
      cout << N << " комплексные корни из единицы" << endl;
      for (int k = 0; k < N; k++)
        { float theta = 2.0*3.1415 9*k/N;
Complex t(cos(theta), sin(theta)), x = t;
cout << k << ": " << t << " ";
for (int j = 0; j < N-1; j++) x *= t;
cout << x << endl;
        }
    }
        

При умножении комплексных чисел вещественные или мнимые части могут сокращаться (принимать значения 0), например:

            (1  -  i) (1  -  i) = 1  -  i  -  i + i2 =  - 2i,
            (1 + i)4 = 4i2 = -4,
            (1 + i)8 = 16.
        

Разделив обе части последнего уравнения на 16 = $$$(\sqrt{2})^{8}$$$, получим

$$$\left(\dfrac{1}{\sqrt{2}}+\dfrac{i}{\sqrt{2}}\right)^{8}=1$$$

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

$$$\cos{\left(\dfrac{2\pi k}{N}\right)} +i\sin\left(\dfrac{2\pi k}{N}\right)$$$,

для к = 0, 1, ... , N - 1 (см. упражнение 4.68). Например, если в этой формуле взять к = 1 и N = 8, получим только что найденный корень восьмой степени из единицы.

Программа 4.17 вычисляет все корни N-ой степени из единицы для любого данного N и затем возводит их в N-ю степень с помощью операции . При этом каждое из этих чисел, возведенное в N-ю степень, должно дать один и тот же результат - 1, или 1 + 0i. Полученные мнимые части не равны строго нулю из-за ограниченной точности вычислений. Наш интерес к этой программе объясняется тем, что класс Complex используется в ней точно так же, как встроенный тип данных. Ниже будет подробно показано, почему это возможно.

Даже в таком простом примере важно, чтобы тип данных был абстрактным, поскольку имеется еще одно стандартное представление, которым можно было бы воспользоваться - полярные координаты (см. упражнение 4.67).

(рис 4.12) Комплексные корни из единицы

Эта таблица содержит выходные данные программы 4.17 для вызова с параметрами a.out 8, а реализация перегруженной операции << выполняет соответствующее форматирование выходных данных (см. упр. 4.70). Восемь комплексных корней из единицы равны: $$$\pm1{, } \pm i{, и }\pm\dfrac{\sqrt{2}}{2}\pm\dfrac{\sqrt{2}}{2}i$$$ (два левых столбца). При возведении в восьмую степень все эти восемь чисел дают в результате 1 + 0i (два левых столбца).

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

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

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

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

class Complex
  {
    private:
      // Программный код, зависящий от реализации 
    public:
      Complex(float, float);
      float Re() const;
      float Im() const;
      Complex operator*=(Complex);
  };
        

Программа 4.19. АТД первого класса для комплексных чисел

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

Перегруженная операция << в текущей реализации не форматирует выходные данные (см. упр. 4.70).

#include <iostream.h>
class Complex
  {
    private:
      float re, im;
    public:
      Complex(float x, float y)
        { re = x; im = y; }
      float Re() const
        { return re; }
      float Im() const
        { return im; }
      Complex operator*=(const Complex rhs)
        { float t = Re();
re = Re()*rhs.Re() - Im()*rhs.Im();
im = t*rhs.Im() + Im()*rhs.Re();
return *this;
        }
   };
  ostream operator<<(ostream t, const Complex c)
   { t << c.Re() << " " << c.Im(); return t; }
        

На самом деле в языке C++ к типам данных первого класса относится любой класс, если ни один из его данных-членов не является указателем. При копировании объекта копируется каждый его член; при присваивании объекту значения перезаписывается каждый его член; когда объект выходит за пределы области видимости, занимаемая им память освобождается. В системе существуют стандартные механизмы для каждой из упомянутых ситуаций: в каждом классе имеются стандартные конструктор копирования, операция присваивания и деструктор.

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

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

Программа 4.20. Клиентская программа, имитирующая обслуживание с очередями

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

Здесь неявно предполагается, что класс QUEUE принадлежит к типу данных первого класса. Эта программа не будет корректно работать с реализациями, предоставленными в программах 4.14 и 4.15, из-за неправильной семантики копирования во внутреннем цикле for.

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

#include <iostream.h>
#include <stdlib.h>
#include "QUEUE.cxx"
static const int M = 4;
int main(int argc, char *argv[])
  { int N = atoi(argv[1]);
    QUEUE<int> queues[M];
    for (int i = 0; i < N; i++, cout << endl)
      { int in = rand() % M, out = rand() % M;
        queues[in].put(i);
        cout << i << " поступил ";
        if (!queues[out].empty())
          cout << queues[out].get() << " обслужен";
        cout << endl;
        for (int k = 0; k < M; k++, cout << endl)
          {
QUEUE<int> q = queues[k];
cout << k << ": ";
while (!q.empty())
  cout << q.get() << " ";
          }
      }
  }
        

Предположим, что используется рассмотренная ранее реализация очереди на базе связного списка из программы 4.14. Когда выполняется операция p = q, где p и q являются объектами класса QUEUE, система выделяет память для нового объекта и копирует в новый объект значения, относящиеся к объекту q. Но это указатели head и tail - сам связный список не копируется! Если впоследствии связный список, относящийся к объекту p, изменяется, тем самым изменяется и связный список, относящийся к объекту q. Безусловно, программа 4.20 не рассчитана на такое поведение. Если использовать объект класса QUEUE как аргумент функции, процесс будет выглядеть так же. В случае встроенных типов данных мы ожидаем, что внутри функции будет свой собственный объект, который можно использовать по своему усмотрению. Это ожидание означает, что в случае структуры данных с указателями требуется создание копии. Однако система не знает, как это сделать - именно мы должны предоставить необходимый код. То же самое справедливо и для возвращаемых значений функций.

(рис 4.13) Моделирование неупорядоченной очереди

Здесь приведена заключительная часть выходных данных программы 4.20 для вызова из командной строки с аргументом 8 0. Показано содержимое очередей после указанных операций:случайным образом выбирается очередь, и в нее заносится следующий элемент; затем еще раз выбирается очередь (также случайно) и, если она не пуста, из нее извлекается элемент.

Еще хуже обстоят дела, когда объект класса QUEUE выходит за пределы видимости: система освобождает память, относящуюся к указателям, но не всю память, занимаемую собственно связным списком. Действительно, как только указатели прекращают свое существование, исчезает возможность доступа к данной области памяти. Вот вам пример утечки памяти (memory leak) - серьезной проблемы, всегда требующей особого внимания при написании программы, которая имеет дело с распределением памяти.

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

Конструктор копирования - для создания нового объекта, который является копией данного объекта.

Перегруженную операцию присваивания - чтобы объект мог присутствовать в левой части оператора присваивания.

Деструктор - для освобождения памяти, выделенной под объект во время его создании.

Когда системе необходимо выполнить указанные операции, она использует эти функции-члены. Если таких функций в классе нет, система обращается к стандартным функциям. Они работают так, как это описано для класса Complex, однако ведут к неверной семантике копирования и утечкам памяти, если какие-нибудь данные-члены являются указателями. Программа 4.21 - интерфейс очереди FIFO, в который включены три перечисленных функции. Подобно конструкторам, они имеют отличительные сигнатуры, в которые входит имя класса.

Когда при создании объекту присваивается начальное значение, либо объект передается в качестве параметра или возвращается из функции, система автоматически вызывает конструктор копирования QUEUE(const QUEUE). Для выполнения операции = вызывается операция присваивания QUEUE operator=(const QUEUE), которая и присваивает значение одной очереди другой. Деструктор ~QUEUE() вызывается в том случае, когда необходимо освободить память, выделенную под какую-либо очередь. Если в программе присутствует объявление без установки начального значения, наподобие QUEUE<int> q;, то для создания объекта q система использует конструктор QUEUE(). Но если объект при объявлении инициализируется, наподобие QUEUE<int> q = p (или эквивалентной формы QUEUE<int> q(p)), система использует конструктор копирования QUEUE(const QUEUE). Эта функция должна создавать новую копию объекта p, а не просто еще один указатель на него. Как обычно для ссылочных параметров, ключевое слово const означает намерение не изменять объект p, а использовать его только для доступа к информации.

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

template <class Item>
class QUEUE
  {
    private:
      // Код, зависящий от реализации 
    public:
      QUEUE(int);
      QUEUE(const QUEUE);
      QUEUE operator=(const QUEUE);
      ~QUEUE();
      int empty() const;
      void put(Item);
      Item get();
  };
        

Программа 4.22 содержит реализацию конструктора копирования, перегруженной операции присваивания и деструктора для реализации очереди на базе связного списка из программы 4.14. Деструктор проходит по всей очереди и с помощью операции delete освобождает память, выделенную под каждый узел. Если клиентская программа присваивает значения некоторого объекта самому себе, то операция присваивания ничего не делает; иначе вызывается деструктор, а затем с помощью put копируется каждый элемент очереди, стоящей справа от знака операции. Конструктор копирования очищает очередь и затем с помощью операции присваивания выполняет копирование.

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

часто используется только один экземпляр объекта определенного класса;

даже при наличии нескольких экземпляров может оказаться необходимым запрет непреднамеренного копирования огромных структур данных.

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

Приведенные рассуждения также объясняют, почему библиотека языка C++ включает класс string, несмотря на привлекательность низкоуровневой структуры данных типа строки в стиле языка C. C-строки не принадлежат к типам данных первого класса, поскольку по сути это просто указатели. И многие программисты впервые сталкиваются с некорректной семантикой копирования именно при копировании указателя на C-строку, ожидая, что будет скопирована сама строка. В противоположность этому, класс string языка C++ является типом данных первого класса, поэтому при работе с очень длинными строками следует соблюдать особую осторожность.

Программа 4.22. Реализация очереди первого класса на базе связного списка

Можно модернизировать реализацию класса очереди FIFO из программы 4.14, чтобы превратить этот тип данных в "первоклассный". Для этого в класс потребуется добавить приведенные ниже реализации конструктора копирования, перегруженной операции присваивания и деструктора. Эти функции перекрывают функции, используемые по умолчанию, и вызываются, когда необходимо копировать или уничтожать объекты.

Деструктор ~QUEUE() вызывает приватную функцию-член deletelist, которая проходит по всему связному списку, вызывая для каждого узла функцию delete. Таким образом, при освобождении памяти, связанной с указателями, освобождается и вся память, занимаемая объектом.

Если перегруженная операция присваивания вызывается для присваивания объекта самому себе (например, q = q), никакие действия не выполняются. Иначе вызывается функция deletelist, чтобы очистить память, связанную со старой копией объекта (в результате получается пустой список). Затем для каждого элемента списка из правой части операции присваивания вызывается функция put, и таким образом создается копия этого списка. В обоих случаях возвращаемое значение представляет собой ссылку на объект, которому присвоено значение другого объекта.

Конструктор копирования QUEUE(const QUEUE) очищает список, а затем с помощью перегруженной операции присваивания создает копию аргумента.

private:
  void deletelist()
    {
      for (link t = head; t != 0; head = t)
        { t = head->next; delete head; }
    }
public:
  QUEUE(const QUEUE rhs)
    { head = 0; *this = rhs; }
  QUEUE operator=(const QUEUE rhs)
    {
      if (this == rhs) return *this;
      deletelist();
      link t = rhs.head;
      while (t != 0)
        { put(t->item); t = t->next; }
      return *this;
    }
   ~QUEUE()
     { deletelist(); }
        

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

Утечка памяти - это трудно выявляемый дефект, который поражает многие большие системы. Хотя освобождение памяти, занятой некоторым объектом, обычно является в принципе несложным делом, на практике очень тяжело следить за всеми выделенными областями памяти. Механизм деструкторов в языке C++ помогает, однако система не может гарантировать, что обход структур данных выполняется так, как задумано. Когда объект прекращает свое существование, его указатели теряются безвозвратно, и любой указатель, не обработанный деструктором, является потенциальным источником утечки памяти. Один из типичных источников - когда в классе вообще забывают определить деструктор - конечно же, стандартный деструктор вряд ли корректно очистит память. Особое внимание этому вопросу необходимо уделить при использовании абстрактных классов, наподобие класса из программы 4.12.

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

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

Упражнения

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

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

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

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

путем определяет вероятность раздачи различных наборов карт при игре в покер.

4.67. Разработайте реализацию для АТД комплексных чисел на базе представления комплексных чисел в полярных координатах (т.е. в формате $$re^{i\theta}$$ ).

4.68. Воспользуйтесь тождеством $$e^{i\theta}=\cos{\theta}+i\sin{\theta}$$ для доказательства того, что $$е^{2\pi i}= 1$$ , а N комплексных корней N-ой степени из единицы равны $$$$\cos{\left(\dfrac{2\pi k}{N}\right)}+i \sin{\left(\dfrac{2\pi k}{N}\right)}$$$$

для к = 0, 1, ... , N - 1.

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

4.70. Используя операции precision и setw из файла iostream.h, создайте реализацию перегруженной операции для программы 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 таким образом, чтобы она вычисляла постфиксные выражения, состоящие из комплексных чисел с целыми коэффициентами. Для простоты считайте, что все комплексные числа имеют ненулевые целые коэффициенты как для вещественной, так и для мнимой частей, и записываются без пробелов. Например, для исходного выражения

1+2i0+1i+1-2i*3+4i+

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

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

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

В качестве заключительного примера рассмотрим специализированный АТД, который демонстрирует связь между прикладными областями и алгоритмами и структурами данных, которые обсуждаются в настоящей книге. Этот АТД полинома взят из области символьной математики, в которой компьютеры помогают оперировать с абстрактными математическими объектами. Цель заключается в том, чтобы получить возможность писать программы, которые могут оперировать с полиномами и выполнять вычисления наподобие $$$$\left(1-x+\dfrac{x^{2}}{2}-\dfrac{x^{3}}{6}\right)(1+x+x^{2}+x^{3})=1+\dfrac{x^{2}}{2}+\dfrac{x^{3}}{3}-\dfrac{2x^{4}}{3}+\dfrac{x^{5}}{3}-\dfrac{x^{6}}{6}$$$$

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

  (х + 1)2 = x2 + 2х + 1,
  (х + 1)3 = x3 + 3x2 + 3х + 1,
  (х + 1)4 = x4 + 4x3 + 6x2 + 4х + 1,
  (х + 1)5 = x5 + 5x4 + 10x3 + 10x2 + 5х + 1,
  ... .
        

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

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

Программа 4.23. Клиентская программа для АТД полинома (биномиальные коэффициенты)

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

#include <iostream.h>
#include <stdlib.h>
#include "POLY.cxx"
int main(int argc, char *argv[])
  { int N = atoi(argv[1]); float p = atof(argv[2]);
    cout << "Биномиальные коэффициенты" << endl;
    POLY<int> x(1,1), one(1,0), t = x + one, y = t;
    for (int i = 0; i < N; i++)
      { y = y*t; cout << y << endl; }
    cout << y.eval(p) << endl;
  }
        

Программа 4.24. Интерфейс АТД полинома

Чтобы можно было задавать коэффициенты различных типов, в этом интерфейсе АТД полинома используется шаблон. Здесь перегружены бинарные операции + и *, поэтому клиентские программы могут использовать полиномы в арифметических выражениях. Конструктор, вызванный с аргументами c и N, создает полином, соответствующий выражению cx^N.

template <class Number>
class POLY
  {
    private:
      // Программный код, зависящий от реализации
    public:
      POLY<Number>(Number, int);
      float eval(float) const;
      friend POLY operator+(POLY , POLY );
      friend POLY operator*(POLY , POLY );
  };
        

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

Для сложения (add) двух полиномов складываются их коэффициенты. Если полиномы представлены в виде массивов, то для их сложения, как показано в программе 4.25, достаточно одного цикла по этим массивам. Для умножения (multiply) двух полиномов применяется элементарный алгоритм, основанный на свойстве дистрибутивности. Один полином умножается на каждый член другого, результаты выравниваются так, чтобы степени х соответствовали друг другу, и затем складываются для получения окончательного результата. В следующей таблице кратко показывается этот вычислительный процесс для (1 - х + x2/ 2 - x3/ 6 ) (1 + х + x2 + x3) : $$ \begin{align*} 1-x+\dfrac{x^{2}}{2}-\dfrac{x^{3}}{6}\\ +x-x^{2}+\dfrac{x^{3}}{2}-\dfrac{x^{4}}{6}\\ +x^{2}-x^{3}+\dfrac{x^{4}}{2}-\dfrac{x^{5}}{6}\\ +x^{3}-x^{4}+\dfrac{x^{5}}{2}-\dfrac{x^{6}}{6}\\ 1+\dfrac{x^{2}}{2}+\dfrac{x^{3}}{3}-\dfrac{2x^{4}}{3}+\dfrac{x^{5}}{3}-\dfrac{x^{5}}{6} \end{align*} $$

Очевидно, что время, необходимое для умножения таким способом двух полиномов, пропорционально N². Отыскать более быстрый алгоритм решения данной задачи весьма непросто. Эта тема рассматривается более подробно в части VIII, где будет показано, что время, необходимое для решения такой задачи с помощью алгоритма "разделяй-и-властвуй", пропорционально N^3/2, а время, необходимое для ее решения с помощью быстрого преобразования Фурье, пропорционально N lgN.

В реализации функции evaluate (вычислить) из программы 4.25 используется эффективный классический алгоритм, известный как алгоритм Горнера (Horner). Cамая простая реализация этой функции заключается в непосредственном вычислении выражения с использованием функции, вычисляющей х N. При таком подходе требуется время с квадратичной зависимостью от N. В более сложной реализации значения xⁱ запоминаются в таблице и затем используются при непосредственных вычислениях. При таком подходе требуется дополнительный объем памяти, линейно зависящий от N.

Программа 4.25. Реализация АТД полинома на базе массива

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

template <class Number>
class POLY
  {
    private:
      int n; Number *a;
    public:
      POLY<Number>(Number c, int N)
        { a = new Number[N+1]; n = N+1; a[N] = c;
          for (int i = 0; i < N; i++) a[i] = 0;
        }
      float eval(float x) const
        { double t = 0.0;
          for (int i = n-1; i >= 0; i - )
t = t*x + a[i];
          return t;
        }
      friend POLY operator+(POLY p, POLY q)
        { POLY t(0, p.n>q.n ? p.n-1 : q.n-1);
          for (int i = 0; i < p.n; i++)
t.a[i] += p.a[i];
          for (int j = 0; j < q.n; j++)
t.a[j] += q.a[j];
          return t;
        }
      friend POLY operator*(POLY p, POLY q)
        { POLY t(0, (p.n-1)+(q.n-1));
          for (int i = 0; i < p.n; i++)
for (int j = 0; j < q.n; j++)
  t.a[i+j] += p.a[i]*q.a[j];
          return t;
        }
 };
        

Алгоритм Горнера - это прямой оптимальный линейный алгоритм, основанный на следующем использовании круглых скобок: $$$$a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}=(((a_{4}x+a_{3})x+a_{2})x+a_{1})x+a_{0}$$$$.

Алгоритм Горнера часто представляют как ловкий прием, экономящий время, но в действительности это первый выдающийся пример элегантного и эффективного алгоритма, который сокращает время, необходимое для выполнения этой важной вычислительной задачи, с квадратичного до линейного. Разновидностью алгоритма Горнера является преобразование строк с ASCII-символами в целые числа, выполняемое в программе 4.5. Мы еще встретимся с алгоритмом Горнера в , где на нем основаны важные вычисления, связанные с некоторыми реализациями таблиц символов и поиска строк.

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

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

(1 + х1000000)(1 + х2000000) = 1+ х1000000 + х2000000 + хЗОООООО

поскольку в ней будет использоваться память под массив с миллионами неиспользуемых коэффициентов. Более подробно вариант со связным списком рассматривается в упражнении 4.78.

Упражнения

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

4.79. Устраните утечку памяти в программе 4.25, добавив в нее конструктор копирования, перегруженную операцию присваивания и деструктор.

4.80. Добавьте перегруженные операции += и *= в АТД полинома из программы 4.25.

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

4.82. Измените полученный АТД полинома из упражнения 4.81 так, чтобы в нем игнорировались все члены со степенями, большими или равными целому числу M, которое передается из клиента во время инициализации.

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

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

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

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

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

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

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

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

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

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

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

Перспективы

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

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

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

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

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

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

Один АТД можно создавать на базе другого. Абстракции, подобные указателям и структурам, определенным в языке C++, использовались для построения связных списков. Далее абстракции связных списков и массивов, доступных в C++, применялись при построении стеков магазинного типа. А стеки магазинного типа использовались для организации вычислений арифметических выражений. Понятие АТД позволяет создавать большие системы на основе разных уровней абстракции, от машинных инструкций до разнообразных возможностей языка программирования, вплоть до сортировки, поиска и других возможностей высокого уровня, которые обеспечиваются алгоритмами, рассматриваемыми в частях III и IV Некоторые приложения требуют еще более высокого уровня абстракции, о которых речь идет в частях V - VIII. Абстрактные типы данных - лишь один этап в бесконечном процессе создания все более и более мощных абстрактных механизмов, в чем и заключается суть эффективного использования компьютеров для решения современных задач.