В корзину
Купить в 1 клик
Бесплатная доставка Новой Почтой
Отправка на следующий рабочий день
Отправка на следующий рабочий день
Описание
2011г.
Количество страниц: 704
Второе издание одной из самых авторитетных книг Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре по программированию посвящено использованию структур данных и алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом разрабатываемое программное обеспечение будет использовать структуры данных. На четких и простых программных примерах автор объясняет эту сложную тему, предлагая читателям написать собственные программы и на практике освоить полученные знания. Рассматриваемые примеры написаны на языке Java, хотя для усвоения материала читателю не обязательно хорошо знать его — достаточно владеть любым языком программирования, например C++. Первая часть книги представляет собой введение в алгоритмизацию и структуры данных, а также содержит изложение основ объектно-ориентированного программирования. Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы. Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи.
Оглавление книги
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 Кнопка Zoom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 Просмотр разных узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 Эксперименты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446 Реализация дерева 2-3-4 на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 Класс DataItem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 Класс Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 Класс Tree234 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448 Класс Tree234App . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 Полный код программы tree234.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 Деревья 2-3-4 и красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 Преобразование деревьев 2-3-4 в красно-черные деревья . . . . . . . . . . . . 457 Эквивалентность операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 Эффективность деревьев 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 Скорость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 Затраты памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
Деревья 2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 Разбиение узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 Внешнее хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 Обращение к внешним данным . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 Последовательное хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469 B-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 Индексирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476 Сложные критерии поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 Сортировка внешних файлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Глава 11. Хеш-таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 Табельные номера как ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 Индексы как ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 Словарь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Коллизии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 Открытая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 Линейное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 Реализация хеш-таблицы с линейным пробированием на языке Java . . . 500 Квадратичное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 Двойное хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 Метод цепочек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 Приложение HashChain Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 Реализация метода цепочек на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . 520 Хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 Быстрые вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 Случайные ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 Неслучайные ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 Хеширование строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 Свертка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530 Эффективность хеширования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530 Открытая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530 Метод цепочек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 Сравнение открытой адресации с методом цепочек . . . . . . . . . . . . . . . . . . 534 Хеширование и внешнее хранение данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 Таблица файловых указателей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 Неполные блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 Полные блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536 Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540 Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
Глава 12. Пирамиды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 Приоритетные очереди, пирамиды и ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 Слабая упорядоченность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547 Условные перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548 Приложение Heap Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549 Заполнение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550 Изменение приоритета . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Количество страниц: 704
Второе издание одной из самых авторитетных книг Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре по программированию посвящено использованию структур данных и алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом разрабатываемое программное обеспечение будет использовать структуры данных. На четких и простых программных примерах автор объясняет эту сложную тему, предлагая читателям написать собственные программы и на практике освоить полученные знания. Рассматриваемые примеры написаны на языке Java, хотя для усвоения материала читателю не обязательно хорошо знать его — достаточно владеть любым языком программирования, например C++. Первая часть книги представляет собой введение в алгоритмизацию и структуры данных, а также содержит изложение основ объектно-ориентированного программирования. Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы. Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи.
Оглавление книги
Структуры данных и алгоритмы в 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 Кнопка Zoom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 Просмотр разных узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 Эксперименты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446 Реализация дерева 2-3-4 на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 Класс DataItem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 Класс Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 Класс Tree234 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448 Класс Tree234App . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 Полный код программы tree234.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 Деревья 2-3-4 и красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 Преобразование деревьев 2-3-4 в красно-черные деревья . . . . . . . . . . . . 457 Эквивалентность операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 Эффективность деревьев 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 Скорость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 Затраты памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
Деревья 2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 Разбиение узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 Внешнее хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 Обращение к внешним данным . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 Последовательное хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469 B-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 Индексирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476 Сложные критерии поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 Сортировка внешних файлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Глава 11. Хеш-таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 Табельные номера как ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 Индексы как ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 Словарь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Коллизии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 Открытая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 Линейное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 Реализация хеш-таблицы с линейным пробированием на языке Java . . . 500 Квадратичное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 Двойное хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 Метод цепочек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 Приложение HashChain Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 Реализация метода цепочек на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . 520 Хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 Быстрые вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 Случайные ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 Неслучайные ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 Хеширование строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 Свертка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530 Эффективность хеширования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530 Открытая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530 Метод цепочек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 Сравнение открытой адресации с методом цепочек . . . . . . . . . . . . . . . . . . 534 Хеширование и внешнее хранение данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 Таблица файловых указателей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 Неполные блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 Полные блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536 Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540 Программные проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
Глава 12. Пирамиды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 Приоритетные очереди, пирамиды и ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 Слабая упорядоченность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547 Условные перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548 Приложение Heap Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549 Заполнение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550 Изменение приоритета . . . . . . . . . . . . . . . . . . . . . . . . . . . . .