Что такое абстрактная структура данных

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

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

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

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

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

Примеры АТД

См. также

Ссылки

Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • First-class function • Opaque data type • Recursive data type • Семафор • Поток • Высший тип • Type class • Unit type • Void

Абстрактный тип данных • Структура данных • Интерфейс • Kind (type theory) • Примитивный тип • Subtyping • Шаблоны C++ • Конструктор типа • Parametric polymorphism

• Типы данных
• Структуры данных
• Теория типов

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Абстрактный тип данных» в других словарях:

абстрактный тип данных — Тип данных (абстрактный класс), определенный посредством перечисления его методов и свойств, без создания их конкретной реализации. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN Abstract Data TypeADT … Справочник технического переводчика

Алгебраический тип данных — в теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых… … Википедия

Целое (тип данных) — Целое, целочисленный тип данных (англ. Integer), в информатике  один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… … Википедия

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

Комплексный тип данных — Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках … Википедия

Указатель (тип данных) — У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer)  переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения  нулевого адреса.… … Википедия

Обобщённый алгебраический тип данных — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… … Википедия

Типаж (абстрактный тип) — Типаж (англ. trait)  это абстрактный тип, в информатике, используемый, как «простая концептуальная модель для структурирования объектно ориентированных программ»[1]. Типажи подобны mixins, но могут включать определения методов класса.… … Википедия

Структура данных — Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure)  программная единица, позволяющая хран … Википедия

Высший тип — (top type) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤),  универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется… … Википедия

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

Определение. Под структурой данных (СД) мы будем понимать два множества S = , гдеD– множество элементов данных, а R – множество взаимосвязей между ними. Другими словами СД – это организованное определенным образом множество элементов данных. В множество R включаются не все взаимосвязи между элементами, а только те, которые не зависят от конкретных значений элементов структуры, т. е. связи характерные для данного типа структуры, которые описывают ее общие характеристики.

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

Структура – это сложная конструкция данных и с ней можно связать ряд общих характеристик, таких как

— методы расположения и обработки и т.д.

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

Под методом доступа будем понимать множество операций (действий), выполнив которые, мы получим отдельный выделенный элемент структуры. В большинстве случаев метод доступа можно описать тремя процедурами:

— метод идентификации, т.е.

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

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

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

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

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

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

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

Лекція 4. Обзор основних структур даних.

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

Языки программирования высокого уровня(Паскаль, Си..) предоставляют удобный интерфейс для чисел: операции +, *, = .. и т.п, но при этом скрывают саму реализацию этих операций, машинные команды.

Структуры данных разделяют на два типа: статические и динамические.

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

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

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

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

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

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

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

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

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

большая гибкость структуры.

Вместе с тем связное представление не лишено и недостатков, основные из которых:

на поля связок расходуется дополнительная память;

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

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

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

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

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

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

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

В наиболее абстрактном виде любую структуру данных можно представить в виде:

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

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

Тело структуры данных — это набор взаимосвязанных элементов структуры, ради хранения и обработки которых структура, собственно, и была создана.

Что такое абстрактная структура данных

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

Каждый уже имел дело с простыми абстрактными структурами данных — например, когда оперировал с числами. Языки программирования высокого уровня(Паскаль, Си..) предоставляют удобный интерфейс для чисел: операции +, *, = .. и т.п, но при этом скрывают саму реализацию этих операций, машинные команды.

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

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

Слово ‘массив’ употребляется в различных контекстах:

как АТД, т.е множество с операциями:

• Получить элемент с номером N
• Записать элемент с номером N

и как физическая структура, реализованая в виде непрерывной области памяти.

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

• доступ за константное время к любому элементу
• память тратится только на данные *

Минус — один, но тоже большой: статичность, неизменность структуры. Одномерный массив иногда называют вектором.

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

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

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

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

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

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

Вместе с тем связное представление не лишено и недостатков, основные из которых:

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

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

Cписки

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

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

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

Двусвязный список характеризуется наличием пары указателей в каждом элементе: на предыдущий элемент и на следующий:

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

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

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

1. массива: выделяется место под N элементов разом, а затем описываются операции над данным типом данных в терминах операций над элементами массива.
2. списка: память выделяется и освобождается по мере необходимости.

Cтек

Стек — такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека — магазин и очередь, функционирующая по принципу LIFO (Last — In — First- Out — «последним пришел — первым исключается»). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.

Основные операции над стеком — включение нового элемента (английское название push — заталкивать) и исключение элемента из стека (англ. pop — выскакивать).

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

Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.

• а). пустого;
• б-г). после последовательного включения в него элементов с именами ‘A’, ‘B’, ‘C’;
• д, е). после последовательного удаления из стека элементов ‘C’ и ‘B’;
• ж). после включения в стек элемента ‘D’.

Как видно из рис. С.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D. Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

Очередь FIFO

Очередью FIFO (First — In — First- Out — «первым пришел — первым исключается»). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение — с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.

Основные операции над очередью — те же, что и над стеком — включение, исключение, определение размера, очистка, неразрушающее чтение.

Дек

Дек — особый вид очереди. Дек (от англ. deq — double ended queue,т.е очередь с двумя концами) — это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека — дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

• включение элемента справа;
• включение элемента слева;
• исключение элемента справа;
• исключение элемента слева;
• определение размера;
• очистка.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

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

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

Концепция Абстрактного Типа Данных

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

Что же означает слово “абстрактный”? В первую очередь понятие “абстрактность” означет сосредоточение внимания на чем-то важном и, при этом, нам нужно отвлечься от неважных, на данный момент, деталей. Определение абстрактности хорошо раскрыто в книге Гради Буча (“Grady Booch”). Звучит определение так:

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

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

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

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

Преимущества АТД

Использование АТД имеет массу преимуществ (все описанные преимущества можно найти в книге Стива Макконнелла «Совершенный код”):

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

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

• Ограничение области использования данных.
  Используя АТД мы можем быть уверены, что данные, представляющие внутреннюю структуру АТД не будут зависеть от других участков кода. При этом реализуется “независимость” АТД.

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

Стив Макконнелл рекомендует представлять в виде АТД низкоуровнеые типы данных, такие как стек или список. Спросите себя, что представляет собой этот список. Если он представляет список сотрудников банка, то и рассматривайте АТД как список сотрудников банка.

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

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

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

Стив Макконнелл – “Совершенный код”;
Роберт Седжвик – «Алгоритмы на Java».