Структуры данных и алгоритмы в Java. Классика Computers Science

Содержание книги «Структуры данных и алгоритмы в Java. Классика Computers Science»:

• 18 Введение
  • 18 Второе издание
    • 18 Дополнительные темы
    • 19 Вопросы
    • 19 Упражнения
    • 19 Программные проекты
  • 19 О чем эта книга
  • 20 Чем эта книга отличается от других
    • 20 Доступность
    • 21 Приложения Workshop
    • 21 Примеры кода Java
  • 22 Для кого написана эта книга
  • 22 Что необходимо знать читателю
  • 22 Необходимые программы
  • 22 Как организован материал книги
  • 24 Вперед!
• 25 Глава 1 Общие сведения
  • 25 Зачем нужны структуры данных и алгоритмы?
    • 26 Хранение реальных данных
    • 26 Инструментарий программиста
    • 27 Моделирование
    • 27 Обзор структур данных
  • 28 Алгоритмы
  • 28 Определения
    • 29 База данных
    • 29 Запись
    • 29 Поле
    • 30 Ключ
  • 30 Объектно-ориентированное программирование
    • 30 Недостатки процедурных языков
    • 31 Объекты в двух словах
    • 32 Создание объектов
    • 33 Вызов методов объекта
    • 33 Пример объектно-ориентированной программы
    • 36 Наследование и полиморфизм
  • 37 Программотехника
  • 37 Java для программистов C++
    • 37 В Java нет указателей
    • 41 Ввод/вывод
    • 41 Вывод
  • 44 Структуры данных библиотеки Java
  • 44 Итоги
  • 45 Вопросы
• 46 Глава 2 Массивы
  • 46 Приложение Array Workshop
    • 48 Вставка
    • 48 Поиск
    • 49 Удаление
    • 50 Проблема дубликатов
    • 51 Не слишком быстро
  • 52 Поддержка массивов в Java
    • 52 Создание массива
    • 52 Обращение к элементам массива
    • 53 Инициализация
    • 53 Пример массива
  • 56 Деление программы на классы
    • 58 Классы LowArray и LowArrayApp
  • 58 Интерфейсы классов
    • 59 Не слишком удобно
    • 59 Кто чем занимается?
    • 60 Пример highArray.java
    • 63 Удобство пользователя
    • 63 Абстракция
  • 63 Приложение Ordered Workshop
    • 64 Линейный поиск
    • 65 Двоичный поиск
  • 67 Реализация упорядоченного массива на языке Java
    • 67 Двоичный поиск с методом find()
    • 69 Класс OrdArray
    • 72 Преимущества упорядоченных массивов
  • 72 Логарифмы
    • 73 Формула
    • 74 Операция, обратная возведению в степень
  • 75 Хранение объектов
    • 75 Класс Person
    • 76 Программа classDataArray.java
  • 79 O-синтаксис
    • 80 Вставка в неупорядоченный массив: постоянная сложность
    • 80 Линейный поиск: сложность пропорциональна N
    • 80 Двоичный поиск: сложность пропорциональна log(N)
    • 81 Константа не нужна
  • 82 Почему бы не использовать только массивы?
  • 83 Итоги
  • 84 Вопросы
  • 85 Упражнения
  • 85 Программные проекты
• 87 Глава 3 Простая сортировка
  • 87 Как это делается?
  • 89 Пузырьковая сортировка
    • 89 Пример пузырьковой сортировки
    • 91 Приложение BubbleSort Workshop
    • 94 Реализация пузырьковой сортировки на языке Java
    • 97 Инварианты
    • 97 Сложность пузырьковой сортировки
    • 98 Сортировка методом выбора
    • 98 Пример сортировки методом выбора
    • 100 Приложение SelectSort Workshop
    • 101 Реализация сортировки методом выбора на языке Java
    • 103 Инвариант
    • 103 Сложность сортировки методом выбора
  • 104 Сортировка методом вставки
    • 104 Пример сортировки методом вставки
    • 106 Приложение InsertSort Workshop
    • 106 Сортировка 10 столбцов
    • 108 Реализация сортировки методом вставки на языке Java
    • 111 Инварианты сортировки методом вставки
    • 111 Сложность сортировки методом вставки
  • 112 Сортировка объектов
    • 112 Реализация сортировки объектов на языке Java
    • 115 Лексикографические сравнения
    • 115 Устойчивость сортировки
  • 116 Сравнение простых алгоритмов сортировки
  • 116 Итоги
  • 117 Вопросы
  • 118 Упражнения
  • 119 Программные проекты
