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

Словари пакета java.util

Добавлено Дата: 14 December, 2011 категория: Java, Структуры данных и алгоритмы

Стандартный пакет java.util содержит и интерфейс АТД «словарь», называемый java.util.Map. Кроме того, этот пакет включает абстрактный класс java.util.Dictionary, который тоже соответствует описанному выше АТД «словарь». Но этот абстрактный класс считается устаревшим. И java.util.Map, и java.util.Dictionary сформулированы таким образом, что реализация класса требует уникальности ключей. Так, например, в интерфейсе java.util.Map отсутствует метод, соответствующий методу findAllElements(A;). За исключением требования уникальности ключей, интерфейс java.util.Map почти полностью соответствует вышеописанному АТД «словарь». И все же имеются два почти неуловимых отличия между описанным АТД и интерфейсом java.util.Map, о чем ниже.

Читать »

Локаторные методы очереди с приоритетами

Добавлено Дата: 14 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Читать »

Направленные графы

Добавлено Дата: 14 December, 2011 категория: Java, Структуры данных и алгоритмы

В этом разделе обсуждаются вопросы, специфические для направленных графов, известных также как диграфы (digraph), все пути которых строго направлены.

Достижимость

Одним из основополагающих вопросов теории направленных графов является понятие достижимости, определяющее место, которого можно достичь в направленном графе. Обходы в направленном графе выполняются только в направлении, определяемом направлениями маршрутов, то есть направлениями прохождения всех путей в процессе обхода. Имея узлы и и v в диграфе G, говорим, что и достигает v (и v достижим для и), если имеет направленный путь от и к v. Можно также сказать, что узел v достигает пути (w,z), если v достигает узла происхождения w данного пути.

Читать »

Наследование классов и полиморфизм

Добавлено Дата: 14 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Читать »

Реализация AVL-дерева на Java

Добавлено Дата: 13 December, 2011 категория: Java, Структуры данных и алгоритмы

Теперь перейдем к деталям реализации и проанализируем использование AVL-дерева Теп составными узлами для реализации упорядоченного словаря из п объектов. Алгоритмы ввода и удаления для Т требуют

Читать »

Итераторы абстрактное представление процесса просмотра коллекций элементов по порядку

Добавлено Дата: 13 December, 2011 категория: Java, Структуры данных и алгоритмы

Типичные вычисления, производимые над вектором, списком или последовательностью, связаны с просмотром всех элементов по порядку, например, для поиска определенного элемента.

Итератором является абстрактное представление процесса просмотра коллекций элементов по порядку. Итератор включает последовательность S, текущую позицию в S, а также способ перехода к следующей позиции S и превращение ее в текущую позицию. Таким образом, итератор расширяет понятие позиции, определенное в разделе 5.2. В действительности позицию можно рассматривать как итератор, остающийся на месте. Итератор инкапсулирует понятия «место» и «следующий» в коллекциях объектов.

Читать »

Структура списка смежности

Добавлено Дата: 13 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Читать »

Наследование классов

Добавлено Дата: 13 December, 2011 категория: Java, Структуры данных и алгоритмы

Во избежание избыточного повторения кода модульная и иерархическая структура объектно-ориентированного программирования позволяет осуществлять использование имеющегося кода благодаря технологии наследования. Эта технология предполагает создание общих классов, которые затем разделяются на частные, причем в этих частных классах автоматически повторяется код общего класса. Нацример, класс Number содержит классы Float, Integer и Long. В универсальном классе, называемом также базовый класс, или суперкласс, описываются «общие» переменные экземпляра класса, а также методы, применимые в самых различных ситуациях. Далее в классах, которые уточняют, расширяют или наследуют общий класс, повторно не указывается реализация общих методов, так как они автоматически наследуются из суперкласса. В конкретных классах описываются методы, характерные только для этого подкласса (который называют также производный класс).

Читать »

Операции с узлами списки

Добавлено Дата: 13 December, 2011 категория: Java, Структуры данных и алгоритмы

Для доступа к месту расположения элемента в списке может применяться не только понятие разряда. Если имеется список S, реализованный на основе однонаправленного или двусвязного списка, более удобным и эффективным является использование для определения места доступа и обновления списка .узлов вместо разрядов. Рассмотрим абстрактное понятие узла, описывающего определенное «место» в списке, не вдаваясь в детали реализации списка.

