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

Методы дерева

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

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

Читать »

Модели проектирования

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

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

Читать »

Связная структура для обычных деревьев

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

Описанная выше связная структура может применяться как для бинарных деревьев, так и для обычных деревьев. Поскольку при этом не оговаривается количество дочерних элементов узла v обычного дерева, то для их хранения вместо переменных экземпляров применим контейнер (к примеру, список или вектор). Схема такой структуры приводится на рис. 6.22.

Читать »

Поисковые деревья

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

Человеку свойственен выбор. Всегда хочется иметь несколько вариантов решения возникающих проблем, так как можно ознакомиться с преимуществами и последствиями каждого из них. Эта глава посвящена изучению разных способов решения проблем, обсуждавшихся в предыдущей главе — реализации упорядоченных словарей (глава 8). Конкретно исследуем несколько альтернативных структур данных на основе деревьев, используемых для реализации упорядоченных словарей.

Читать »

Восходящее построение пирамиды

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

Анализ алгоритма сортировки пирамиды показывает, что можно создать пирамиду для сортировки п пар «ключ-элемент» за 0(п log п) времени, выполняя п раз операцию insertltem, и затем использовать эту пирамиду для извлечения элементов в нужном порядке. Тем не менее в случае если заранее имеются все ключи, возможен альтернативный восходящий (bottom-up) метод построения, выполняющийся за О(п) времени.

Читать »

Кратчайшие маршруты

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

Допустим, G — взвешенный граф. Длина (вес) маршрута — это сумма длин (весов) каждого пути в Р. То есть если Р— (vo,vj), (v\,v2), (vfc-hvk)> то длина Р, обозначаемая как w(P), определяется как

Рис. 12.14. Взвешенный граф, узлы которого представляют крупнейшие аэропорты США, а пути — расстояния в милях. Данный граф имеет маршрут из JFK до LAX общим весом в 2777 (через ORD и DFW), и это минимальный вес маршрута от JFK до LAX во всем графе

Читать »

Trie

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

В предыдущих разделах представлены алгоритмы, скорость поиска в которых увеличивалась за счет предварительной обработки шаблона (вычисление функции отказа в КМП-алгоритме или функции last в БМ-алго- ритме). В этом разделе рассматривается другой подход, где поисковый алгоритм сразу обрабатывает исходный текст. Этот подход применяется в приложениях, в которых к одному и тому же тексту направляется серия запросов и, следовательно, предварительная обработка текста увеличивает скорость последующих запросов (например, поиск шаблона «Гамлет» на Web-сайте или поисковая машина для нахождения страниц, имеющих заголовок «Гамлет»).

Читать »

Написание программы на языке Java

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

Процесс написания программы на языке Java состоит из трех этапов:

1)                     проектирование,

2)                      кодирование,

Читать »

Подпроцессы Java*

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

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

Читать »

Сортировка слиянием

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

Читатель уже убедился, насколько удобно при описании алгоритмов пользоваться возможностями рекурсии (например, методики проходов дерева, представленные в главе 6). В этом разделе представляется методика сортировки под названием сортировка методом слияния, которая легко описывается с помощью рекурсии. Этот алгоритм тоже создан на основе проектной алгоритмической модели, названной «разделяй и властвуй», одновременно удобной и универсальной.

Читать »

Абстрактный тип данных «словарь»

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

Словарь хранит пары «ключ-элемент» (к,е), где к — ключ, а е — элемент. Для обеспечения полноты универсальности будем считать, что ключ и элемент могут быть представлены любыми типами объектов (см. рис. 8.1). Например, словарь сведений о студентах (имя, адрес, оценки по предметам) в качестве ключей может использовать номера студенческих билетов. В некоторых приложениях ключом может служить сам элемент. Например, в словаре простых чисел в качестве ключей (и, конечно, элементов) могут использоваться сами числа.

Читать »

Абстрактный тип данных «дерево»

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

Дерево — это абстрактный тип данных (АТД) для иерархического хранения элементов. За исключением элемента во главе дерева, каждый элемент структуры имеет родителя {parent element) и ноль или более дочерних элементов {children element). Для придания древовидной структуре большей наглядности ее элементы изображаются в виде овалов или прямоугольников, а связи между ними — в виде прямых линий (рис. 6.2). Обычно головной элемент дерева называется корнем (root% хотя он является самым верхним элементом структуры, а остальные расположены под ним (в отличие от обычного, биологического дерева).

Читать »

АТД «упорядоченный словарь»

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

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

Читать »

Java-реализация

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

Метод computeDailyHighSpan, представленный во фрагменте кода 4.18, является Java-реализацией алгоритма computeSpans2. Массив объектов класса Quote, представленный во фрагменте кода 4.19, используется методом computeDailyHighSpan для доступа к информации о курсе акций, а также для хранения вычисленных интервалов.

Читать »

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

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

Так как дек предусматривает возможность добавления и удаления объектов на обоих концах списка, его реализация на основе однонаправленного связного списка не может быть эффективной (см. п. 4.3.1). Однако существует тип связного списка, который обладает большими возможностями, в том числе добавлением и удалением элементов на обоих концах списка, которые выполняются за время 0(1), — двусвязный список. Узел двусвязного списка содержит две ссылки — ссылку к следующему узлу списка next и ссылку к предыдущему узлу списка prev. Java-реализация узлов двусвязного списка представлена фрагментом кода 4.13.

Читать »