• 121 Глава 4 Стеки и очереди
  • 121 Другие структуры
    • 121 Инструменты программиста
    • 121 Ограничение доступа
    • 122 Абстракция
  • 122 Стеки
    • 123 Почтовая аналогия
    • 124 Приложение Stack Workshop
    • 126 Реализация стека на языке Java
    • 129 Пример использования стека № 1 Перестановка букв в слове
    • 132 Пример № 2 Поиск парных скобок
    • 136 Эффективность стеков
  • 136 Очереди
    • 137 Приложение Queue Workshop
    • 140 Циклическая очередь
    • 141 Реализация очереди на языке Java
    • 146 Эффективность очередей
    • 146 Дек
  • 146 Приоритетные очереди
    • 148 Приложение The PriorityQ Workshop
    • 150 Реализация приоритетной очереди на языке Java
    • 152 Эффективность приоритетных очередей
  • 152 Разбор арифметических выражений
    • 153 Постфиксная запись
    • 154 Преобразование инфиксной записи в постфиксную
    • 154 Как мы вычисляем результаты инфиксных выражений
    • 170 Вычисление результата постфиксного выражения
  • 175 Итоги
  • 176 Вопросы
  • 178 Упражнения
  • 178 Программные проекты
• 180 Глава 5 Связанные списки
  • 180 Строение связанного списка
    • 181 Ссылки и базовые типы
    • 182 Отношения вместо конкретных позиций
  • 183 Приложение LinkList Workshop
    • 183 Вставка
    • 184 Поиск
    • 184 Удаление
  • 185 Простой связанный список
    • 185 Класс Link
    • 186 Класс LinkList
    • 190 Программа linkList.java
  • 192 Поиск и удаление заданных элементов
    • 195 Метод find()
    • 195 Метод delete()
    • 196 Другие методы
  • 196 Двусторонние списки
  • 200 Эффективность связанных списков
  • 200 Абстрактные типы данных
    • 201 Реализация стека на базе связанного списка
    • 204 Реализация очереди на базе связанного списка
    • 207 Типы данных и абстракция
    • 208 Списки ADT
    • 209 Абстрактные типы данных как инструмент проектирования
  • 209 Сортированные списки
    • 211 Реализация вставки элемента в сортированный список на языке Java
    • 212 Программа sortedList.java
    • 214 Эффективность сортированных списков
    • 215 Сортировка методом вставки
  • 217 Двусвязные списки
    • 219 Перебор
    • 219 Вставка
    • 221 Удаление
    • 222 Программа doublyLinked.java
    • 226 Двусвязный список как база для построения дека
  • 226 Итераторы
    • 227 Ссылка на элемент списка?
    • 227 Итератор
    • 228 Другие возможности итераторов
    • 229 Методы итераторов
    • 230 Программа interIterator.java
    • 236 На что указывает итератор?
    • 236 Метод atEnd()
    • 236 Итеративные операции
  • 238 Другие методы
  • 238 Итоги
  • 239 Вопросы
  • 240 Упражнения
  • 241 Программные проекты
• 243 Глава 6 Рекурсия
  • 243 Треугольные числа
    • 244 Вычисление n-го треугольного числа в цикле
    • 245 Вычисление n-го треугольного числа с применением рекурсии
    • 247 Программа triangle.java
    • 248 Что реально происходит?
    • 249 Характеристики рекурсивных методов
    • 250 Насколько эффективна рекурсия?
    • 250 Математическая индукция
  • 250 Факториал
  • 252 Анаграммы
  • 257 Рекурсивный двоичный поиск
    • 258 Замена цикла рекурсией
    • 262 Алгоритмы последовательного разделения
  • 262 Ханойская башня
    • 263 Приложение Towers Workshop
    • 264 Перемещение поддеревьев
    • 264 Рекурсивный алгоритм
    • 266 Программа towers.java
  • 267 Сортировка слиянием
    • 268 Слияние двух отсортированных массивов
    • 270 Сортировка слиянием
    • 273 Приложение MergeSort Workshop
    • 274 Программа mergeSort.java
    • 281 Устранение рекурсии
    • 287 Что дальше?
  • 289 Интересные применения рекурсии
    • 289 Возведение числа в степень
    • 291 Задача о рюкзаке
    • 292 Комбинации и выбор команды
  • 294 Итоги
  • 295 Вопросы
  • 297 Упражнения
  • 297 Программные проекты
