Главная » Java, Структуры данных и алгоритмы » Реализация векторного АТД с помощью массива

0

Самым очевидным способом реализации векторного АТД является его реализация на основе массива А, где A[i] содержит ссылку на элемент разряда /. Считаем длину N массива А достаточно большой, а для обозначения количества элементов вектора используем переменную п < N. Реализация методов векторного АТД достаточно проста. При выполнении операции elemAtRank(r) программа возвращает А[г]. Реализация методов insertAtRank(r,e) и removeAtRank(r) показана во фрагменте кода 5.1. Одна из операций (занимающая значительную часть времени) заключается в перемещении элементов таким образом, чтобы занятые ячейки массива образовывали неразрывную последовательность. Такое перемещение необходимо для соблюдения установленного нами правила о хранении элемента с разрядом / в А с индексом / (см. рис. 5.1 и упражнение М-5.10).

Алгоритм insert At Rank(r,e)

for / = л – 1, л – 2…………………………….. г do

A [i + 1] <– A[i\ (создает место для нового элемента) A[r\ <- е л <- л + 1

Алгоритм removeAtRank(r)

е <- A[r\ (е — временная переменная) for / = г, г + 1, л – 2 do

A[i\ А [/’ + 1] (замещает удаленный элемент) л <- л – 1 return е

Фрагмент кода 5,1. Методы реализации векторного АТД на основе массива

Рис. 5.1. Реализация вектора S, содержащего л элементов, на основе массива: (а) перемещение элементов вперед для вставки нового элемента с разрядом г, (Ь) перемещение элементов назад для заполнения разряда г удаленного элемента

В табл. 5.2 представлено время выполнения методов реализации вектора на основе массива. Методы isEmpty, size и elemAtRank выполняются за время 0(1), однако для выполнения методов вставки и удаления элементов может потребоваться гораздо больше времени. В частности, в худшем случае метод insertAtRank (г,е) будет выполняться за время 0(л). Худшими условиями для данного метода является ситуация, когда г = О, так как все существующие п элементов должны быть перемещены вперед. То же можно сказать и о методе remove At Rank(r), который выполняется за время О(п), так как в худшем случае г = 0, и ему необходимо переместить п – 1 элементов. В действительности, если предположить, что каждый разряд равновероятно может быть аргументом данных операций, среднее время выполнения есть 0(я), так как в среднем необходимо будет переместить я/2 элементов.

Метод

Время

size

0(1)

isEmpty()

0(1)

elemAtRank(a)

0(1)

replaceAtrank(r,e)

0(1)

insertAtRank(rfe)

0(n)

removeAtRank(a)

O(n)

Таблица 5.2. Выполнение вектора, реализованного на основе массива. Размер используемого пространства 0(N), где N — размер массива

При более детальном рассмотрении методов insertAtRank(r,e) и removeAtRank(r) можно определить, что время выполнения каждого из них равно 0(п- г + 1), так как в ходе исполнения программы перемещаются только элементы с разрядом г и выше. Таким образом, для добавления или удаления элемента в конце вектора с помощью методов insertAtRank(/i,e) и removeAtRank(fl – 1) необходимо время 0(1). Более того, такой вывод имеет интересные последствия при адаптации векторного АТД к дековому АТД, описанному в п. 5.1.1. Если в данном случае вектор реализован на основе массива, как показано выше, то методы insertLast и removeLast, описанные для дека, выполняются за время О (1) каждый. Но в то же время методы дека insertFirst и removeFirst выполняются за О (п) времени.

Действительно, можно реализовать вектор на основе массива таким образом, что время добавления или удаления элемента с разрядом 0 составит 0(1), то же относится и к операциям добавления и удаления в конце вектора. Для достижения этого следует отказаться от правила хранения элемента с разрядом / в ячейке массива с индексом / и применить круговую модель массива, как при реализации очереди в разделе 4.2. Подробности предлагается рассмотреть в упражнении 3-5.14.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии