год-2011
407 страницы
II-е издание одной из наиболее авторитетных книжек Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре по программированию посвящено применению структур данных и алгоритмов. Алгоритмы - основа программирования, определяющая, как разрабатываемое ПО будет применять структуры данных. На четких и простых программных примерах автор объясняет эту сложную тематику, предлагая читателям написать собственные утилиты и на практике освоить полученные познания. Рассматриваемые примеры написаны на языке Java, впрочем для усвоения материала читателю не непременно неплохо знать его - довольно владеть любым языком программирования, к примеру C++. I-я часть книжки представляет собою введение в алгоритмизацию и структуры данных, и содержит изложение основ объектно-ориентированного программирования. Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные перечни, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы. Приводятся рекомендации по применению алгоритмов и выбору какой-либо структуры данных в зависимости от поставленной задачи.
Оглавление книги
Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Второе издание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Дополнительные темы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
О чем эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Чем эта книга отличается от других . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Доступность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Приложения Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Примеры кода Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Для кого написана эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Что необходимо знать читателю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Необходимые программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Как организован материал книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Вперед! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Глава 1. Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Зачем нужны структуры данных и алгоритмы? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Хранение реальных данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Инструментарий программиста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Моделирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Обзор структур данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
База данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Запись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Поле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Ключ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Объектно-ориентированное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Недостатки процедурных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Объекты в двух словах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Создание объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Вызов методов объекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Пример объектно-ориентированной программы . . . . . . . . . . . . . . . . . . . . . . 33
Наследование и полиморфизм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Программотехника . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Java для программистов C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
В Java нет указателей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Ввод/вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Структуры данных библиотеки Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Глава 2. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Приложение Array Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Проблема дубликатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Не слишком быстро . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Поддержка массивов в Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Создание массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Обращение к элементам массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Инициализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Пример массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Деление программы на классы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Классы LowArray и LowArrayApp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Интерфейсы классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Не слишком удобно . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Кто чем занимается? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Пример highArray.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Удобство пользователя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Приложение Ordered Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Линейный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Двоичный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Реализация упорядоченного массива на языке Java . . . . . . . . . . . . . . . . . . . . . . . 67
Двоичный поиск с методом find() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Класс OrdArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Преимущества упорядоченных массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Логарифмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Формула . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Операция, обратная возведению в степень . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Хранение объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Класс Person . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Программа classDataArray.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
O-синтаксис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Вставка в неупорядоченный массив: постоянная сложность . . . . . . . . . . . . 80
Линейный поиск: сложность пропорциональна N . . . . . . . . . . . . . . . . . . . . . . 80
Двоичный поиск: сложность пропорциональна log(N) . . . . . . . . . . . . . . . . . . 80
Константа не нужна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Почему бы не использовать только массивы? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Глава 3. Простая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Как это делается? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Пузырьковая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Пример пузырьковой сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Приложение BubbleSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Реализация пузырьковой сортировки на языке Java . . . . . . . . . . . . . . . . . . . 94
Инварианты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Сложность пузырьковой сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Сортировка методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Пример сортировки методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Приложение SelectSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Реализация сортировки методом выбора на языке Java . . . . . . . . . . . . . . . 101
Инвариант . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Сложность сортировки методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Сортировка методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Пример сортировки методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Приложение InsertSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Сортировка 10 столбцов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Реализация сортировки методом вставки на языке Java . . . . . . . . . . . . . . 108
Инварианты сортировки методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Сложность сортировки методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Сортировка объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Реализация сортировки объектов на языке Java . . . . . . . . . . . . . . . . . . . . . 112
Лексикографические сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Устойчивость сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Сравнение простых алгоритмов сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Глава 4. Стеки и очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Другие структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Инструменты программиста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Ограничение доступа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Почтовая аналогия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Приложение Stack Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Реализация стека на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Пример использования стека № 1. Перестановка букв в слове . . . . . . . . . 129
Пример № 2. Поиск парных скобок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Эффективность стеков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Приложение Queue Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Циклическая очередь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Реализация очереди на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Эффективность очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Дек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Приоритетные очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Приложение The PriorityQ Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Реализация приоритетной очереди на языке Java . . . . . . . . . . . . . . . . . . . . 150
Эффективность приоритетных очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Разбор арифметических выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Постфиксная запись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
Преобразование инфиксной записи в постфиксную . . . . . . . . . . . . . . . . . . 154
Как мы вычисляем результаты инфиксных выражений . . . . . . . . . . . . . . . . 154
Вычисление результата постфиксного выражения . . . . . . . . . . . . . . . . . . . 170
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Глава 5. Связанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Строение связанного списка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Ссылки и базовые типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Отношения вместо конкретных позиций . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Приложение LinkList Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Простой связанный список . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Класс Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Класс LinkList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
Программа linkList.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Поиск и удаление заданных элементов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
Метод find() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Метод delete() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Другие методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Двусторонние списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Эффективность связанных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Абстрактные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Реализация стека на базе связанного списка . . . . . . . . . . . . . . . . . . . . . . . . 201
Реализация очереди на базе связанного списка . . . . . . . . . . . . . . . . . . . . . 204
Типы данных и абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
Списки ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Абстрактные типы данных как инструмент проектирования . . . . . . . . . . . . 209
Сортированные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
Реализация вставки элемента в сортированный список на языке Java . . 211
Программа sortedList.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Эффективность сортированных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Сортировка методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Двусвязные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Перебор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Программа doublyLinked.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Двусвязный список как база для построения дека . . . . . . . . . . . . . . . . . . . . 226
Итераторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Ссылка на элемент списка? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Итератор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Другие возможности итераторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Методы итераторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Программа interIterator.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
На что указывает итератор? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Метод atEnd() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Итеративные операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Другие методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
Глава 6. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Треугольные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Вычисление n-го треугольного числа в цикле . . . . . . . . . . . . . . . . . . . . . . . . 244
Вычисление n-го треугольного числа с применением рекурсии . . . . . . . . 245
Программа triangle.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Что реально происходит? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Характеристики рекурсивных методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
Насколько эффективна рекурсия? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Математическая индукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Факториал . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Анаграммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
Рекурсивный двоичный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
Замена цикла рекурсией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
Алгоритмы последовательного разделения . . . . . . . . . . . . . . . . . . . . . . . . . 262
Ханойская башня . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
Приложение Towers Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Перемещение поддеревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Рекурсивный алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Программа towers.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Слияние двух отсортированных массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
Приложение MergeSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
Программа mergeSort.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
Устранение рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
Интересные применения рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
Возведение числа в степень . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
Задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
Комбинации и выбор команды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
Глава 7. Нетривиальная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Сортировка Шелла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Сортировка методом вставок: слишком много копирования . . . . . . . . . . . 300
N-сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
Сокращение интервалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Приложение Shellsort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Реализация сортировки Шелла на языке Java . . . . . . . . . . . . . . . . . . . . . . . . 305
Другие интервальные последовательности . . . . . . . . . . . . . . . . . . . . . . . . . 307
Эффективность сортировки Шелла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
Разбиение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Приложение Partition Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Остановка и перестановка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
Алгоритм быстрой сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
Выбор опорного значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Приложение QuickSort1 Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
Вырожденное быстродействие O(N2
) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
Определение медианы по трем точкам . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
Обработка малых подмассивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
Устранение рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
Поразрядная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
Проектирование программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
Эффективность поразрядной сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
Глава 8. Двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
Для чего нужны двоичные деревья? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
Медленная вставка в упорядоченном массиве . . . . . . . . . . . . . . . . . . . . . . . 346
Медленный поиск в связанном списке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Деревья приходят на помощь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Что называется деревом? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Терминология . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
Аналогия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
Как работают двоичные деревья? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
Приложение Binary Tree Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
Представление деревьев в коде Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
Поиск узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
Поиск узла в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
Реализация поиска узла на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
Эффективность поиска по дереву . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
Вставка узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
Вставка узла в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
Реализация вставки на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
Обход дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
Симметричный обход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
Реализация обхода на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
Обход дерева из трех узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
Обход дерева в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
Симметричный и обратный обход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
Поиск минимума и максимума . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
Удаление узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
Случай 1. Удаляемый узел не имеет потомков . . . . . . . . . . . . . . . . . . . . . . . 368
Случай 2. Удаляемый узел имеет одного потомка . . . . . . . . . . . . . . . . . . . . 370
Случай 3. Удаляемый узел имеет двух потомков . . . . . . . . . . . . . . . . . . . . . . 372
Эффективность двоичных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
Представление дерева в виде массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
Дубликаты ключей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
Полный код программы tree.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
Код Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Коды символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Декодирование по дереву Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Построение дерева Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
Кодирование сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
Создание кода Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
Глава 9. Красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
Наш подход к изложению темы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
Концептуальное понимание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
Нисходящая вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
Сбалансированные и несбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . 404
Вырождение до O(N) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
Спасительный баланс . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
Характеристики красно-черного дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
Исправление нарушений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
Работа с приложением RBTree Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
Щелчок на узле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Кнопка Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Кнопка Ins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Кнопка Del . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Кнопка Flip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Кнопка RoL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Кнопка RoR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Кнопка R/B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Текстовые сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Где кнопка Find? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Эксперименты с приложением Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
Эксперимент 1. Вставка двух красных узлов . . . . . . . . . . . . . . . . . . . . . . . . . 411
Эксперимент 2. Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
Эксперимент 3. Переключение цветов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
Эксперимент 4. Несбалансированное дерево . . . . . . . . . . . . . . . . . . . . . . . 413
Эксперименты продолжаются . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
Красно-черные правила и сбалансированные деревья . . . . . . . . . . . . . . . . 414
Пустые потомки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
Простые повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
Переходящий узел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
Перемещения поддеревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
Люди и компьютеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
Вставка узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
Общая схема процесса вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
Переключения цветов при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . 420
Повороты после вставки узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
Повороты при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
Эффективность красно-черных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
Реализация красно-черного дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
Другие сбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
Глава 10. Деревья 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
Знакомство с деревьями 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
Почему деревья 2-3-4 так называются? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
Структура дерева 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
Поиск в дереве 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
Разбиение узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
Разбиение корневого узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
Разбиение при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
Приложение Tree234 Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
Кнопка Fill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
Кнопка Find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
Кнопка Ins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
