Главная | Обратная связь | Поможем написать вашу работу!

Линейные структуры данных.

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

Список базовых операций для (различного вида) последовательностей [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.

Для варианта с последовательным доступом к компонентам аргумент «позиция» (номер) становится не нужным, все операции привязываются к текущей позиции.

Пусть —линейная последовательность из элементов. Каждый элемент последовательности имеет уникальный индекс, выраженный целым числом в интервале [0, — 1], равный числу элементов, предшествующих . Таким образом, определим, что номер элемента последовательности равен количеству элементов, находящихся перед , то есть номер первого элемента последовательности равен 0, а последнего — — 1. Данный метод соответствует принципу индексирования массивов в Java и других языках программирования (в том числе С и C++). В определении не требуется, чтобы реализованная в массиве последовательность сохраняла элемент с номером 0 в ячейке с индексом 0, хотя это один из возможных вариантов. Понятие номера позволяет обращаться к «индексу» элемента последовательности без учета конкретной реализации списка. Итак, если элемент является r-ным элементом последовательности, его разряд равен г— 1. Таким образом, если номер элемента равен r, то номер предыдущего элемента (если он существует) равен r — 1, а следующего элемента (если он существует) — r+ 1. Следует, однако, отметить, что номер элемента может изменяться при обновлении последовательности. Например, при добавлении нового элемента в начале последовательности номер каждого элемента увеличится на 1. Линейная последовательность элементов, в которой доступ к элементам осуществляется по их номеру, называется вектором. Номер является простым и в то же время удобным средством, так как с его помощью определяется место добавления нового элемента или удаления элемента вектора.

Отметим, что массив – фактически статическая структура данных, а потому требует предварительного резервирования памяти, в то время как предварительная оценка максимального размера обрабатываемой последовательности для решаемой задачи может оказаться затруднительной. Кольцевой массив (circular array) – структура данных, основанная на техническом приеме, когда конец вектора как бы подклеивается к его началу. Последовательность хранится в таком векторе, начиная с некоторого (вообще говоря) промежуточного индекса в порядке возрастания индекса (с перескоком к нулевому на правой границе). Такой прием используется, когда операции добавления-удаления допускаются с обоих (или разных) концов последовательности, например в реализации очередей. Он позволяет повторно использовать освобождающийся сегмент вектора и при этом устранить необходимость сдвига элементов последовательности.

Вектор является абстрактным типом данных (АТД), который поддерживает следующие основные методы:

§ elemAtRank(r): возвращает элемент последовательности с номером r.

§ replaceAtRank(r,s): замещает элемент с номером r на s и возвращает замещаемый.

§ insertAtRank(r,s): добавляет новый элемент s в качестве r-го элемента последовательности

§ removeAtRank(r): удаляет из последовательности элемент с номером r.

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

Предположим, имеются средства увеличения размера массива А, содержащего элементы вектора S. Безусловно, в Java (и других языках программирования) в действительности невозможно увеличить размер массива, его длина ограничена заданным значением , как отмечалось ранее. Вместо этого при возникновении переполнения, то есть при ,

и вызове метода insertAtRank выполняются следующие операции:

1) создается новый массив длиной ;

2) копируется A[i] в B[i], где / = 0,..., N- 1;

3) присваивается А = В, то есть используется В как массив, содержащий S.

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

C точки зрения эффективности приведенная стратегия замещения массивов кажется относительно медленной, так как для замещения одного массива при необходимости вставки элемента требуется O{n) времени, что не очень приемлемо. Тем не менее, следует отметить, что после замещения массива появляется возможность добавления новых элементов перед необходимостью нового замещения. В результате можно показать, что время выполнения операций, производимых над изначально пустым вектором, в действительности не так уж велико. Для краткости назовем добавление последнего элемента вектора операцией «проталкивания». Далее, используя модель проектирования, называемую амортизацией, покажем, что последовательность подобных операций над вектором, реализованным на основе расширяемого массива, может быть достаточно эффективной.

Утверждение 5.1. Пусть S— вектор, реализованный на основе расширяемого массива А, как было описано выше. Общее время выполнения последовательности п операций проталкивания в массиве S при условии, что S изначально пустой, а А имеет размер N= n, есть O(n).

Для доступа к месту расположения элемента в списке может применяться не только понятие разряда. Если имеется список S, реализованный на основе однонаправленного или двусвязного списка, более удобным и эффективным является использование для определения места доступа и обновления списка узлов вместо разрядов. Рассмотрим абстрактное понятие узла, описывающего определенное «место» в списке, не вдаваясь в детали реализации списка.

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

Каждая компонента в этой структуре состоит из двух ячеек памяти. Первая ячейка содержит сам элемент, вторая — указатель следующего элемента. Это можно реализовать в виде двух массивов, которые названы ИМЯ и СЛЕДУЮЩАЯ.

