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

Модель Adapter примеры программ

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

Зачастую существуют классы, обладающие схожими с другими классами возможностями и имеющие лишь незначительные отличия. Например, выше рассматривался класс, который выполняет операции вставки и удаления в каталог объектов Person, и необходимо создать каталог, который содержит только объекты Student. Безусловно, можно переписать всю программу обработки каталога объектов Student, однако это лишняя потеря сил и времени. Вместо этого можно использовать модель Adapter для адаптации функций существующего класса таким образом, чтобы они соответствовали функциям вновь создаваемого класса.

Читать »

Методы графа

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

Как АТД граф представляет собой позиционный контейнер элементов, хранящихся в узлах и путях графа, которые и являются позициями. Следовательно, элементы графа можно хранить либо в узлах, либо в путях, либо и там и там одновременно. С точки зрения реализации на Java это позволяет определить интерфейсы Vertex и Edge, каждый из которых расширяет интерфейс Position. Напомним, что позиция содержит метод element(), возвращающий хранимый в ней элемент.. Будем также использовать специализированные итераторы для узлов и путей, которые называются Vertoxlterator и Edgelterator.

Читать »

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

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

 

Рассмотрим использование однонаправленного связного списка для реализации стекового АТД. В принципе, вершина стека может находиться как в начале, так и в конце списка. С другой стороны, так как добавление и удаление элементов за время 0(1) возможно только в начале списка, именно здесь более эффективно определить вершину стека. Кроме того, для выполнения операции size за время 0(1) контролировать текущее число элементов будем с помощью переменной экземпляра. представлена фрагментом кода 4.11. Все методы интерфейса Stack выполняются за время 0(1).

Читать »

Утилиты пакета java.lang

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

Пакет java.lang включает базовые классы языка Java, а также несколько статических методов, и стандартные классы, содержащие различные полезные утилиты. Выше уже упоминались некоторые классы этого пакета, например, класс String и числовые классы (Integer, Float и другие). В этом пакете содержатся и исключения, представляющие собой классы, связанные с возникновением ошибок в программах Java. Более подробно исключения будут рассмотрены в разделе 2.3.

Читать »

Обработка текста

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

Обработка документов становится одной из наиболее важных функций компьютера. Компьютеры используются для редактирования, поиска, пересылки документов через Интернет, отображения на экране монитора и распечатки на принтере. Поиск и добавление информации в Сети становятся одной из важнейших сфер применения компьютеров, а значительная часть работы с документами состоит из обработки символьных строк и использования^ строковых шаблонов. Например, документы в формате HTML и XML изначально являются текстовыми, дополненными специальными метками, называемыми тэгами (tag), мультимедийного контекста. Чтобы найти требуемое в огромном объеме информации, имеющейся в Сети, необходимы значительные затраты на обработку текста.

Читать »

Объекты Java

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

В Java создание нового объекта определенного класса осуществляется использованием оператора new. Оператор new создает новый объект указанного класса и возвращает ссылку на него. Ниже приводится выражение, содержащее оператор new:

new <class_type>([param, param, …])

Читать »

Операторы организации выполнения алгоритма Java

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

В языке Java существуют операторы, позволяющие явно изменять последовательность выполнения программы.

Оператор return

Если при объявлении метода указывается тип возвращаемого значения void, то алгоритм возвращается в вызвавший его метод после последней строки своего кода либо По оператору return без аргументов. Если же при объявлении метода указывается тип возвращаемого значения, то метод представляет собой функцию, и в конце выполнения должен возвращать значение функции в качестве аргумента оператора return. Ниже представлен (верный) пример возвращения из функции:

Читать »

Сведения из области математики

Добавлено Дата: 10 January, 2012 категория: Java, Структуры данных и алгоритмы

Настоящее приложение содержит некоторые математические сведения, свойства и правила.

Логарифмическая и показательная функции

Логарифмическая функция определяется как

Полезные математические правила

Для определенного типа функций можно воспользоваться соответствующими правилами.

Читать »

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

Добавлено Дата: 10 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Представление обычных деревьев с помощью бинарных деревьев

Добавлено Дата: 10 January, 2012 категория: Java, Структуры данных и алгоритмы

