Алгоритмы - это основа программирования, определяющая, каким образом разрабатываемое программное обеспечение будет использовать структуры данных.
На четких и простых программных примерах автор объясняет эту сложную тему, предлагая читателям написать собственные программы и на практике освоить полученные знания. Рассматриваемые примеры написаны на языке Java, хотя для усвоения материала читателю не обязательно хорошо знать его - достаточно владеть любым языком программирования, например C++.
Первая часть книги представляет собой введение в алгоритмизацию и структуры данных, а также содержит изложение основ объектно-ориентированного программирования.
Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы.
Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи.
Оглавление книги Структуры данных и алгоритмы java:
Введение
Второе издание
Дополнительные темы
Вопросы
Упражнения
Программные проекты
О чем эта книга
Чем эта книга отличается от других
Доступность
Приложения Workshop
Примеры кода Java
Для кого написана эта книга
Что необходимо знать читателю
Необходимые программы
Как организован материал книги
Вперед!
Глава 1. Общие сведения
Зачем нужны структуры данных и алгоритмы?
Хранение реальных данных
Инструментарий программиста
Моделирование
Обзор структур данных
Алгоритмы
Определения
База данных
Запись
Поле
Ключ
Объектно-ориентированное программирование
Недостатки процедурных языков
Объекты в двух словах
Создание объектов
Вызов методов объекта
Пример объектно-ориентированной программы
Наследование и полиморфизм
Программотехника
Java для программистов C++
В Java нет указателей
Ввод/вывод
Вывод
Структуры данных библиотеки Java
Итоги
Вопросы
Глава 2. Массивы
Приложение Array Workshop
Вставка
Поиск
Удаление
Проблема дубликатов
Не слишком быстро
Поддержка массивов в Java
Создание массива
Обращение к элементам массива
Инициализация
Пример массива
Деление программы на классы
Классы LowArray и LowArrayApp
Интерфейсы классов
Не слишком удобно
Кто чем занимается?
Пример highArray..java
Удобство пользователя
Абстракция
Приложение Ordered Workshop
Линейный поиск
Двоичный поиск
Реализация упорядоченного массива на языке Java
Двоичный поиск с методом find()
Класс OrdArray
Преимущества упорядоченных массивов
Логарифмы
Формула
Операция, обратная возведению в степень
Хранение объектов
Класс Person
Программа classDataArray..java
O-синтаксис
Вставка в неупорядоченный массив: постоянная сложность
Линейный поиск: сложность пропорциональна N
Двоичный поиск: сложность пропорциональна log(N)
Константа не нужна
Почему бы не использовать только массивы?
Итоги
Вопросы
Упражнения
Программные проекты
Глава 3.. Простая сортировка.
Как это делается?
Пузырьковая сортировка
Пример пузырьковой сортировки
Приложение BubbleSort Workshop
Реализация пузырьковой сортировки на языке Java
Инварианты
Сложность пузырьковой сортировки
Сортировка методом выбора
Пример сортировки методом выбора
Приложение SelectSort Workshop
Реализация сортировки методом выбора на языке Java
Инвариант103
Сложность сортировки методом выбора
Сортировка методом вставки
Пример сортировки методом вставки
Приложение InsertSort Workshop
Сортировка 10 столбцов
Реализация сортировки методом вставки на языке Java
Инварианты сортировки методом вставки
Сложность сортировки методом вставки
Сортировка объектов
Реализация сортировки объектов на языке Java
Лексикографические сравнения
Устойчивость сортировки
Сравнение простых алгоритмов сортировки
Итоги
Вопросы
Упражнения
Программные проекты
Глава 4. Стеки и очереди
Другие структуры
Инструменты программиста
Ограничение доступа
Абстракция
Стеки
Почтовая аналогия
Приложение Stack Workshop
Реализация стека на языке Java
Пример использования стека № 1.. Перестановка букв в слове
Пример № 2.. Поиск парных скобок
Эффективность стеков
Очереди
Приложение Queue Workshop
Циклическая очередь
Реализация очереди на языке Java
Эффективность очередей
Дек
Приоритетные очереди
Приложение The PriorityQ Workshop
Реализация приоритетной очереди на языке Java
Эффективность приоритетных очередей
Разбор арифметических выражений
Постфиксная запись
Преобразование инфиксной записи в постфиксную
Как мы вычисляем результаты инфиксных выражений
Вычисление результата постфиксного выражения
Итоги
Вопросы
Упражнения
Программные проекты
Глава 5. Связанные списки
Строение связанного списка
Ссылки и базовые типы
Отношения вместо конкретных позиций
Приложение LinkList Workshop
Вставка
Поиск
Удаление
Простой связанный список
Класс Link
Класс LinkList
Программа linkList..java
Поиск и удаление заданных элементов
Метод find()
Метод delete()
Другие методы
Двусторонние списки
Эффективность связанных списков
Абстрактные типы данных
Реализация стека на базе связанного списка
Реализация очереди на базе связанного списка
Типы данных и абстракция
Списки ADT
Абстрактные типы данных как инструмент проектирования
Сортированные списки
Реализация вставки элемента в сортированный список на языке Java
Программа sortedList..java
Эффективность сортированных списков
Сортировка методом вставки
Двусвязные списки
Перебор
Вставка
Удаление
Программа doublyLinked..java
Двусвязный список как база для построения дека
Итераторы
Ссылка на элемент списка?
Итератор
Другие возможности итераторов
Методы итераторов
Программа interIterator..java
На что указывает итератор?
Метод atEnd()
Итеративные операции
Другие методы
Итоги
Вопросы
Упражнения
Программные проекты
Глава 6. Рекурсия
Треугольные числа
Вычисление n-го треугольного числа в цикле
Вычисление n-го треугольного числа с применением рекурсии
Программа triangle..java
Что реально происходит?
Характеристики рекурсивных методов
Насколько эффективна рекурсия?
Математическая индукция
Факториал
Анаграммы
Рекурсивный двоичный поиск
Замена цикла рекурсией
Алгоритмы последовательного разделения
Ханойская башня
Приложение Towers Workshop
Перемещение поддеревьев
Рекурсивный алгоритм
Программа towers..java
Сортировка слиянием
Слияние двух отсортированных массивов
Сортировка слиянием
Приложение MergeSort Workshop
Программа mergeSort..java
Устранение рекурсии
Что дальше?
Интересные применения рекурсии
Возведение числа в степень
Задача о рюкзаке
Комбинации и выбор команды
Итоги
Вопросы
Упражнения
Программные проекты
Глава 7. Нетривиальная сортировка
Сортировка Шелла
Сортировка методом вставок: слишком много копирования
N-сортировка
Сокращение интервалов
Приложение Shellsort Workshop
Реализация сортировки Шелла на языке Java
Другие интервальные последовательности
Эффективность сортировки Шелла
Разбиение
Приложение Partition Workshop
Остановка и перестановка
Быстрая сортировка
Алгоритм быстрой сортировки
Выбор опорного значения
Приложение QuickSort1 Workshop
Вырожденное быстродействие O(N2)
Определение медианы по трем точкам
Обработка малых подмассивов
Устранение рекурсии
Поразрядная сортировка
Проектирование программы
Эффективность поразрядной сортировки
Итоги
Вопросы
Упражнения
Программные проекты
Глава 8. Двоичные деревья
Для чего нужны двоичные деревья?
Медленная вставка в упорядоченном массиве
Медленный поиск в связанном списке
Деревья приходят на помощь
Что называется деревом?
Терминология
Аналогия
Как работают двоичные деревья?
Приложение Binary Tree Workshop
Представление деревьев в коде Java
Поиск узла
Поиск узла в приложении Workshop
Реализация поиска узла на языке Java
Эффективность поиска по дереву
Вставка узла
Вставка узла в приложении Workshop
Реализация вставки на языке Java
Обход дерева
Симметричный обход
Реализация обхода на языке Java
Обход дерева из трех узлов
Обход дерева в приложении Workshop
Симметричный и обратный обход
Поиск минимума и максимума
Удаление узла
Случай 1. Удаляемый узел не имеет потомков
Случай 2. Удаляемый узел имеет одного потомка
Случай 3. Удаляемый узел имеет двух потомков
Эффективность двоичных деревьев
Представление дерева в виде массива
Дубликаты ключей
Полный код программы tree..java
Код Хаффмана
Коды символов
Декодирование по дереву Хаффмана
Построение дерева Хаффмана
Кодирование сообщения
Создание кода Хаффмана
Итоги
Вопросы
Упражнения
Программные проекты
Глава 9. Красно-черные деревья
Наш подход к изложению темы
Концептуальное понимание
Нисходящая вставка
Сбалансированные и несбалансированные деревья
Вырождение до O(N)
Спасительный баланс
Характеристики красно-черного дерева
Исправление нарушений
Работа с приложением RBTree Workshop
Щелчок на узле
Кнопка Start
Кнопка Ins
Кнопка Del
Кнопка Flip
Кнопка RoL
Кнопка RoR
Кнопка R/B
Текстовые сообщения
Где кнопка Find?
Эксперименты с приложением Workshop
Эксперимент 1. Вставка двух красных узлов
Эксперимент 2. Повороты
Эксперимент 3. Переключение цветов
Эксперимент 4. Несбалансированное дерево
Эксперименты продолжаются
Красно-черные правила и сбалансированные деревья
Пустые потомки
Повороты
Простые повороты
Переходящий узел
Перемещения поддеревьев
Люди и компьютеры
Вставка узла
Общая схема процесса вставки
Переключения цветов при перемещении вниз
Повороты после вставки узла
Повороты при перемещении вниз
Удаление
Эффективность красно-черных деревьев
Реализация красно-черного дерева
Другие сбалансированные деревья
Итоги
Вопросы
Упражнения
Глава 10. Деревья 2-3-4
Знакомство с деревьями 2-3-4
Почему деревья 2-3-4 так называются?
Структура дерева 2-3-4
Поиск в дереве 2-3-4
Вставка
Разбиение узлов
Разбиение корневого узла
Разбиение при перемещении вниз
Приложение Tree2 Workshop
Кнопка Fill
Кнопка Find
Кнопка Ins
Кнопка Zoom
Просмотр разных узлов
Эксперименты
Реализация дерева 2-3-4 на языке Java
Класс DataItem
Класс Node
Класс Tree2
Класс Tree2App
Полный код программы tree2..java
Деревья 2-3-4 и красно-черные деревья
Преобразование деревьев 2-3-4 в красно-черные деревья
Эквивалентность операций
Эффективность деревьев 2-3-4
Скорость
Затраты памяти
Деревья 2-
Разбиение узлов
Реализация
Внешнее хранение
Обращение к внешним данным
Последовательное хранение
B-деревья
Индексирование
Сложные критерии поиска
Сортировка внешних файлов
Итоги
Вопросы
Упражнения
Программные проекты
Глава 11. Хеш-таблицы
Хеширование
Табельные номера как ключи
Индексы как ключи
Словарь
Хеширование
Коллизии
Открытая адресация
Линейное пробирование
Реализация хеш-таблицы с линейным пробированием на языке Java
Квадратичное пробирование
Двойное хеширование
Метод цепочек
Приложение HashChain Workshop
Реализация метода цепочек на языке Java
Хеш-функции
Быстрые вычисления
Случайные ключи
Неслучайные ключи
Хеширование строк
Свертка
Эффективность хеширования
Открытая адресация
Метод цепочек
Сравнение открытой адресации с методом цепочек
Хеширование и внешнее хранение данных
Таблица файловых указателей
Неполные блоки
Полные блоки
Итоги
Вопросы
Упражнения
Программные проекты
Глава 12. Пирамиды
Общие сведения
Приоритетные очереди, пирамиды и ADT
Слабая упорядоченность
Удаление
Вставка
Условные перестановки
Приложение Heap Workshop
Заполнение
Изменение приоритета
Удаление
Вставка
Реализация пирамиды на языке Java
Вставка
Удаление
Изменение ключа
Размер массива
Программа heap..java
Расширение массива
Эффективность операций с пирамидой
Пирамидальное дерево
Пирамидальная сортировка
Ускоренное смещение вниз
Сортировка «на месте»
Программа heapSort..java
Эффективность пирамидальной сортировки
Итоги
Вопросы
Упражнения
Программные проекты
Глава 13. Графы
Знакомство с графами
Определения
Немного истории
Представление графа в программе
Добавление вершин и ребер в граф
Класс Graph
Обход
Обход в глубину
Обход в ширину
Минимальные остовные деревья
Приложение GraphN Workshop
Реализация построения минимального остовного дерева на языке Java.
Топологическая сортировка с направленными графами
Пример
Направленные графы
Топологическая сортировка
Приложение GraphD Workshop
Циклы и деревья
Реализация на языке Java
Связность в направленных графах
Таблица связности
Алгоритм Уоршелла
Реализация алгоритма Уоршелла
Итоги
Вопросы
Упражнения
Программные проекты
Глава 14. Взвешенные графы
Минимальное остовное дерево во взвешенных графах
Пример: кабельное телевидение в джунглях
Приложение GraphW Workshop
Рассылка инспекторов
Создание алгоритма
Реализация на языке Java
Программа mstw..java
Задача выбора кратчайшего пути
Железная дорога
Направленный взвешенный граф
Алгоритм Дейкстры
Агенты и поездки
Приложение GraphDW Workshop
Реализация на языке Java
Программа path..java
Поиск кратчайших путей между всеми парами вершин
Эффективность
Неразрешимые задачи
Обход доски ходом шахматного коня
Задача коммивояжера
Гамильтоновы циклы
Итоги
Вопросы
Упражнения
Программные проекты
Глава 15. Рекомендации по использованию
Структуры данных общего назначения
Скорость и алгоритмы
Библиотеки
Массивы
Связанные списки
Деревья двоичного поиска
Сбалансированные деревья
Хеш-таблицы
Быстродействие структур данных общего назначения
Специализированные структуры данных
Стек
Очередь
Приоритетная очередь
Сортировка
Графы
Внешнее хранение данных
Последовательное хранение
Индексированные файлы
B-деревья
Хеширование
Виртуальная память
Итоги
Приложение А. Приложения Workshop и примеры программ
Приложения Workshop
Примеры программ
Sun Microsystems SDK
Программы командной строки
Настройка пути
Запуск приложений Workshop
Работа с приложениями Workshop
Запуск примеров
Компилирование примеров
Редактирование исходного кода
Завершение примеров
Одноименные файлы классов
Другие системы разработки
Приложение Б. Литература
Структуры данных и алгоритмы
Объектно-ориентированные языки программирования
Объектно-ориентированное проектирование и разработка
Приложение В. Ответы на вопросы