- •Глава 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
- •Наследование и повторное использование
- •Парадигмы ооп
- •Управляющие объекты
- •Контролирующий объект
- •Итератор
- •Дружественный класс
- •Интерфейс
- •Порождающий объект
- •Единственный объект
- •Преобразование в последовательную форму
- •Парадигма Модель/Вид/Контроллер.
- •Контроллеры
- •Виды/Контроллеры
- •Требования к аппаратному обеспечению
- •Выполнение программ примеров
Представление нумерацией связей
Представление нумерацией связей (forward star), впервые упомянутое в 4 главе, позволяет компактно представить деревья, графы и сети при помощи массива. Для представления дерева нумерацией связей, в массиве FirstLink записывается индекс для первых ветвей, выходящих из каждого узла. В другой массив, ToNode, заносятся узлы, к которым ведет ветвь.
Сигнальная метка в конце массива FirstLink указывает на точку сразу после последнего элемента массива ToNode. Это позволяет легко определить, какие ветви выходят из каждого узла. Ветви, выходящие из узла I, находятся под номерами от FirstLink(I) до FirstLink(I+1)-1. Для вывода связей, выходящих из узла I, можно использовать следующий код:
For link = FirstLink(I) To FirstLink(I + 1) - 1
Print Format$(I) & " -> " & Format$(ToNode(link))
Next link
@Рис. 6.6. Программа Nary
=======123
На рис. 6.7 показано дерево и его представление нумерацией связей. Связи, выходящие из 3 узла (обозначенного буквой D) это связи от FirstLink(3) до FirstLink(4)-1. Значение FirstLink(3) равно 9, а FirstLink(4) = 11, поэтому это связи с номерами 9 и 10. Записи ToNode для этих связей равны ToNode(9) = 10 и ToNode(10) = 11, поэтому узлы 10 и 11 будут дочерними для 3 узла. Это узлы, обозначенные буквами K и L. Это означает, что связи, покидающие узел D, ведут к узлам K и L.
Представление дерева нумерацией связей компактно и основано на массиве, поэтому деревья, представленные таким образом, можно легко считывать из файлов и записывать в файл. Операции для работы с массивами, которые используются при таком представлении, также могут быть быстрее, чем операции, нужные для использования узлов, содержащих коллекции дочерних узлов.
По этим причинам большая часть литературы по сетевым алгоритмам использует представление нумерацией связей. Например, многие статьи, касающиеся вычисления кратчайшего пути, предполагают, что данные находятся в подобном формате. Если вам когда‑либо придется изучать эти алгоритмы в журналах, таких как “Management Science” или “Operations Research”, вам необходимо разобраться в этом представлении.
@Рис. 6.7. Дерево и его представление нумерацией связей
=======123
Используя представление нумерацией связей, можно быстро найти связи, выходящие из определенного узла. С другой стороны, очень сложно изменять структуру данных, представленных в таком виде. Чтобы добавить к узлу A на рис. 6.7 еще одного потомка, придется изменить почти все элементы в обоих массивах FirstLink и ToNode. Во‑первых, каждый элемент в массиве ToNode нужно сдвинуть на одну позицию вправо, чтобы освободить место под новый элемент. Затем, нужно вставить новую запись в массив ToNode, которая указывает на новый узел. И, наконец, нужно обойти массив ToNode, обновив каждый элемент, чтобы он указывал на новое положение соответствующей записи ToNode. Поскольку все записи в массиве ToNode сдвинулись на одну позицию вправо, чтобы освободить место для новой связи, потребуется добавить единицу ко всем затронутым записям FirstLink.
На рис. 6.8 показано дерево после добавления нового узла. Записи, которые изменились, закрашены серым цветом.
Удаление узла из начала представления нумерацией связей так же сложно, как и вставка узла. Если удаляемый узел имеет потомков, процесс занимает еще больше времени, поскольку придется удалять и все дочерние узлы.
Относительно простой класс с открытой коллекцией дочерних узлов лучше подходит, если нужно часто модифицировать дерево. Обычно проще понимать и отлаживать процедуры, которые оперируют деревьями в этом представлении. С другой стороны, представление нумерацией связей иногда обеспечивает более высокую производительность для сложных алгоритмов работы с деревьями. Оно также являются стандартной структурой данных, обсуждаемой в литературе, поэтому вам следует ознакомиться с ним, если вы хотите продолжить изучение алгоритмов работы с сетями и деревьями.
@Рис. 6.8. Вставка узла в дерево, представленное нумерацией связей
=======124
Программа Fstar использует представление нумерацией связей для работы с деревом, имеющим узлы разного порядка. Она аналогична программе NAry, за исключением того, что она использует представление на основе массива, а не коллекций.
Если вы посмотрите на код программы Fstar, вы увидите, насколько сложно в ней добавлять и удалять узлы. Следующий код демонстрирует удаление узла из дерева.
Sub FreeNodeAndChildren(ByVal parent As Integer, _
ByVal link As Integer, ByVal node As Integer)
' Recursively remove the node's children.
Do While FirstLink(node) < FirstLink(node + 1)
FreeNodeAndChildren node, FirstLink(node), _
ToNode(FirstLink(node))
Loop
' Удалить связь.
RemoveLink parent, link
' Удалить сам узел.
RemoveNode node
End Sub
Sub RemoveLink(node As Integer, link As Integer)
Dim i As Integer
' Обновить записи массива FirstLink.
For i = node + 1 To NumNodes
FirstLink(i) = FirstLink(i) - 1
Next i
' Сдвинуть массив ToNode чтобы заполнить пустую ячейку.
For i = link + 1 To NumLinks - 1
ToNode(i - 1) = ToNode(i)
Next i
' Удалить лишний элемент из ToNode.
NumLinks = NumLinks - 1
If NumLinks > 0 Then ReDim Preserve ToNode(0 To NumLinks - 1)
End Sub
Sub RemoveNode(node As Integer)
Dim i As Integer
' Сдвинуть элементы массива FirstLink, чтобы заполнить
' пустую ячейку.
For i = node + 1 To NumNodes
FirstLink(i - 1) = FirstLink(i)
Next i
' Сдвинуть элементы массива NodeCaption.
For i = node + 1 To NumNodes - 1
NodeCaption(i - 1) = NodeCaption(i)
Next i
' Обновить записи массива ToNode.
For i = 0 To NumLinks - 1
If ToNode(i) >= node Then ToNode(i) = ToNode(i) - 1
Next i
' Удалить лишнюю запись массива FirstLink.
NumNodes = NumNodes - 1
ReDim Preserve FirstLink(0 To NumNodes)
ReDim Preserve NodeCaption(0 To NumNodes - 1)
Unload FStarForm.NodeLabel(NumNodes)
End Sub
Это намного сложнее, чем соответствующий код в программе NAry:
Public Function DeleteDescendant(target As NAryNode) As Boolean
Dim i As Integer
Dim child As NAryNode
' Является ли узел дочерним узлом.
For i = 1 To Children.Count
If Children.Item(i) Is target Then
Children.Remove i
DeleteDescendant = True
Exit Function
End If
Next i
' Если это не дочерний узел, рекурсивно
' проверить остальных потомков.
For Each child In Children
If child.DeleteDescendant(target) Then
DeleteDescendant = True
Exit Function
End If
Next child
End Function
=======125-126