Ready-to-Run Delphi 3.0 Algorithms

Description

All the algorithms you′ll ever need for use in your Delphi programs Ready–to–Run Delphi 3.0 Algorithms This book/CD package arms you with a library of powerful algorithms completely implemented in Delphi source code. Just as importantly, it shows you when, where, and how to use them, and when you shouldn′t use them. You′ll find out how to handle just about any design requirement you′ll encounter, such as managing data structures, sorting, searching, hashing, networking, and other important program functions. In plain English, and with the help of sample code and numerous working examples, programming guru Rod Stephens brings you up to speed on algorithm fundamentals, and, with the help of ready–to–run programs that you can use to try out the algorithms, he shows you how to: ∗ Compare the strengths and weaknesses of different algorithms to select the best one for a particular situation ∗ Analyze algorithms both theoretically and in real–world situations ∗ Anticipate performance problems before they become disasters ∗ Customize algorithms to suit your particular needs ∗ Effectively use both classical algorithms and the latest object–oriented techniques ∗ Identify performance bottlenecks where changes can have the greatest impact on speed The CD–ROM supplies you with: ∗ Delphi source code for all the algorithms described in the book ∗ Test programs to try them out ∗ A library of important algorithms you can use immediately without wasting valuable programming time Visit the author′s comprehensive Delphi site at :www.delphi–helper.com Введение Глава 1. Основные понятия Что такое алгоритмы Анализ скорости выполнения алгоритмов Память или время Оценка с точностью до порядка Определение сложности Сложность рекурсивных алгоритмов Средний и наихудший случай Общие функции оценки сложности Логарифмы Скорость работы алгоритма в реальных условиях Обращение к файлу подкачки Резюме Глава 2. Списки Основные понятия о списках Простые списки Изменение размеров массивов Список переменного размера Класс SimpleList Неупорядоченные списки Связанные списки Добавление элементов Удаление элементов Метки Доступ к ячейкам Разновидности связанных списков Циклические связанные списки Двусвязные списки Списки с потоками Другие связанные структуры Резюме Глава 3. Стеки и очереди Стеки Стеки на связанных списках Очереди Циклические очереди Очереди на основе связанных списков Очереди с приоритетом Многопоточные очереди Резюме Глава 4. Массивы Треугольные массивы Диагональные элементы Нерегулярные массивы Линейное представление с указателем Нерегулярные связанные списки Динамические массивы Delphi Разреженные массивы Индексирование массива Сильно разреженные массивы Резюме Глава 5. Рекурсия Что такое рекурсия Рекурсивное вычисление факториалов Анализ сложности Рекурсивное вычиcление наибольшего общего делителя Анализ сложности Рекурсивное вычисление чисел Фибоначчи Анализ сложности Рекурсивное построение кривых Гильберта Анализ сложности Рекурсивное построение кривых Серпинского Анализ сложности Недостатки рекурсии Бесконечная рекурсия Потери памяти Необоснованное применение рекурсии Когда нужно использовать рекурсию Удаление хвостовой рекурсии Нерекурсивное вычисление чисел Фибоначчи Устранение рекурсии в общем случае Нерекурсивное создание кривых Гильберта Нерекурсивное построение кривых Серпинского Резюме Глава 6. Деревья Определения Представления деревьев Полные узлы Списки дочерних узлов Представление нумерацией связей Полные деревья Обход дерева Упорядоченные деревья Добавление элементов Удаление элементов Обход упорядоченных деревьев Деревья со ссылками Особенности работы Q-деревья Изменение значения MAX_QTREE_NODES Восьмеричные деревья Резюме Глава 7. Сбалансированные деревья Балансировка AVL-деревья Добавление узлов к AVL-дереву Удаление узлов из AVL-дерева Б-деревья Производительность Б-дерева Удаление элементов из Б-дерева Добавление элементов в Б-дерево Разновидности Б-дерева Усовершенствование Б-деревьев Вопросы доступа к диску База данных на основе Б+дерева Резюме Глава 8. Деревья решений Поиск в игровых деревьях Минимаксный перебор Оптимизация поиска в деревьях решений Поиск нестандартных решений Ветви и границы Эвристика Сложные задачи Задача о выполнимости Задача о разбиении Задача поиска Гамильтонова пути Задача коммивояжера Задача о пожарных депо Краткая характеристика сложных задач Резюме Глава 9. Сортировка Общие принципы Таблицы указателей Объединение и сжатие ключей Пример программы Сортировка выбором Перемешивание Сортировка вставкой Вставка в связанных списках Пузырьковая сортировка Быстрая сортировка Сортировка слиянием Пирамидальная сортировка Пирамиды Очереди с приоритетом Алгоритм пирамидальной сортировки Сортировка подсчетом Блочная сортировка Блочная сортировка с использованием связанных списков Резюме Глава 10. Поиск Примеры программ Полный перебор Перебор сортированных списков Перебор связанных списков Двоичный поиск Интерполяционный поиск Строковые данные Следящий поиск Двоичное отслеживание и поиск Интерполяционный следящий поиск Резюме Глава 11. Хеширование Связывание Преимущества и недостатки связывания Блоки Хранение хеш-таблиц на диске Связывание блоков Удаление элементов Преимущества и недостатки использования блоков Открытая адресация Линейная проверка Квадратичная проверка Псевдослучайная проверка Удаление элементов Резюме Глава 12. Сетевые алгоритмы Определения Представления сетей Управление узлами и связями Обход сети Наименьший каркас дерева Кратчайший путь Расстановка меток Коррекция меток Варианты поиска кратчайшего пути Применение алгоритмов поиска кратчайшего пути Максимальный поток Сферы применения Резюме Глава 13. Объектно-ориентированные методы Преимущества ООП Инкапсуляция Полиморфизм Многократное использование и наследование Парадигмы ООП Управляющие объекты Контролирующий объект Итератор Дружественный класс Интерфейс Фасад Фабрика Единственный объект Сериализация Парадигма Модель/Вид/Контроллер Резюме Приложение 1. Архив примеров Cодержание архива с примерами Аппаратные требования Запуск примеров программ Информация и поддержка пользователей Приложение 2. Список примеров программ Предметный указатель