Программирование, всегда было достаточно сложной задачей. Эта книга поможет вам легко преодолеть возникающие трудности с помощью библиотеки мощных алгоритмов, полностью реализованных в исходном коде Delphi. Вы узнаете, как выбрать способ, наиболее подходящий для решения конкретной задачи, и как добиться максимальной производительности вашего приложения. Рассматриваются типичные и наихудшие случаи реализации алгоритмов, что позволит вам вовремя распознать возможные трудности и при необходимости переписать или заменить часть программы. Подробно описываются важнейшие элементы алгоритмов хранения и обработки данных (списки, стеки, очереди, деревья, сортировка, поиск, хеширование и т. д.). Приводятся не только традиционные решения, но и методы, основанные на последних достижениях объектно-ориентированного программирования. Книга предназначена для начинающих программистов на Delphi, но благодаря четкой структуризации материала и богатой библиотеке готовых алгоритмов будет также интересна и специалистам.
Введение Глава 1. Основные понятия Что такое алгоритмы Анализ скорости выполнения, алгоритмов Память или время Оценка с точностью до порядка Определение сложности Сложность рекурсивных алгоритмов Средний и наихудший случай Общие функции оценки сложности Логарифмы Скорость работы алгоритма в реальных условиях Обращение к файлу подкачки Резюме Глава 2. Списки Основные понятия о списках Простые списки Изменение размеров массивов Список переменного размера Класс SimpleList Неупорядоченные списки Связанные списки Добавление элементов Удаление элементов Метки Доступ к ячейкам Разновидности связанных списков Циклические связанные списки Двусвязные списки Списки с потоками Другие связанные структуры Резюме Глава 3. Стеки и очереди Стеки Стеки на связанных списках Очереди Циклические очереди Очереди на основе связанных списков Очереди с приоритетом Многопоточные очереди Резюме Глава 4. Массивы Треугольные массивы Диагональные элементы Нерегулярные массивы Линейное представление с указателем Нерегулярные связанные списки Динамические массивы Delphi Разреженные массивы Индексирование массива Сильно разреженные массивы Резюме Глава 5. Рекурсия Что такое рекурсия Рекурсивное вычисление факториалов Анализ сложности Рекурсивное вычисление наибольшего общего делителя Анализ сложности Рекурсивное вычисление чисел Фибоначчи Анализ сложности Рекурсивное построение кривых Гильберта Анализ сложности Рекурсивное построение кривых Серпинского Анализ сложности Недостатки рекурсии Бесконечная рекурсия Потери памяти Необоснованное применение рекурсии Когда нужно использовать рекурсию Удаление хвостовой рекурсии Нерекурсивное вычисление чисел Фибоначчи Устранение рекурсии в общем случае Нерекурсивное создание кривых Гильберта Нерекурсивное построение кривых Серпинского Резюме Глава 6. Деревья Определения Представления деревьев Полные узлы Списки дочерних узлов Представление нумерацией связей Полные деревья Обход дерева Упорядоченные деревья Добавление элементов Удаление элементов Обход упорядоченных деревьев Деревья со ссылками Особенности работы Q-деревья Изменение значения MAX_QTREE_NODES Восьмеричные деревья Резюме Глава 7. Сбалансированные деревья Балансировка AVL-деревья Добавление узлов к AVL-дереву Удаление узлов из AVL-дерева Б-деревья Производительность Б-дерева Удаление элементов из Б-дерева Добавление элементов в Б-дерево Разновидности Б-дерева Усовершенствование Б-деревьев Вопросы доступа к диску База данных на основе Б+дерева Резюме Глава 8. Деревья решений Поиск в игровых деревьях Минимаксный перебор Оптимизация поиска в деревьях решений Поиск нестандартных решений Ветви и границы Эвристика Сложные задачи Задача о выполнимости Задача о разбиении Задача поиска Гамильтонова пути Задача коммивояжера Задача о пожарных депо Краткая характеристика сложных задач Резюме Глава 9. Сортировка Общие принципы Таблицы указателей Объединение и сжатие ключей Пример программы Сортировка выбором Перемешивание Сортировка вставкой Вставка в связанных списках Пузырьковая сортировка Быстрая сортировка Сортировка слиянием Пирамидальная сортировка Пирамиды Очереди с приоритетом Алгоритм пирамидальной сортировки Сортировка подсчетом Блочная сортировка Блочная сортировка с использованием связанных списков Резюме Глава 10. Поиск Примеры программ Полный перебор Перебор сортированных списков Перебор связанных списков Двоичный поиск Интерполяционный поиск Строковые данные Следящий поиск Двоичное отслеживание и поиск Интерполяционный следящий поиск Резюме Глава 11. Хеширование Связывание Преимущества и недостатки связывания Блоки Хранение хеш-таблиц на диске Связывание блоков Удаление элементов Преимущества и недостатки использования блоков Открытая адресация Линейная проверка Квадратичная проверка Псевдослучайная проверка Удаление элементов Резюме Глава 12. Сетевые алгоритмы Определения Представления сетей Управление узлами и связями Обход сети Наименьший каркас дерева Кратчайший путь Расстановка меток Коррекций меток Варианты поиска кратчайшего пути Применение алгоритмов поиска кратчайшего пути Максимальный поток Сферы применения Резюме Глава 13. Объектно-ориентированные методы Преимущества ООП Инкапсуляция Полиморфизм Многократное использование и наследование Парадигмы ООП Управляющие объекты Контролирующий объект Итератор Дружественный класс Интерфейс Фасад Фабрика Единственный объект Сериализация Парадигма Модель/Вид/Контроллер Резюме Приложение 1. Архив примеров Содержание архива с примерами Аппаратные требования Запуск примеров программ Информация и поддержка пользователей Приложение 2. Список примеров программ Предметный указатель
