Упорядоченные структуры данных

Ассоциативные массивы

Очередь и стек

Реализация многомерных массивов

Двумерные таблицы могут быть реализованы различным образом:

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

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

Реализация многомерных таблиц осуществляется аналогично.

Очередь - это последовательность элементов одного и того же типа, к которой добавление и удаление элементов происходит только с одного из концов.

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

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

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

Ограниченные очереди и стеки достаточно легко рализуются через вектор, неограниченные - через список.

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

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

Реализация ассоциативного массива рассмотрена в параграфе 3.4.

Другие струткуры данных рассмотрены в параграфах 3.4 - 3.6.

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

Наиболее простым решением является хранение данных, упорядоченных по значению. В этом случае, используя метод половинного деления (двоичного поиска) сложность алгоритма составляет log₂(N).

(Алгоритм половинного деления)

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

Чтобы данные были расположены упорядоченно, их требуется отсортировать.