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

0

Предположим, требуется реализовать последовательность S, сохраняя каждый элемент е из Sb ячейке A[i] массива А. Ясно, что объект в позиции р содержит в качестве переменных индекс / и ссылку на массив А. С помощью метода element(р) получаем A[i]. Основной недостаток такого подхода состоит в том, что ссылки массива А не содержат ссылок на соответствующие им позиции. Таким образом, после выполнения операции insertFirst невозможно увеличение разрядов позиций S на 1 (поскольку позиции в последовательности описываются относительно соседних им позиций, а не их разрядов). Таким образом, при использовании массива для реализации общей последовательности следует избрать другой подход.

Рассмотрим вариант решения, при котором вместо хранения элементов S в каждой ячейке массива А поместим новый позиционный объект. Этот новый объект позиции р содержит индекс / и элемент е, связанный с р. При такой структуре данных (рис. 5.8) массив легко просматривается и можно изменять переменную / для тех позиций, разряд которых изменяется в результате операций добавления или удаления.

Рис. 5.8. Реализация АТД «последовательность» на основе массива

При реализации последовательности на основе массива время выполнения методов insertFirst, insertBefore* insertAfter и remove есть 0{п), так как перемещаются позиции объектов для освобождения места под новую позицию или заполнения места удаленной позиции (как и в случае методов вставки и удаления с использованием разрядов). Для выполнения всех остальных методов, применяющих позиции, требуется время 0(1).

При этом возможно использование кругового варианта массива, как и при реализации очереди (см. п. 4.2.2). После небольших изменений метод insertFirst будет выполняться за время 0(1). Но методы insertBefore, insertAfter и remove будут выполняться за время 0{п). В этом случае наибольшие затраты времени будут, если разряд вставляемого или удаляемого элемента равен \ п / 2J.

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

По теме:

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