• 299 Глава 7 Нетривиальная сортировка
  • 299 Сортировка Шелла
    • 300 Сортировка методом вставок: слишком много копирования
    • 300 N-сортировка
    • 302 Сокращение интервалов
    • 303 Приложение Shellsort Workshop
    • 305 Реализация сортировки Шелла на языке Java
    • 307 Другие интервальные последовательности
    • 308 Эффективность сортировки Шелла
  • 309 Разбиение
    • 309 Приложение Partition Workshop
    • 313 Остановка и перестановка
  • 316 Быстрая сортировка
    • 317 Алгоритм быстрой сортировки
    • 318 Выбор опорного значения
    • 323 Приложение QuickSort1 Workshop
    • 327 Вырожденное быстродействие O(N2)
    • 328 Определение медианы по трем точкам
    • 333 Обработка малых подмассивов
    • 336 Устранение рекурсии
  • 339 Поразрядная сортировка
    • 340 Проектирование программы
    • 340 Эффективность поразрядной сортировки
  • 341 Итоги
  • 343 Вопросы
  • 344 Упражнения
  • 344 Программные проекты
• 346 Глава 8 Двоичные деревья
  • 346 Для чего нужны двоичные деревья?
    • 346 Медленная вставка в упорядоченном массиве
    • 347 Медленный поиск в связанном списке
    • 347 Деревья приходят на помощь
    • 347 Что называется деревом?
    • 348 Терминология
  • 351 Аналогия
  • 352 Как работают двоичные деревья?
    • 352 Приложение Binary Tree Workshop
    • 354 Представление деревьев в коде Java
  • 356 Поиск узла
    • 356 Поиск узла в приложении Workshop
    • 358 Реализация поиска узла на языке Java
    • 358 Эффективность поиска по дереву
  • 359 Вставка узла
    • 359 Вставка узла в приложении Workshop
    • 359 Реализация вставки на языке Java
  • 361 Обход дерева
    • 361 Симметричный обход
    • 362 Реализация обхода на языке Java
    • 362 Обход дерева из трех узлов
    • 363 Обход дерева в приложении Workshop
    • 365 Симметричный и обратный обход
    • 367 Поиск минимума и максимума
  • 368 Удаление узла
    • 368 Случай 1 Удаляемый узел не имеет потомков
    • 370 Случай 2 Удаляемый узел имеет одного потомка
    • 372 Случай 3 Удаляемый узел имеет двух потомков
  • 379 Эффективность двоичных деревьев
  • 381 Представление дерева в виде массива
  • 382 Дубликаты ключей
  • 383 Полный код программы tree.java
    • 391 Код Хаффмана
    • 391 Коды символов
    • 393 Декодирование по дереву Хаффмана
    • 394 Построение дерева Хаффмана
    • 396 Кодирование сообщения
    • 397 Создание кода Хаффмана
  • 397 Итоги
  • 399 Вопросы
  • 400 Упражнения
  • 401 Программные проекты
• 403 Глава 9 Красно-черные деревья
  • 403 Наш подход к изложению темы
    • 404 Концептуальное понимание
    • 404 Нисходящая вставка
  • 404 Сбалансированные и несбалансированные деревья
    • 405 Вырождение до O(N)
    • 406 Спасительный баланс
    • 406 Характеристики красно-черного дерева
    • 408 Исправление нарушений
  • 408 Работа с приложением RBTree Workshop
    • 409 Щелчок на узле
    • 409 Кнопка Start
    • 409 Кнопка Ins
    • 409 Кнопка Del
    • 410 Кнопка Flip
    • 410 Кнопка RoL
    • 410 Кнопка RoR
    • 410 Кнопка R/B
    • 410 Текстовые сообщения
    • 410 Где кнопка Find?
  • 411 Эксперименты с приложением Workshop
    • 411 Эксперимент 1 Вставка двух красных узлов
    • 412 Эксперимент 2 Повороты
    • 412 Эксперимент 3 Переключение цветов
    • 413 Эксперимент 4 Несбалансированное дерево
    • 414 Эксперименты продолжаются
    • 414 Красно-черные правила и сбалансированные деревья
    • 415 Пустые потомки
  • 415 Повороты
    • 416 Простые повороты
    • 416 Переходящий узел
    • 417 Перемещения поддеревьев
  • 419 Люди и компьютеры
  • 419 Вставка узла
    • 419 Общая схема процесса вставки
    • 420 Переключения цветов при перемещении вниз
    • 422 Повороты после вставки узла
    • 427 Повороты при перемещении вниз
  • 430 Удаление
  • 431 Эффективность красно-черных деревьев
    • 431 Реализация красно-черного дерева
  • 432 Другие сбалансированные деревья
  • 433 Итоги
  • 433 Вопросы
  • 435 Упражнения
