Абстрактный тип данных - Abstract data type

Не путать с алгебраический тип данных.

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

Формально ADT можно определить как «класс объектов, логическое поведение которых определяется набором значений и набором операций»;[1] это аналогично алгебраическая структура по математике. То, что подразумевается под «поведением», варьируется в зависимости от автора, причем два основных типа формальных спецификаций поведения аксиоматическая (алгебраическая) спецификация и абстрактная модель;[2] они соответствуют аксиоматическая семантика и операционная семантика из абстрактная машина, соответственно. Некоторые авторы также включают вычислительная сложность («стоимость») как во времени (для вычислительных операций), так и в пространстве (для представления значений). На практике многие распространенные типы данных не являются ADT, поскольку абстракция не идеальна, и пользователи должны знать о таких проблемах, как арифметическое переполнение которые связаны с представлением. Например, целые числа часто хранятся как значения фиксированной ширины (32-битные или 64-битные двоичные числа), и поэтому целочисленное переполнение если максимальное значение превышено.

ADT - это теоретическая концепция в информатике, используемая при разработке и анализе алгоритмы, структуры данных и программные системы, и не соответствуют специфическим особенностям компьютерные языки - основные компьютерные языки напрямую не поддерживают официально определенные ADT. Однако различные языковые функции соответствуют определенным аспектам ADT, и их легко спутать с собственно ADT; к ним относятся абстрактные типы, непрозрачные типы данных, протоколы, и дизайн по контракту. ADT были впервые предложены Барбара Лисков и Стивен Н. Зиллес в 1974 году в рамках разработки CLU язык.[3]

Примеры

Например, целые числа являются ADT, определяемыми как значения ..., −2, −1, 0, 1, 2, ..., а также операциями сложения, вычитания, умножения и деления вместе с более, менее, и т.д., которые ведут себя согласно знакомой математике (с осторожностью целочисленное деление ), независимо от того, как целые числа представляются компьютером.[а] Явно «поведение» включает в себя соблюдение различных аксиом (ассоциативность и коммутативность сложения и т. Д.) И предварительных условий для операций (не может делиться на ноль). Обычно целые числа представлены в структуре данных как двоичные числа, чаще всего как два дополнения, но может быть двоично-десятичный или в дополнение, но пользователь абстрагируется от конкретного выбора представления и может просто использовать данные как типы данных.

ADT состоит не только из операций, но также из значений базовых данных и ограничений на операции. «Интерфейс» обычно относится только к операциям и, возможно, к некоторым ограничениям на операции, особенно к предварительным условиям и постусловиям, но не к другим ограничениям, таким как отношения между операциями.

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

Вступление

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

Термин абстрактный тип данных также можно рассматривать как обобщенный подход ряда алгебраические структуры, такие как решетки, группы и кольца.[4] Понятие абстрактных типов данных связано с концепцией абстракция данных важно в объектно-ориентированного программирования и дизайн по контракту методологии для разработка программного обеспечения.[5]

Определение абстрактного типа данных

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

Определение императивного стиля

В философии императивное программирование языков абстрактная структура данных рассматривается как объект, который изменчивый- это означает, что он может быть в разных состояния в разное время. Некоторые операции могут изменить состояние ADT; поэтому порядок, в котором оцениваются операции, важен, и одна и та же операция с одними и теми же объектами может иметь разные эффекты, если выполняется в разное время - точно так же, как инструкции компьютера или команды и процедуры императивного языка. Чтобы подчеркнуть эту точку зрения, принято говорить, что операции казнен или же применяемый, скорее, чем оценен. Императивный стиль часто используется при описании абстрактных алгоритмов. (Видеть Искусство программирования к Дональд Кнут Больше подробностей)

Абстрактная переменная

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

  • хранить(V, Икс) куда Икс это ценить неустановленного характера;
  • принести(V), что дает значение,

с ограничением, что

  • принести(V) всегда возвращает значение Икс используется в самых последних хранить(V, Икс) операция с той же переменной V.

Как и во многих языках программирования, операция хранить(V, Икс) часто пишут V ← Икс (или другое подобное обозначение), и принести(V) подразумевается всякий раз, когда переменная V используется в контексте, где требуется значение. Так, например, V ← V + 1 обычно понимается как сокращение от хранить(V,принести(V) + 1).

