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

Алгоритм кодирования Хаффмана

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

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

Читать »

Полиморфизм

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

Дословно «полиморфизм» означает «много форм». В контексте объектно-ориентированного программирования полиморфизм обозначает спо- собность переменной объекта принимать различные формы В языках объектно-ориентированного программирования обращение к объектам осуществляется с помощью переменных ссылочного типа. Переменная ссылочного типа о содержит описание класса, объекты которого она может вызывать в рамках некоторого класса S. Это означает, что переменная о может обращаться к любому объекту класса Ту который расширяет класс S. Рассмотрим пример, когда и в классе Г, и в классе дописан метод а(). Алгоритм динамической компоновки при обращении к методу всегда начинает поиск с самого низшего, базового класса. Если переменная о вызывает объект класса Г, то при передаче сообщения о.а() будет выполнен метод а(), описанный в классе Г, а не в классе S. В данном случае говорят, что метод а() был переопределен из класса S в подкласс Т. В противном случае, если переменная о обращается к объекту класса S (отсутствующему в классе Т), то при обработке сообщения оя() программа выполнит метод а(), описанный в классе S. Преимущество полиморфизма заключается в том, что для корректного выполнения метода а() отправитель сообщения 0.а() не обязан знать, относится ли переменная о к экземпляру класса Гили класса S. Таким образом, переменная о типа ссылки на объект может быть полиморфной, то есть принимать различные формы в зависимости от особенностей классов вызываемых ею объектов. Такое свойство позволяет конкретному классу Г расширять общий класс 5, наследовать «общие» методы класса S, а также описывать методы, не указанные в классе S, применяемые для обработки специфических свойств объектов класса Т.

Читать »

Поисковые таблицы

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

Если имеется упорядоченный словарь D, то можно хранить его объекты в векторе S в неубывающем порядке значений ключей (см. рис. 8.7). Особо отметим, что S — вектор, а не обычная последовательность, так как упорядочение ключей в векторе S позволяет осуществлять поиск быстрее, чем применением связного списка. В дальнейшем будем ссылаться на такую векторную реализацию упорядоченного словаря D как на поисковую таблицу (look-up table).

Читать »

Каскадный метод

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

Алгоритм Хаффмана для осуществления оптимального кодирования является примером применения алгоритмической проектной модели под названием каскадный метод (greedy method). Эта модель применяется в задачах оптимизации, когда требуется некая структура с минимизацией или максимизацией определенного свойства.

Читать »

Пакеты Java как способ организаций классов

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

В языке Java используется общий и удобный способ организаций классов в Программы. Каждый открытый класс в Java сохраняется в отдельном файле с расширением Java, имя которого совпадает с именем класса. Таким образом, открытый класс SmartBoard сохраняется в файле SmartBoard.java. Совокупность связанных классов хранится в одном каталоге и образует пакет. Описание каждого файла пакета начинается строкой:

Читать »

Поразрядная сортировка

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

Одной из причин необходимости стабильной сортировки является возможность ее применения не только к упорядочению целых чисел. Предположим, необходимо отсортировать объекты пар (к, /), в которых к и / — целые числа в пределах [0, N — 1] для некоторого N>2. Для такой задачи естественно определять порядок этих объектов с помощью лексикографического (словарного) правила, в котором (к\, l\) < (ki, /2) при к\ < к2 или при к\ = ki и 1\ < /2 (п. 7.1.4). Это двухточечная версия лексикографической сравнительной функции, обычно применяемой к символьным строкам одинаковой длины (и легко преобразуемая для кортежей d-чисел при d > 2).

Читать »

Распределение памяти в Java

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

В п. 4.1.3 рассматривался способ размещения Java-машиной локальных переменных метода в его фрейме, находящемся в Java-стеке. Java-стек не единственный вид памяти, доступный для данных Java-nporpaMMbi.

Распределение памяти, Необходимой для хранения объектов, може^г осуществляться динамически во время выполнения метода благодаря использованию встроенного в Java бйератора new. Например, можно создать новый объект из 12 элементов класса Vector с помощью следующей команды:

Читать »

Квадратичная функция времени выполнения алгоритма

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

Решение указанной задачи представлено во фрагменте кода 4.16.

Алгоритм computeSpansl (Р):

Input: массив чисел Л содержащий п элементов.

Output: массив чисел S, содержащий п элементов, причем S[i] является максимальным целым значением к, где к< /+1, а Р [j ] < Р [/ ], при j = / — к + 1,…, /.

Читать »

Класс StringBuffer в Java

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

Основными методами класса StringBuffer являются следующие:

append(Q): возвращает S + Q, замещая S на S + Q. Input: String; Output: StringBuffer.

insert(/,Q): возвращает 5 c введенной в нее, начиная с индекса /, подстрокой Q, начинающейся с индекса / в S. Input: String; Output: StringBuffer.

Читать »

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

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

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

Читать »

Векторная структура для бинарных деревьев

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

В основу простейшей структуры представления бинарного дерева Т положен принцип нумерации узлов дерева. Каждый узел v дерева Гполу- чает порядковый номер p{v) в виде целого числа, который определяется следующим образом:

•    если v является корнем Г, то p(v) = 1;

Читать »

Приведение типов переменных в выражениях

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

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

Читать »

Сортировка, множества и выборка

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

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

Читать »

Дерево Терминология и основные свойства

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

Дерево (tree) Т — это набор узлов (node), хранящих элементы, состоящие в отношениях «отцы и дети», со следующими свойствами:

•                       Гимеет особый узел г, называемый корнем данного древа (root of Т)\

Читать »

Реализация векторного АТД с помощью массива

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

Самым очевидным способом реализации векторного АТД является его реализация на основе массива А, где A[i] содержит ссылку на элемент разряда /. Считаем длину N массива А достаточно большой, а для обозначения количества элементов вектора используем переменную п < N. Реализация методов векторного АТД достаточно проста. При выполнении операции elemAtRank(r) программа возвращает А[г]. Реализация методов insertAtRank(r,e) и removeAtRank(r) показана во фрагменте кода 5.1. Одна из операций (занимающая значительную часть времени) заключается в перемещении элементов таким образом, чтобы занятые ячейки массива образовывали неразрывную последовательность. Такое перемещение необходимо для соблюдения установленного нами правила о хранении элемента с разрядом / в А с индексом / (см. рис. 5.1 и упражнение М-5.10).

Читать »