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

0

Концепция последовательности, в которой элементы следуют друг за другом, в программировании является фундаментальной. Последовательность встречается в построковом выводе кода компьютерной программы, где порядок команд определяет выполняемые программой действия. Последовательность сетевых пакетов составляет сообщение электронной почты, поскольку сообщение будет иметь смысл только при приеме пакетов в той же последовательности, в которой они отправлены. Последовательности представляют такие важцые отношения между объектами, как «следующий» и «предыдущий». Кроме того, последовательности зачастую используются для реализации других структур данных, то есть они представляют собой блоки, на которых базируется проектирование таких структур.

В главе представлены АТД «вектор», «список» и «последовательность», каждый из которых содержит коллекции линейно связанных элементов и обеспечивает методы доступа, добавления и удаления произвольных элементов. Различие между ними состоит в Способах описания. Можно рассматривать стеки, очереди и деки, описанные в главе 4, как ограниченные типы последовательностей, в которых Доступ возможен лишь к первому и/или последнему элементу. Важной характеристикой последовательности, рассмотренной на примере стеков? очередей и деков, является зависимость порядка элементов от операций, указанных для данного АТД, а не от значений элементов последовательности.

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

АТД «список» является объектно-ориентированным расширением конкретной структуры данных связного списка. Он описывает методы доступа и обновления, основанные на инкапсуляции узлов связного списка. Данные абстрактные узлы-объекты называются позициями, так как содержат ссылки на «места» хранения элементов, независимые от особенностей реализации списка.

АТД «последовательность» объединяет’вектор и список, что предоставляет удобство их использования при необходимости обобщенного типа структуры данных, который может быть реализован с помощью массива или связного списка. Однако покажем, что подобная обобщенность имеет и свои недостатки — рассмотрим два способа реализации последовательности (на основе массива или двусвязного списка) и степень их эффективности.

Работу с АТД «последовательность» покажем на примере реализации известного (хотя и неэффективного) алгоритма сортировки, известного как пузырьковая сортировка (bubble sorting). Кроме того, рассмотрим проектную модель Iterator (просмотр) и ее реализацию с помощью вектора и списка.

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

По теме:

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