- •Глава 1. Основные понятия 14
- •Глава 2. Списки 30
- •Глава 3. Стеки и очереди 59
- •Глава 4. Массивы 74
- •Глава 5. Рекурсия 86
- •Глава 6. Деревья 121
- •Глава 7. Сбалансированные деревья 153
- •Глава 8. Деревья решений 180
- •Глава 9. Сортировка 213
- •Введение
- •Целевая аудитория
- •Глава 1. Основные понятия
- •Что такое алгоритмы?
- •Анализ скорости выполнения алгоритмов
- •Пространство — время
- •Оценка с точностью до порядка
- •Поиск сложных частей алгоритма
- •Сложность рекурсивных алгоритмов
- •Многократная рекурсия
- •Косвенная рекурсия
- •Требования рекурсивных алгоритмов к объему памяти
- •Наихудший и усредненный случай
- •Часто встречающиеся функции оценки порядка сложности
- •Логарифмы
- •Реальные условия — насколько быстро?
- •Обращение к файлу подкачки
- •Псевдоуказатели, ссылки на объекты и коллекции
- •Коллекции
- •Вопросы производительности
- •Глава 2. Списки
- •Знакомство со списками
- •Простые списки
- •Коллекции
- •Список переменного размера
- •Класс SimpleList
- •Неупорядоченные списки
- •Связные списки
- •Добавление элементов к связному списку
- •Удаление элементов из связного списка
- •Уничтожение связного списка
- •Сигнальные метки
- •Инкапсуляция связных списков
- •Доступ к ячейкам
- •Разновидности связных списков
- •Циклические связные списки
- •Проблема циклических ссылок
- •Двусвязные списки
- •Другие связные структуры
- •Псевдоуказатели
- •Глава 3. Стеки и очереди
- •Множественные стеки
- •Очереди
- •Циклические очереди
- •Очереди на основе связных списков
- •Применение коллекций в качестве очередей
- •Приоритетные очереди
- •Многопоточные очереди
- •Модель очереди
- •Глава 4. Массивы
- •Треугольные массивы
- •Диагональные элементы
- •Нерегулярные массивы
- •Прямая звезда
- •Нерегулярные связные списки
- •Разреженные массивы
- •Индексирование массива
- •Очень разреженные массивы
- •Глава 5. Рекурсия
- •Что такое рекурсия?
- •Рекурсивное вычисление факториалов
- •Анализ времени выполнения программы
- •Рекурсивное вычисление наибольшего общего делителя
- •Анализ времени выполнения программы
- •Рекурсивное вычисление чисел Фибоначчи
- •Анализ времени выполнения программы
- •Рекурсивное построение кривых Гильберта
- •Анализ времени выполнения программы
- •Рекурсивное построение кривых Серпинского
- •Анализ времени выполнения программы
- •Опасности рекурсии
- •Бесконечная рекурсия
- •Потери памяти
- •Необоснованное применение рекурсии
- •Когда нужно использовать рекурсию
- •Хвостовая рекурсия
- •Нерекурсивное вычисление чисел Фибоначчи
- •Устранение рекурсии в общем случае
- •Нерекурсивное построение кривых Гильберта
- •Нерекурсивное построение кривых Серпинского
- •Глава 6. Деревья
- •Определения
- •Представления деревьев
- •Полные узлы
- •Списки потомков
- •Представление нумерацией связей
- •Полные деревья
- •Обход дерева
- •Упорядоченные деревья
- •Добавление элементов
- •Удаление элементов
- •Обход упорядоченных деревьев
- •Деревья со ссылками
- •Работа с деревьями со ссылками
- •Квадродеревья
- •Изменение max_per_node
- •Использование псевдоуказателей в квадродеревьях
- •Восьмеричные деревья
- •Глава 7. Сбалансированные деревья
- •Сбалансированность дерева
- •Авл‑деревья
- •Вращения авл‑деревьев
- •Правое вращение
- •Левое вращение
- •Вращение влево‑вправо
- •Вращение вправо‑влево
- •Вставка узлов на языке Visual Basic
- •Удаление узла из авл‑дерева
- •Левое вращение
- •Вращение вправо‑влево
- •Другие вращения
- •Реализация удаления узлов на языке Visual Basic
- •Б‑деревья
- •Производительность б‑деревьев
- •Вставка элементов в б‑дерево
- •Удаление элементов из б‑дерева
- •Разновидности б‑деревьев
- •Нисходящие б‑деревья
- •Улучшение производительности б‑деревьев
- •Балансировка для устранения разбиения блоков
- •Добавление свободного пространства
- •Вопросы, связанные с обращением к диску
- •Псевдоуказатели
- •Выбор размера блока
- •Кэширование узлов
- •Глава 8. Деревья решений
- •Поиск в деревьях игры
- •Минимаксный поиск
- •Улучшение поиска в дереве игры
- •Предварительное вычисление начальных ходов
- •Определение важных позиций
- •Эвристики
- •Поиск в других деревьях решений
- •Метод ветвей и границ
- •Эвристики
- •Восхождение на холм
- •Метод наименьшей стоимости
- •Сбалансированная прибыль
- •Случайный поиск
- •Последовательное приближение
- •Момент остановки
- •Локальные оптимумы
- •Алгоритм «отжига»
- •Сравнение эвристик
- •Другие сложные задачи
- •Задача о выполнимости
- •Задача о разбиении
- •Задача поиска Гамильтонова пути
- •Задача коммивояжера
- •Задача о пожарных депо
- •Краткая характеристика сложных задач
- •Глава 9. Сортировка
- •Общие соображения
- •Объединение и сжатие ключей
- •Примеры программ
- •Сортировка выбором
- •Рандомизация
- •Сортировка вставкой
- •Вставка в связных списках
- •Пузырьковая сортировка
- •Быстрая сортировка
- •Сортировка слиянием
- •Пирамидальная сортировка
- •Пирамиды
- •Приоритетные очереди
- •Анализ пирамид
- •Алгоритм пирамидальной сортировки
- •Сортировка подсчетом
- •Блочная сортировка
- •Блочная сортировка с применением связного списка
- •Блочная сортировка на основе массива
- •Глава 10. Поиск
- •Примеры программ
- •Поиск методом полного перебора
- •Поиск в упорядоченных списках
- •Поиск в связных списках
- •Двоичный поиск
- •Интерполяционный поиск
- •Строковые данные
- •Следящий поиск
- •Интерполяционный следящий поиск
- •Глава 11. Хеширование
- •Связывание
- •Преимущества и недостатки связывания
- •Хранение хеш‑таблиц на диске
- •Связывание блоков
- •Удаление элементов
- •Преимущества и недостатки применения блоков
- •Открытая адресация
- •Линейная проверка
- •Первичная кластеризация
- •Упорядоченная линейная проверка
- •Квадратичная проверка
- •Псевдослучайная проверка
- •Удаление элементов
- •Рехеширование
- •Изменение размера хеш‑таблиц
- •Глава 12. Сетевые алгоритмы
- •Определения
- •Представления сети
- •Оперирование узлами и связями
- •Обходы сети
- •Наименьшие остовные деревья
- •Кратчайший маршрут
- •Установка меток
- •Варианты метода установки меток
- •Коррекция меток
- •Варианты метода коррекции меток
- •Другие задачи поиска кратчайшего маршрута
- •Двухточечный кратчайший маршрут
- •Вычисление кратчайшего маршрута для всех пар
- •Штрафы за повороты
- •Небольшое число штрафов за повороты
- •Большое число штрафов за повороты
- •Применения метода поиска кратчайшего маршрута
- •Разбиение на районы
- •Составление плана работ с использованием метода критического пути
- •Планирование коллективной работы
- •Максимальный поток
- •Приложения максимального потока
- •Непересекающиеся пути
- •Распределение работы
- •Глава 13. Объектно‑ориентированные методы
- •Преимущества ооп
- •Инкапсуляция
- •Обеспечение инкапсуляции
- •Полиморфизм
- •Зарезервированное слово Implements
- •Наследование и повторное использование
- •Парадигмы ооп
- •Управляющие объекты
- •Контролирующий объект
- •Итератор
- •Дружественный класс
- •Интерфейс
- •Порождающий объект
- •Единственный объект
- •Преобразование в последовательную форму
- •Парадигма Модель/Вид/Контроллер.
- •Контроллеры
- •Виды/Контроллеры
- •Требования к аппаратному обеспечению
- •Выполнение программ примеров
Представления деревьев
Теперь, когда вы познакомились с терминологией, вы можете представить себе способы реализации деревьев на языке Visual Basic. Один из способов — создать отдельный класс для каждого типа узлов дерева. Для построения дерева, показанного на рис. 6.3, вы можете определить структуры данных для узлов, которые имеют ноль, один, два или три дочерних узла. Этот подход был бы довольно неудобным. Кроме того, что нужно было бы управлять четырьмя различными классами, в классах потребовались бы какие‑то флаги, которые бы указывали тип дочерних узлов. Алгоритмы, которые оперировали бы этими деревьями, должны были бы уметь работать со всем различными типами деревьев.
Полные узлы
В качестве простого решения можно определить один тип узлов, который содержит достаточное число указателей на потомков для представления всех нужных узлов. Я называю это методом полных узлов, так как некоторые узлы могут быть большего размера, чем необходимо на самом деле.
Дерево, изображенное на рис 6.3, имеет 3 порядок. Для построения этого дерева с использованием метода полных узлов (fat nodes), требуется определить единственный класс, который содержит указатели на три дочерних узла. Следующий код демонстрирует, как эти указатели могут быть определены в классе TernaryNode.
Public LeftChild As TernaryNode
Public MiddleChild As TernaryNode
Public RightChild As TernaryNode
@Рис. 6.3. Части троичного (3 порядка) дерева
======119
При помощи этого класса можно построить дерево, используя записи Child узлов, для связи их друг с другом. Следующий фрагмент кода строит два верхних уровня дерева, показанного на рис. 6.3.
Dim A As New TernaryNode
Dim B As New TernaryNode
Dim C As New TernaryNode
Dim D As New TernaryNode
:
Set A.LeftChild = B
Set A.MiddleChild = C
Set A.RightChild = D
:
Программа Binary, показанная на рис. 6.4, использует метод полных узлов для работы с двоичным деревом. Когда вы выбираете узел с помощью мыши, программа подсвечивает кнопку Add Left (Добавить слева), если узел не имеет левого потомка и кнопку Add Right (Добавить справа), если узел не имеет правого потомка. Кнопка Remove (Удалить) разблокируется, если выбранный узел не является корневым. Если вы нажмете на кнопку Remove, программа удалит узел и всех его потомков.
Поскольку программа позволяет создать узлы с нулевым числом, одним или двумя дочерними узлами, она использует представление в виде полных узлов. Вы можете легко распространить этот пример на деревья более высоких порядков.
Списки потомков
Если порядки узлов в дереве сильно различаются, метод полных узлов приводит к напрасному расходованию большого количества памяти. Чтобы построить дерево, показанное на рис. 6.5 с использованием полных узлов, вам понадобится определить в каждом узле по шесть указателей, хотя только в одном узле все шесть из них используются. Это представление дерева потребует 72 указателей на дочерние узлы, из которых в действительности будет использоваться только 11.
@Рис. 6.4. Программа Binary
======120
Некоторые программы добавляют и удаляют узлы, изменяя порядок узлов в процессе выполнения. В этом случае метод полных узлов не будет работать. Такие динамически изменяющиеся деревья можно представить, поместив дочерние узлы в списки. Есть несколько подходов, которые можно использовать для создания списков дочерних узлов. Наиболее очевидный подход заключается в создании в классе узла открытого (public) массива дочерних узлов, как показано в следующем коде. Тогда для оперирования дочерними узлами можно использовать методы работы со списками на основе массивов.
Public Children() As TreeNode
Public NumChildren As Integer
К сожалению, Visual Basic не позволяет определять открытые массивы в классах. Это ограничение можно обойти, определив массив как закрытый (private), и оперируя элементами массива при помощи процедур свойств.
Private m_Chirdren() As TreeNode
Private m_NumChildren As Integer
Property Get Children(Index As Integer) As TreeNode
Set Children = m_Children(Index)
End Property
Property Get NumChildren() As Integer
NumChildren = m_NumChildren()
End Property
Второй подход состоит в том, чтобы сохранять ссылки на дочерние узлы в связных списках. Каждый узел содержит ссылку на первого потомка. Он также содержит ссылку на следующего потомка на том же уровне дерева. Эти связи образуют связный список узлов одного уровня, поэтому я называю этот метод представлением в виде связного списка узлов одного уровня (linked sibling). За информацией о связных списках вы можете обратиться ко 2 главе.
@Рис. 6.5. Дерево с узлами различных порядков
======121
Третий подход заключается в том, чтобы определить в классе узла открытую коллекцию, которая будет содержать дочерние узлы:
Public Children As New Collection
Это решение позволяет использовать все преимущества коллекций. Программа может при этом легко добавлять и удалять элементы из коллекции, присваивать дочерним узлам ключи, и использовать оператор For Each для выполнения циклов со ссылками на дочерние узлы.
Программа NAry, показанная на рис. 6.6, использует коллекцию дочерних узлов для работы с деревьями порядка N в основном таким же образом, как программа Binary работает с двоичными деревьями. В этой программе, тем не менее, можно добавлять к каждому узлу любое количество потомков.
Для того чтобы избежать чрезмерного усложнения пользовательского интерфейса, программа NAry всегда добавляет новые узлы в конец коллекции дочерних узлов родителя. Вы можете модифицировать эту программу, реализовав вставку дочерних узлов в середину коллекции, но пользовательский интерфейс при этом усложнится.