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

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

  • автор:

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

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

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

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

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

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

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

  • Получить элемент с номером 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 очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.

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

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

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

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

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

Примеры АТД

См. также

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

Ссылки

Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • 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.

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

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

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

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

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

../_images/adt.png

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

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

readers online now | | Back to top

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

ЛЕКЦИЯ № 8. Абстрактные структуры данных

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

Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими. К ним относятся стеки, очереди, списки, деревья и др.

Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два поля: одно поле типа «указатель», а второе – для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью.

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

1) добавление элемента к списку;

2) удаление элемента из списка с заданным ключом;

3) поиск элемента с заданным значением ключевого поля;

4) сортировка элементов списка;

5) деление списка на два и более списков;

6) объединение двух и более списков в один;

7) другие операции.

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

Данный текст является ознакомительным фрагментом.

Продолжение на ЛитРес

Читайте также

Структуры данных

Структуры данных Первое, в чем следует разобраться, — это структуры данных, которые управляют работой библиотеки:• управляющая структура resmgr_attr_t• таблица функций установления соединения resmgr_connect_funcs_t• таблица функций ввода-вывода resmgr_io_funcs_t и еще одна внутренняя

11.7.1. Структуры данных

11.7.1. Структуры данных Хотя код в ladsh1.с поддерживает концепцию задания как множества процессов (предположительно, объединенных вместе каналами), он не предоставляет способа указания того, какие файлы использовать для ввода и вывода. Чтобы позволить это, добавляются новые

Лекция 4. Управляющие структуры

Структуры данных

Структуры данных Структура данных socket, описывающая сокет, представлена на рис. 6.21. В этой структуре хранится информация о типе сокета (so_type), его текущем состоянии (so_state) и используемом протоколе (so_proto). Рис. 6.21. Структуры данных сокетаСокет является коммуникационным узлом

ЛЕКЦИЯ № 5. Строковый тип данных

ЛЕКЦИЯ № 5. Строковый тип данных 1. Строковый тип в Pascal Последовательность символов определенной длины называется строкой. Переменные строкового типа определяются путем указания имени переменной, зарезервированного слова string, и возможно, но не обязательно указания

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

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

ЛЕКЦИЯ № 9. Древовидные структуры данных

ЛЕКЦИЯ № 9. Древовидные структуры данных 1. Древовидные структуры данных Древовидной структурой данных называется конечное множество элементов-узлов, между которыми существуют отношения – связь исходного и порожденного.Если использовать рекурсивное определение,

ЛЕКЦИЯ № 11. Объектный тип данных

ЛЕКЦИЯ № 11. Объектный тип данных 1. Объектный тип в Pascal. Понятие объекта, его описание и использование Исторически первым подходом в программировании являлось процедурное программирование, иначе называемое программированием снизу вверх. Вначале создавались общие

ЛЕКЦИЯ № 17. Структуры команд на Ассемблере

ЛЕКЦИЯ № 17. Структуры команд на Ассемблере 1. Структура машинной команды Машинная команда представляет собой закодированное по определенным правилам указание микропроцессору на выполнение некоторой операции или действия. Каждая команда содержит элементы,

Интерфейсы и абстрактные поставщики данных

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

Лекция 6. Абстрактные типы данных (АТД)

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

Абстрактные типы данных и скрытие информации

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

Лекция 7. Статические структуры: классы

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

Лекция 8. Динамические структуры: объекты

Лекция 8. Динамические структуры: объекты В предыдущей лекции отмечалось, что экземпляры классов называют объектами. Настало время переключить внимание на эти объекты, и в общем смысле — на модель ОО-вычислений времени выполнения. В предыдущих лекциях рассматривались в

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

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

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

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