- Структура данных
- программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике.
- Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Понятно, что структуры данных – множество практически неограниченное. Мы рассмотрим несколько типовых структур данных и обсудим сложность операций их интерфейсов.
Последовательности
Многие структуры данных реализуют абстрактную модель “последовательности” – некого упорядоченного набора значений. “Упорядоченного” в данном случае означает только то, что есть ответ на вопрос “какой элемент следующий за данным”.
Линейный массив
Линейный массив является, возможно, простейшей нетривиальной структурой данных, и представляет из себя непрерывный участок памяти размера \(N\cdot |x|\), где \(N\) – число элементов массива, \(|x|\) – объём памяти, используемый для хранения одного элемента.
Доступ к \(i\)-тому элементу сводится к вычислению смещения \(M+i\cdot s,\) где \(M\) – адрес первого элемента. Полагая, что \(i,\), \(s\) являются целыми фиксированного размера, сложность доступа к элементу в массиве – \(\mathcal O(1).\)
Добавление элемента в массив в общем случае может требовать выделения нового линейного блока памяти размера \(N+1\) и копирования данных в этот блок, поэтому добавление элемента имеет сложность \(\mathcal O(N).\)
Удаление элемента из конца массива в принципе может иметь сложность \(\mathcal O(1)\) (если просто игнорировать удалённый элемент). Удаление, однако, из середины требует перемещения всех элементов после данного, поэтому удаление элемента в общем случае тоже имеет сложность \(\mathcal O(N).\)
Поиск элемента в массиве требует просмотра всех элементов, поэтому имеет сложность \(\mathcal O(N).\)
Односвязный список
Список представляет из себя набор элементов, каждый из которых имеет указатель на следующий элемент. Последний элемент списка указывает на некорректный адрес памяти (обычно NULL). Элементы могут быть расположены в памяти произвольным образом.
В качестве собственно самого “списка” хранится указатель на первый элемент.
Доступ к \(i\)-тому элементу требует прохода по первым \(i\) элементам. Обычно говорят что сложность доступа к произвольному элементу \(\mathcal O(N).\)
Добавление элемента после данного или в начало списка имеет сложность \(\mathcal O(1),\) так как сводится к изменению двух указателей на следующий элемент.
Удаление элемента аналогично имеет сложность \(\mathcal O(1)\) при условии что известен предыдущий элемент. В противном случае для поиска предыдущего элемента требуется \(\mathcal O(N)\) операций.
Поиск требует просмотра всех элементов, поэтому имеет сложность \(\mathcal O(N).\)
Двусвязный список
Двусвязный список кроме указателя на следующий элемент содержит также указатель на предыдущий элемент.
Основные отличие от односвязного списка в том, что удаление данного элемента безусловно имеет сложность \(\mathcal O(1),\) и возможен проход по списку как в прямом, так и в обратном направлении.
Дерево
Дерево представляет из себя древовидную структуру – набор связанных узлов. Можно рассматривать дерево как обобщение идеи связанного списка, где у одного элемента, называемого узлом, может быть несколько “следующих”, называемых дочерними. С другой стороны, дерево является ациклическим направленным графом.
Дерево фактически может быть представлено различным образом. Наиболее популярные варианты – в виде элементов с указателями на дочерние или в виде массива, в котором отношения между элементами определяются положением в массиве.
В общем случае у узла дерева может быть произвольное число дочерних узлов. Такие деревья иногда называют “розовыми”. Выделяют также деревья, в которых у каждого узла не более двух дочерних – их называют бинарными.
Узлы, не имеющие дочерних, называют “листьями”. Узел, не имеющий родительских называют корневым.
Абстрактные структуры данных
Абстрактные структуры данных могут быть реализованы на основе различных базовых структур, и реализуют определённый абстрактный интерфейс доступа к нижележащим данным.
Стек
Стек, также известный как магазинная память, реализует дисциплину доступа к данным “LIFO” (“последний на входе – первый на выходе”). Идеологически, элементы в стеке ведут себя как патроны в магазине – их можно добавлять “на вершину”, можно удалять “с вершины”, можно читать элемент “на вершине”.
Стек может быть реализован как на основе массива, так и на основе односвязного списка.
Добавление, удаление, чтение элемента на вершине стека имеет сложность \(\mathcal O(1).\)
Очередь
Очередь реализует дисциплину доступа к данным “FIFO” (“первый на входе – первый на выходе”).
Очередь может быть реализована на основе массива (в варианте кольцевого буфера) или на основе односвязного списка.
В варианте на основе односвязного списка, новые элементы добавляются в конец списка, а удаляются из начала.
В варианте на основе массива, используется два указателя на начало и конец очереди. Добавление элемента смещает указатель на конец очереди, удаление элемента смещает указатель на начало очереди. Таким образом оба указателя смещаются в направлении конца массива. Если один из указателей выходит за границы массива, он перемещается в начало. Такой вариант имеет жёстко ограниченную максимальную длину очереди.
Добавление, удаление, чтение текущего элемента имеет сложность \(\mathcal O(1).\)
Также очередь можно реализовать при помощи двух стеков, однако удаление элемента при такой реализации в худшем случае имеет сложность \(\mathcal O(N).\)
Куча
Куча – дерево, которое удовлетворяет свойству кучи: дочерние узлы в каком-то смысле не больше родительских. Т.е. над узлами дерева так или иначе определён полный порядок (операции сравнения), и от корня к листьям дерево упорядочено по невозрастанию. Наибольший элемент всегда является корневым узлом, поэтому такие кучи называют max-кучами. Также есть симметричное понятие min-кучи.
Куча поддерживает следующие операции:
- найти максимум или найти минимум: найти максимальный элемент в max-куче или минимальный элемент в min-куче, соответственно
- удалить максимум или удалить минимум: удалить корневой узел в max- или min-куче, соответственно
- добавить: добавление нового узла в кучу.
- слияние: соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных.
Существует множество различных вариантов реализации кучи с различными оценками сложности. Мы рассмотрим двоичную кучу.
Двоичная куча является двоичным деревом, обладающим свойством кучи, и дополнительно обладает следующими свойствами:
- Глубина всех листьев (расстояние до корня) отличается не более чем на 1.
- Последний слой заполняется слева направо без пропусков.
Двоичная куча часто представляется массивом, в котором корень находится на позиции с индексом \(i\), а дочерние узлы (при нумерации с \(0\)) – на позициях \(2i+1\) и \(2i+2.\) В таком случае дополнительные свойства соблюдаются “автоматически”.
Сложность операций:
- найти корень: \(\mathcal O(1)\)
- удалить корень: \(\mathcal O(\log N)\)
- добавить: \(\mathcal O(\log N)\)
- слияние: \(\mathcal O(N)\)
Отметим, что построение двоичной кучи из массива аналогично сортировке и имеет сложность \(\mathcal O(N\log N)\)
Очередь с приоритетом
Очередь с приоритетом – вариация на тему очереди, в которой у элементов есть “приоритет”, такой, что сперва из очереди выходят элементы с более высоким приоритетом.
Технически, очередь с приоритетом можно реализовать на основе массива или списка, но тогда добавление/удаление элементов будет иметь высокую сложность (\(\mathcal O(N)\)). Обычно очередь с приоритетом реализуется на основе кучи (например, двоичной), что даёт оценки операций \(\mathcal O(\log N)\) или даже \(\mathcal O(1)\) в среднем (в зависимости от типа кучи)
Ассоциативный массив (словарь)
Ассоциативный массив, также называемый map, таблица символов, словарь – это набор пар ключ-значение, где ключ и значение – произвольные типы данных. Можно рассматривать ассоциативный массив как обобщение обычного массива, в котором “индексом” могут выступать любые данные, а не только натуральные числа.
Существует два основных подхода к реализации словарей:
- на основе упорядоченных двоичных деревьев (деревьев поиска)
- на основе хэш-таблиц
Хэш-таблица
Хэш-таблица представляет из себя массив списков пар ключ-значение, где индекс массива определяется как \(h(k)\mod K,\) где \(h\) – хэш-функция, \(k\) – ключ, \(K\) – количество элементов массива.
Добавление/удаление элементов в таком случае \(\mathcal O(1),\) поиск элемента по ключу в среднем при достаточно большом \(K\) – \(\mathcal O(1),\) в худшем случае \(\mathcal O(N).\)
Средняя эффективность крайне чувствительна к выбору функции \(h:\) хорошая функция \(h\) имеет равномерное распределение значений по пространству возможных ключей (аргументов).
Как правило, хэш-функция каким-то образом “перемешивает” данные ключа для получения равномерного распределения.
Ситуация совпадения \(h(k_1)\) и \(h(k_2)\) при \(k_1\neq k_2\) называется коллизией. Коллизий стараются избежать.
В качестве метрики используется фактор загрузки \(α=\frac{N}{K}\). С ростом фактора загрузки, работа хэш-таблицы замедляется. Практические реализации часто перестраивают хэш-таблицу с увеличенным \(K\) при достижении некоторого заранее определённого \(α.\)
Дерево поиска
Дерево поиска представляет из себя двоичное дерево, где у каждого элемента “левые” потомки строго меньше данного, “правые” – не меньше данного.
Поиск элемента в двоичном дереве имеет сложность \(O(D),\) где \(D\) – глубина дерева. Глубина двоичного дерева составляет в лучшем случае \(\mathcal O(\log N),\) если дерево “сбалансировано”, т.е. дочерних элементов “слева” от каждого элемента примерно столько же, сколько “справа”, в худшем – \(O(N),\) если дерево по сути развёрнуто в список.
Практически, обычно используют самобалансирующиеся алгоритмы деревьев поиска, в частности АВЛ-дерево, красно-чёрное дерево.