Альтернативным способом представления обычного дерева Г является трансформация последнего в бинарное дерево Т’ (рис. 6.23). Допустим, что Т упорядочено или имеет произвольный порядок. Трансформация выполняется следующим образом:

•          для каждого узла и дерера Г существует составной узел и’ дерева Т\ ассоциируемого с и;

Читать »

Красно-черные деревья

Добавлено Дата: 9 January, 2012 категория: Java, Структуры данных и алгоритмы

Хотя AVL-деревья и (2,4)-деревья обладают рядом прекрасных свойств, тем не менее существуют приложения, для которых они не подходят. Например, AVL-деревьям требуется большое количество операций (ротаций) после удаления элемента, а (2,4)-деревьям приходится выполнять разделения или слияния, как после ввода или удаления элемента. В этом разделе рассматривается структура данных под названием крас- но-черные деревья, не имеющая этих недостатков, но требующая для сохранения сбалансированности 0(1) структурных изменений после каждого обновления.

Читать »

Массивы Java основные определения

Добавлено Дата: 9 January, 2012 категория: Java, Структуры данных и алгоритмы

Массив — это индексированная совокупность переменных одного типа. У каждой переменной или элемента массива существует свой индекс. Все элементы массива последовательно пронумерованы от 0 до N- 1, где N — длина массива, которая называется также размерностью массива. Если значение индекса не входит в диапазон от 0 до N- 1, говорят, что индекс находится вне пределов массива.

Читать »

Графы

Добавлено Дата: 8 January, 2012 категория: Java, Структуры данных и алгоритмы

В греческой мифологии описывается лабиринт, в котором был заключен получеловек-полубык по имени Минотавр. Лабиринт был настолько сложен, что ни человек, ни чудовище не могли из него выбраться. Ни один человек до греческого героя Тесея, воспользовавшегося помощью царской дочери Ариадны, не смог воплотить один из алгоритмов, обсуждаемых в этой главе. Тесей привязал нить к двери лабиринта и разматывал ее при движении по извилистым коридорам в поисках монстра. Очевидно, что Тесей разбирался в вопросах проектирования, так как после того, как он нашел и убил чудовище, смог вернуться обратно, воспользовавшись направлением, отмеченным нитью, прямо в объятья влюбленной Ариадны.

Читать »

Что такое время выполнения алгоритма?

Добавлено Дата: 8 January, 2012 категория: Java, Структуры данных и алгоритмы

Время выполнения алгоритма или операции над структурой данных зависит, как правило, от целого ряда факторов, вследствие чего* возникает вопрос — как следует проводить его измерение. При реализации алгоритма можно определить затраты времени, регистрируя действительное время, затраченное на выполнение алгоритма в каждом отдельном случае запуска с различными исходными данными. Подобные измерения должны проводиться с достаточной точностью с помощью системных вызовов, встроенных в язык или операционную систему, для которой написан данный алгоритм (например, метод System.currentTimeMillis() или вызовом исполняющей среды с возможностью профилирования). В общем, требуется определить, каким образом время выполнения программы зависит от количества исходных данных. Для решения этой задачи можно провести ряд экспериментов, в которых будет использовано различное количество исходных данных. Далее полученные результаты наглядно представляются с помощью графика, где каждый случай выполнения алгоритма обозначается с помощью точки, координата х которой равна размеру исходных данных п, а координата у — времени выполнения алгоритма t (см. рис. 3.1). Чтобы сделать определенные выводы на основе полученных экспериментов, необходимо использовать качественные образцы исходных данных и провести достаточно большое число экспериментов — что позволит определить некоторые статистические характеристики в отношении времени выполнения алгоритма.

Читать »

Реализация интерфейса Java

Добавлено Дата: 7 January, 2012 категория: Java, Структуры данных и алгоритмы

Основным структурным элементом Java, лежащим в основе ИПП, является интерфейс. Интерфейс представляет собой совокупность заголовков методов без их реализации и данных. Другими словами, методы интерфейса всегда пусты. Если в классе реализуется интерфейс, в нем реализуются и все методы, объявленные в интерфейсе. Таким образом, интерфейс поддерживает наследование типа конкретизации, при котором требуется указание всех наследуемых методов.

Читать »