В этом определении неявно предполагается, что сохранение значения в переменной U не влияет на состояние отдельной переменной V. Чтобы сделать это предположение явным, можно добавить ограничение, которое

  • если U и V - различные переменные, последовательность { хранить(U, Икс); хранить(V, у) } эквивалентно { хранить(V, у); хранить(U, Икс) }.

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

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

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

Создание экземпляра

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

  • результат Создайте() отличается от любого экземпляра, используемого алгоритмом.

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

Пример: абстрактный стек (обязательно)

В качестве другого примера, определение абстрактного стека в императивном стиле может указывать, что состояние стека S могут быть изменены только операциями

  • толкать(S, Икс), куда Икс есть некоторые ценить неустановленного характера;
  • поп(S), что в результате дает значение,

с ограничением, что

  • Для любого значения Икс и любая абстрактная переменная V, последовательность операций { толкать(S, Икс); V ← поп(S) } эквивалентно V ← Икс.

Поскольку назначение V ← Икспо определению не может изменить состояние S, из этого условия следует, что V ← поп(S) восстанавливает S в состояние, которое было до толкать(S, Икс). Из этого условия и из свойств абстрактных переменных следует, например, что последовательность

{ толкать(S, Икс); толкать(S, у); U ← поп(S); толкать(S, z); V ← поп(S); W ← поп(S) }

куда Икс, у, и z любые значения, и U, V, W - попарно различные переменные, эквивалентно

{ U ← у; V ← z; W ← Икс }

Здесь неявно предполагается, что операции с экземпляром стека не изменяют состояние любого другого экземпляра ADT, включая другие стеки; то есть,

  • Для любых значений Икс, у, и любые отдельные стеки S и Т, последовательность { толкать(S, Икс); толкать(Т, у) } эквивалентно { толкать(Т, у); толкать(S, Икс) }.

Определение абстрактного стека обычно включает также Булево -значная функция пустой(S) и Создайте(), которая возвращает экземпляр стека с аксиомами, эквивалентными

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

Единичный стиль

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

С другой стороны, некоторые ADT не могут быть осмысленно определены без использования нескольких экземпляров. Это тот случай, когда одна операция принимает в качестве параметров два разных экземпляра ADT. Например, рассмотрите возможность дополнения определения абстрактного стека операцией сравнивать(S, Т), который проверяет, S и Т содержат одинаковые предметы в том же порядке.

Определение функционального стиля

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

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

Пример: абстрактный стек (функциональный)

Например, полное определение абстрактного стека в функциональном стиле может использовать три операции:

  • толкать: принимает состояние стека и произвольное значение, возвращает состояние стека;
  • верх: принимает состояние стека, возвращает значение;
  • поп: принимает состояние стека, возвращает состояние стека.

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

Вместо Создайте(), определение абстрактного стека в функциональном стиле может предполагать наличие специального состояния стека, пустой стекобозначается специальным символом типа Λ или "()"; или определить Нижний() операция, которая не принимает аргументов и возвращает это особое состояние стека. Обратите внимание, что из аксиом следует, что

  • толкать(Λ, Икс) ≠ Λ.

В функциональном определении стека не требуется пустой предикат: вместо этого можно проверить, пуст ли стек, проверяя, равен ли он Λ.

Обратите внимание, что эти аксиомы не определяют эффект верх(s) или же поп(s), пока не s состояние стека, возвращаемое толкать. С толкать оставляет стек непустым, эти две операции не определены (следовательно, недопустимы), когда s = Λ. С другой стороны, аксиомы (и отсутствие побочных эффектов) подразумевают, что толкать(s, Икс) = толкать(т, у) если и только если Икс = у и s = т.

Как и в некоторых других разделах математики, принято также считать, что состояния стека - это только те состояния, существование которых можно доказать с помощью аксиом за конечное число шагов. В приведенном выше примере абстрактного стека это правило означает, что каждый стек является конечный последовательность значений, которая становится пустым стеком (Λ) после конечного числа попс. Сами по себе аксиомы выше не исключают существования бесконечных стеков (которые могут быть попed навсегда, каждый раз приводя к другому состоянию) или круговых стеков (которые возвращаются в то же состояние после конечного числа попс). В частности, они не исключают состояния s такой, что поп(s) = s или же толкать(s, Икс) = s для некоторых Икс. Однако, поскольку невозможно получить такие состояния стека с помощью данных операций, предполагается, что они «не существуют».