• 436 Глава 10 Деревья 2-3-4
  • 436 Знакомство с деревьями 2-3-4
    • 437 Почему деревья 2-3-4 так называются?
    • 438 Структура дерева 2-3-4
    • 439 Поиск в дереве 2-3-4
    • 439 Вставка
    • 440 Разбиение узлов
    • 441 Разбиение корневого узла
    • 442 Разбиение при перемещении вниз
  • 442 Приложение Tree234 Workshop
    • 443 Кнопка Fill
    • 443 Кнопка Find
    • 444 Кнопка Ins
    • 444 Кнопка Zoom
    • 445 Просмотр разных узлов
    • 446 Эксперименты
  • 447 Реализация дерева 2-3-4 на языке Java
    • 447 Класс DataItem
    • 447 Класс Node
    • 448 Класс Tree234
    • 449 Класс Tree234App
    • 450 Полный код программы tree234.java
  • 457 Деревья 2-3-4 и красно-черные деревья
    • 457 Преобразование деревьев 2-3-4 в красно-черные деревья
    • 459 Эквивалентность операций
  • 461 Эффективность деревьев 2-3-4
    • 461 Скорость
    • 462 Затраты памяти
  • 462 Деревья 2-3
    • 463 Разбиение узлов
    • 465 Реализация
  • 466 Внешнее хранение
    • 466 Обращение к внешним данным
    • 469 Последовательное хранение
    • 471 B-деревья
    • 476 Индексирование
    • 478 Сложные критерии поиска
    • 479 Сортировка внешних файлов
  • 482 Итоги
  • 484 Вопросы
  • 485 Упражнения
  • 485 Программные проекты
• 487 Глава 11 Хеш-таблицы
  • 487 Хеширование
    • 488 Табельные номера как ключи
    • 488 Индексы как ключи
    • 489 Словарь
    • 492 Хеширование
    • 494 Коллизии
  • 495 Открытая адресация
    • 495 Линейное пробирование
    • 500 Реализация хеш-таблицы с линейным пробированием на языке Java
    • 507 Квадратичное пробирование
    • 509 Двойное хеширование
  • 517 Метод цепочек
    • 517 Приложение HashChain Workshop
    • 520 Реализация метода цепочек на языке Java
  • 525 Хеш-функции
    • 526 Быстрые вычисления
    • 526 Случайные ключи
    • 526 Неслучайные ключи
    • 528 Хеширование строк
    • 530 Свертка
  • 530 Эффективность хеширования
    • 530 Открытая адресация
    • 532 Метод цепочек
    • 534 Сравнение открытой адресации с методом цепочек
  • 535 Хеширование и внешнее хранение данных
    • 535 Таблица файловых указателей
    • 535 Неполные блоки
    • 536 Полные блоки
  • 537 Итоги
  • 538 Вопросы
  • 540 Упражнения
  • 540 Программные проекты
