Что такое абстрактная структура данных
Перейти к содержимому

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

  • автор:

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

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

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

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

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

Примеры АТД

См. также

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

Ссылки

Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • 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) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤), универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется… … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cписки

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

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

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

Рис. 1: Представление односвязного списка в памяти

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

Рис. 2: Представление двусвязного списка в памяти

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

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

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

Рис. 3: Структура кольцевого двухсвязного списка

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

Cтек

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

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

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

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

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

Рис. 4: Включение и исключение элементов из стека

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

Очередь FIFO

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

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

[Статическая реализация очереди на основе массива]
Динамическая реализация очереди аналогична реализации стека.

Дек

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

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

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

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

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

Абстрактные типы данных. Изложение для начинающих

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

Тип данных — множество значений и [допустимых] операций над этими значениями.

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

Представьте себе такой диалог матери и маленького сына лет трех, который еще не очень освоил абстрактное мышление:

— Сынок, принеси, пожалуйста, со стола ручку, мне надо записать кое‑что!

— Мама, тут нет ручки!

— Тогда карандаш.

— И карандаша нет.

— А что есть?

— Фломастеры есть и маркер.

— Ну, тогда неси фломастер!

Взрослый человек скорее всего сразу бы принес фломастер и сказал: «ручки не было, думаю, фломастер сгодится». Почему? — Потому что с какого‑то уровня развития абстрактного мышления и умения взаимодействовать с другими людьми, человек уже понимает, что в этой просьбе главное не конкретный тип объекта — ручка — а ее свойство писать по бумаге. Таким же свойством обладают и другие объекты: карандаши, фломастеры, маркеры, даже кусочек угля. Таким образом, он машинально объединяет несколько типов инструментов в один тип: «то, чем можно писать». Это умение часто упрощает нам повседневную жизнь и общение с окружающими, при этом несколько отдаляя нас от конкретных физических объектов. Чтобы добраться до работы, мы используем «общественный транспорт» — маршруты и конкретные вагоны или машины могут быть разными, но главное, что они обладают нужными нам свойствами: мы можем войти, выйти, оплатить проезд, мы заранее уверены в том, что это можно сделать с каждым из объектов этого типа. Когда мы в незнакомом городе хотим сходить в кафе, мы спрашиваем у друзей или в интернете: «где в городе Н можно вкусно поесть?», — то есть мы не определяем конкретное заведение, даже его тип, а ставим во главу угла самое важное свойство группы заведений: мы можем прийти туда и заказать еду.

Иными словами, в некоторых ситуациях нам важен не объект конкретного типа, а какие‑то определенные его свойства: то есть, что именно мы можем с ним делать. Часто искомыми свойствами обладают несколько типов данных, и все они нам так или иначе подойдут, как в описанных выше примерах. Это подводит нас к определению абстрактного типа данных. Сначала приведем формальное определение, а затем раскроем его в более простых терминах.

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

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

Углубляемся в детали и разбираем примеры

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

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

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

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

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

Остается самый важный вопрос: зачем все это нужно? Чтобы ответить на него, давайте рассмотрим задачу подробнее.

Представим, что в очереди уже есть талоны с номерами 109, 101, 105, 112 с приоритетами 5, 3, 1, 1 соответственно. Следующему пациенту выдается талон 113 с приоритетом 3. Тогда этот талон «обходит» номера 105 и 112, потому что их приоритет ниже, и встает позади талона 101, с которым их приоритеты равны (рис. 1). Когда врач готов принять следующего пациента, то вызван будет пациент с номером 109 (рис. 2).

Рис. 1. Новый пациент в очереди. Рис.2. Выбор следующего пациента в очереди.

Давайте напишем код, реализующий эту логику. Будем использовать язык javascript. Сначала опишем обычную очередь, без учета приоритета. Создадим класс PriorityQueue . Объекты этого класса будут содержать изначально пустой массив data (создается в конструкторе). Функция add_elem будет добавлять переданный ей параметр — номер талона — в конец массива data , а функция get_next будет описывать вызов врачом пациента на прием: возвращать значение первого элемента в массиве — номер пациента, который встал в очередь раньше всех остальных, удаляя из массива этот элемент, так как, отправляясь на прием, пациент покидает очередь. Также определим функцию print_queue , которая будет выводить в консоль все элементы очереди по порядку.

