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

Пример программы Java

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

В данном разделе приводится пример простой Java-программы, которая демонстрирует многие из описанных выше конструкций. В примере имеются два класса: CreditCard, в котором описаны объекты — кредитные карточки, и второй класс — Test, который проверяет работу класса CreditCard. Объекты — кредитные карточки, описываемые в классе CreditCard, являются упрощенными вариантами настоящих кредитных карточек. В них указаны идентификационный номер, информация о владельце счета и банке, информация о текущем состоянии счета и кредитный лимит.

Читать »

Пирамида

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

Одной из наиболее эффективных реализаций очереди с приоритетами служит структура данных под названием пирамида (heap). Эта структура позволяет как вводить, так и удалять элементы в логарифмическом времени, что значительно быстрее по сравнению с реализациями с помощью последовательности, рассмотренными в разделе 7.2. Фундаментальным принципом, за счет которого достигается повышение эффективности, является отказ от идеи сортировки элементов и ключей в последовательности, вместо чего используется сортировка элементов и ключей в бинарном дереве.

Читать »

Ключи, приоритеты и полностью упорядоченные отношения

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

/

Приложения обычно требуют выполнения сравнений и расположения объектов согласно параметрам или свойствам, предписанным каждому из них и получившим название «ключей». Формально определим ключ как объект, предписываемый элементу в качестве его специфического атрибута, который можёт бытЬ!испоЛьзован для идентификации, ранжирования или взвешивания элемента! Заметив, что ключ обычно присваивается элементу либо пользователем, либо приложением; следовательно, ключ может представлять свойбтво, которым сам элемент в действительности может и не управлять![17]

Читать »

Индукция и инварианты цикла

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

В большинстве случаев в утверждениях о времени выполнения программы или используемом пространстве применяется целочисленный параметр п (обозначающий «размеры» задачи). Более того, подобные утверждения равносильны, как правило, утверждению типа «q(n) истинно для всех п> 1». Так как данное утверждение относится к бесконечному множеству чисел, невозможно провести исчерпывающее прямое доказательство.

Читать »

Реализация на основе расширяемого массива

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

Основной недостаток реализации вектора на основе простого массива, рассмотренной в п. 5.1.2, состоит в необходимости предварительного указания размера массива /V, то есть максимального числа элементов вектора. Если же действительное число элементов значительно меньше N, то при такой реализации бесполезно занимается место в памяти. Хуже того, если п окажется больше значения /V, то реализация приведет к сбою программы. К счастью, существует простой способ разрешения этой проблемы.

Читать »

Сортировка с помощью очереди с приоритетами

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

Другим не менее важным применением очереди с приоритетами является сортировка, когда п элементов из множества S могут сравниваться в соответствии с отношениями упорядочения, и требуется реорганизовать их в порядке возрастания (или, по крайней мере, в порядке неубывания). Алгоритм сортировки So помощью приоритетной очереди Q доста- 1 точно прост и состоит из двух шагов:

Читать »

Пирамидальная сортировка

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

Как показано выше, реализация очереди с приоритетами с помощью пирамиды имеет то преимущество, что все методы выполняются в логарифмическом времени и даже быстрее. Следовательно, такая реализация удовлетворяет требованиям приложений, где требуется быстрое выполнение всех методов очереди с приоритетами. Поэтому еще раз рассмотрим схему сортировки PriorityQueueSort (п. 7Л.2), в которой для сортировки последовательности S используется очередь Р.

Читать »

Вектор

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

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

Читать »

Tree Interface в Java

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

Абстрактный тип данных «дерево» (tree ADT) может использоваться для определения Java-интерфейсов, описывающих методы, реализуемые каждым деревом. Вместо того чтобы включать три описанные группы методов напрямую, вначале отделим относящиеся непосредственно к структуре дерева методы от общих методов, а затем разграничим методы доступа и запросов и методы обновления. Полученный в результате набор интерфейсов показан фрагментами кода 6.1-6.2. Кроме того, интерфейс InspectableContainer расширен (см. рис. 5.11) дополнительным методом isEmpty(). Однако заметим, что, согласно приведенному определению дерева, этот метод должен всегда возвращать «false», поскольку дерево не может быть пустым (имеется хотя бы один узел — корень).

Читать »

Тестирование и отладка Java

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

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

Тестирование

Читать »

Skip-список

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

Интересной разновидностью структуры данных эффективной реализации АТД «упорядоченный словарь» является skip^cnucoK (skip list). Эта структура данных организует объекты в произвольном порядке таким

образом, что поиск и обновление в среднем выполняются за 0(log п) времени, где п — количество объектов словаря. Интересно, что понятие усредненной временной сложности, используемое здесь, не зависит от возможного распределения ключей при вводе. Наоборот, оно продиктовано использованием генераторов случайных чисел в реализации процесса ввода, чтрбы облегчить процесс принятия решения о месте вставки нового объекта. Время выполнения в этом случае будет равно среднему значению времени выполнения ввода любых случайных чисел, используемых в качестве входных объектов.

Читать »

Средства анализа Java

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

В одной старинной истории рассказывается о том, как известного математика Архимеда попросили определить, была ли полученная царем корона из чистого золота, или в ней имелись примеси серебра, как сообщил доносчик. Способ определить состав короны Архимед понял, когда принимал ванну. Он заметил, что количество воды, которое выливается из ванной при погружении в нее, пропорционально массе его тела. Поняв сущность этого явления, он выскочил из ванной и голый побежал по улицам города с криками «Эврика, эврика!». Таким образом Архимед открыл средство анализа (вытеснение), которое в сочетании с обычными весами позволило определить подлинность новой короны царя. Однако это открытие оказалось губительным для мастера, который отливал эту корону, так как анализ Архимеда показал, что корона вытесняет больше воды, чем слиток чистого золота той же массы, что и явилось доказательством наличия примесей.

Читать »

Строковые операции

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

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

Читать »

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

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

Предположим, необходимо создать АТД «список» с помощью дважды связного списка. В самом простом случае узлы двусвязного списка будут соответствовать позиции АТД. Другими словами, каждый узел реализует интерфейс Position и, следовательно, содержит метод element(), который возвращает элемент, хранящийся в данном узле. Таким образом, сами узлы выступают в качестве позиций, имея двойственный характер: с одной стороны, это внутренние узлы связного списка, а с другой — традиционные позиции. Таким образом, для каждого узла v можно задать переменные next и prev, осуществляющие обращения соответственно к последующему и предыдущему узлам (которые могут быть просто сигнальными узлами, обозначающими начало или конец списка). Далее с точки зрения позиции в S «откроем» позицию р, чтобы найти узел v. Эта операция выполняется с помощью приведения типа позиции к узлу. Поскольку действия осуществляются с узлами, можно выполнить метод before(/?), возвращая v.prev (при условии, что v.prev не является головным сигнальным узлом, иначе это приведет к ошибке). Таким образом, позиции списка при реализации двусвязным списком используют преимущества объектно-ориентированного программирования, причем для этого не требуются дополнительные затраты места и времени. Кроме того, данный подход позволяет скрыть детали реализации, что обеспечивает возможность неоднократного использования кода, так как пользователь не будет знать, что позиционные объекты, передаваемые и возвращаемые как параметры, в действительности являются объектами узлов.

Читать »

Краткий обзор математических понятий

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

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

Читать »