Абстрактные типы данных. Структура данных

данных
Массив (англ. array)
Связный список (англ. linked list)
Бинарная куча (англ. binary heap) – специализированная древовидная структура данных

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

ФПМИ БГУ

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

ФПМИ БГУ

Реализациями абстрактных типов данных являются конкретные структуры данных. Реализация определяет, как именно представлены в памяти данные и как функционирует та или иная операция.

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

словарь (associative array/map/dictiona)
Приоритетная очередь (priority queue)

Примеры абстрактных типов данных:

ФПМИ БГУ

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

Массив – структура однородна, так как все компоненты имеют один и тот же тип.

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

ФПМИ БГУ

Размер массива равен 10

Начальный индекс

Элемент (с индексом 8)

Индексы

базовых операций

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

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

Подсчитаем общее число «лишних» операций по перемещению данных.

ФПМИ БГУ

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

Расширение с запасом

Число реально занятых ячеек памяти будем называть логическим размером (size) динамического массива.

Общее число зарезервированных ячеек будем называть ёмкостью (capacity).

ФПМИ БГУ

Ёмкость

Размер

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

Расширение на Δ:
будем каждый раз расширять массив не на один элемент, а сразу на ∆ элементов (∆ > 1).

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

Последующие (2-й, 3-й, … ,∆-1, ∆) элементы будут добавлены легко и быстро, так как не потребуется выполнять операции пере выделения памяти.

ФПМИ БГУ

∆=4

1 общее число операций по перемещению данных в памяти, которые выполняются при последовательном добавлении n элементов, растёт линейно с ростом n.

Начинаем работу с массива ёмкости 1.

Оценка сверху на число «лишних операций»:

ФПМИ БГУ

 

в массиве есть свободная ёмкость;
или за линейное, когда свободного места нет и выполняется реаллокация.

Усреднённо время вставки одного элемента в динамический массив константное.

Для получения усреднённой оценки некоторой операции выполняют некоторое число раз эту операцию, считают суммарное затраченное время (в худшем случае) и делят это время на число выполненных операций.
Если следовать стратегии удвоения размера, то на добавление в динамический массив k элементов требуется затратить время O(k). Тогда усреднённая оценка трудоёмкости добавления одного элемента в динамический массив:
В этом случае говорят, что O(1) — амортизированная оценка для операции вставки.

ФПМИ БГУ

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

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

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

Связный список (англ. linked list)

Доступ к элементам списка осуществляется последовательно, т. е. чем дальше в структуре расположен элемент, тем дольше к нему по времени будет осуществляться доступ.

Список состоит из узлов (англ. nodes). Каждый узел включает две части: информационную (непосредственные данные, принадлежащие элементу) и ссылочную (указатель/ссылка на следующий и/или предыдущий узел).

ФПМИ БГУ

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

В двусвязном, или двунаправленном связном, списке (англ. doubly linked list) ссылки в каждом узле указывают на предыдущий и на последующий узел.

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

При работе со списком вводятся дополнительные ссылки на первый и последний элемент списка. Будем называть их head («голова») и tail («хвост»).

ФПМИ БГУ

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

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

head=1

tail=0

ФПМИ БГУ

list[i]

next[i]

задана ссылка на элемент, который предшествует удаляемому

ФПМИ БГУ

элемент, после которого выполняется добавление

3. Удаление элемента
задана ссылка на элемент, который предшествует удаляемому

Время выполнения базовых операций

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

ФПМИ БГУ

удаления определённого элемента списка выполняются за O(1) при условии, что на вход даётся ссылка на узел (идущий перед точкой вставки или предшествующий узлу, который будет удалён). Если такая ссылка не предоставлена, то операции работают за O(n).
В то же время вставка в произвольное место динамического массива требует перемещения в среднем половины элементов, а в худшем случае — всех элементов. Хотя можно «удалить» элемент из массива за константное время, пометив его ячейку как «свободную», это вызовет фрагментацию, которая будет негативно влиять на скорость прохода по массиву.

