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

Реализация последовательности на основе массива

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

Предположим, требуется реализовать последовательность S, сохраняя каждый элемент е из Sb ячейке A[i] массива А. Ясно, что объект в позиции р содержит в качестве переменных индекс / и ссылку на массив А. С помощью метода element(р) получаем A[i]. Основной недостаток такого подхода состоит в том, что ссылки массива А не содержат ссылок на соответствующие им позиции. Таким образом, после выполнения операции insertFirst невозможно увеличение разрядов позиций S на 1 (поскольку позиции в последовательности описываются относительно соседних им позиций, а не их разрядов). Таким образом, при использовании массива для реализации общей последовательности следует избрать другой подход.

Читать »

Реализация хеш-таблиц на Java

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

Фрагменты кода 8.1—8.2 иллюстрируют большую часть класса LinearProbingHashTable, реализующего АТД «словарь» с применением хеш-таблицы и линейного зондирования для разрешения противоречий. Этот отрывок кода включает основные методы словаря (остальное — в упражнении М-8.9).

Читать »

Бинарное дерево поиска

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

Бинарные деревья представляют собой прекрасную структуру данных для хранения объектов упорядоченного словаря. Как отмечалось в п. 6.3.4, бинарным поисковым деревом является дерево Г, каждый составной узел v которого хранит объект (к,е) словаря D и

•                       |<слючи, хранящиеся в левой ветви v, меньше или равны к\

Читать »

Методы Java

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

Метод в Java соответствует понятиям «функция» и «процедура», используемым в других языках программирования высокого уровня, и представляет собой «куски» кода, которые могут вызываться для определенного объекта (некоторого класса). Методы принимают параметры в качестве аргументов, а выполняемые методом действия зависят от обрабатываемого объекта и Значений йерейайных параметров. В Java методы описываются в теле класса. Описание метода состоит из двух частей: сигнатуры, определяющей имя, число и типы параметров метода, и тела метода, в котором описываются выполняемые действия.

Читать »

Деревья

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

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

Читать »

Стандартный ввод и вывод Java

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

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

Читать »

Реализация стека с помощью массива

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

В этом параграфе рассмотрим реализацию стека путем хранения его элементов в виде массива. Так как длина массива должна быть задана при его создании, то одним из важных аспектов приводимой реализации стека является необходимость указания некоторого максимального размера N стека, например, N= 1000 элементов. Таким образом, полученный стек состоит из массива S, содержащего 7Vэлементов, плюс целочисленная переменная /, которая обозначает индекс последнего элемента массива S

Читать »

Реализация очередь с приоритетами на Java

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

Реализация на Java очереди с приоритетами с помощью пирамиды представлена фрагментами кода 7.5—7.7. Для обеспечения модульного принципа построения введем новую структуру данных под названием «пирамидальное дерево» (heap-tree), расширяющую свойства бинарного дерева и реализующую следующие дополнительные методы обновления:

Читать »

(а,Ь)-деревья

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

Для уменьшения воздействий различия времени доступа к внутренней и внешней памяти при поиске представим словарь с помощью многопроходного поискового дерева (раздел 9.3). При этом перейдем от структуры (2,4)-дерева к более универсальной структуре, известной как (я,6)-деревЬ.

Читать »

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

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

Во фрагменте кода 10.2 приведена Java-реализация алгоритма сортировки методом слияния. Метод mergeSort является рекурсивным и вызывает метод merge для слияния. Компаратор (см. п. 7.1.4) используется для определения относительного порядка двух элементов в методе merge.

Читать »

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

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

Одним изрозможных вариантов является реализация последовательности на основе двусвязного списка. В этом случае все методы АТД «список» реализуются таким образом, что время их выполнения равно 0(1). Методы же АТД «вектор» также могут быть реализованы с помощью . двусэяздого списка,, хотя’д ,м$нее.эффективно. В частности^ для эффективного выполнения методов списка (с использованием позиций в качестве указателей места доступа и обновления списка) не обязательно явно сохранять разряды элементов последовательности. Другими словами, для выполнения операции elemAtRank(r) необходимо переходить по ссылке от одного конца списка к другому, до тех пор пока не обнаружится узел, содержащий элемент с разрядом г. Чтобы несколько облегчить задачу, поиск можно начать с ближайшего конца последовательности, в результате чего время выполнения составит

Читать »

Абстрактные классы

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

содержат описания ттустых методов (то есть не содержащих тела Метода), Описания обычных методов и/или переменных. Таким образом, абстрактные классы занимают промежуточное положение между интерфейсами to полноценными классами. Подобно интерфейсам, нельзя сбзда^ь Экземпляр абстрактного класса. Реализация абстрактных методов класса происходит в его подклассе при условии, что этот подкласс не является абстрактным. Однако, как и обычные классы, абстрактный класс А может наследовать другой абстрактный класс, может порождать другие абстрактные и конкретные классы. В конечном итоге необходимо описать класс, который не является абстрактным и расширяет (наследует) абстрактный суперкласс, и именно в этом новом классе происходит реализация абстрактных методов. Таким образом, в абстрактных классах используется тип наследования — определение, хотя разрешены также конкретизация и расширение.

Читать »

Псевдокод

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

Зачастую программистам требуется создать описание алгоритма, предназначаемое только для человека. Подобные описания не являются программами, но вместе с тем они более структурированы, чем обычный текст. В частности, «высокоуровневые» описания сочетают естественный язык и распространенные структуры языка программирования, что делает их доступными и вместе с тем информативными. Такие описания способствуют проведению высокоуровневого анализа структуры данных или алгоритма. Подобные описания принято называть псевдокодом.

Читать »

Сортировка методом выбора и сортировка методом ввода

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

Обратимся к схеме PriorityQueueSort, приведенной в п. 7.1.2. В этой схеме несортированная последовательность S, имеющая п элементов, сортируется с помощью очереди Рв две стадии. На первой стадии осуществляется ввод элементов друг за другом, а на второй — элементы последовательно удаляются с помощью операции removeMin. В этом разделе рассматриваются два варианта такого алгоритма сортировки.

Читать »

Анализ средних и худших показателей

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

На примере метода аггауМах можно убедиться, что при определенном типе исходных данных алгоритм выполняется быстрее, чем при других. В данном случае можно попытаться выразить время выполнения алгоритма как среднее, взятое на основе результатов, полученных при всех возможных исходных данных. К сожалению, проведение анализа с точки зрения средних показателей является весьма проблематичным, так как в этом случае требуется определить вероятностное распределение входящего потока. На рис. 3.3 схематично представлена зависимость времени выполнения алгоритма от распределения входного потока данных. Например, если исходные данные только типа «А» или «D».

Читать »