Линейные структуры данных: массив, список, стек, очередь, дек. Способы представления, очереди над ними
Для представления последовательностей используются массивы и линейные связные
списковые структуры данных (с указателями). Используются также и смешанные способы представления на основе этих структур данных. Например, последовательность сложных (объемных) элементов может быть представлена вектором указателей на её элементы. Различные способы представления имеют различные сложностные характеристики по памяти и времени (в частности разные для разных операций) и могут оказаться более или менее приемлемыми в различных ситуациях.
Список базовых операций для (различного вида) последовательностей 17 [13 п.5.3.]:
§ size(): возвращает количество элементов в последовательности.
§ isEmpty(): возвращает логическое значение, подтверждающее, что
последовательность пуста.
§ atRank(r): возвращает позицию элемента с номером r.
§ rankOf(р): возвращает номер элемента в позиции р.
§ first(), last(): возвращает позицию «первого, последнего» элемента
последовательности.
§ before(р), after(р): возвращает позицию элемента последовательности, который
«предшествует элементу, следует за элементом» позиции р.
§ elemAtRank(r): возвращает элемент последовательности с номером r.
§ replaceAtRank(r,e): замещает элемент с номером r на е и возвращает замещаемый.
§ replaceElement(р,e): замещает элемент в позиции р на е и возвращает замещаемый.
§ insertAtRank(r,e): добавляет новый элемент e в качестве r-го элемента
последовательности.
§ insertFirst(e): вставляет новый элемент е в качестве первого элемента в
последовательности.
§ insertLast(e): вставляет новый элемент е в качестве последнего элемента в
последовательности.
§ insertBefore(р,e): вставляет новый элемент е перед позицией p последовательности.
§ insertAfter(р,e): вставляет новый элемент е после позиции p последовательности.
§ remove(р): удаляет из последовательности элемент в позиции р.
§ removeAtRank(r): удаляет из последовательности элемент с номером r.
17 В нижеследующем списке операций различаются понятия «номер» и «позиция» элемента в последовательности, об этом см. выше п.2.1 (о прямом доступе).
Для варианта с последовательным доступом к компонентам аргумент «позиция» (номер) становится не нужным, все операции привязываются к текущей позиции. В нижеследующей таблице представлены оценки времени (в худшем) для двух видов реализации этих операций - массивом и линейным связным списком.
Отметим, что массив – фактически статическая структура данных, а потому требует предварительного резервирования памяти, в то время как предварительная оценка максимального размера обрабатываемой последовательности для решаемой задачи может оказаться затруднительной. Кольцевой массив (circular array) – структура данных, основанная на техническом приеме, когда конец вектора как бы подклеивается к его началу. Последовательность хранится в таком векторе, начиная с некоторого (вообще говоря) промежуточного индекса в порядке возрастания индекса (с перескоком к нулевому на правой границе). Такой прием используется, когда операции добавления- удаления допускаются с обоих (или разных) концов последовательности, например в реализации очередей. Он позволяет повторно использовать освобождающийся сегмент вектора и при этом устранить необходимость сдвига элементов последовательности. Реализация связным списком позволяет выделять память динамически (в периоде выполнения) - столько и тогда, сколько и когда действительно требуется. Двусвязный список используется, когда необходим равноправный доступ, как к следующему, так и предшествующему элементам последовательности. Операции Массив (кольцевой)
Список (двусвязный)
size, isEmpty 0(1) 0(1)
atRank, rankOf, elemAtRank 0(1) 0(n)
first, last, before, after 0(1) 0(1)
replaceElement 0(1) 0(1)
replaceAtRank 0(1) 0(n)
insertAtRank, removeAtRank 0(n) 0(n)
insertFirst, insertLast 0(1) 0(1)
insertAfter, insertBefore 0(n) 0(1)
remove 0(n) 0(1)
В определенном смысле близким к понятию последовательность является понятие
«Разреженный массив» (Sparse Array) – массив в котором ненулевые элементы составляют лишь малую долю от общего числа элементов. Такие вектора и матрицы часто встречаются в практических задачах линейной алгебры. С одной стороны, с концептуальной точки зрения – это статические типы (и структуры) данных с классическим набором операций линейной алгебры. Но с другой стороны, количество (и места) нулей в таком векторе может изменяться – его можно трактовать как последовательность ненулевых элементов с индексом в качестве позиции элемента. Интересный и во многих отношениях полезный пример рассмотрен в классическом энциклопедическом труде «Искусство программирования» Кнут Д.Э. [14], задача «Осевое преобразование разреженной матрицы» т.1. п.2.2.6. «Массивы и ортогональные списки». В алгоритме решения этой задачи используется ортогонально (по строкам и столбцам) связное представление для разреженной матрицы, которое можно определить как базовый класс «Ортогональные списки» с парой индексов в качестве позиции элемента и операциями, аналогичными приведенным для последовательностей. А наследованием можно определить класс для разреженных матриц с классическим набором операций линейной алгебры. Отметим другой вариант трактовки разреженных массивов – как разновидность АТД Словарь с парой индексов в качестве ключа элемента. 45
Линейные структуры данных, массивы и линейные связные списковые структуры (с указателями), используются и для представления множеств (и наборов). Для представления множеств посредством характеристических 0-1-векторов необходимо иметь оценку мощности универсального множества (т.к. массив – статическая структура данных) и установить взаимно однозначное соответствие18 между элементами универсального множества и областью допустимых значений индексов массива-вектора. При таком представлении базовые операции для множеств реализуются с хорошими характеристиками по времени, но по памяти оно может оказаться расточительным, если универсальное множество очень большое, а используемые его подмножества относительно очень маленькие (получаем случай очень разреженного массива). Для реализации теоретико множественных операций (È, Ç, разность) потребуется полный просмотр такого вектора (размером, равным мощности универсального множества). Представление множеств линейными связными списками устраняет ограничения, свойственные статическим структурам данных, но при этом теряются возможности эффективного прямого доступа по индексу – операция Принадлежать (Найти элемент) реализуема только просмотром списка. Аналогичные характеристики для представления упорядоченных множеств массивами и линейными связными списками, причем появляются проблемы поддержания отношения порядка и соответствующие варианты решения этих проблем. Для представления более сложных АТД используются более сложно организованные
структуры данных.