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

Векторы, списки и последовательности

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

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

Читать »

Операторы if и switch

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

Алгоритмы управления в Java аналогичны соответствующим алгоритмам другкх развитых языков. В данном разделе подробнее рассмотрим основную структуру и синтаксис алгоритма управления, в том числе возвращаемые методом значения, операторы условия, операторы варианта, циклы и частные формы «переходов»* (операторы break и continue).

Читать »

Приведение типов в иерархии наследования

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

Переменные объектов (ссылочного типа) могут быть различных типов, но при объявлении переменных может быть указан только один тип (класс или интерфейс). Более того, объявленный тип переменной определяет, каким образом она используется и каким образом над ней выполняются определенные методы. Для предотвращения ошибок в Java используется технология строгого контроля типов, при которой переменная может быть только одного типа, а описание методов должно содержать тип переменных, необходимых для выполнения метода. Однако, несмотря на необходимость строгого соблюдения типа, иногда требуется проводить явное преобразование, или приведение типа переменной. В п. 1.3.3 уже рассматривалось приведение исходных типов переменных. В данном разделе рассмотрим преобразование типов переменных ссылочного типа.

Читать »

Интерфейс Stack

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

Класс Stack является одним из’«встроенных» классов Java, который входит в пакет java.util. Класс java.util.Stack является структурой данных объединяющей общие объекты Java, а также методы push(obj), popQ peek() (эквивалент top()), size() и empty() (эквивалент isEmptyO). Методь pop() и peek() могут генерировать исключение StackEmptyException, если при обращении к ним стек пуст. Хотя использование встроенного класа java.util.Stack является достаточно понятным, все же рассмотрим, каки\ образом изначально происходит создание и реализация стека.

Читать »

Простые приемы доказательства[1]

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

Иногда возникает необходимость доказать некие утверждения в отношении определенной структуры данных или алгоритма. Например, требуется продемонстрировать правильность и быстроту исполнения алгоритма. Для строгого доказательства утверждений необходимо использовать математический язык, который послужит доказательством или обоснованием высказываний. К счастью, существует несколько простых способов подобного доказательства.

Читать »

Важная модель проектирования — adapter

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

Методы класса DequeStack, показанного на фрагменте кода 4.15, демонстрируют рассмотренную в п. 2.6.1 важную модель проектирования — adapter. Эта модель использует модификации методов одного класса таким образом, чтобы они могли применяться при реализации методов другого класса. Существует несколько типичных ситуаций, при которых может понадобиться использование адаптера. Одна из них представлена в классе DequeStack, где необходимо конкретизировать общий класс и упростить его применение, изменив имена некоторых методов. В случае класса DequeStack адаптируется класс MyDeque, осуществляющий сложный интерфейс Deque, таким образом, чтобы он мог реализовывать более простой интерфейс Stack. Модель adapter может быть использована для конкретизации типов объектов, применяемых общим классом. Эта модель применима для описания класса IntegerArrayStack, адаптирующего класс ArrayStack (см. фрагменты кодов 4.4-т4.5) таким образом, чтобы стек содержал только объекты Integer. Далее класс IntegerArrayStack может применяться в таких методах, как метод reverse из фрагмента кода 4.6, что способствует сокращению количества вводимых исходных данных и уменьшает возможные сложности приведения типов, поскольку это действие будет выполняться внутри класса.

Читать »

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

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

Рассмотрим структуры данных, напоминающие очереди, но в которых добавление и удаление элементов может осуществляться как в начало, так и в конец. Подобный усовершенствованный вариант очереди называется двунаправленной очередью, или деком (deque — double-ended queue — очередь с двумя концами).

Читать »

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

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

