Фундаментальные алгоритмы на C. Части 1 - 4. Анализ. Структуры данных. Сортировка. Поиск

Содержание книги «Фундаментальные алгоритмы на C. Части 1 - 4. Анализ. Структуры данных. Сортировка. Поиск»:

• 17 Часть 1. Анализ
• 18 Глава 1. Введение
  • 19 1.1. Алгоритмы
  • 21 1.2. Пример задачи связности
  • 25 1.3. Алгоритмы объединения-поиска
  • 36 1.4. Перспективы
  • 38 1.5. Обзор тем
• 40 Глава 2. Принципы анализа алгоритмов
  • 41 2.1. Реализация и эмпирический анализ
  • 45 2.2. Анализ алгоритмов
  • 48 2.3. Возрастание функций
  • 54 2.4. O-нотация
  • 59 2.5. Простейшие рекурсии
  • 63 2.6. Примеры анализа алгоритмов
  • 68 2.7. Гарантии, предсказания и ограничения
  • 72 Ссылки к части 1
• 74 Часть 2. Структуры данных
• 75 Глава 3. Элементарные структуры данных
  • 76 3.1. Строительные блоки
  • 86 3.2. Массивы
  • 92 3.3. Связные списки
  • 98 3.4. Обработка простых списков
  • 106 3.5. Распределение памяти под списки
  • 109 3.6. Строки
  • 114 3.7. Составные структуры данных
• 124 Глава 4. Абстрактные типы данных
  • 128 4.1. Абстрактные объекты и коллекции объектов
  • 131 4.2. АТД для стека магазинного типа
  • 134 4.3. Примеры клиентов, использующих ATД стека
  • 140 4.4. Реализации АТД стека
  • 144 4.5. Создание нового АТД
  • 147 4.6. Очереди FIFO и обобщенные очереди
  • 155 4.7. Повторяющиеся и индексные элементы
  • 160 4.8. АТД первого класса
  • 170 4.9. Пример использования АТД в приложениях
  • 175 4.10. Перспективы
• 177 Глава 5. Рекурсия и деревья
  • 178 5.1. Рекурсивные алгоритмы
  • 185 5.2. Разделяй и властвуй
  • 199 5.3. Динамическое программирование
  • 206 5.4. Деревья
  • 215 5.5. Математические свойства бинарных деревьев
  • 218 5.6. Обход дерева
  • 224 5.7. Рекурсивные алгоритмы для бинарных деревьев
  • 229 5.8. Обход графа
  • 235 5.9. Перспективы
  • 236 Ссылки для части 2
• 237 Часть 3. Сортировка
• 238 Глава 6. Элементарные методы сортировки
  • 240 6.1. Правила игры
  • 246 6.2. Сортировка выбором
  • 247 6.3. Сортировка вставками
  • 250 6.4. Пузырьковая сортировка
  • 252 6.5. Характеристики производительности элементарных методов сортировки
  • 258 6.6. Сортировка Шелла
  • 267 6.7. Сортировка других типов данных
  • 271 6.8. Сортировка по индексам и указателям
  • 278 6.9. Сортировка связных списков
  • 282 6.10. Метод распределяющего подсчета
• 285 Глава 7. Быстрая сортировка
  • 286 7.1. Базовый алгоритм
  • 291 7.2. Характеристики производительности быстрой сортировки
  • 295 7.3. Размер стека
  • 299 7.4. Подфайлы небольшого размера
  • 302 7.5. Метод разделения с вычислением медианы из трех элементов
  • 307 7.6. Дублированные
  • 310 7.7. Строки и векторы
  • 312 7.8. Выборка
• 316 Глава 8. Слияние и сортировка слиянием
  • 318 8.1. Двухпутевое слияние
  • 320 8.2. Абстрактное обменное слияние
  • 322 8.3. Нисходящая сортировка слиянием
  • 325 8.4. Усовершенствования базового алгоритма
  • 328 8.5. Восходящая сортировка слиянием
  • 331 8.6. Производительность сортировки слиянием
  • 335 8.7. Реализации сортировки слиянием для связных списков
  • 338 8.8. Возврат к рекурсии
• 340 Глава 9. Очереди с приоритетами и пирамидальная сортировка
  • 344 9.1. Элементарные реализации
  • 347 9.2. Пирамидальная структура данных
  • 349 9.3. Алгоритмы на пирамидальных деревьях
  • 356 9.4. Пирамидальная сортировка
  • 363 9.5. Абстрактный тип данных очереди с приоритетами
  • 368 9.6. Очереди с приоритетами для индексных элементов
  • 372 9.7. Биномиальные очереди
• 383 Глава 10. Поразрядная сортировка
  • 385 10.1. Биты, байты и слова
  • 388 10.2. Бинарная быстрая сортировка
  • 394 10.3. Поразрядная сортировка MSD
  • 402 10.4. Трехпутевая поразрядная быстрая сортировка
  • 406 10.5. Поразрядная сортировка LSD
  • 410 10.6. Характеристики производительности поразрядных сортировок
  • 414 10.7. Сортировки с сублинейным временем выполнения
• 419 Глава 11. Специальные методы сортировки
  • 421 11.1. Нечетно-четная сортировка слиянием Бэтчера
  • 426 11.2. Сети сортировки
  • 434 11.3. Внешняя сортировка
  • 441 11.4. Реализации сортировки-слияния
  • 448 11.5. Параллельная сортировка-слияние
  • 453 Ссылки для части 3
• 455 Часть 4. Поиск
• 456 Глава 12. Таблицы символов и деревья бинарного поиска
  • 458 12.1. Абстрактный тип данных таблицы символов
  • 463 12.2. Распределяющий поиск
  • 466 12.3. Последовательный поиск
  • 472 12.4. Бинарный поиск
  • 477 12.5. Деревья бинарного поиска
  • 483 12.6. Характеристики производительности деревьев бинарного поиска
  • 486 12.7. Индексные реализации таблиц символов
  • 490 12.8. Вставка в корень в деревьях бинарного поиска
  • 495 12.9. Реализации других функций АТД с помощью BST-дерева
• 504 Глава 13. Сбалансированные деревья
  • 508 13.1. Рандомизированные BST-деревья
  • 514 13.2. Скошенные деревья бинарного поиска
  • 520 13.3. Нисходящие 2-3-4-деревья
  • 525 13.4. Красно-черные, или RB-деревья
  • 535 13.5. Списки пропусков
  • 543 13.6. Характеристики производительности
• 547 Глава 14. Хеширование
  • 548 14.1. Хеш-функции
  • 558 14.2. Раздельное связывание
  • 562 14.3. Линейное зондирование
  • 567 14.4. Двойное хеширование
  • 573 14.5. Динамические хеш-таблицы
  • 577 14.6. Перспективы
• 582 Глава 15. Поразрядный поиск
  • 583 15.1. Деревья цифрового поиска
  • 588 15.2. Trie-деревья
  • 597 15.3. Patricia-деревья
  • 605 15.4. Многопутевые trie-деревья и TST-деревья
  • 622 15.5. Алгоритмы индексирования текстовых строк
• 627 Глава 16. Внешний поиск
  • 629 16.1. Правила игры
  • 631 16.2. Индексно-последовательный доступ
  • 634 16.3. B-деревья
  • 646 16.4. Расширяемое хеширование
  • 657 16.5. Перспективы
  • 660 Ссылки для части 4
• 663 Предметный указатель к частям 1-4