Следует ли включать сложность

Помимо поведения в терминах аксиом, в определение операции ADT также можно включить их алгоритмическая сложность. Александр Степанов, конструктор C ++ Стандартная библиотека шаблонов, включил гарантии сложности в спецификацию STL, утверждая:

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

— Александр Степанов[6]

Преимущества абстрактной типизации данных

Инкапсуляция

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

Локализация изменения

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

Гибкость

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

Типичные операции

Некоторые операции, которые часто указываются для ADT (возможно, под другими именами):

  • сравнивать(s, т), который проверяет, эквивалентны ли состояния двух экземпляров в каком-то смысле;
  • хэш(s), который вычисляет некоторые стандартные хеш-функция из состояния экземпляра;
  • Распечатать(s) или же Показать(s), который создает удобочитаемое представление состояния экземпляра.

В определениях ADT императивного стиля часто встречаются

  • Создайте(), что дает новый экземпляр ADT;
  • инициализировать(s), который подготавливает вновь созданный экземпляр s для дальнейших операций, либо сбрасывает в какое-то «начальное состояние»;
  • копировать(s, т), который помещает экземпляр s в состоянии, эквивалентном состоянию т;
  • клон(т), который выполняет s ← Создайте(), копировать(s, т) и возвращает s;
  • свободный(s) или же разрушать(s), который восстанавливает память и другие ресурсы, используемые s.

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

Примеры

Некоторые распространенные ADT, которые доказали свою полезность в большом количестве приложений:

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

Абстрактный графический тип данных

Расширение ADT для компьютерной графики было предложено в 1979 году:[7] ан абстрактный графический тип данных (АГДТ). Он был представлен Надя Магненат Тельманн, и Даниэль Тельманн. AGDT предоставляют преимущества ADT со средствами для структурированного построения графических объектов.

Выполнение

Дальнейшая информация: Непрозрачный тип данных

Реализация ADT означает предоставление одного процедура или функция для каждой абстрактной операции. Экземпляры ADT представлены некоторыми конкретными структура данных который управляется этими процедурами в соответствии со спецификациями ADT.

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

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

При реализации ADT каждый экземпляр (в определениях императивного стиля) или каждое состояние (в определениях функционального стиля) обычно представлен ручка какой-то.[8]

Современные объектно-ориентированные языки, такие как C ++ и Ява, поддерживают абстрактные типы данных. Когда класс используется как тип, это абстрактный тип, который относится к скрытому представлению. В этой модели ADT обычно реализуется как учебный класс, и каждый экземпляр ADT обычно объект этого класса. Интерфейс модуля обычно объявляет конструкторы как обычные процедуры, а большинство других операций ADT как методы этого класса. Однако такой подход нелегко инкапсулировать несколько вариантов представления, найденных в ADT. Это также может подорвать расширяемость объектно-ориентированных программ. В чисто объектно-ориентированной программе, которая использует интерфейсы как типы, типы относятся к поведению, а не к представлениям.

Пример: реализация абстрактного стека

В качестве примера, вот реализация абстрактного стека выше в Язык программирования C.

Интерфейс в императивном стиле

Интерфейс в императивном стиле может быть:

typedef структура stack_Rep stack_Rep;       // тип: представление экземпляра стека (непрозрачная запись)typedef stack_Rep* stack_T;               // тип: дескриптор экземпляра стека (непрозрачный указатель)typedef пустота* stack_Item;                 // тип: значение хранится в экземпляре стека (произвольный адрес)stack_T stack_create(пустота);               // создает новый пустой экземпляр стекапустота stack_push(stack_T s, stack_Item Икс); // добавляет элемент вверху стекаstack_Item stack_pop(stack_T s);          // удаляет верхний элемент из стека и возвращает егоbool stack_empty(stack_T s);              // проверяет, пуст ли стек