Как видно на примере списков и бинарных деревьев, абстрактная позиционная информация в контейнере представляет собой достаточно мощное инструментальное средство. АТД «позиция», описанный в п. 5.2.2, позволяет обнаружить специфическое место,в контейнере, способное хранить элемент. Хранящийся в этом месте элемент может быть изменен, например, операцией swapElements, но само место не изменяется. В разделе 5.4 приводились способы применения позиций в реализациях алгоритмов упорядочивания. Существуют приложения, в которых необходимо отслеживать движение элементов внутри позиционного контейнера. Предположим, требуется удалить элемент е из последовательности S. Методы удаления из АТД «последовательность» требуют указать либо позицию, либо ранг е в S. Если после ввода е последовательность S модифицируется серией операций swapElements, то элемент е оказывается в позиции, отличной от той, в которую он был введен. Значит, чтобы удалить элемент е, понадобится найти е в последовательности S (затратив время, в крайнем случае пропорциональное размерности -5), что не всегда удобно. Естественно, предпочтительнее иметь механизм отслеживания позиций элементов в контейнере.

Читать »

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

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

В этом разделе рассмотрим, каким образом осуществляется реализация очереди с помощью массива Q, длина которого для хранения элементов очереди, например, N = 1000. Так как основной характеристикой АТД «очередь» является добавление и удаление объектов по принципу FIFO, необходимо определить способ наблюдения за началом и концом очереди.

Читать »

АТД «множество»

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

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

Читать »

Модель проектирования стандартных методов

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

Описанные выше методы прохода дерева по существу являются примерами любопытной модели объектно-ориентированного проектирования — шаблона стандартных методов (template method pattern). Эта модель- описывает обобщенный механизм обработки, который специальным образом может быть использован для конкретного применения путем переопределения соответствующих шагов.

Читать »

Алгоритм сортировки пузырьковым методом

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

Рассмотрим последовательность из п элементов, которые можно сравнивать между собой по некоторым отношениям (например, компании, сравниваемые по прибылям, государства, сравниваемые по численности населения, лексикографическое сравнение слов). Задача сортировки состоит в изменении порядка следования элементов таким образом, чтобы они находились в порядке убывания. , или пузырьковой сортировки (рис. 5.9) решает эту задачу, выполняя серии проходов внутри последовательности. При каждом проходе элементы просматриваются в направлении увеличения разряда, от разряда 0 до конца последовательности. В каждой позиции элемент сравнивается с соседним элементом, и, если их порядок неверен (то есть предыдущий элемент больше последующего), эти элементы меняются местами. Сортировка последовательности осуществляется при выполнении п таких проходов.

Читать »

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

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

Еще раз вернемся к пройденному материалу и проведем небольшой сравнительный анализ рассмотренных алгоритмов сортировки. Были представлены методы «bubble-sort», «insertion-sort» и «selection-sort», которые во всех случаях и при любых условиях выполняются за 0(п2) времени. Обсуждались также методы «heap-sort», «merge-sort» и «quick-sort» со временем выполнения 0(п log п). И наконец, показан специальный класс алгоритмов сортировки, а именно методы сегментной сортировки «bucket-sort» и поразрядной сортировки «radix-sort», выполняющиеся за линейное время для определенных типов ключей. Конечно, алгоритмы пузырьковой сортировки и выборочной сортировки не являются лучшим решением для приложений, поскольку даже в лучшем случае выполняются за 0(я2) времени. Но какой из алгоритмов лучше?

Читать »

Многопроходные поисковые деревья

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

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

Читать »

Компрессия (сжатие) текста

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

В этом разделе рассматривается еще одна из форм обработки текста — компрессия текста (сжатие). Допустим, имеется строка ^некоторого алфавита, например, ASCII или Unicode, и требуется эффективно перекодировать X в компактную бинарную строку Y (применяя только 0 и 1). Компрессия текста удобна тем, что можно пользоваться каналами с невысокой пропускной способностью типа модема или инфракрасного соединения, при этом сводя до Ьшнимума время передачи текста. Компрессия текста эффективна и в случае хранения наборов больших документов, чтобы разместить в хранилище с постоянным объемом наибольшее количество документов.

Читать »