Структуры данных и алгоритмы в Java — Второе издание одной из самых авторитетных книг по программированию посвящено использованию структур данных и алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом разрабатываемое программное обеспечение будет использовать структуры данных. На чётких и простых программных примерах автор объясняет эту сложную тему, предлагая читателям написать собственные программы и на практике усвоить полученные знания. Рассматриваемые примеры написаны на языке Java, хотя для усвоения материала читателю не обязательно хорошо знать его — достаточно владеть любым языком программирования, например С++. Первая часть книги представляет собой введение в алгоритмизацию и структуры данных, а также содержит изложение основ объектно-ориентированного программирования. Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы. Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи.
Название: Структуры данных и алгоритмы в Java Автор: Лафоре Р. Издательство: Питер Год: 2013 Страниц: 703 Формат: PDF Размер: 12,34 МБ ISBN: 978-5-496-00740-5 Качество: Отличное Серия: Классика Computer Science
Содержание:
Введение Второе издание Дополнительные темы Вопросы Упражнения Программные проекты О чем эта книга Чем эта книга отличается от других Доступность Приложения Workshop Примеры кода Java Для кого написана эта книга Что необходимо знать читателю Необходимые программы Как организован материал книги Вперед! Глава 1. Общие сведения Зачем нужны структуры данных и алгоритмы? Хранение реальных данных Инструментарий программиста Моделирование Обзор структур данных Алгоритмы Определения База данных Запись Поле Ключ Объектно-ориентированное программирование Недостатки процедурных языков Объекты в двух словах Создание объектов Вызов методов объекта Пример объектно-ориентированной программы Наследование и полиморфизм Программотехника Java для программистов C++ В Java нет указателей Ввод/вывод Вывод Структуры данных библиотеки Java Итоги Вопросы Глава 2. Массивы Приложение Array Workshop Вставка Поиск Удаление Проблема дубликатов Не слишком быстро Поддержка массивов в Java Создание массива Обращение к элементам массива Инициализация Пример массива Деление программы на классы Классы LowArray и LowArrayApp Интерфейсы классов Не слишком удобно Кто чем занимается? Пример highArray.java Удобство пользователя Абстракция Приложение Ordered Workshop Линейный поиск Двоичный поиск Реализация упорядоченного массива на языке Java Двоичный поиск с методом find() Класс OrdArray Преимущества упорядоченных массивов Логарифмы Формула Операция, обратная возведению в степень Хранение объектов Класс Person Программа classDataArray.Java О-синтаксис Вставка в неупорядоченный массив: постоянная сложность Линейный поиск: сложность пропорциональна N Двоичный поиск: сложность пропорциональна log (N) Константа не нужна Почему бы не использовать только массивы? Итоги Вопросы Упражнения Программные проекты Глава 3. Простая сортировка Как это делается? Пузырьковая сортировка Пример пузырьковой сортировки Приложение BubDieSort Workshop Реализация пузырьковой сортировки на языке Java Инварианты Сложность пузырьковой сортировки Сортировка методом выбора Пример сортировки методом выбора Приложение SelectSortWorkshop Реализация сортировки методом выбора на языке Java Инвариант Сложность сортировки методом выбора Сортировка методом вставки Пример сортировки методом вставки Приложение InsertSortWorkshop Сортировка 10 столбцов Реализация сортировки методом вставки на языке Java Инварианты сортировки методом вставки Сложность сортировки методом вставки Сортировка объектов Реализация сортировки объектов на языке Java Лексикографические сравнения Устойчивость сортировки Сравнение простых алгоритмов сортировки Итоги Вопросы Упражнения Программные проемы Глава 4. Стеки и очереди Другие структуры Инструменты программиста Ограничение доступа Абстракция Стеки Почтовая аналогия Приложение StackWorkshop Реализация стека на языке Java Пример использования стека № 1. Перестановка букв в слове Пример № 2. Поиск парных скобок Эффективность стеков Очереди Приложение Queue Workshop Циклическая очередь Реализация очереди на языке Java Эффективность очередей Дек Приоритетные очереди Приложение The PriotityQWorkshop Реализация приоритетной очереди на языке Java Эффективность приоритетных очередей Разбор арифметических выражений Постфиксная запись Преобразование инфиксной записи в постфиксную Как мы вычисляем результаты инфиксных выражений Вычисление результата постфиксного выражения Итоги Вопросы Упражнения Программные проекты Глава 5. Связанные списки Строение связанного списка Ссылки и базовые типы Отношения вместо конкретных позиций Приложение LinkListWorkshop Вставка Поиск Удаление Простой связанный список Класс Link Класс Linkbst Программа linkList.Java Поиск и удаление заданных элементов Метод find() Метод delete() Другие методы Двусторонние списки Эффективность связанных списков Абстрактные типы данных Реализация стека на базе связанного списка Реализация очереди на базе связанного списка Типы данных и абстракция Списки ADT Абстрактные типы данных как инструмент проектирования Сортированные списки Реализация вставки элемента в сортированный список на языке Java Программа sorledUst.java Эффективность сортированных списков Сортировка методом вставки Двусеязные списки Перебор Вставка Удаление Программа doublyLinked.java Деусвязный список как база для построения дека Итераторы Ссылка на элемент списка? Итератор Другие возможности итераторов Методы итераторов Программа interlterator.java На что указывает итератор? Метод atEnd() Итеративные операции Другие методы Итоги Вопросы Упражнения Программные проекты Глава 6. Рекурсия Треугольные числа Вычисление n-го треугольного числа в цикле Вычисление n-го треугольного числа с применением рекурсии Программа triangle.java Что реально происходит? Характеристики рекурсивных методов Насколько эффективна рекурсия? Математическая индукция Факториал Анаграммы Рекурсивный двоичный поиск Замена цикла рекурсией Алгоритмы последовательного разделения Ханойская башня Приложение Towers Workshop Перемещение поддеревьев Рекурсивный алгоритм Программа towersjava Сортировка слиянием Слияние двух отсортированных массивов Сортировка слиянием Приложение MergeSort Workshop Программа mergeSort.java Устранение рекурсии Что дальше? Интересные применения рекурсии Возведение числа в степень Задача о рюкзаке Комбинации и выбор команды Итоги Вопросы Упражнения Программные проекты Глава 7. Нетривиальная сортировка Сортировка Шелла Сортировка методом вставок: слишком много копирования N-соргировка Сокращение интервалов Приложение Shellsotl Workshop Реализация сортировки Шелла на языке Java Другие интервальные последовательности Эффективность сортировки Шелла Разбиение Приложение Partition Workshop Остановка и перестановка Быстрая сортировка Алгоритм быстрой сортировки Выбор опорного значения Приложение QuickSortl Workshop Вырожденное быстродействие O(N<sup>2</sup>) Определение медианы по трем точкам Обработка малых подмассивов Устранение рекурсии Поразрядная сортировка Проектирование программы Эффективность поразрядной сортировки Итоги Вопросы Упражнения Программные проекты Глава 8. Двоичные деревья Для чего нужны двоичные деревья? Медленная вставка в упорядоченном массиве Медленный поиск в связанном списке Деревья приходят на помощь Что называется деревом? Терминология Аналогия Как работают двоичные деревья? Приложение Birtaiy Tree Workshop Представление деревьев в коде Java Поиск узла Поиск узла в приложении Workshop Реализация поиска узла на языке Java Эффективность поиска по дереву Вставка узла Вставка узла в приложении Workshop Реализация вставки на языке Java Обход дерева Симметричный обход Реализация обхода на языке Java Обход дерева из трех узлов Обход дерева в приложении Workshop Симметричный и обратный обход Поиск минимума и максимума Удаление узла Случай 1. Удаляемый узел не имеет потомков Случай 2. Удаляемый узел имеет одного потомка Случай 3. Удаляемый узел имеет двух потомков Эффективность двоичных деревьев Представление дерева в виде массива Дубликаты ключей Полный код программы ttee.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 Вставка Разбиение узлов Разбиение корневого узла Разбиение при перемещении вниз Приложение Тгее234 Workshop Кнопка Fill Кнопка Find Кнопка Ins Кнопка Zoom Просмотр разных узлов Эксперименты Реализация дерева 2-3-4 на языке Java Класс DalaUem Класс Node Класс Ттее234 Класс Тгее234Арр Полный код npoграммы tiee234.java Деревья 2-3-4 и красно-черные деревья Преобразование деревьев 2-3-4 в красно-черные деревья Эквивалентность операций Эффективность деревьев 2-3-4 Скорость Затраты памяти Деревья 2-3 Разбиение узлов Реализация Внешнее хранение Обращение к внешним данным Последовательное хранение В-деревья Индексирование Сложные критерии поиска Сортировка внешних файлов Итоги Вопросы Упражнения Программные проекты Глава 11. Хеш-таблицы Хеширование Табельные номера как ключи Индексы как ключи Словарь Хеширование Коллизии Открытая адресация Линейное пробирование Реализация хеш-таблицы с линейным пробированием на языке Java Квадратичное пробирование Двойное хеширование Метод цепочек Приложение HashCnain Workshop Реализация метода цепочек на языке Java Хеш-функции Быстрые вычисления Случайные ключи Неслучайные ключи Хеширование строк Свертка Эффективность хеширования Открытая адресация Метод цепочек Сравнение открытой адресации с методом цепочек Хеширование и внешнее хранение данных Таблица файловых указателей Неполные блоки Полные блоки Итоги Вопросы Упражнения Программные проекты Глава 12. Пирамиды Общие сведения Приоритетные очереди, пирамиды и ADT Слабая упорядоченность Удаление Вставка Условные перестановки Приложение Heap Workshop Заполнение Изменение приоритета Удаление Вставка Реализация пирамиды на языке Java Вставка Удаление Изменение ключа Размер массива Программа heap. fava Расширение массива Эффективность операций с пирамидой Пирамидальное дерево Пирамидальная сортировка Ускоренное смещение вниз Сортировка - на месте- Программа heapSort. iava Эффективность пирамидальной сортировки Итоги Вопросы Упражнения Программные проекты Глава 13. Графы Знакомство с графами Определения Немного истории Представление графа в программе Добавление вершин и ребер в граф Класс Graph Обход Обход в глубину Обход в ширину Минимальные остовные деревья Приложение GraphN Workshop Реализация построения минимального остовного дерева на языке Java Топологическая сортировка с направленными графами Пример Направленные i рафы Топологическая сортировка Приложение GraphD Workshop Циклы и деревья Реализация на языке Java Связность в направленных графах Таблица связности Алгоритм Уоршелла Реализация алгоритма Уоршелла Итоги Вопросы Упражнения Программные проекты Глава 14. Взвешенные графы Минимальное остовное дерево во взвешенных графах Пример: кабельное телевидение в джунглях Приложение GraphW Workshop Рассылка инспекторов Создание алгоритма Реализация на языке Java Программа mstw.java Задача выбора кратчайшего пути Железная дорога Направленный взвешенный граф Алгоритм Дейкстры Агенты и поездки Приложение GiaphDW Workshop Реализация на языке Java Программа path.iava Поиск кратчайших путей между всеми парами вершин Эффективность Неразрешимые задачи Обход доски ходом шахматного коня Задача коммивояжера Гамильтоновы циклы Итоги Вопросы Упражнения Программные проекты Глава 15. Рекомендации по использованию Структуры данных общего назначения Скорость и алгоритмы Библиотеки Массивы Связанные списки Деревья двоичного поиска Сбалансированные деревья Хеш-таблицы Быстродействие структур данных общего назначения Специализированные структуры данных Стек Очередь Приоритетная очередь Сортировка Графы внешнее хранение данных Последовательное хранение Индексированные файлы В-деревья Хеширование Виртуальная память Итоги Приложение А. Приложения Workshop и примеры программ Приложения Workshop Примеры программ Sun Microsystems SDK Программы командной строки Настройка пути Запуск приложений Workshop Работа с приложениями Workshop Запуск примеров Компилирование примеров Редактирование исходного кода Завершение примеров Одноименные файлы классов Другие системы разработки Приложение Б. Литература Структуры данным и алгоритмы Объектно-ориентированные языки программирования Объектно-ориентированное проектирование и разработка Приложение В. Ответы на вопросы Об авторе Алфавитный указатель