Если КОМПОНЕНТА — индекс в рассматриваемом массиве, то ИМЯ [КОМПОНЕНТА] — сам элемент, хранящийся там, а СЛЕДУЮЩАЯ [КОМПОНЕНТА]— индекс следующего элемента в списке (если такой элемент существует). Если КОМПОНЕНТА — индекс последнего элемента в этом списке, то СЛЕДУЮЩАЯ[КОМПОНЕНТА]=0.

procedure ВСТАВИТЬЭЛЕМЕНТ(СВОБОДНАЯ, ПОЗИЦИЯ):

begin

ИМЯ[СВОБОДНАЯ] ЭЛЕМЕНТ;

СЛЕДУЮЩАЯ[СВОБОДНАЯ] СЛЕДУЮЩАЯ[ПОЗИЦИЯ];

СЛЕДУЮЩАЯ [ПОЗИЦИЯ] СВОБОДНАЯ

end

Очевидным образом, время выполнения операции вставки не зависит от длины списка.

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

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

Операции	Массив (кольцевой)	Список (двусвязный)
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)

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

Списки можно сделать проходимыми в обоих направлениях, если добавить еще один массив, называемый ПРЕДЫДУЩАЯ. Значение ПРЕДЫДУЩАЯ[i] равно ячейке, в которой помещается тот элемент списка, который стоит непосредственно перед элементом из ячейки. Список такого рода называется дважды связанным. Из дважды связанного списка можно удалить элемент или вставить в него элемент, не зная ячейку, где находится предыдущий элемент.

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

Интересный и во многих отношениях полезный пример рассмотрен в классическом энциклопедическом труде «Искусство программирования» Кнут Д.Э. [14], задача «Осевое преобразование разреженной матрицы» т.1. п.2.2.6. «Массивы и ортогональные списки». В алгоритме решения этой задачи используется ортогонально (по строкам и столбцам) связное представление для разреженной матрицы, которое можно определить как базовый класс «Ортогональные списки» с парой индексов в качестве позиции элемента и операциями, аналогичными приведенным для последовательностей. А наследованием можно определить класс для разреженных матриц с классическим набором операций линейной алгебры.

Отметим другой вариант трактовки разреженных массивов – как разновидность АТД Словарь с парой индексов в качестве ключа элемента.

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

Со списком часто работают очень ограниченными приемами. Например, элементы добавляются или удаляются только на конце списка. Иными словами, элементы вставляются и удаляются по принципу "последний вошел — первый вышел". В этом случае список называют стеком или магазином.

Часто стек реализуется в виде одного массива. Например, список

Элем 1, Элем 2, Элем 3

можно было бы хранить в массиве ИМЯ, как показано на рисунке

Переменная ВЕРШИНА является указателем последнего элемента, добавленного к стеку. Чтобы добавить (ЗАТОЛКНУТЬ) новый элемент в стек, значение ВЕРШИНА увеличивают на 1, а затем помещают новый элемент в ИМЯ1ВЕРШИНА]. (Поскольку массив ИМЯ имеет конечную длину , перед попыткой вставить новый элемент следует проверить, что ВЕРШИНА < ) Чтобы удалить (ВЫТОЛКНУТЬ) элемент из вершины стека, надо просто уменьшить значение ВЕРШИНА на 1. Заметим, что не обязательно физически стирать элемент, удаляемый из стека. Чтобы узнать, пуст ли стек, достаточно проверить, не имеет ли ВЕРШИНА значение, меньшее нуля. Понятно, что время выполнения операций ЗАТОЛКНУТЬ и ВЫТОЛКНУТЬ и проверка пустоты не зависят от числа элементов в стеке.

Другой специальный вид списка — очередь, т. е. список, в который элементы всегда добавляются с одного (переднего) конца, а удаляются с другого. Как и стек, очередь можно реализовать одним массивом, как показано на рис. 2.5, где приведена очередь, содержащая список из элементов Р, Q, R, S, Т.

Реализация очереди в виде одного массива

Два указателя обозначают ячейки текущего переднего и заднего концов очереди. Чтобы добавить (ВПИСАТЬ) новый элемент к очереди, как и в случае стека, полагают ПЕРЕДНИЙ = ПЕРЕДНИЙ +1 и помещают новый элемент в ИМЯ1ПЕРЕДНИЙ]. Чтобы удалить (ВЫПИСАТЬ) элемент из очереди, заменяют ЗАДНИЙ на ЗАДНИЙ +1. Заметьте, что эта техника с точки зрения доступа к элементам основана на принципе "первый вошел — первый вышел".

Поскольку массив ИМЯ имеет конечную длину, скажем , указатели ПЕРЕДНИЙ и ЗАДНИЙ рано или поздно доберутся до его конца. Если длина списка, представленного этой очередью, никогда не превосходит , то можно трактовать ИМЯ[0] как элемент, следующий за элементом ИМЯ[n-1].

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

⇐ Предыдущая 4 5 6 7 8 9 101112 13 Следующая ⇒