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

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

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

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

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

Примеры АТД

• Список
• Стек
• Очередь
• Ассоциативный массив
• Очередь с приоритетом

См. также

• Интерфейс программирования приложений
• Объектно-ориентированное программирование

Ссылки

• [www.rsdn.ru/article/alg/adt/adt.xml Лапшин В. А. Абстрактные типы данных в программировании]

Отрывок, характеризующий Абстрактный тип данных

За обедом разговор зашел о последней политической новости, о захвате Наполеоном владений герцога Ольденбургского и о русской враждебной Наполеону ноте, посланной ко всем европейским дворам.
– Бонапарт поступает с Европой как пират на завоеванном корабле, – сказал граф Ростопчин, повторяя уже несколько раз говоренную им фразу. – Удивляешься только долготерпению или ослеплению государей. Теперь дело доходит до папы, и Бонапарт уже не стесняясь хочет низвергнуть главу католической религии, и все молчат! Один наш государь протестовал против захвата владений герцога Ольденбургского. И то… – Граф Ростопчин замолчал, чувствуя, что он стоял на том рубеже, где уже нельзя осуждать.
– Предложили другие владения заместо Ольденбургского герцогства, – сказал князь Николай Андреич. – Точно я мужиков из Лысых Гор переселял в Богучарово и в рязанские, так и он герцогов.
– Le duc d'Oldenbourg supporte son malheur avec une force de caractere et une resignation admirable, [Герцог Ольденбургский переносит свое несчастие с замечательной силой воли и покорностью судьбе,] – сказал Борис, почтительно вступая в разговор. Он сказал это потому, что проездом из Петербурга имел честь представляться герцогу. Князь Николай Андреич посмотрел на молодого человека так, как будто он хотел бы ему сказать кое что на это, но раздумал, считая его слишком для того молодым.
– Я читал наш протест об Ольденбургском деле и удивлялся плохой редакции этой ноты, – сказал граф Ростопчин, небрежным тоном человека, судящего о деле ему хорошо знакомом.
Пьер с наивным удивлением посмотрел на Ростопчина, не понимая, почему его беспокоила плохая редакция ноты.
– Разве не всё равно, как написана нота, граф? – сказал он, – ежели содержание ее сильно.
– Mon cher, avec nos 500 mille hommes de troupes, il serait facile d'avoir un beau style, [Мой милый, с нашими 500 ми тысячами войска легко, кажется, выражаться хорошим слогом,] – сказал граф Ростопчин. Пьер понял, почему графа Ростопчина беспокоила pедакция ноты.
– Кажется, писак довольно развелось, – сказал старый князь: – там в Петербурге всё пишут, не только ноты, – новые законы всё пишут. Мой Андрюша там для России целый волюм законов написал. Нынче всё пишут! – И он неестественно засмеялся.
Разговор замолк на минуту; старый генерал прокашливаньем обратил на себя внимание.
– Изволили слышать о последнем событии на смотру в Петербурге? как себя новый французский посланник показал!
– Что? Да, я слышал что то; он что то неловко сказал при Его Величестве.
– Его Величество обратил его внимание на гренадерскую дивизию и церемониальный марш, – продолжал генерал, – и будто посланник никакого внимания не обратил и будто позволил себе сказать, что мы у себя во Франции на такие пустяки не обращаем внимания. Государь ничего не изволил сказать. На следующем смотру, говорят, государь ни разу не изволил обратиться к нему.