Читать »

Алгоритмы шаблонного сопоставления

Добавлено Дата: 12 December, 2011 категория: Java, Структуры данных и алгоритмы

В классической задаче сравнения с шаблоном (pattern matching) или шаблонного сопоставления строк имеется текстовая строка Т длиной п и шаблонная строка Р длиной m и определяется, является ли Р подстрокой Т. Понятие «сравнения» состоит в том, что существует подстрока строки Т, начинающаяся с индекса / и совпадающая с Р посимвольно, так что T[i] = Р[0], T[i+ 1] = Р[ 1], T[i + m- 1] = P[m- 1]. То есть Р— Г[/…/ + m – 1]. Следовательно, результатом алгоритма шаблонного согласования будет либо указание на то, что в Гнет Р, либо целое число, обозначающее индекс начала подстроки Р в Т. Это точное описание работы метода indexOf Java-ioiacca String. Можно также определить все индексы, с которых начинается совпадение подстроки из Т со строкой Р.

Читать »

Реализация очереди с приоритетами с помощью пирамиды

Добавлено Дата: 12 December, 2011 категория: Java, Структуры данных и алгоритмы

В этом разделе покажем способ реализации АТД «очередь с приоритетами» с помощью пирамиды. Представленная структура данных очереди состоит из следующих элементов (см. рис. 7.4):

•          heap (пирамида) — полное бинарное дерево Г, элементы которого хранятся в составных узлах и имеют ключи, отвечающие требованиям упорядоченного дерева. В рассматриваемом случае бинарное дерево Г реализовано вектором, как описано в п. 6.4.1. Для каждого составного узла v дерева допределен ключ элемента k{v), хранящийся в v;

Читать »

Применение динамического программирования для поиска наиболее длинной общей подпоследовательности

Добавлено Дата: 12 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Напомним, что для решения поставленной задачи имеются две строки X и У длиной пит каждая, и требуется определить самую длинную строку S, которая будет подпоследовательностью обеих строк одновременно. Так как Хи У состоят из символов, имеется естественное множество индексов, с помощью которых можно определить подзадачи — индексы в строке Хи в строке К

Читать »

Реализация бинарного поискового дерева на Java

Добавлено Дата: 12 December, 2011 категория: Java, Структуры данных и алгоритмы

Теперь опишем класс бинарного поискового дерева BinarySearchTree, хранящий пары «ключ-элемент» класса Item (показанного повторно во фрагменте кода 9.2) в качестве элементов, расположенных в позициях (узлах) его бинарного дерева. Код BinarySearchTree приведен во фрагментах кода 9.3—9.5. Заметим, что показанное бинарное дерево Г использует только интерфейс BinaryTree, а также содержит методы expandExternal и removeAboveExternal (см. п. 6.4.2).

Читать »

Направленные ацикличные графы

Добавлено Дата: 11 December, 2011 категория: Java, Структуры данных и алгоритмы

Направленные графы, не’имеющие направленных циклов, встречаются во многих приложениях. Подобный тип диграфа принято называть направленным ацикличным графом (directed acyclic graph), или, для краткости, DAG. Такие графы применяются:

•        при наследовании между классами в Java-nporpaMMax;

Читать »

Сочетания и компараторы

Добавлено Дата: 11 December, 2011 категория: Java, Структуры данных и алгоритмы

АТД «очередь с приоритетами» применяет две стандартные модели проектирования — сочетания и компараторы, которые и приводятся в этом подразделе.

Композиционная модель проектирования

Одной из этих моделей является композиционная модель (composition pattern). В ней объект е определяется как сочетание (композиция) других элементов. Эта модель используется в АТД «очередь с приоритетами» при необходимости представить объекты, хранимые в приоритетной очереди, в виде пары. Пара (к,е) представляет собой простейшее сочетание, состоящее из двух объектов. Для реализации данной концепции определим класс, который помещает два объекта в две свои переменные экземпляров и предоставляет метод доступа и обновления этих переменных. Во фрагменте кода 7.2 приведен пример реализации на Java парного шаблона применительно к парам «ключ-элемент», используемым в очереди с приоритетами. К другим видам сочетаний можнр отнести хроцкр, состоящие из, jpex объектов, четверки и, произвольные сочетания, способные хранить любое количество объектрв (например, с домощью последовательности).

Читать »