Главная » Java, Структуры данных и алгоритмы » Классы java.util.ArrayList и java.util.Vector

0

являются встроенными классами Java, которые обладают аналогичными вышеописанным функциями АТД «вектор». Более того, стандартная реализация этих классов осуществляется на основе расширяемых массивов, как описано в предыдущем разделе. Соответствие между этими классами и АТД «вектор» представлено в табл. 5.3. Обратите внимание, что ме ч оды классов java.util имеют короткие имена, что ускоряет процесс кодирования, хотя и уменьшает читабельность и понятность, поскольку, чтобы понять, каким образом осуществляется доступ и обновление вектора, необходима вся сигнатура метода, а не только его имя.

Метод АТД вектора

Метод java util Vector

size(),isEmpty()

size(),isEmpty()

elemAtRank(r)

get (r)

replaceAtrank(r,e)

set (r,e)

insertAtRank (r,e)

add (r,e)

removeAtRank(r)

remove (r)

Таблица 5.3. Соответствие между аналогичными методами АТД «вектор» и класса java.util.Vector. Соответствующие методы класса java util ArrayList аналогичны методам класса java.util.Vector

Кроме того, Java-классы java.util.ArrayList и java.util.Vector обладают дополнительными характеристиками и методами, не рассматривавшимися для упрощенного АТД «вектор». Например, класс java.util.Vector содержит целочисленный параметр capacitylncrement, который определяет увеличение исходного расширяемого массива. Если значение параметра capacitylncrement равно 0, то длина массива удваивается (как в классе ArrayVector). Если же данный параметр является положительным числом к, то длина массива увеличивается на к ячеек. Данный параметр следует использовать осторожно, в большинстве приложений оптимальное значение параметра capacitylncrement равно 0, как показано в утверждении ниже.

Утверждение 5.2. Для пустого объекта класса java util.Vector с определенным значением переменной capacitylncrement на выполнение последовательности операций проталкивания над данным вектором потребуется времяП(л2).

Доказательство: пусть с > О является значением capacitylncrement и пусть со > 0 обозначает первоначальную длину массива. Переполнение массива может возникнуть в случае, если операция add выполняется, когда текущее число элементов таблицы равно со + /с, при / = 0,т – 1, где т =л[(п – с0) / Согласно утверждению 3.4, общее время решения проблемы переполнения пропорционально

что составляет П (п2). Таким образом, для выполнения п операций проталкивания требуется время D. (п2).

На рис. 5.4 приведено сравнение времени выполнения операции проталкивания над изначально пустым объектом класса java.util.Vector при двух значениях capacitylncrement.

Рис. 5.4. Время выполнения операций add над объектом класса java.util.Vector при значениях capacitylncrement (а) = 0 и (Ь) = 3

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

По теме:

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