- •Глава 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
- •Наследование и повторное использование
- •Парадигмы ооп
- •Управляющие объекты
- •Контролирующий объект
- •Итератор
- •Дружественный класс
- •Интерфейс
- •Порождающий объект
- •Единственный объект
- •Преобразование в последовательную форму
- •Парадигма Модель/Вид/Контроллер.
- •Контроллеры
- •Виды/Контроллеры
- •Требования к аппаратному обеспечению
- •Выполнение программ примеров
Уничтожение связного списка
Можно предположить, что для уничтожения связного списка необходимо обойти весь список, устанавливая значение NextCell для всех ячеек равным Nothing. На самом деле процесс гораздо проще: только top_cell принимает значение Nothing.
Когда программа устанавливает значение top_cell равным Nothing, счетчик ссылок для первой ячейки становится равным нулю, и Visual Basic уничтожает эту ячейку.
Во время уничтожения ячейки, система определяет, что в поле NextCell этой ячейки содержится ссылка на другую ячейку. Поскольку первый объект уничтожается, то число ссылок на второй объект уменьшается. При этом счетчик ссылок на второй объект списка становится равным нулю, поэтому система уничтожает и его.
Во время уничтожения второго объекта, система уменьшает число ссылок на третий объект, и так далее до тех пор, пока все объекты в списке не будут уничтожены. Когда в программе уже не будет ссылок на объекты списка, можно уничтожить и весь список при помощи единственного оператора Set top_cell = Nothing.
@Рис. 2.6. Удаление элемента из середины связного списка
========31
Сигнальные метки
Для добавления или удаления элементов из начала или середины списка используются различные процедуры. Можно свести оба этих случая к одному и избавиться от избыточного кода, если ввести специальную сигнальную метку (sentinel) в самом начале списка. Сигнальную метку нельзя удалить. Она не содержит данных и используется только для обозначения начала списка.
Теперь вместо того, чтобы обрабатывать особый случай добавления элемента в начало списка, можно помещать элемент после метки. Таким же образом, вместо особого случая удаления первого элемента из списка, просто удаляется элемент, следующий за меткой.
Использование сигнальных меток пока не вносит особых различий. Сигнальные метки играют важную роль в гораздо более сложных алгоритмах. Они позволяют обрабатывать особые случаи, такие как начало списка, как обычные. При этом требуется написать и отладить меньше кода, и алгоритмы становятся более согласованными и более простыми для понимания.
В табл. 2.1 сравнивается сложность выполнения некоторых типичных операций с использованием списков на основе массивов со «сборкой мусора» или связных списков.
Списки на основе массивов имеют одно преимущество: они используют меньше памяти. Для связных списков необходимо добавить поле NextCell к каждому элементу данных. Каждая ссылка на объект занимает четыре дополнительных байта памяти. Для очень больших массивов это может потребовать больших затрат памяти.
Программа LnkList1 демонстрирует простой связный список с сигнальной меткой. Введите значение в текстовое поле ввода, и нажмите на элемент в списке или на метку. Затем нажмите на кнопку Add After (Добавить после), и программа добавит новый элемент после указанного. Для удаления элемента из списка, нажмите на элемент и затем на кнопку Remove After (Удалить после).
@Таблица 2.1. Сравнение списков на основе массивов и связных списков
=========32
Инкапсуляция связных списков
Программа LnkList1 управляет списком явно. Например, следующий код показывает, как программа удаляет элемент из списка. Когда подпрограмма начинает работу, глобальная переменная SelectedIndex дает положение элемента, предшествующего удаляемому элементу в списке. Переменная Sentinel содержит ссылку на сигнальную метку списка.
Private Sub CmdRemoveAfter_Click()
Dim ptr As ListCell
Dim position As Integer
If SelectedIndex < 0 Then Exit Sub
‘ Найти элемент.
Set ptr = Sentinel
position = SelectedIndex
Do While position > 0
position = position - 1
Set ptr = ptr.nextCell
Loop
‘ Удалить следуюший элемент.
Set ptr.NextCell = ptr.NextCell.NextCell
NumItems = NumItems - 1
SelectItem SelectedIndex ‘ Снова выбрать элемент.
DisplayList
NewItem.SetFocus
End Sub
Чтобы упростить использование связного списка, можно инкапсулировать его функции в классе. Это реализовано в программе LnkList2 . Она аналогична программе LnkList1, но использует для управления списком класс LinkedList.
Класс LinekedList управляет внутренней организацией связного списка. В нем находятся процедуры для добавления и удаления элементов, возвращения значения элемента по его индексу, числа элементов в списке, и очистки списка. Этот класс позволяет обращаться со связным списком почти как с массивом.
Это намного упрощает основную программу. Например, следующий код показывает, как программа LnkList2 удаляет элемент из списка. Только одна строка в программе в действительности отвечает за удаление элемента. Остальные отображают новый список. Сравните этот код с предыдущей процедурой:
Private sub CmdRemoveAfter_Click()
Llist.RemoveAfter SelectedIndex
SelectedItem SelectedList ‘ Снова выбрать элемент.
DisplayList
NewItem.SetFocus
CmdClearList.Enabled
End Sub
=====33