Главная » Java, Структуры данных и алгоритмы » Вектор

0

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

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

Линейная последовательность элементов, в которой доступ к элементам осуществляется по их разряду, называется вектором. Разряд является простым и в то же время удобным средством, так как с его помощью определяется место добавления нового элемента или удаления элемента вектора. Например, можно указать разряд, который получит новый элемент после его добавления (например, insert at rank 2). Разряд также указывает элемент, который должен быть удален из вектора (например, remove the element at rank 2).

Пример 5.1. В приведенной ниже таблице представлены операции с использованием разрядов, выполняемые над изначально пустым вектором S.

Операция

Output

S

insert 7 at rank 0

-

(7)

insert 4 at rank 0

-

(4, 7)

return the element at rank 1

7

(4, 7)

insert 2 at rank 2

-

(4, 7, 2)

return the element at rank 3

«error»

(4, 7, 2)

move the element at rank 1

7

(4, 2)


Операция

Output

S

insert 5 at rank 1

-

(4, 5, 2)

insert 3 at rank 1

-

(4, 3, 5, 2)

insert 9 at rank 4

-

(4, 3, 5, 2, 9)

return the element at rank 2

5

(4, 3, 5, 2, 9)

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

По теме:

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