Главная » Java, Структуры данных и алгоритмы » Абстрактный тип данных «вектор»

0

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

elemAtRank (г): возвращает элемент S с. разрядом г; если г < 0 или г > п – 1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число; Output: объект.

replaceAtRank (г,е): замещает объектом е элемент с разрядом г и возвращает замещаемый объект. Если г < 0 или г > п- 1, где п — текущее число элементов, выдается сообщение об ошибке.

Input: целое число г и объект е\ Output: объект.

insertAtRank (г,е): добавляет в S новый элемент е\ если г < 0 или г > я, где п — текущее число элементов, выдается сообщение об ошибке.

Input: целое число г и объект е\ Output: нет.

removeAtRank (г): удаляет из S элемент с разрядом г\ если г < 0 или г > п – 1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число; Output: объект.

Кроме того, вектор поддерживает стандартные методы size() и isEmptyO. Приведенное небольшое число методов вектора достаточно для описания адаптирующего класса (см. п. 4.4.4), с помощью которого реализуется дековый АТД. Одна из возможных адаптаций представлена в табл. 5.1 (см. упражнение М-5.13).

Реализация с помощью дека

Реализация с помощью вектора

 

size() isEmptyO

size() isEmptyO

 

Реализация с помощью дека

Реализация с помощью вектора

first()

elemAtRank(O)

last()

elemAtRank(size() – 1)

insertFirst(e)

insertAtRank(0,e)

insertLast(e)

insertAtRank(size(),e)

removeFirst()

removeAtRank(O)’

removeLast()

removeAtRank(size() – 1)

Таблица 5,1, Реализация дека с помощью вектора

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

По теме:

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