Преимущества связных списков

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

ФПМИ БГУ

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

Недостатки связных списков

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

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

ФПМИ БГУ

крайне редко.

Применение на практике связных списков

Однако есть ряд алгоритмов, при разработке которых не обойтись без классических связных списков (например, к ним относятся многие механизмы кеширования).

ФПМИ БГУ

Динамические массивы обычно оказываются удобнее и эффективнее.

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

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

Список (list)
Стек (stack)
Очередь (queue)
Двухстороняя очередь (deque)
Множество (set)
Ассоциативный массив/словарь (associative array/ map/ dictionary)

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

ФПМИ БГУ

которые следуют в определённом порядке.

ФПМИ БГУ

Список является компьютерной реализацией математического понятия конечной последовательности.

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

3. операцию по добавлению объекта в начало или конец списка;

2. проверка, является ли список пустым;

4. операцию по получению ссылки на первый элемент («голову») или последний элемент («хвост») списка;

5. операцию перехода от одного элемента к следующему или предыдущему элементу;

6. операцию для доступа к элементу по заданному индексу.

Реализация интерфейса:

ФПМИ БГУ

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

3. Push(x) — добавление элемента x; заданный элемент добавляется на вершину стека

2. IsEmpty() — проверка стека на пустоту; возвращается значение «истина», если стек пуст, и «ложь» в противном случае;

4. Pop() — удаление элемента из стека; выполняется при условии, что стек не пуст, поэтому сначала надо убедиться в этом, а затем — извлечь с вершины стека последний занесённый в него элемент.

Реализация интерфейса:

Если при добавлении и исключении элементов реализуется принцип «последним пришёл — первым вышел» (англ. LIFO — last in first out), то такой абстрактный тип данных называют стеком.

Push(x)

Pop()

моделирования очереди:
на статическом массиве (кольцевая очередь) и на связном списке.

3. Enqueue(x) — добавление элемента x; заданный элемент добавляется в конец очереди

2. IsEmpty() — проверка очереди на пустоту;

4. Dequeue() — удаление элемента из очереди; элемент удаляется из начала очереди; операция выполняется при условии, что очередь не пуста, поэтому сначала надо убедиться в этом, а затем — извлечь элемент.

Реализация интерфейса:

Если при добавлении и исключении элементов реализуется принцип «первым пришёл — первым вышел» (англ. FIFO — first in first out), то такой абстрактный тип данных называют очередью.

ФПМИ БГУ

Enqueue(x)

Dequeue()

где добавление и удаление элементов возможно с обоих концов.

1.PushBack (x) — заданный элемент x добавляется в конец очереди;
2.PushFront (x) —заданный элемент x добавляется в начало очереди;
3.PopBack () — удаление элемента из конца очереди;
4.PopFront() — удаление элемента из начала очереди;
5.IsEmpty ()— проверка наличия элементов.
6.Clear ()— очистка.

Базовые операции:

ФПМИ БГУ

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

PushFront (x)

PushBack (x)

PopBack ()

PopFront ()

head

tail

объектов без определённого порядка.

Отличия множества от списка:
В множестве все элементы уникальны (в списке одинаковые элементы могут храниться несколько раз).
В множестве порядок следования элементов не сохраняется (в списке – сохраняется).

Базовые операции:

Insert(x) — добавить в множество ключ x;
Contains(x) — проверить, содержится ли в множестве ключ x;
Remove(x) — удалить ключ x из множества.

ФПМИ БГУ

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

Базовые операции:

Insert(k,v) — добавить пару, состоящую из ключа k и значения v;
Find(k) — найти значение, ассоциированное с ключом k, или сообщить, что значения, связанного с заданным ключом, нет;;
Remove(k) — удалить пару, ключ в которой равен k.

Реализация ассоциативного массива технически немного сложнее, чем множества (set), но использует те же идеи.

ФПМИ БГУ