• 542 Глава 12 Пирамиды
  • 543 Общие сведения
    • 544 Приоритетные очереди, пирамиды и ADT
    • 544 Слабая упорядоченность
    • 545 Удаление
    • 547 Вставка
    • 548 Условные перестановки
  • 549 Приложение Heap Workshop
    • 550 Заполнение
    • 550 Изменение приоритета
    • 550 Удаление
    • 550 Вставка
  • 550 Реализация пирамиды на языке Java
    • 551 Вставка
    • 552 Удаление
    • 553 Изменение ключа
    • 554 Размер массива
    • 554 Программа heap.java
    • 560 Расширение массива
    • 560 Эффективность операций с пирамидой
  • 560 Пирамидальное дерево
  • 562 Пирамидальная сортировка
    • 562 Ускоренное смещение вниз
    • 564 Сортировка «на месте»
    • 565 Программа heapSort.java
    • 569 Эффективность пирамидальной сортировки
  • 570 Итоги
  • 571 Вопросы
  • 572 Упражнения
  • 572 Программные проекты
• 574 Глава 13 Графы
  • 574 Знакомство с графами
    • 575 Определения
    • 577 Немного истории
    • 578 Представление графа в программе
    • 580 Добавление вершин и ребер в граф
    • 581 Класс Graph
  • 582 Обход
    • 583 Обход в глубину
    • 592 Обход в ширину
  • 599 Минимальные остовные деревья
    • 600 Приложение GraphN Workshop
    • 600 Реализация построения минимального остовного дерева на языке Java
  • 604 Топологическая сортировка с направленными графами
    • 605 Пример
    • 605 Направленные графы
    • 606 Топологическая сортировка
    • 607 Приложение GraphD Workshop
    • 608 Циклы и деревья
    • 609 Реализация на языке Java
  • 615 Связность в направленных графах
    • 615 Таблица связности
    • 615 Алгоритм Уоршелла
    • 618 Реализация алгоритма Уоршелла
  • 618 Итоги
  • 619 Вопросы
  • 620 Упражнения
  • 620 Программные проекты
• 622 Глава 14 Взвешенные графы
  • 622 Минимальное остовное дерево во взвешенных графах
    • 622 Пример: кабельное телевидение в джунглях
    • 623 Приложение GraphW Workshop
    • 624 Рассылка инспекторов
    • 628 Создание алгоритма
    • 630 Реализация на языке Java
    • 632 Программа mstw.java
  • 637 Задача выбора кратчайшего пути
    • 638 Железная дорога
    • 639 Направленный взвешенный граф
    • 639 Алгоритм Дейкстры
    • 639 Агенты и поездки
    • 644 Приложение GraphDW Workshop
    • 648 Реализация на языке Java
    • 652 Программа path.java
  • 656 Поиск кратчайших путей между всеми парами вершин
  • 658 Эффективность
  • 659 Неразрешимые задачи
    • 660 Обход доски ходом шахматного коня
    • 660 Задача коммивояжера
    • 661 Гамильтоновы циклы
  • 661 Итоги
  • 662 Вопросы
  • 663 Упражнения
  • 664 Программные проекты
• 666 Глава 15 Рекомендации по использованию
  • 666 Структуры данных общего назначения
    • 667 Скорость и алгоритмы
    • 668 Библиотеки
    • 669 Массивы
    • 669 Связанные списки
    • 670 Деревья двоичного поиска
    • 670 Сбалансированные деревья
    • 670 Хеш-таблицы
    • 671 Быстродействие структур данных общего назначения
  • 671 Специализированные структуры данных
    • 672 Стек
    • 672 Очередь
    • 673 Приоритетная очередь
  • 673 Сортировка
  • 674 Графы
  • 675 Внешнее хранение данных
    • 675 Последовательное хранение
    • 676 Индексированные файлы
    • 676 B-деревья
    • 676 Хеширование
    • 676 Виртуальная память
  • 677 Итоги
• 678 Приложение А Приложения Workshop и примеры программ
  • 678 Приложения Workshop
  • 679 Примеры программ
  • 679 Sun Microsystems SDK
    • 679 Программы командной строки
    • 680 Настройка пути
    • 680 Запуск приложений Workshop
    • 680 Работа с приложениями Workshop
    • 681 Запуск примеров
    • 681 Компилирование примеров
    • 682 Редактирование исходного кода
    • 682 Завершение примеров
  • 682 Одноименные файлы классов
  • 682 Другие системы разработки
• 683 Приложение Б Литература
  • 683 Структуры данных и алгоритмы
  • 684 Объектно-ориентированные языки программирования
  • 684 Объектно-ориентированное проектирование и разработка
• 686 Приложение В Ответы на вопросы
  • 694 Об авторе
  • 695 Алфавитный указатель