Этот интерфейс можно использовать следующим образом:

#включают  // включает интерфейс стекаstack_T s = stack_create(); // создает новый пустой экземпляр стекаint Икс = 17;stack_push(s, &Икс);          // добавляет адрес x наверху стекапустота* у = stack_pop(s);     // удаляет адрес x из стека и возвращает егоесли (stack_empty(s)) { }     // что-то делает, если стек пуст

Этот интерфейс можно реализовать разными способами. Реализация может быть произвольно неэффективной, поскольку формальное определение ADT, приведенное выше, не указывает, сколько места может использовать стек и сколько времени должна занимать каждая операция. Он также не указывает, является ли состояние стека s продолжает существовать после звонка Икс ← поп(s).

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

Функциональный интерфейс

Определения ADT функционального стиля больше подходят для языков функционального программирования, и наоборот. Однако можно предоставить интерфейс в функциональном стиле даже на императивном языке, таком как C.Например:

typedef структура stack_Rep stack_Rep;          // тип: представление состояния стека (непрозрачная запись)typedef stack_Rep* stack_T;                  // тип: дескриптор состояния стека (непрозрачный указатель)typedef пустота* stack_Item;                    // тип: значение состояния стека (произвольный адрес)stack_T stack_empty(пустота);                   // возвращает состояние пустого стекаstack_T stack_push(stack_T s, stack_Item Икс); // добавляет элемент наверху состояния стека и возвращает результирующее состояние стекаstack_T stack_pop(stack_T s);                // удаляет верхний элемент из состояния стека и возвращает результирующее состояние стекаstack_Item stack_top(stack_T s);             // возвращает верхний элемент состояния стека

Библиотеки ADT

Многие современные языки программирования, такие как C ++ и Java, поставляются со стандартными библиотеками, реализующими несколько распространенных ADT, например перечисленные выше.

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

Спецификация некоторых языков программирования намеренно расплывчата относительно представления определенных встроенных типов данных, определяя только операции, которые могут быть выполнены с ними. Следовательно, эти типы можно рассматривать как «встроенные ADT». Примерами являются массивы на многих языках сценариев, таких как Awk, Lua, и Perl, который можно рассматривать как реализацию абстрактного списка.

Смотрите также

Примечания

  1. ^ Сравните с характеристикой целых чисел в абстрактной алгебре.

Цитаты

  1. ^ Дейл и Уокер 1996, п. 3.
  2. ^ Дейл и Уокер 1996, п. 4.
  3. ^ Лисков и Зиллес 1974.
  4. ^ Рудольф Лидл (2004). Абстрактная алгебра. Springer. ISBN  978-81-8128-149-4., Глава 7, раздел 40.
  5. ^ "Что такое объектно-ориентированное программирование?". Наем | Upwork. 2015-05-05. Получено 2016-10-28.
  6. ^ Стивенс, Эл (март 1995 г.). "Интервью Эла Стивенса Алексу Степанову". Журнал доктора Добба. Получено 31 января 2015.
  7. ^ Д. Тельманн, Н. Магненат Тальманн (1979). Дизайн и реализация абстрактных графических типов данных. IEEE. Дои:10.1109 / CMPSAC.1979.762551., Proc. 3-я Международная конференция по компьютерному программному обеспечению и приложениям (COMPSAC'79), IEEE, Чикаго, США, стр. 519-524
  8. ^ Роберт Седжвик (1998). Алгоритмы на C. Эддисон / Уэсли. ISBN  978-0-201-31452-6., определение 4.4.

Рекомендации

  • Лисков, Варвара; Зиллес, Стивен (1974). «Программирование с абстрактными типами данных». Материалы симпозиума ACM SIGPLAN по языкам очень высокого уровня. Уведомления SIGPLAN. 9. С. 50–59. CiteSeerX  10.1.1.136.3043. Дои:10.1145/800233.807045.CS1 maint: ref = harv (связь)
  • Дейл, Нелл; Уокер, Генри М. (1996). Абстрактные типы данных: спецификации, реализации и приложения. Джонс и Бартлетт Обучение. ISBN  978-0-66940000-7.CS1 maint: ref = harv (связь)

дальнейшее чтение

внешняя ссылка