class PriorityQueue < constructor()< this.data = []; >add_elem(e) < this.data.push(e); >get_next() < return this.data.shift() >print_queue() < for(var i in this.data) console.log(this.data[i]); >>;

Приведем пример использования этого класса в коде программы:

Q = new PriorityQueue(); Q.add_elem(105); Q.add_elem(101); Q.add_elem(109); console.log("next:",Q.get_next()) // next: 105 console.log("remains:") Q.print_queue(); // 101 109

Давайте модифицируем получившийся класс, чтобы очередь учитывала приоритет элемента. Для этого будем в массиве data хранить не просто переданный элемент, а объект с двумя полями: значение ( value ) и приоритет ( priority ). В коде такой объект будет задаваться выражением вида var obj = ; Перепишем функцию добавления элемента в очередь:

//теперь функция принимает два аргумента: значение и приоритет add_elem(e,p) < //просматриваем очередь с конца for (var i = this.data.length - 1; i >= 0; i--) < // как только нашли элемент с равным или большим приоритетом if(this.data[i].priority >= p)< //вставляем новый элемент позади найденного this.data.splice(i+1,0,); return; //выходим из функции, добавление завершено > > //если более приоритетных (или равных) элементов в очереди нет, //то новый элемент становиться первым в очереди. this.data.splice(0,0,); >

Смоделируем ситуацию, проиллюстрированную на рисунках 1 и 2.

Q = new PriorityQueue(); Q.add_elem(109,5); Q.add_elem(101,3); Q.add_elem(105,1); Q.add_elem(112,1); Q.add_elem(113,3); console.log("next:",Q.get_next()) // next: < value: 109, priority: 5 >console.log("remains:") Q.print_queue(); // value: 101, priority: 3 > // < value: 113, priority: 3 >// < value: 105, priority: 1 >//

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

Для этого изменим функцию выбора следующего элемента get_next .

get_next() < var e = this.data.shift(); for(var i in this.data)< //для всех оставшихся в очереди элементов if(this.data[i].priority<8) //если они еще не достигли максимума this.data[i].priority++; //увеличиваем приоритет на 1 >return e; >

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

Получившийся код программы можно условно разделить на две части: описание класса PriorityQueue и использование этого класса. Заметим, что использование класса выглядит достаточно лаконично по сравнению с его описанием. При работе с классом и его функциями программист, который выступает в данном случае как пользователь класса, может не иметь представления, как именно реализована логика работы внутри функций класса. Для его работы достаточно того, что эта логика соответствует заявленному описанию работы приоритетной очереди. В таком случае говорят, что класс реализует определенный интерфейс — набор методов работы с классом, где зафиксированы входные и выходные параметры. В данном примере это методы add_elem , get_next и print_queue . Можно поменять внутреннюю логику работы этих методов, если того потребует задача, как это было в случае с повышением приоритета при долгом ожидании. Однако для пользователя класса эти изменения не будут заметны и не потребуют изменения кода основной программы.

Бонус. Что такое структура данных?

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

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

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

Заключение

Подведем итоги проделанной работы. Класс PriorityQueue обладает следующими свойствами:

  1. Он может хранить в себе любые элементы с приоритетом, который задается числом.
  2. Определен интерфейс взаимодействия с классом: методы add_elem , get_next и print_queue .
  3. Описанные методы реализуют заявленную логику работы приоритетной очереди.
  4. Методы обладают определенным поведением (см., например, бонус).

Таким образом, мы создали свой абстрактный тип данных и реализовали его на языке javascript. Что мы от этого выиграли:

  1. Код основной программы лаконичен и понятен, так как не содержит «технических» подробностей внутренней работы очереди.
  2. Удобно вносить изменения в логику работы очереди, не затрагивая основной код.
  3. Класс PriorityQueue может быть переиспользован в других программах, где требуется похожая логика.
  4. В случае командной работы можно разделить между людьми работу над классом и разработку с использованием этого класса. Связующим звеном будет являться интерфейс класса.

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

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

Помните, что у высказывания Дэвида Уиллера и есть и вторая, менее известная, часть:

В компьютерной науке все проблемы могут быть решены с помощью дополнительного уровня косвенности. Но как правило это создаёт другую проблему

Для чего изучать структуры и абстрактные типы данных?¶

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

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

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

../_images/adt.png

Рисунок 2: Абстрактный тип данных

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

readers online now | | Back to top

© Copyright 2014 Brad Miller, David Ranum. Created using Sphinx 1.2.3.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *