.

VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 18531
Скачать документ

TOC \o “1-3” Введение PAGEREF _Toc3148911 \h 8

Целевая аудитория PAGEREF _Toc3148912 \h 10

Глава 1. Основные понятия PAGEREF _Toc3148913 \h 15

Что такое алгоритмы? PAGEREF _Toc3148914 \h 15

Анализ скорости выполнения алгоритмов PAGEREF _Toc3148915 \h 16

Пространство — время PAGEREF _Toc3148916 \h 17

Оценка с точностью до порядка PAGEREF _Toc3148917 \h 17

Поиск сложных частей алгоритма PAGEREF _Toc3148918 \h 19

Сложность рекурсивных алгоритмов PAGEREF _Toc3148919 \h 20

Многократная рекурсия PAGEREF _Toc3148920 \h 21

Косвенная рекурсия PAGEREF _Toc3148921 \h 22

Требования рекурсивных алгоритмов к объему памяти PAGEREF _Toc3148922
\h 22

Наихудший и усредненный случай PAGEREF _Toc3148923 \h 23

Часто встречающиеся функции оценки порядка сложности PAGEREF
_Toc3148924 \h 24

Логарифмы PAGEREF _Toc3148925 \h 25

Реальные условия — насколько быстро? PAGEREF _Toc3148926 \h 25

Обращение к файлу подкачки PAGEREF _Toc3148927 \h 26

Псевдоуказатели, ссылки на объекты и коллекции PAGEREF _Toc3148928 \h
27

Резюме PAGEREF _Toc3148929 \h 29

Глава 2. Списки PAGEREF _Toc3148930 \h 30

Знакомство со списками PAGEREF _Toc3148931 \h 31

Простые списки PAGEREF _Toc3148932 \h 31

Коллекции PAGEREF _Toc3148933 \h 32

Список переменного размера PAGEREF _Toc3148934 \h 33

Класс SimpleList PAGEREF _Toc3148935 \h 36

Неупорядоченные списки PAGEREF _Toc3148936 \h 37

Связные списки PAGEREF _Toc3148937 \h 41

Добавление элементов к связному списку PAGEREF _Toc3148938 \h 43

Удаление элементов из связного списка PAGEREF _Toc3148939 \h 44

Уничтожение связного списка PAGEREF _Toc3148940 \h 44

Сигнальные метки PAGEREF _Toc3148941 \h 45

Инкапсуляция связных списков PAGEREF _Toc3148942 \h 46

Доступ к ячейкам PAGEREF _Toc3148943 \h 47

Разновидности связных списков PAGEREF _Toc3148944 \h 49

Циклические связные списки PAGEREF _Toc3148945 \h 49

Проблема циклических ссылок PAGEREF _Toc3148946 \h 50

Двусвязные списки PAGEREF _Toc3148947 \h 50

Потоки PAGEREF _Toc3148948 \h 53

Другие связные структуры PAGEREF _Toc3148949 \h 56

Псевдоуказатели PAGEREF _Toc3148950 \h 56

Резюме PAGEREF _Toc3148951 \h 59

Глава 3. Стеки и очереди PAGEREF _Toc3148952 \h 60

Стеки PAGEREF _Toc3148953 \h 60

Множественные стеки PAGEREF _Toc3148954 \h 62

Очереди PAGEREF _Toc3148955 \h 63

Циклические очереди PAGEREF _Toc3148956 \h 65

Очереди на основе связных списков PAGEREF _Toc3148957 \h 69

Применение коллекций в качестве очередей PAGEREF _Toc3148958 \h 70

Приоритетные очереди PAGEREF _Toc3148959 \h 70

Многопоточные очереди PAGEREF _Toc3148960 \h 72

Резюме PAGEREF _Toc3148961 \h 74

Глава 4. Массивы PAGEREF _Toc3148962 \h 75

Треугольные массивы PAGEREF _Toc3148963 \h 75

Диагональные элементы PAGEREF _Toc3148964 \h 77

Нерегулярные массивы PAGEREF _Toc3148965 \h 78

Прямая звезда PAGEREF _Toc3148966 \h 78

Нерегулярные связные списки PAGEREF _Toc3148967 \h 79

Разреженные массивы PAGEREF _Toc3148968 \h 80

Индексирование массива PAGEREF _Toc3148969 \h 82

Очень разреженные массивы PAGEREF _Toc3148970 \h 85

Резюме PAGEREF _Toc3148971 \h 86

Глава 5. Рекурсия PAGEREF _Toc3148972 \h 86

Что такое рекурсия? PAGEREF _Toc3148973 \h 87

Рекурсивное вычисление факториалов PAGEREF _Toc3148974 \h 88

Анализ времени выполнения программы PAGEREF _Toc3148975 \h 89

Рекурсивное вычисление наибольшего общего делителя PAGEREF _Toc3148976
\h 90

Анализ времени выполнения программы PAGEREF _Toc3148977 \h 91

Рекурсивное вычисление чисел Фибоначчи PAGEREF _Toc3148978 \h 92

Анализ времени выполнения программы PAGEREF _Toc3148979 \h 93

Рекурсивное построение кривых Гильберта PAGEREF _Toc3148980 \h 94

Анализ времени выполнения программы PAGEREF _Toc3148981 \h 96

Рекурсивное построение кривых Серпинского PAGEREF _Toc3148982 \h 98

Анализ времени выполнения программы PAGEREF _Toc3148983 \h 100

Опасности рекурсии PAGEREF _Toc3148984 \h 101

Бесконечная рекурсия PAGEREF _Toc3148985 \h 101

Потери памяти PAGEREF _Toc3148986 \h 102

Необоснованное применение рекурсии PAGEREF _Toc3148987 \h 103

Когда нужно использовать рекурсию PAGEREF _Toc3148988 \h 104

Хвостовая рекурсия PAGEREF _Toc3148989 \h 105

Нерекурсивное вычисление чисел Фибоначчи PAGEREF _Toc3148990 \h 107

Устранение рекурсии в общем случае PAGEREF _Toc3148991 \h 110

Нерекурсивное построение кривых Гильберта PAGEREF _Toc3148992 \h 114

Нерекурсивное построение кривых Серпинского PAGEREF _Toc3148993 \h
117

Резюме PAGEREF _Toc3148994 \h 121

Глава 6. Деревья PAGEREF _Toc3148995 \h 121

Определения PAGEREF _Toc3148996 \h 122

Представления деревьев PAGEREF _Toc3148997 \h 123

Полные узлы PAGEREF _Toc3148998 \h 123

Списки потомков PAGEREF _Toc3148999 \h 124

Представление нумерацией связей PAGEREF _Toc3149000 \h 126

Полные деревья PAGEREF _Toc3149001 \h 129

Обход дерева PAGEREF _Toc3149002 \h 130

Упорядоченные деревья PAGEREF _Toc3149003 \h 135

Добавление элементов PAGEREF _Toc3149004 \h 135

Удаление элементов PAGEREF _Toc3149005 \h 136

Обход упорядоченных деревьев PAGEREF _Toc3149006 \h 139

Деревья со ссылками PAGEREF _Toc3149007 \h 141

Работа с деревьями со ссылками PAGEREF _Toc3149008 \h 144

Квадродеревья PAGEREF _Toc3149009 \h 145

Изменение MAX_PER_NODE PAGEREF _Toc3149010 \h 151

Использование псевдоуказателей в квадродеревьях PAGEREF _Toc3149011 \h
151

Восьмеричные деревья PAGEREF _Toc3149012 \h 152

Резюме PAGEREF _Toc3149013 \h 152

Глава 7. Сбалансированные деревья PAGEREF _Toc3149014 \h 153

Сбалансированность дерева PAGEREF _Toc3149015 \h 153

АВЛ-деревья PAGEREF _Toc3149016 \h 154

Удаление узла из АВЛ-дерева PAGEREF _Toc3149017 \h 161

Б-деревья PAGEREF _Toc3149018 \h 166

Производительность Б-деревьев PAGEREF _Toc3149019 \h 167

Вставка элементов в Б-дерево PAGEREF _Toc3149020 \h 167

Удаление элементов из Б-дерева PAGEREF _Toc3149021 \h 168

Разновидности Б-деревьев PAGEREF _Toc3149022 \h 169

Улучшение производительности Б-деревьев PAGEREF _Toc3149023 \h 171

Балансировка для устранения разбиения блоков PAGEREF _Toc3149024 \h
171

Вопросы, связанные с обращением к диску PAGEREF _Toc3149025 \h 173

База данных на основе Б+дерева PAGEREF _Toc3149026 \h 176

Резюме PAGEREF _Toc3149027 \h 179

Глава 8. Деревья решений PAGEREF _Toc3149028 \h 179

Поиск в деревьях игры PAGEREF _Toc3149029 \h 180

Минимаксный поиск PAGEREF _Toc3149030 \h 181

Улучшение поиска в дереве игры PAGEREF _Toc3149031 \h 185

Поиск в других деревьях решений PAGEREF _Toc3149032 \h 187

Метод ветвей и границ PAGEREF _Toc3149033 \h 187

Эвристики PAGEREF _Toc3149034 \h 191

Другие сложные задачи PAGEREF _Toc3149035 \h 207

Задача о выполнимости PAGEREF _Toc3149036 \h 207

Задача о разбиении PAGEREF _Toc3149037 \h 208

Задача поиска Гамильтонова пути PAGEREF _Toc3149038 \h 209

Задача коммивояжера PAGEREF _Toc3149039 \h 210

Задача о пожарных депо PAGEREF _Toc3149040 \h 211

Краткая характеристика сложных задач PAGEREF _Toc3149041 \h 212

Резюме PAGEREF _Toc3149042 \h 212

Глава 9. Сортировка PAGEREF _Toc3149043 \h 213

Общие соображения PAGEREF _Toc3149044 \h 213

Таблицы указателей PAGEREF _Toc3149045 \h 213

Объединение и сжатие ключей PAGEREF _Toc3149046 \h 215

Примеры программ PAGEREF _Toc3149047 \h 217

Сортировка выбором PAGEREF _Toc3149048 \h 219

Рандомизация PAGEREF _Toc3149049 \h 220

Сортировка вставкой PAGEREF _Toc3149050 \h 221

Вставка в связных списках PAGEREF _Toc3149051 \h 222

Пузырьковая сортировка PAGEREF _Toc3149052 \h 224

Быстрая сортировка PAGEREF _Toc3149053 \h 227

Сортировка слиянием PAGEREF _Toc3149054 \h 232

Пирамидальная сортировка PAGEREF _Toc3149055 \h 234

Пирамиды PAGEREF _Toc3149056 \h 235

Приоритетные очереди PAGEREF _Toc3149057 \h 237

Алгоритм пирамидальной сортировки PAGEREF _Toc3149058 \h 240

Сортировка подсчетом PAGEREF _Toc3149059 \h 241

Блочная сортировка PAGEREF _Toc3149060 \h 242

Блочная сортировка с применением связного списка PAGEREF _Toc3149061
\h 243

Блочная сортировка на основе массива PAGEREF _Toc3149062 \h 245

Резюме PAGEREF _Toc3149063 \h 248

Глава 10. Поиск PAGEREF _Toc3149064 \h 248

Примеры программ PAGEREF _Toc3149065 \h 249

Поиск методом полного перебора PAGEREF _Toc3149066 \h 249

Поиск в упорядоченных списках PAGEREF _Toc3149067 \h 250

Поиск в связных списках PAGEREF _Toc3149068 \h 251

Двоичный поиск PAGEREF _Toc3149069 \h 253

Интерполяционный поиск PAGEREF _Toc3149070 \h 255

Строковые данные PAGEREF _Toc3149071 \h 259

Следящий поиск PAGEREF _Toc3149072 \h 260

Интерполяционный следящий поиск PAGEREF _Toc3149073 \h 261

Резюме PAGEREF _Toc3149074 \h 262

Глава 11. Хеширование PAGEREF _Toc3149075 \h 263

Связывание PAGEREF _Toc3149076 \h 265

Преимущества и недостатки связывания PAGEREF _Toc3149077 \h 266

Блоки PAGEREF _Toc3149078 \h 268

Хранение хеш-таблиц на диске PAGEREF _Toc3149079 \h 270

Связывание блоков PAGEREF _Toc3149080 \h 274

Удаление элементов PAGEREF _Toc3149081 \h 275

Преимущества и недостатки применения блоков PAGEREF _Toc3149082 \h
277

Открытая адресация PAGEREF _Toc3149083 \h 277

Линейная проверка PAGEREF _Toc3149084 \h 278

Квадратичная проверка PAGEREF _Toc3149085 \h 284

Псевдослучайная проверка PAGEREF _Toc3149086 \h 286

Удаление элементов PAGEREF _Toc3149087 \h 289

Резюме PAGEREF _Toc3149088 \h 291

Глава 12. Сетевые алгоритмы PAGEREF _Toc3149089 \h 292

Определения PAGEREF _Toc3149090 \h 292

Представления сети PAGEREF _Toc3149091 \h 293

Оперирование узлами и связями PAGEREF _Toc3149092 \h 295

Обходы сети PAGEREF _Toc3149093 \h 296

Наименьшие остовные деревья PAGEREF _Toc3149094 \h 298

Кратчайший маршрут PAGEREF _Toc3149095 \h 302

Установка меток PAGEREF _Toc3149096 \h 304

Коррекция меток PAGEREF _Toc3149097 \h 308

Другие задачи поиска кратчайшего маршрута PAGEREF _Toc3149098 \h 311

Применения метода поиска кратчайшего маршрута PAGEREF _Toc3149099 \h
316

Максимальный поток PAGEREF _Toc3149100 \h 319

Приложения максимального потока PAGEREF _Toc3149101 \h 325

Резюме PAGEREF _Toc3149102 \h 327

Глава 13. Объектно-ориентированные методы PAGEREF _Toc3149103 \h 327

Преимущества ООП PAGEREF _Toc3149104 \h 328

Инкапсуляция PAGEREF _Toc3149105 \h 328

Полиморфизм PAGEREF _Toc3149106 \h 330

Наследование и повторное использование PAGEREF _Toc3149107 \h 333

Парадигмы ООП PAGEREF _Toc3149108 \h 335

Управляющие объекты PAGEREF _Toc3149109 \h 335

Контролирующий объект PAGEREF _Toc3149110 \h 336

Итератор PAGEREF _Toc3149111 \h 337

Дружественный класс PAGEREF _Toc3149112 \h 338

Интерфейс PAGEREF _Toc3149113 \h 340

Фасад PAGEREF _Toc3149114 \h 340

Порождающий объект PAGEREF _Toc3149115 \h 340

Единственный объект PAGEREF _Toc3149116 \h 341

Преобразование в последовательную форму PAGEREF _Toc3149117 \h 341

Парадигма Модель/Вид/Контроллер. PAGEREF _Toc3149118 \h 344

Резюме PAGEREF _Toc3149119 \h 346

Требования к аппаратному обеспечению PAGEREF _Toc3149120 \h 346

Выполнение программ примеров PAGEREF _Toc3149121 \h 346

HYPERLINK mailto:prog[email protected] [email protected]

Далее следует «текст», который любой уважающий себя программист должен
прочесть хотя бы один раз. (Это наше субъективное мнение)

Введение

Программирование под Windows всегда было нелегкой задачей. Интерфейс
прикладного программирования (Application Programming Interface) Windows
предоставляет в распоряжение программиста набор мощных, но не всегда
безопасных инструментов для разработки приложений. Можно сравнить его с
бульдозером, при помощи которого удается добиться поразительных
результатов, но без соответствующих навыков и осторожности, скорее
всего, дело закончится только разрушениями и убытками.

Эта картина изменилась с появлением Visual Basic. Используя визуальный
интерфейс, Visual Basic позволяет быстро и легко разрабатывать
законченные приложения. При помощи Visual Basic можно разрабатывать и
тестировать сложные приложения без прямого использования функций API.
Избавляя программиста от проблем с API, Visual Basic позволяет
сконцентрироваться на деталях приложения.

Хотя Visual Basic и облегчает разработку пользовательского интерфейса,
задача написания кода для реакции на входные воздействия, обработки их,
и представления результатов ложится на плечи программиста. Здесь
начинается применение алгоритмов.

Алгоритмы представляют собой формальные инструкции для выполнения
сложных задач на компьютере. Например, алгоритм сортировки может
определять, как найти конкретную запись в базе из 10 миллионов записей.
В зависимости от класса используемых алгоритмов искомые данные могут
быть найдены за секунды, часы или вообще не найдены.

В этом материале обсуждаются алгоритмы на Visual Basic и содержится
большое число мощных алгоритмов, полностью написанных на этом языке. В
ней также анализируются методы обращения со структурами данных, такими,
как списки, стеки, очереди и деревья, и алгоритмы для выполнения
типичных задач, таких как сортировка, поиск и хэширование.

Для того чтобы успешно применять эти алгоритмы, недостаточно их просто
скопировать в свою программу. Необходимо кроме этого понимать, как
различные алгоритмы ведут себя в разных ситуациях, что в конечном итоге
и будет определять выбор наиболее подходящего алгоритма.

В этом материале поведение алгоритмов в типичном и наихудшем случаях
описано доступным языком. Это позволит понять, чего вы вправе ожидать от
того или иного алгоритма и распознать, в каких условиях встречается
наихудший случай, и в соответствии с этим переписать или поменять
алгоритм. Даже самый лучший алгоритм не поможет в решении задачи, если
применять его неправильно.

=============xi

Все алгоритмы также представлены в виде исходных текстов на Visual
Basic, которые вы можете использовать в своих программах без каких-либо
изменений. Они демонстрируют использование алгоритмов в программах, а
также важные характерные особенности работы самих алгоритмов.

Что дают вам эти знания

После ознакомления с данным материалом и примерами вы получите:

Понятие об алгоритмах. После прочтения данного материала и выполнения
примеров программ, вы сможете применять сложные алгоритмы в своих
проектах на Visual Basic и критически оценивать другие алгоритмы,
написанные вами или кем-либо еще.

Большую подборку исходных текстов, которые вы сможете легко добавить к
вашим программам. Используя код, содержащийся в примерах, вы сможете
легко добавлять мощные алгоритмы к вашим приложениям.

Готовые примеры программ дадут вам возможность протестировать алгоритмы.
Вы можете использовать эти примеры и модифицировать их для углубленного
изучения алгоритмов и понимания их работы, или использовать их как
основу для разработки собственных приложений.

Целевая аудитория

В этом материале обсуждаются углубленные вопросы программирования на
Visual Basic. Они не предназначена для обучения программированию на этом
языке. Если вы хорошо разбираетесь в основах программирования на Visual
Basic, вы сможете сконцентрировать внимание на алгоритмах вместо того,
чтобы застревать на деталях языка.

В этом материале изложены важные концепции программирования, которые
могут быть с успехом применены для решения новых задач. Приведенные
алгоритмы используют мощные программные методы, такие как рекурсия,
разбиение на части, динамическое распределение памяти и сетевые
структуры данных, которые вы можете применять для решения своих
конкретных задач.

Даже если вы еще не овладели в полной мере программированием на Visual
Basic, вы сможете скомпилировать примеры программ и сравнить
производительность различных алгоритмов. Более того, вы сможете выбрать
удовлетворяющие вашим требованиям алгоритмы и добавить их к вашим
проектам на Visual Basic.

Совместимость с разными версиями Visual Basic

Выбор наилучшего алгоритма определяется не особенностями версии языка
программирования, а фундаментальными принципами программирования.

=================xii

Некоторые новые понятия, такие как ссылки на объекты, классы и
коллекции, которые были впервые введены в 4-й версии Visual Basic,
облегчают понимание, разработку и отладку некоторых алгоритмов. Классы
могут заключать некоторые алгоритмы в хорошо продуманных модулях,
которые легко вставить в программу. Хотя для того, чтобы применять эти
алгоритмы, необязательно разбираться в новых понятиях языка, эти новые
возможности предоставляют слишком большие преимущества, чтобы ими можно
было пренебречь.

Поэтому примеры алгоритмов в этом материале написаны для использования в
4-й и 5-й версиях Visual. Если вы откроете их в 5-й версии Visual Basic,
среда разработки предложит вам сохранить их в формате 5-й версии, но
никаких изменений в код вносить не придется. Все алгоритмы были
протестированы в обеих версиях.

Эти программы демонстрируют использование алгоритмов без применения
объектно-ориентированного подхода. Ссылки и коллекции облегчают
программирование, но их применение может приводить к некоторому
замедлению работы программ по сравнению со старыми версиями.

Тем не менее, игнорирование классов, объектов и коллекций привело бы к
упущению многих действительно мощных свойств. Их использование позволяет
достичь нового уровня модульности, разработки и повторного использования
кода. Их, безусловно, необходимо иметь в виду, по крайней мере, на
начальных этапах разработки. В дальнейшем, если возникнут проблемы с
производительностью, вы сможете модифицировать код, используя более
быстрые низкоуровневые методы.

Языки программирования зачастую развиваются в сторону усложнения, но
редко в противоположном направлении. Замечательным примером этого
является наличие оператора goto в языке C. Это неудобный оператор,
потенциальный источник ошибок, который почти не используется
большинством программистов на C, но он по-прежнему остается в синтаксисе
языка с 1970 года. Он даже был включен в C++ и позднее в Java, хотя
создание нового языка было хорошим предлогом избавиться от него.

Так и новые версии Visual Basic будут продолжать вводить новые свойства
в язык, но маловероятно, что из них будут исключены строительные блоки,
использованные при применении алгоритмов, описанных в данном материале.
Независимо от того, что будет добавлено в 6-й, 7-й или 8-й версии Visual
Basic, классы, массивы и определяемые пользователем типы данных
останутся в языке. Большая часть, а может и все алгоритмы из приведенных
ниже, будут выполняться без изменений в течение еще многих лет.

Обзор глав

В 1 главе рассматриваются понятия, которые вы должны понимать до того,
как приступить к анализу сложных алгоритмов. В ней изложены методы,
которые потребуются для теоретического анализа вычислительной сложности
алгоритмов. Некоторые алгоритмы с высокой теоретической
производительностью на практике дают не очень хорошие результаты,
поэтому в этой главе также затрагиваются практические соображения,
например обращение к файлу подкачки и сравнивается использование
коллекций и массивов.

Во 2 главе показано, как образуются различные виды списков с
использованием массивов, объектов, и псевдоуказателей. Эти структуры
данных можно с успехом применять во многих программах, и они
используются в следующих главах

В 3 главе описаны два особых типа списков: стеки и очереди. Эти
структуры данных используются во многих алгоритмах, включая некоторые
алгоритмы, описанные в последующих главах. В конце главы приведена
модель очереди на регистрацию в аэропорту.

В 5 главе обсуждается мощный инструмент — рекурсия. Рекурсия может быть
также запутанной и приводить к проблемам. В 5 главе объясняется, в каких
случаях следует применять рекурсию и показывает, как можно от нее
избавиться, если это необходимо.

В 6 главе используются многие из ранее описанных приемов, такие как
рекурсия и связные списки, для изучения более сложной темы — деревьев.
Эта глава также охватывает различные представления деревьев, такие как
деревья с XE “Деревья:с полными узлами” полными узлами (fat node XE
“fat node” ) и представление в виде XE “Деревья:представление
нумерацией связей” нумерацией связей (forward star XE “forward star”
). В ней также описаны некоторые важные алгоритмы работы с деревьями,
таки как обход вершин дерева.

В 7 главе затронута более сложная тема. Сбалансированные деревья
обладают особыми свойствами, которые позволяют им оставаться
уравновешенными и эффективными. Алгоритмы сбалансированных деревьев
удивительно просто описываются, но их достаточно трудно реализовать
программно. В этой главе используется одна из наиболее мощных структур
подобного типа — XE “Деревья:Б+деревья” Б+дерево (B+Tree XE “B+Tree”
) для создания сложной базы данных.

В 8 главе обсуждаются задачи, которые можно описать как поиск ответов в
дереве решений. Даже для небольших задач, эти деревья могут быть
гигантскими, поэтому необходимо осуществлять поиск в них максимально
эффективно. В этой главе сравниваются некоторые различные методы,
которые позволяют выполнить такой поиск.

Глава 9 посвящена, пожалуй, наиболее изучаемой области теории
алгоритмов — сортировке. Алгоритмы сортировки интересны по нескольким
причинам. Во-первых, сортировка — часто встречающаяся задача. Во-вторых,
различные алгоритмы сортировок обладают своими сильными и слабыми
сторонами, поэтому не существует одного алгоритма, который показывал бы
наилучшие результаты в любых ситуациях. И, наконец, алгоритмы сортировки
демонстрируют широкий спектр важных алгоритмических методов, таких как
рекурсия, пирамиды, а также использование генератора случайных чисел для
уменьшения вероятности выпадения наихудшего случая.

В главе 10 рассматривается близкая к сортировке тема. После выполнения
сортировки списка, программе может понадобиться найти элементы в нем. В
этой главе сравнивается несколько наиболее эффективных методов поиска
элементов в сортированных списках.

=========xiv

В главе 11 обсуждаются методы сохранения и поиска элементов, работающие
даже быстрее, чем это возможно при использовании деревьев, сортировки
или поиска. В этой главе также описаны некоторые методы хэширования,
включая использование блоков и связных списков, и несколько вариантов
открытой адресации.

В главе 12 описана другая категория алгоритмов — сетевые алгоритмы.
Некоторые из этих алгоритмов, такие как вычисление кратчайшего пути,
непосредственно применимы к физическим сетям. Эти алгоритмы также могут
косвенно применяться для решения других задач, которые на первый взгляд
не кажутся связанными с сетями. Например, алгоритмы поиска кратчайшего
расстояния могут разбивать сеть на районы или определять критичные
задачи в расписании проекта.

В главе 13 объясняются методы, применение которых стало возможным
благодаря введению классов в 4-й версии Visual Basic. Эти методы
используют объектно-ориентированный подход для реализации нетипичного
для традиционных алгоритмов поведения.

===================xv

Аппаратные требования

Для работы с примерами вам потребуется компьютер, конфигурация которого
удовлетворяет требованиям для работы программной среды Visual Basic. Эти
требования выполняются почти для всех компьютеров, на которых может
работать операционная система Windows.

На компьютерах разной конфигурации алгоритмы выполняются с различной
скоростью. Компьютер с процессором Pentium Pro с тактовой частотой 2000
МГц и 64 Мбайт оперативной памяти будет работать намного быстрее, чем
машина с 386 процессором и всего 4 Мбайт памяти. Вы быстро узнаете, на
что способно ваше аппаратное обеспечение.

Изменения во втором издании

Самое большое изменение в новой версии Visual Basic — это появление
классов. Классы позволяют рассмотреть некоторые задачи с другой стороны,
позволяя использовать более простой и естественный подход к пониманию и
применению многих алгоритмов. Изменения в коде программ в этом изложении
используют преимущества, предоставляемые классами. Их можно разбить на
три категории:

Замена псевдоуказателей классами. Хотя все алгоритмы, которые были
написаны для старых версий VB, все еще работают, многие из тех, что были
написаны с применением псевдоуказателей (описанных во 2 главе), гораздо
проще понять, используя классы.

Инкапсуляция. Классы позволяют заключить алгоритм в компактный модуль,
который легко использовать в программе. Например, при помощи классов
можно создать несколько связных списков и не писать при этом
дополнительный код для управления каждым списком по отдельности.

Объектно-ориентированные технологии. Использование классов также
позволяет легче понять некоторые объектно-ориентированные алгоритмы. В
главе 13 описываются методы, которые сложно реализовать без
использования классов.

Как пользоваться этим материалом

В главе 1 даются общие понятия, которые используются на протяжении всего
изложения, поэтому вам следует начать чтение с этой главы. Вам стоит
ознакомиться с этой тематикой, даже если вы не хотите сразу же достичь
глубокого понимания алгоритмов.

В 6 главе обсуждаются понятия, которые используются в 7, 8 и 12 главах,
поэтому вам следует прочитать 6 главу до того, как браться за них.
Остальные главы можно читать в любом порядке.

=============xvi

В табл. 1 показаны три возможных учебных плана, которыми вы можете
руководствоваться при изучении материала в зависимости от того,
насколько широко вы хотите ознакомиться с алгоритмами. Первый план
включает в себя освоение основных методов и структур данных, которые
могут быть полезны при разработке вами собственных программ. Второй
кроме этого описывает также основные алгоритмы, такие как алгоритмы
сортировки и поиска, которые могут понадобиться при написании более
сложных программ.

Последний план дает порядок для изучения всего материала целиком. Хотя 7
и 8 главы логически вытекают из 6 главы, они сложнее для изучения, чем
следующие главы, поэтому они изучаются несколько позже.

Почему именно Visual Basic?

Наиболее часто встречаются жалобы на медленное выполнение программ,
написанных на Visual Basic. Многие другие компиляторы, такие как Delphi,
Visual C++ дают более быстрый и гибкий код, и предоставляют программисту
более мощные средства, чем Visual Basic. Поэтому логично задать вопрос —
«Почему я должен использовать именно Visual Basic для написания сложных
алгоритмов? Не лучше было бы использовать Delphi или C++ или, по крайней
мере, написать алгоритмы на одном из этих языков и подключать их к
программам на Visual Basic при помощи библиотек?» Написание алгоритмов
на Visual Basic имеет смысл по нескольким причинам.

Во-первых, разработка приложения на Visual C++ гораздо сложнее и
проблематичнее, чем на Visual Basic. Некорректная реализация в программе
всех деталей программирования под Windows может привести к сбоям в вашем
приложении, среде разработки, или в самой операционной системе Windows.

Во-вторых, разработка библиотеки на языке C++ для использования в
программах на Visual Basic включает в себя много потенциальных
опасностей, характерных и для приложений Windows, написанных на C++.
Если библиотека будет неправильно взаимодействовать с программой на
Visual Basic, она также приведет к сбоям в программе, а возможно и в
среде разработки и системе.

В-третьих, многие алгоритмы достаточно эффективны и показывают неплохую
производительность даже при применении не очень быстрых компиляторов,
таких, как Visual Basic. Например, алгоритм сортировки подсчетом,

@Таблица 1. Планы занятий

===============xvii

описываемый в 9 главе, сортирует миллион целых чисел менее чем за 2
секунды на компьютере с процессором Pentium с тактовой частотой 233 МГц.
Используя библиотеку C++, можно было бы сделать алгоритм немного
быстрее, но скорости версии на Visual Basic и так хватает для
большинства приложений. Скомпилированные при помощи 5-й версией Visual
Basic исполняемые файлы сводят отставание по скорости к минимуму.

В конечном счете, разработка алгоритмов на любом языке программирования
позволяет больше узнать об алгоритмах вообще. По мере изучения
алгоритмов, вы освоите методы, которые сможете применять в других частях
своих программ. После того, как вы овладеете в совершенстве алгоритмами
на Visual Basic, вам будет гораздо легче реализовать их на Delphi или
C++, если это будет необходимо.

=============xviii

Глава 1. Основные понятия

В этой главе содержатся общие понятия, которые нужно усвоить перед
началом серьезного изучения алгоритмов. Начинается она с вопроса «Что
такое алгоритмы?». Прежде чем углубиться в детали программирования
алгоритмов, стоит потратить немного времени, чтобы разобраться в том,
что это такое.

Затем в этой главе дается введение в формальную XE “Теория:сложности
алгоритмов” теорию сложности алгоритмов (complexity theory XE
“complexity theory” ). При помощи этой теории можно оценить
теоретическую вычислительную сложность алгоритмов. Этот подход позволяет
сравнивать различные алгоритмы и предсказывать их производительность в
разных условиях. В главе приводится несколько примеров применения теории
сложности к небольшим задачам.

Некоторые алгоритмы с высокой теоретической производительностью не
слишком хорошо работают на практике, поэтому в данной главе также
обсуждаются некоторые реальные предпосылки для создания программ.
Слишком частое обращение к файлу подкачки или плохое использование
ссылок на объекты и коллекции может значительно снизить
производительность прекрасного в остальных отношениях приложения.

После знакомства с основными понятиями, вы сможете применять их к
алгоритмам, изложенным в последующих главах, а также для анализа
собственных программ для оценки их производительности и сможете
предугадывать возможные проблемы до того, как они обернутся катастрофой.

Что такое алгоритмы?

Алгоритм – это последовательность инструкций для выполнения какого-либо
задания. Когда вы даете кому-то инструкции о том, как отремонтировать
газонокосилку, испечь торт, вы тем самым задаете алгоритм действий.
Конечно, подобные бытовые алгоритмы описываются неформально, например,
так:

Проверьте, находится ли машина на стоянке.

Убедитесь, что машина поставлена на ручной тормоз.

Поверните ключ.

И т.д.

==========1

При этом по умолчанию предполагается, что человек, который будет
следовать этим инструкциям, сможет самостоятельно выполнить множество
мелких операций, например, отпереть и открыть дверь, сесть за руль,
пристегнуть ремень, найти ручной тормоз и так далее.

Если же составляется алгоритм для исполнения компьютером, вы не можете
полагаться на то, что компьютер поймет что-либо, если это не описано
заранее. Словарь компьютера (язык программирования) очень ограничен и
все инструкции для компьютера должны быть сформулированы на этом языке.
Поэтому для написания компьютерных алгоритмов используется
формализованный стиль.

Интересно попробовать написать формализованный алгоритм для обычных
ежедневных задач. Например, алгоритм вождения машины мог бы выглядеть
примерно так:

Если дверь закрыта:

Вставить ключ в замок

Повернуть ключ

Если дверь остается закрытой, то:

Повернуть ключ в другую сторону

Повернуть ручку двери

И т.д.

Этот фрагмент «кода» отвечает только за открывание двери; при этом даже
не проверяется, какая дверь открывается. Если дверь заело или в машине
установлена противоугонная система, то алгоритм открывания двери может
быть достаточно сложным.

Формализацией алгоритмов занимаются уже тысячи лет. За 300 лет до н.э.
Евклид написал алгоритмы деления углов пополам, проверки равенства
треугольников и решения других геометрических задач. Он начал с
небольшого словаря аксиом, таких как «параллельные линии не
пересекаются» и построил на их основе алгоритмы для решения сложных
задач.

Формализованные алгоритмы такого типа хорошо подходят для задач
математики, где должна быть доказана истинность какого-либо положения
или возможность выполнения каких-то действий, скорость же исполнения
алгоритма не важна. Для выполнения реальных задач, связанных с
выполнением инструкций, например задачи сортировки на компьютере записей
о миллионе покупателей, эффективность выполнения становится важной
частью постановки задачи.

Анализ скорости выполнения алгоритмов

Есть несколько способов оценки сложности алгоритмов. Программисты обычно
сосредотачивают внимание на скорости алгоритма, но важны и другие
требования, например, к размеру памяти, свободному месту на диске или
другим ресурсам. От быстрого алгоритма может быть мало толку, если под
него требуется больше памяти, чем установлено на компьютере.

Многие алгоритмы предоставляют выбор между скоростью выполнения и
используемыми программой ресурсами. Задача может выполняться

быстрее, используя больше памяти, или наоборот, медленнее, заняв меньший
объем памяти.

===========2

Хорошим примером в данном случае может служить алгоритм нахождения
кратчайшего пути. Задав карту улиц города в виде сети, можно написать
алгоритм, вычисляющий кратчайшее расстояние между любыми двумя точками в
этой сети. Вместо того чтобы каждый раз заново пересчитывать кратчайшее
расстояние между двумя заданными точками, можно заранее просчитать его
для всех пар точек и сохранить результаты в таблице. Тогда, чтобы найти
кратчайшее расстояние для двух заданных точек, достаточно будет просто
взять готовое значение из таблицы.

При этом мы получим результат практически мгновенно, но это потребует
большого объема памяти. Карта улиц для большого города, такого как
Бостон или Денвер, может содержать сотни тысяч точек. Для такой сети
таблица кратчайших расстояний содержала бы более 10 миллиардов записей.
В этом случае выбор между временем исполнения и объемом требуемой памяти
очевиден: поставив дополнительные 10 гигабайт оперативной памяти, можно
заставить программу выполняться гораздо быстрее.

Из этой связи вытекает идея пространственно-временной сложности
алгоритмов. При этом подходе сложность алгоритма оценивается в терминах
времени и пространства, и находится компромисс между ними.

В этом материале основное внимание уделяется временной сложности, но мы
также постарались обратить внимание и на особые требования к объему
памяти для некоторых алгоритмов. Например, сортировка слиянием
(mergesort), обсуждаемая в 9 главе, требует больше временной памяти.
Другие алгоритмы, например пирамидальная сортировка (heapsort), которая
также обсуждается в 9 главе, требует обычного объема памяти.

Оценка с точностью до порядка

При сравнении различных алгоритмов важно понимать, как сложность
алгоритма соотносится со сложностью решаемой задачи. При расчетах по
одному алгоритму сортировка тысячи чисел может занять 1 секунду, а
сортировка миллиона — 10 секунд, в то время как расчеты по другому
алгоритму могут потребовать 2 и 5 секунд соответственно. В этом случае
нельзя однозначно сказать, какая из двух программ лучше — это будет
зависеть от исходных данных.

Различие производительности алгоритмов на задачах разной вычислительной
сложности часто более важно, чем просто скорость алгоритма. В
вышеприведенном случае, первый алгоритм быстрее сортирует короткие
списки, а второй — длинные.

Производительность алгоритма можно оценить по порядку величины. Алгоритм
имеет сложность порядка O(f(N)) (произносится «О большое от F от N»),
если время выполнения алгоритма растет пропорционально функции f(N) с
увеличением размерности исходных данных N. Например, рассмотрим фрагмент
кода, сортирующий положительные числа:

For I = 1 To N

‘Поиск наибольшего элемента в списке.

MaxValue = 0

For J = 1 to N

If Value(J) > MaxValue Then

MaxValue = Value(J)

MaxJ = J

End If

Next J

‘Вывод наибольшего элемента на печать.

Print Format$(MaxJ) & “:” & Str$(MaxValue)

‘Обнуление элемента для исключения его из дальнейшего поиска.

Value(MaxJ) = 0

Next I

===============3

В этом алгоритме переменная цикла I последовательно принимает значения
от 1 до N. Для каждого приращения I переменная J в свою очередь также
принимает значения от 1 до N. Таким образом, в каждом внешнем цикле
выполняется еще N внутренних циклов. В итоге внутренний цикл выполняется
N*N или N2 раз и, следовательно, сложность алгоритма порядка O(N2).

При оценке порядка сложности алгоритмов используется только наиболее
быстро растущая часть уравнения алгоритма. Допустим, время выполнения
алгоритма пропорционально N3+N. Тогда сложность алгоритма будет равна
O(N3). Отбрасывание медленно растущих частей уравнения позволяет оценить
поведение алгоритма при увеличении размерности данных задачи N.

При больших N вклад второй части в уравнение N3+N становится все менее
заметным. При N=100, разность N3+N=1.000.100 и N3 равна всего 100, или
менее чем 0,01 процента. Но это верно только для больших N. При N=2,
разность между N3+N =10 и N3=8 равна 2, а это уже 20 процентов.

Постоянные множители в соотношении также игнорируются. Это позволяет
легко оценить изменения в вычислительной сложности задачи. Алгоритм,
время выполнения которого пропорционально 3*N2, будет иметь порядок
O(N2). Если увеличить N в 2 раза, то время выполнения задачи возрастет
примерно в 22, то есть в 4 раза.

Игнорирование постоянных множителей позволяет также упростить подсчет
числа шагов алгоритма. В предыдущем примере внутренний цикл выполняется
N2 раз, при этом внутри цикла выполняется несколько инструкций. Можно
просто подсчитать число инструкций If, можно подсчитать также
инструкции, выполняемые внутри цикла или, кроме того, еще и инструкции
во внешнем цикле, например операторы Print.

Вычислительная сложность алгоритма при этом будет пропорциональна N2,
3*N2 или 3*N2+N. Оценка сложности алгоритма по порядку величины даст
одно и то же значение O(N3) и отпадет необходимость в точном подсчете
количества операторов.

Поиск сложных частей алгоритма

Обычно наиболее сложным является выполнение циклов и вызовов процедур. В
предыдущем примере, весь алгоритм заключен в двух циклах.

============4

Если процедура вызывает другую процедуру, необходимо учитывать сложность
вызываемой процедуры. Если в ней выполняется фиксированное число
инструкций, например, осуществляется вывод на печать, то при оценке
порядка сложности ее можно не учитывать. С другой стороны, если в
вызываемой процедуре выполняется O(N) шагов, она может вносить
значительный вклад в сложность алгоритма. Если вызов процедуры
осуществляется внутри цикла, этот вклад может быть еще больше.

Приведем в качестве примера программу, содержащую медленную процедуру
Slow со сложностью порядка O(N3) и быструю процедуру Fast со сложностью
порядка O(N2). Сложность всей программы будет зависеть от соотношения
между этими двумя процедурами.

Если процедура Slow вызывается в каждом цикле процедуры Fast, порядки
сложности процедур перемножаются. В этом случае сложность алгоритма
равна произведению O(N2) и O(N3) или O(N3*N2)=O(N5). Приведем
иллюстрирующий этот случай фрагмент кода:

Sub Slow()

Dim I As Integer

Dim J As Integer

Dim K As Integer

For I = 1 To N

For J = 1 To N

For K = 1 To N

‘ Выполнить какие-либо действия.

Next K

Next J

Next I

End Sub

Sub Fast()

Dim I As Integer

Dim J As Integer

Dim K As Integer

For I = 1 To N

For J = 1 To N

Slow ‘ Вызов процедуры Slow.

Next J

Next I

End Sub

Sub MainProgram()

Fast

End Sub

С другой стороны, если процедуры независимо вызываются из основной
программы, их вычислительная сложность суммируется. В этом случае полная
сложность будет равна O(N3)+O(N2)=O(N3). Такую сложность, например,
будет иметь следующий фрагмент кода:

Sub Slow()

Dim I As Integer

Dim J As Integer

Dim K As Integer

For I = 1 To N

For J = 1 To N

For K = 1 To N

‘ Выполнить какие-либо действия.

Next K

Next J

Next I

End Sub

Sub Fast()

Dim I As Integer

Dim J As Integer

For I = 1 To N

For J = 1 To N

‘ Выполнить какие-либо действия.

Next J

Next I

End Sub

Sub MainProgram()

Slow

Fast

End Sub

==============5

Сложность рекурсивных алгоритмов

XE “Процедура:рекурсивная” Рекурсивными процедурами (recursive
procedure XE “recursive procedure” ) называются процедуры, вызывающие
сами себя. Во многих рекурсивных алгоритмах именно степень вложенности
рекурсии определяет сложность алгоритма, при этом не всегда легко
оценить порядок сложности. Рекурсивная процедура может выглядеть
простой, но при этом вносить большой вклад в сложность программы,
многократно вызывая саму себя.

Следующий фрагмент кода содержит подпрограмму всего из двух операторов.
Тем не менее, для заданного N подпрограмма выполняется N раз, таким
образом, вычислительная сложность фрагмента порядка O(N).

Sub CountDown(N As Integer)

If N ArraySize Then

ArraySize = ArraySize + 10

ReDim Preserve List(1 To ArraySize)

End If

List(NumInList) = value

End Sub

‘ Удалить последний элемент из списка. Если осталось больше

‘ 20 пустых ячеек, уменьшить список, освобождая память.

Sub RemoveFromList()

NumInList = NumInList – 1

If ArraySize – NumInList > 20 Then

ArraySize = ArraySize –10

ReDim Preserve List(1 To ArraySize)

End If

End Sub

=============20

Для очень больших массивов это решение может также оказаться не самым
лучшим. Если вам нужен список, содержащий 1000 элементов, к которому
обычно добавляется по 100 элементов, то все еще слишком много времени
будет тратиться на изменение размера массива. Очевидной стратегией в
этом случае было бы увеличение приращения размера массива с 10 до 100
или более ячеек. Тогда можно было бы добавлять по 100 элементов
одновременно без частого изменения размера списка.

Более гибким решением будет изменение приращения в зависимости от
размера массива. Для небольших списков это приращение было бы также
небольшим. Хотя изменения размера массива происходили бы чаще, они
потребовали бы относительно немного времени для небольших массивов. Для
больших списков, приращение размера будет больше, поэтому их размер
будет изменяться реже.

Следующая программа пытается поддерживать примерно 10 процентов списка
свободным. Когда массив заполняется, его размер увеличивается на 10
процентов. Если свободное пространство составляет более 20 процентов от
размера массива, программа уменьшает его.

При увеличении размера массива, добавляется не меньше 10 элементов, даже
если 10 процентов от размера массива составляют меньшую величину. Это
уменьшает число необходимых изменений размера массива, если список очень
мал.

Const WANT_FREE_PERCENT = .1 ‘ 10% свободного места.

Const MIN_FREE = 10 ‘ Минимальное число пустых ячеек.

Global List() As String ‘ Массив элементов списка.

Global ArraySize As Integer ‘ Размер массива.

Global NumItems As Integer ‘ Число элементов в списке.

Global ShrinkWhen As Integer ‘ Уменьшить размер, если NumItems ArraySize Then ResizeList

List(NumItems) = value

End Sub

‘ Удалить последний элемент из списка.

‘ Если в массиве много пустых ячеек, уменьшить его размер.

Sub RemoveLast()

NumItems = NumItems – 1

If NumItems m_MaxGarbage Then CollectGarbage

End Sub

Программа Garbage демонстрирует этот метод чистки памяти. Она пишет
рядом с неиспользуемыми элементами списка слово «unused», а рядом с
помеченными как ненужные — слово «garbage». Программа использует класс
GarbageList примерно так же, как программа SimList использовала класс
SimpleList, но при этом она еще осуществляет «сборку мусора».

Чтобы добавить элемент к списку, введите его значение и нажмите на
кнопку Add (Добавить). Для удаления элемента выделите его, а затем
нажмите на кнопку Remove (Удалить). Если список содержит слишком много
«мусора», программа начнет выполнять чистку памяти.

При каждом изменении размера списка объекта GarbageList, программа
выводит окно сообщения, в котором приводится число используемых и
свободных элементов в списке, а также значения переменных MaxGarbage и
ShrinkWhen. Если удалить достаточное количество элементов, так что
больше, чем MaxGarbage элементов будут помечены как ненужные, программа
начнет выполнять чистку памяти. После ее окончания, программа уменьшает
размер массива, если он содержит меньше, чем ShrinkWhen занятых
элементов.

Если размер массива должен быть увеличен, программа Garbage добавляет к
массиву еще 50 процентов пустых ячеек, и всегда оставляет хотя бы одну
пустую ячейку при любом изменении размера массива. Эти значения были
выбраны для упрощения работы пользователя со списком. В реальной
программе процент свободной памяти должен быть меньше, а число свободных
ячеек — больше. Оптимальными выглядят значения порядка 10 процентов и 10
свободных ячеек.

==========26

Связные списки

Другая стратегия используется при управлении связанными списками.
Связанный список хранит элементы в структурах данных или объектах,
которые называются XE “Ячейка” ячейками (cells XE “cells” ). Каждая
ячейка содержит указатель на следующую ячейку в списке. Так как
единственный тип указателей, которые поддерживает Visual Basic — это
ссылки на объекты, то ячейки в связном списке должны быть объектами.

В классе, задающем ячейку, должна быть определена переменная NextCell,
которая указывает на следующую ячейку в списке. В нем также должны быть
определены переменные, содержащие данные, с которыми будет работать
программа. Эти переменные могут быть объявлены как открытые (public)
внутри класса, или класс может содержать процедуры для чтения и записи
значений этих переменных. Например, в связном списке с записями о
сотрудниках, в этих полях могут находиться имя сотрудника, номер
социального страхования, название должности, и т.д. Определения для
класса EmpCell могут выглядеть примерно так:

Public EmpName As String

Public SSN As String

Public JobTitle As String

Public NextCell As EmpCell

Программа создает новые ячейки при помощи оператора New, задает их
значения и соединяет их, используя переменную NextCell.

Программа всегда должна сохранять ссылку на вершину списка. Для того,
чтобы определить, где заканчивается список, программа должна установить
значение NextCell для последнего элемента списка равным Nothing
(ничего). Например, следующий фрагмент кода создает список,
представляющий трех сотрудников:

Dim top_cell As EmpCell

Dim cell1 As EmpCell

Dim cell2 As EmpCell

Dim cell3 As EmpCell

‘ Создание ячеек.

Set cell1 = New EmpCell

cell1.EmpName = “Стивенс”

cell1.SSN = “123-45-6789”

cell1.JobTitle = “Автор”

Set cell2 = New EmpCell

cell2.EmpName = “Кэтс”

cell2.SSN = “123-45-6789”

cell2.JobTitle = “Юрист”

Set cell3 = New EmpCell

cell3.EmpName = “Туле”

cell3.SSN = “123-45-6789”

cell3.JobTitle = “Менеджер”

‘ Соединить ячейки, образуя связный список.

Set cell1.NextCell = cell2

Set cell2.NextCell = cell3

Set cell3.NextCell = Nothing

‘ Сохранить ссылку на вершину списка.

Set top_cell = cell1

===============27

На рис. 2.2 показано схематическое представление этого связного списка.
Прямоугольники представляют ячейки, а стрелки — ссылки на объекты.
Маленький перечеркнутый прямоугольник представляет значение Nothing,
которое обозначает конец списка. Имейте в виду, что top_cell, cell1 и
cell2 – это не настоящие объекты, а только ссылки, которые указывают на
них.

Следующий код использует связный список, построенный при помощи
предыдущего примера для печати имен сотрудников из списка. Переменная
ptr используется в качестве указателя на элементы списка. Она
первоначально указывает на вершину списка. В коде используется цикл Do
для перемещения ptr по списку до тех пор, пока указатель не дойдет до
конца списка. Во время каждого цикла, процедура печатает поле EmpName
ячейки, на которую указывает ptr. Затем она увеличивает ptr, указывая на
следующую ячейку в списке. В конце концов, ptr достигает конца списка и
получает значение Nothing, и цикл Do останавливается.

Dim ptr As EmpCell

Set ptr = top_cell ‘ Начать с вершины списка.

Do While Not (ptr Is Nothing)

‘ Вывести поле EmpName этой ячейки.

Debug.Print ptr.Empname

‘ Перейти к следующей ячейке в списке.

Set ptr = ptr.NextCell

Loop

После выполнения кода вы получите следующий результат:

Стивенс

Кэтс

Туле

@Рис. 2.2. Связный список

=======28

Использование указателя на другой объект называется XE
“Адресация:косвенная” косвенной адресацией (indirection XE
“addressing:indirect” ), поскольку вы используете указатель для
косвенного манипулирования данными. Косвенная адресация может быть очень
запутанной. Даже для простого расположения элементов, такого, как
связный список, иногда трудно запомнить, на какой объект указывает
каждая ссылка. В более сложных структурах данных, указатель может
ссылаться на объект, содержащий другой указатель. Если есть несколько
указателей и несколько уровней косвенной адресации, вы легко можете
запутаться в них

Для того, чтобы облегчить понимание, в изложении используются
иллюстрации, такие как рис. 2.2,(для сетевой версии исключены, т.к. они
многократно увеличивают размер загружаемого файла) чтобы помочь вам
наглядно представить ситуацию там, где это возможно. Многие из
алгоритмов, которые используют указатели, можно легко проиллюстрировать
подобными рисунками.

Добавление элементов к связному списку

Простой связный список, показанный на рис. 2.2, обладает несколькими
важными свойствами. Во-первых, можно очень легко добавить новую ячейку в
начало списка. Установим указатель новой ячейки NextCell на текущую
вершину списка. Затем установим указатель top_cell на новую ячейку. Рис.
2.3 соответствует этой операции. Код на языке Visual Basic для этой
операции очень прост:

Set new_cell.NextCell = top_cell

Set top_cell = new_cell

@Рис. 2.3. Добавление элемента в начало связного списка

Сравните размер этого кода и кода, который пришлось бы написать для
добавления нового элемента в начало списка, основанного на массиве, в
котором потребовалось бы переместить все элементы массива на одну
позицию, чтобы освободить место для нового элемента. Эта операция со
сложностью порядка O(N) может потребовать много времени, если список
достаточно длинный. Используя связный список, моно добавить новый
элемент в начало списка всего за пару шагов.

======29

Так же легко добавить новый элемент и в середину связного списка.
Предположим, вы хотите вставить новый элемент после ячейки, на которую
указывает переменная after_me. Установим значение NextCell новой ячейки
равным after_me.NextCell. Теперь установим указатель after_me.NextCell
на новую ячейку. Эта операция показана на рис. 2.4. Код на Visual Basic
снова очень прост:

Set new_cell.NextCell = after_me.NextCell

Set after_me.NextCell = new_cell

Удаление элементов из связного списка

Удалить элемент из вершины связного списка так же просто, как и добавить
его. Просто установите указатель top_cell на следующую ячейку в списке.
Рис. 2.5 соответствует этой операции. Исходный код для этой операции еще
проще, чем код для добавления элемента.

Set top_cell = top_cell.NextCell

Когда указатель top_cell перемещается на второй элемент в списке, в
программе больше не останется переменных, указывающих на первый объект.
В этом случае, счетчик ссылок на этот объект станет равен нулю, и
система автоматически уничтожит его.

Так же просто удалить элемент из середины списка. Предположим, вы хотите
удалить элемент, стоящий после ячейки after_me. Просто установите
указатель NextCell этой ячейки на следующую ячейку. Эта операция
показана на рис. 2.6. Код на Visual Basic прост и понятен:

after_me.NextCell = after_me.NextCell.NextCell

@Рис. 2.4. Добавление элемента в середину связного списка

=======30

@Рис. 2.5. Удаление элемента из начала связного списка

Снова сравним этот код с кодом, который понадобился бы для выполнения
той же операции, при использовании списка на основе массива. Можно
быстро пометить удаленный элемент как неиспользуемый, но это оставляет в
списке ненужные значения. Процедуры, обрабатывающие список, должны это
учитывать, и соответственно быть более сложными. Присутствие чрезмерного
количества «мусора» также замедляет работу процедуры, и, в конце концов,
придется проводить чистку памяти.

При удалении элемента из связного списка, в нем не остается пустых
промежутков. Процедуры, которые обрабатывают список, все так же обходят
список с начала до конца, и не нуждаются в модификации.

Уничтожение связного списка

Можно предположить, что для уничтожения связного списка необходимо
обойти весь список, устанавливая значение NextCell для всех ячеек равным
Nothing. На самом деле процесс гораздо проще: только top_cell принимает
значение Nothing.

Когда программа устанавливает значение top_cell равным Nothing, счетчик
ссылок для первой ячейки становится равным нулю, и Visual Basic
уничтожает эту ячейку.

Во время уничтожения ячейки, система определяет, что в поле NextCell
этой ячейки содержится ссылка на другую ячейку. Поскольку первый объект
уничтожается, то число ссылок на второй объект уменьшается. При этом
счетчик ссылок на второй объект списка становится равным нулю, поэтому
система уничтожает и его.

Во время уничтожения второго объекта, система уменьшает число ссылок на
третий объект, и так далее до тех пор, пока все объекты в списке не
будут уничтожены. Когда в программе уже не будет ссылок на объекты
списка, можно уничтожить и весь список при помощи единственного
оператора Set top_cell = Nothing.

@Рис. 2.6. Удаление элемента из середины связного списка

========31

Сигнальные метки

Для добавления или удаления элементов из начала или середины списка
используются различные процедуры. Можно свести оба этих случая к одному
и избавиться от избыточного кода, если ввести специальную XE
“Сигнальная метка” сигнальную метку (sentinel XE “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

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

Доступ к ячейкам

Класс LinkedList, используемый программой LnkLst2, позволяет основной
программе использовать список почти как массив. Например, подпрограмма
Item, приведенная в следующем коде, возвращает значение элемента по его
положению:

Function Item(ByVal position As Long) As Variant

Dim ptr As ListCell

If position m_NumItems Then

‘ Выход за границы. Вернуть NULL.

Item = Null

Exit Function

End If

‘ Найти элемент.

Set ptr = m_Sentinel

Do While position > 0

position = position – 1

Set ptr = ptr.NextCell

Loop

Item = ptr.Value

End Function

Эта процедура достаточно проста, но она не использует преимущества
связной структуры списка. Например, предположим, что программе требуется
последовательно перебрать все объекты в списке. Она могла бы
использовать подпрограмму Item для поочередного доступа к ним, как
показано в следующем коде:

Dim i As Integer

For i = 1 To LList.NumItems

‘ Выполнить какие-либо действия с LList.Item(i).

:

Next i

При каждом вызове процедуры Item, она просматривает список в поиске
следующего элемента. Чтобы найти элемент I, программа должна пропустить
I-1 элементов. Чтобы проверить все элементы в списке из N элементов,
процедура пропустит 0+1+2+3+…+N-1 =N*(N-1)/2 элемента. При больших N
программа потеряет много времени на пропуск элементов.

Класс LinkedList может ускорить эту операцию, используя другой метод
доступа. Можно использовать частную переменную m_CurrentCell для
отслеживания текущей позиции в списке. Для возвращения значения текущего
положения используется подпрограмма CurrentItem. Процедуры MoveFirst,
MoveNext и EndOfList позволяют основной программе управлять текущей
позицией в списке.

=======34

Например, следующий код содержит подпрограмму MoveNext:

Public Sub MoveNext()

‘ Если текущая ячейка не выбрана, ничего не делать.

If Not (m_CurrentCell Is Nothing) Then _

Set m_CurrentCell = m_CurrentCell.NextCell

End Sub

При помощи этих процедур, основная программа может обратиться ко всем
элементам списка, используя следующий код. Эта версия несколько сложнее,
чем предыдущая, но она намного эффективнее. Вместо того чтобы пропускать
N*(N-1)/2 элементов и опрашивать по очереди все N элементов списка, она
не пропускает ни одного. Если список состоит из 1000 элементов, это
экономит почти полмиллиона шагов.

LList.MoveFirst

Do While Not LList.EndOfList

‘ Выполнить какие-либо действия над элементом LList.Item(i).

:

LList.MoveNext

Loop

Программа LnkList3 использует эти новые методы для управления связным
списком. Она аналогична программе LnkList2, но более эффективно
обращается к элементам. Для небольших списков, используемых в программе,
эта разница незаметна. Для программы, которая обращается ко всем
элементам большого списка, эта версия класса LinkedList более
эффективна.

Разновидности связных списков

Связные списки играют важную роль во многих алгоритмах, и вы будете
встречаться с ними на протяжении всего материала. В следующих разделах
обсуждаются несколько специальных разновидностей связных списков.

Циклические связные списки

Вместо того, чтобы устанавливать указатель NextCell равным Nothing,
можно установить его на первый элемент списка, образуя XE
“Список:циклический” циклический список (circular list XE
“list:circular” ), как показано на рис. 2.7.

Циклические списки полезны, если нужно обходить ряд элементов в
бесконечном цикле. При каждом шаге цикла, программа просто перемещает
указатель на следующую ячейку в списке. Допустим, имеется циклический
список элементов, содержащий названия дней недели. Тогда программа могла
бы перечислять дни месяца, используя следующий код:

===========35

@Рис. 2.7. Циклический связный список

‘ Здесь находится код для создания и настройки списка и т.д.

:

‘ Напечатать календарь на месяц.

‘ first_day — это индекс структуры, содержащей день недели для

‘ первого дня месяца. Например, месяц может начинаться

‘ в понедельник.

‘ num_days — число дней в месяце.

Private Sub ListMonth(first_day As Integer, num_days As Integer)

Dim ptr As ListCell

Dim i As Integer

Set ptr = top_cell

For i = 1 to num_days

Print Format$(i) & “: ” & ptr.Value

Set ptr = ptr.NextCell

Next I

End Sub

Циклические списки также позволяют достичь любой точки в списке, начав с
любого положения в нем. Это вносит в список привлекательную симметрию.
Программа может обращаться со всеми элементами списка почти одинаковым
образом:

Private Sub PrintList(start_cell As Integer)

Dim ptr As Integer

Set ptr = start_cell

Do

Print ptr.Value

Set ptr = ptr.NextCell

Loop While Not (ptr Is start_cell)

End Sub

========36

Проблема циклических ссылок

Уничтожение циклического списка требует немного больше внимания, чем
удаление обычного списка. Если вы просто установите значение переменной
top_cell равным Nothing, то программа не сможет больше обратиться к
списку. Тем не менее, поскольку счетчик ссылок первой ячейки не равен
нулю, она не будет уничтожена. На каждый элемент списка указывает
какой-либо другой элемент, поэтому ни один из них не будет уничтожен.

Это XE “Проблема циклических ссылок” проблема циклических ссылок
(circular referencing problem XE “circular referencing problem” ). Так
как ячейки указывают на другие ячейки, ни одна из них не будет
уничтожена. Программа не может получить доступ ни к одной из них,
поэтому занимаемая ими память будет расходоваться напрасно до завершения
работы программы.

Проблема циклических ссылок может встретиться не только в этом случае.
Многие сети содержат циклические ссылки — даже одиночная ячейка, поле
NextCell которой указывает на саму эту ячейку, может вызвать эту
проблему.

Решение ее состоит в том, чтобы разбить цепь ссылок. Например, вы можете
использовать в своей программе следующий код для уничтожения
циклического связного списка:

Set top_cell.NextCell = Nothing

Set top_cell = Nothing

Первая строка разбивает цикл ссылок. В этот момент на вторую ячейку
списка не указывает ни одна переменная, поэтому система уменьшает
счетчик ссылок ячейки до нуля и уничтожает ее. Это уменьшает счетчик
ссылок на третий элемент до нуля, и соответственно, он также
уничтожается. Этот процесс продолжается до тех пор, пока не будут
уничтожены все элементы списка, кроме первого. Установка значения
top_cell элемента в Nothing уменьшает его счетчик ссылок до нуля, и
последняя ячейка также уничтожается.

Двусвязные списки

Во время обсуждения связных списков вы могли заметить, что большинство
операций определялось в терминах выполнения чего-либо после определенной
ячейки в списке. Если задана определенная ячейка, легко добавить или
удалить ячейку после нее или перечислить идущие за ней ячейки. Удалить
саму ячейку, вставить новую ячейку перед ней или перечислить идущие
перед ней ячейки уже не так легко. Тем не менее, небольшое изменение
позволит облегчить и эти операции.

Добавим новое поле указателя к каждой ячейке, которое указывает на
предыдущую ячейку в списке. Используя это новое поле, можно легко
создать XE “Список:двусвязный” двусвязный список (doubly linked list
XE “list:doubly linked” ), который позволяет перемещаться вперед и
назад по списку. Теперь можно легко удалить ячейку, вставить ее перед
другой ячейкой и перечислить ячейки в любом направлении.

@Рис. 2.8. Двусвязный список

============37

Класс DoubleListCell, который используется для таких типов списков,
может объявлять переменные так:

Public Value As Variant

Public NextCell As DoubleListCell

Public PrevCell As DoubleListCell

Часто бывает полезно сохранять указатели и на начало, и на конец
двусвязного списка. Тогда вы сможете легко добавлять элементы к любому
из концов списка. Иногда также бывает полезно размещать сигнальные метки
и в начале, и в конце списка. Тогда по мере работы со списком вам не
нужно будет заботиться о том, работаете ли вы с началом, с серединой или
с концом списка.

На рис. 2.9 показан двусвязный список с сигнальными метками. На этом
рисунке неиспользуемые указатели меток NextCell и PrevCell установлены в
Nothing. Поскольку программа опознает концы списка, сравнивая значения
указателей ячеек с сигнальными метками, и не проверяет, равны ли
значения Nothing, установка этих значений равными Nothing не является
абсолютно необходимой. Тем не менее, это признак хорошего стиля.

Код для вставки и удаления элементов из двусвязного списка подобен
приведенному ранее коду для односвязного списка. Процедуры нуждаются
лишь в незначительных изменениях для работы с указателями PrevCell.

@Рис. 2.9. Двусвязный список с сигнальными метками

Теперь вы можете написать новые процедуры для вставки нового элемента до
или после данного элемента, и процедуру удаления заданного элемента.
Например, следующие подпрограммы добавляют и удаляют ячейки из
двусвязного списка. Заметьте, что эти процедуры не нуждаются в доступе
ни к одной из сигнальных меток списка. Им нужны только указатели на
узел, который должен быть удален или добавлен и узел, соседний с точкой
вставки.

Public Sub RemoveItem(ByVal target As DoubleListCell)

Dim after_target As DoubleListCell

Dim before_target As DoubleListCell

Set after_target = target.NextCell

Set before_target = target.PrevCell

Set after_target.NextCell = after_target

Set after_target.PrevCell = before_target

End Sub

Sub AddAfter (new_Cell As DoubleListCell, after_me As DoubleListCell)

Dim before_me As DoubleListCell

Set before_me = after_me.NextCell

Set after_me.NextCell = new_cell

Set new_cell.NextCell = before_me

Set before_me.PrevCell = new_cell

Set new_cell.PrevCell = after_me

End Sub

Sub AddBefore(new_cell As DoubleListCell, before_me As DoubleListCell)

Dim after_me As DoubleListCell

Set after_me = before_me.PrevCell

Set after_me.NextCell = new_cell

Set new_cell.NextCell = before_me

Set before_me.PrevCell = new_cell

Set new_cell.PrevCell = after_me

End Sub

===========39

Если снова взглянуть на рис. 2.9, вы увидите, что каждая пара соседних
ячеек образует циклическую ссылку. Это делает уничтожение двусвязного
списка немного более сложной задачей, чем уничтожение односвязных или
циклических списков. Следующий код приводит один из способов очистки
двусвязного списка. Вначале указатели PrevCell всех ячеек
устанавливаются равными Nothing, чтобы разорвать циклические ссылки.
Это, по существу, превращает список в односвязный. Когда ссылки
сигнальных меток устанавливаются в Nothing, все элементы освобождаются
автоматически, так же как и в односвязном списке.

Dim ptr As DoubleListCell

‘ Очистить указатели PrevCell, чтобы разорвать циклические ссылки.

Set ptr = TopSentinel.NextCell

Do While Not (ptr Is BottomSentinel)

Set ptr.PrevCell = Nothing

Set ptr = ptr.NextCell

Loop

Set TopSentinel.NextCell = Nothing

Set BottomSentinel.PrevCell = Nothing

Если создать класс, инкапсулирующий двусвязный список, то его обработчик
события Terminate сможет уничтожать список. Когда основная программа
установит значение ссылки на список равным Nothing, список автоматически
освободит занимаемую память.

Программа DblLink работает с двусвязным списком. Она позволяет добавлять
элементы до или после выбранного элемента, а также удалять выбранный
элемент.

=============39

Потоки

В некоторых приложениях бывает удобно обходить связный список не только
в одном порядке. В разных частях приложения вам может потребоваться
выводить список сотрудников по их фамилиям, заработной плате,
идентификационному номеру системы социального страхования, или
специальности.

Обычный связный список позволяет просматривать элементы только в одном
порядке. Используя указатель PrevCell, можно создать двусвязный список,
который позволит перемещаться по списку вперед и назад. Этот подход
можно развить и дальше, добавив больше указателей на структуру данных,
позволяя выводить список в другом порядке.

Набор ссылок, который задает какой-либо порядок просмотра, называется
XE “Потоки” потоком (thread XE “thread” ), а сам полученный список —
XE “Список:многопоточный” многопоточным списком (threaded list XE
“list:threaded” ). Не путайте эти потоки с потоками, которые
предоставляет система Windows NT.

Список может содержать любое количество потоков, хотя, начиная с
какого-то момента, игра не стоит свеч. Применение потока,
упорядочивающего список сотрудников по фамилии, будет обосновано, если
ваше приложение часто использует этот порядок, в отличие от расположения
по отчеству, которое вряд ли когда будет использоваться.

Некоторые расположения не стоит организовывать в виде потоков. Например,
поток, упорядочивающий сотрудников по полу, вряд ли целесообразен
потому, что такое упорядочение легко получить и без него. Для того,
чтобы составить список сотрудников по полу, достаточно просто обойти
список по любому другому потоку, печатая фамилии женщин, а затем
повторить обход еще раз, печатая фамилии мужчин. Для получения такого
расположения достаточно всего двух проходов списка.

Сравните этот случай с тем, когда вы хотите упорядочить список
сотрудников по фамилии. Если список не включает поток фамилий, вам
придется найти фамилию, которая будет первой в списке, затем следующую и
т.д. Это процесс со сложностью порядка O(N2), который намного менее
эффективен, чем сортировка по полу со сложностью порядка O(N).

В общем случае, задание потока может быть целесообразно, если его
необходимо часто использовать, и если при необходимости получить тот же
порядок достаточно сложно. Поток не нужен, если его всегда легко создать
заново.

Программа Treads демонстрирует простой многопоточный список сотрудников.
Заполните поля фамилии, специальности, пола и номера социального
страхования для нового сотрудника. Затем нажмите на кнопку Add
(Добавить), чтобы добавить сотрудника к списку.

Программа содержит потоки, которые упорядочивают список по фамилии по
алфавиту и в обратном порядке, по номеру социального страхования и
специальности в прямом и обратном порядке. Вы можете использовать
дополнительные кнопки для выбора потока, в порядке которого программа
выводит список. На рис. 2.10 показано окно программы Threads со списком
сотрудников, упорядоченным по фамилии.

Класс ThreadedCell, используемый программой Threads, определяет
следующие переменные:

Public LastName As String

Public FirstName As String

Public SSN As String

Public Sex As String

Public JobClass As Integer

Public NextName As TreadedCell ‘ По фамилии в прямом порядке.

Public PrevName As TreadedCell ‘ По фамилии в обратном порядке.

Public NextSSN As TreadedCell ‘ По номеру в прямом порядке.

Public NextJobClass As TreadedCell ‘ По специальности в прямом порядке.

Public PrevJobClass As TreadedCell ‘ По специальности в обратном
порядке.

Класс ThreadedList инкапсулирует многопоточный список. Когда программа
вызывает метод AddItem, список обновляет свои потоки. Для каждого потока
программа должна вставить элемент в правильном порядке. Например, для
того, чтобы вставить запись с фамилией «Смит», программа обходит список,
используя поток NextName, до тех пор, пока не найдет элемент с фамилией,
которая должна следовать за «Смит». Затем она вставляет в поток NextName
новую запись перед этим элементом.

При определении местоположения новых записей в потоке важную роль играют
сигнальные метки. Обработчик событий Class_Initialize класса
ThreadedList создает сигнальные метки на вершине и в конце списка и
инициализирует их указатели так, чтобы они указывали друг на друга.
Затем значение метки в начале списка устанавливается таким образом,
чтобы оно всегда находилось до любого значения реальных данных для всех
потоков.

Например, переменная LastName может содержать строковые значения. Пустая
строка “” идет по алфавиту перед любыми действительными значениями
строк, поэтому программа устанавливает значение сигнальной метки
LastName в начале списка равным пустой строке.

Таким же образом Class_Initialize устанавливает значение данных для
метки в конце списка, превосходящее любые реальные значения во всех
потоках. Поскольку “~” идет по алфавиту после всех видимых символов
ASCII, программа устанавливает значение поля LastName для метки в конце
списка равным “~”.

Присваивая полю LastName сигнальных меток значения “” и “~”, программа
избавляется от необходимости проверять особые случаи, когда нужно
вставить новый элемент в начало или конец списка. Любые новые
действительные значения будут находиться между значениями LastValue
сигнальных меток, поэтому программа всегда сможет определить правильное
положение для нового элемента, не заботясь о том, чтобы не зайти за
концевую метку и не выйти за границы списка.

@Рис. 2.10. Программа Threads

=====41

Следующий код показывает, как класс ThreadedList вставляет новый элемент
в потоки NextName и PrevName. Так как эти потоки используют один и тот
же ключ — фамилии, программа может обновлять их одновременно.

Dim ptr As ThreadedCell

Dim nxt As ThreadedCell

Dim new_cell As New ThreadedCell

Dim new_name As String

Dim next_name As String

‘ Записать значения новой ячейки.

With new_cell

.LastName = LastName

.FirstName = FirstName

.SSN = SSN

•Sex = Sex

.JobClass = JobClass

End With

‘ Определить место новой ячейки в потоке NextThread.

new_name = LastName & “, ” & FirstName

Set ptr = m_TopSentinel

Do

Set nxt = ptr.NextName

next_name = nxt.LastName & “, ” & nxt.FirstName

If next_name >= new_name Then Exit Do

Set ptr = nxt

Loop

‘ Вставить новую ячейку в потоки NextName и prevName.

Set new_cell.NextName = nxt

Set new_cell.PrevName = ptr

Set ptr.NextName = new_cell

Set nxt.PrevName = new_cell

Чтобы такой подход работал, программа должна гарантировать, что значения
новой ячейки лежат между значениями меток. Например, если пользователь
введет в качестве фамилии “~~”, цикл выйдет за метку конца списка, т.к.
“~~” идет после “~”. Затем программа аварийно завершит работу при
попытке доступа к значению nxt.LastName, если nxt было установлено
равным Nothing.

========42

Другие связные структуры

Используя указатели, можно построить множество других полезных
разновидностей связных структур, таких как деревья, нерегулярные
массивы, разреженные массивы, графы и сети. Ячейка может содержать любое
число указателей на другие ячейки. Например, для создания двоичного
дерева можно использовать ячейку, содержащую два указателя, один на
левого потомка, и второй – на правого. Класс BinaryCell может состоять
из следующих определений:

Public LeftChild As BinaryCell

Public RightChild As BinaryCell

На рис. 2.11 показано дерево, построенное из ячеек такого типа. В 6
главе деревья обсуждаются более подробно.

Ячейка может даже содержать коллекцию или связный список с указателями
на другие ячейки. Это позволяет программе связать ячейку с любым числом
других объектов. На рис. 2.12 приведены примеры других связных структур
данных. Вы также встретите похожие структуры далее, в особенности в 12
главе.

Псевдоуказатели

При помощи ссылок в Visual Basic можно легко создавать связные
структуры, такие как списки, деревья и сети, но ссылки требуют
дополнительных ресурсов. Счетчики ссылок и проблемы с распределением
памяти замедляют работу структур данных, построенных с использованием
ссылок.

Другой стратегией, которая часто обеспечивает лучшую производительность,
является применение XE “Псевдоуказатели” псевдоуказателей (fake
pointers XE “fake pointer” ). При этом программа создает массив
структур данных. Вместо использования ссылок для связывания структур,
программа использует индексы массива. Нахождение элемента в массиве
осуществляется в Visual Basic быстрее, чем выборка его по ссылке на
объект. Это дает лучшую производительность при применении
псевдоуказателей по сравнению с соответствующими методами ссылок на
объекты.

С другой стороны, применение псевдоуказателей не столь интуитивно, как
применение ссылок. Это может усложнить разработку и отладку сложных
алгоритмов, таких как алгоритмы сетей или сбалансированных деревьев.

@Рис. 2.11. Двоичное дерево

========43

@Рис. 2.12. Связные структуры

Программа FakeList управляет связным списком, используя псевдоуказатели.
Она создает массив простых структур данных для хранения ячеек списка.
Программа аналогична программе LnkList1, но использует псевдоуказатели.

Следующий код демонстрирует, как программа FakeList создает массив
клеточных структур:

‘ Структура данных ячейки.

Type FakeCell

Value As String

NextCell As Integer

End Type

‘ Массив ячеек связного списка.

Global Cells(0 To 100) As FakeCell

‘ Сигнальная метка списка.

Global Sentinel As Integer

Поскольку псевдоуказатели — это не ссылки, а просто целые числа,
программа не может использовать значение Nothing для маркировки конца
списка. Программа FakeList использует постоянную END_OF_LIST, значение
которой равно -32.767 для обозначения пустого указателя.

Для облегчения обнаружения неиспользуемых ячеек, программа FakeList
также использует специальный «мусорный» список, содержащий
неиспользуемые ячейки. Следующий код демонстрирует инициализацию пустого
связного списка. В нем сигнальная метка NextCell принимает значение
END_OF_LIST. Затем она помещает неиспользуемые ячейки в «мусорный»
список.

========44

‘ Связный список неиспользуемых ячеек.

Global TopGarbage As Integer

Public Sub InitializeList()

Dim i As Integer

Sentinel = 0

Cells(Sentinel).NextCell = END_OF_LIST

‘ Поместить все остальные ячейки в «мусорный» список.

For i = 1 To UBound (Cells) – 1

Cells(i).NextCell = i + 1

Next i

Cells(UBound(Cells)).NextCell = END_OF_LIST

TopGarbage = 1

End Sub

При добавлении элемента к связному списку, программа использует первую
доступную ячейку из «мусорного» списка, инициализирует поле ячейки Value
и вставляет ячейку в список. Следующий код показывает, как программа
добавляет элемент после выбранного:

Private Sub CmdAddAfter_Click()

Dim ptr As Integer

Dim position As Integer

Dim new_cell As Integer

‘ Найти место вставки.

ptr = Sentinel

position = Selectedlndex

Do While position > 0

position = position – 1

ptr = Cells(ptr).NextCell

Loop

‘ Выбрать новую ячейку из «мусорного» списка.

new_cell = TopGarbage

TopGarbage = Cells(TopGarbage).NextCell

‘ Вставить элемент.

Cells (new_cell).Value = NewItem.Text

Cells(new_cell).NextCell = Cells(ptr).NextCell

Cells(ptr).NextCell = new_cell

NumItems = NumItems + 1

DisplayList

SelectItem SelectedIndex + 1 ‘ Выбрать новый элемент.

NewItem.Text = “”

NewItem.SetFocus

CmdClearList.Enabled = True

End Sub

После удаления ячейки из списка, программа FakeList помещает удаленную
ячейку в «мусорный» список, чтобы ее затем можно было легко
использовать:

Private Sub CmdRemoveAfter_Click()

Dim ptr As Integer

Dim target As Integer

Dim position As Integer

If SelectedIndex 0

position = position – 1

ptr = Cells(ptr).NextCell

Loop

‘ Пропустить следующий элемент.

target = Cells(ptr).NextCell

Cells(ptr).NextCell = Cells(target).NextCell

NumItems = NumItems – 1

‘ Добавить удаленную ячейку в «мусорный» список.

Cells(target).NextCell = TopGarbage

TopGarbage = target

SelectItem Selectedlndex ‘ Снова выбрать элемент.

DisplayList

CmdClearList.Enabled = NumItems > 0

NewItem.SetFocus

End Sub

Применение псевдоуказателей обычно обеспечивает лучшую
производительность, но является более сложным. Поэтому имеет смысл
сначала создать приложение, используя ссылки на объекты. Затем, если вы
обнаружите, что программа значительную часть времени тратит на
манипулирование ссылками, вы можете, если необходимо, преобразовать ее с
использованием псевдоуказателей.

=======45-46

Резюме

Используя ссылки на объекты, вы можете создавать гибкие структуры
данных, такие как связные списки, циклические связные списки и
двусвязные списки. Эти списки позволяют легко добавлять и удалять
элементы из любого места списка.

Добавляя дополнительные ссылки к классу ячеек, можно превратить
двусвязный список в многопоточный. Развивая и дальше эти идеи, можно
создавать экзотические структуры данных, включая разреженные массивы,
деревья, хэш-таблицы и сети. Они подробно описываются в следующих
главах.

========47

Глава 3. Стеки и очереди

В этой главе продолжается обсуждение списков, начатое во 2 главе, и
описываются две особых разновидности списков: стеки и очереди. Стек —
это список, в котором добавление и удаление элементов осуществляется с
одного и того же конца списка. Очередь — это список, в котором элементы
добавляются в один конец списка, а удаляются с противоположного конца.
Многие алгоритмы, включая некоторые из представленных в следующих
главах, используют стеки и очереди.

Стеки

XE “Стек” Стек (stack XE “stack” ) — это упорядоченный список, в
котором добавление и удаление элементов всегда происходит на одном конце
списка. Можно представить стек как стопку предметов на полу. Вы можете
добавлять элементы на вершину и удалять их оттуда, но не можете
добавлять или удалять элементы из середины стопки.

Стеки часто называют XE “Список:первый вошел-последний вышел”
списками типа первый вошел — последний вышел (Last-In-First-Out list XE
“Last-In-First-Out list” ). По историческим причинам, добавление
элемента в стек называется проталкиванием (pushing) элемента в стек, а
удаление элемента из стека — выталкиванием (popping) элемента из стека.

Первая реализация простого списка на основе массива, описанная в начале
2 главы, является стеком. Для отслеживания вершины списка используется
счетчик. Затем этот счетчик используется для вставки или удаления
элемента из вершины списка. Небольшое изменение — это новая процедура
Pop, которая удаляет элемент из списка, одновременно возвращая его
значение. При этом другие процедуры могут извлекать элемент и удалять
его из списка за один шаг. Кроме этого изменения, следующий код
совпадает с кодом, приведенным во 2 главе.

Dim Stack() As Variant

Dim StackSize As Variant

Sub Push(value As Variant)

StackSize = StackSize + 1

ReDim Preserve Stack(1 To StackSize)

Stack(StackSize) = value

End Sub

Sub Pop(value As Variant)

value = Stack(StackSize)

StackSize = StackSize – 1

ReDim Preserve Stack(1 To StackSize)

End Sub

=====49

Все предыдущие рассуждения о списках также относятся к этому виду
реализации стеков. В частности, можно сэкономить время, если не изменять
размер при каждом добавлении или выталкивании элемента. Программа
SimList на описанная во 2 главе, демонстрирует этот вид простой
реализации списков.

Программы часто используют стеки для хранения последовательности
элементов, с которыми программа будет работать до тех пор, пока стек не
опустеет. Действия с одним из элементов может приводить к тому, что
другие будут проталкиваться в стек, но, в конце концов, они все будут
удалены из стека. В качестве простого примера можно привести алгоритм
обращения порядка элементов массива. При этом все элементы
последовательно проталкиваются в стек. Затем все элементы выталкиваются
из стека в обратном порядке и записываются обратно в массив.

Dim List() As Variant

Dim NumItems As Integer

‘ Инициализация массива.

:

‘ Протолкнуть элементы в стек.

For I = 1 To NumItems

Push List(I)

Next I

‘ Вытолкнуть элементы из стека обратно в массив.

For I = 1 To NumItems

Pop List(I)

Next I

В этом примере, длина стека может многократно изменяться до того, как, в
конце концов, он опустеет. Если известно заранее, насколько большим
должен быть массив, можно сразу создать достаточно большой стек. Вместо
изменения размера стека по мере того, как он растет и уменьшается, можно
отвести под него память в начале работы и уничтожить его после ее
завершения.

Следующий код позволяет создать стек, если заранее известен его
максимальный размер. Процедура Pop не изменяет размер массива. Когда
программа заканчивает работу со стеком, она должна вызвать процедуру
EmptyStack для освобождения занятой под стек памяти.

======50

Const WANT_FREE_PERCENT = .1 ‘ 10% свободного пространства.

Const MIN_FREE = 10 ‘ Минимальный размер.

Global Stack() As Integer ‘ Стековый массив.

Global StackSize As Integer ‘ Размер стекового массива.

Global Lastltem As Integer ‘ Индекс последнего элемента.

Sub PreallocateStack(entries As Integer)

StackSize = entries

ReDim Stack(1 To StackSize)

End Sub

Sub EmptyStack()

StackSize = 0

LastItem = 0

Erase Stack ‘ Освободить память, занятую массивом.

End Sub

Sub Push(value As Integer)

LastItem = LastItem + 1

If LastItem > StackSize Then ResizeStack

Stack(LastItem) = value

End Sub

Sub Pop(value As Integer)

value = Stack(LastItem)

LastItem = LastItem – 1

End Sub

Sub ResizeStack()

Dim want_free As Integer

want_free = WANT_FREE_PERCENT * LastItem

If want_free QueueMax Then ResizeQueue

Queue(QueueBack) = value

QueueBack = QueueBack + 1

End Sub

Sub LeaveQueue(value As String)

value = Queue(QueueFront)

QueueFront = QueueFront + 1

If QueueFront > ResizeWhen Then ResizeOueue

End Sub

Sub ResizeQueue()

Dim want_free As Integer

Dim i As Integer

‘ Переместить записи в начало массива.

For i = QueueFront To QueueBack – 1

Queue(i – QueueFront) = Queue(i)

Next i

QueueBack = QueueBack – QueuePront

QueueFront = 0

‘ Изменить размер массива.

want_free = WANT_FREE_PERCENT * (QueueBack – QueueFront)

If want_free ResizeWhen, изменить размер массива.

ResizeWhen = want_free

End Sub

При работе с программой, заметьте, что когда вы добавляете и удаляете
элементы, требуется изменение размера очереди, даже если размер очереди
почти не меняется. Фактически, даже при неоднократном добавлении и
удалении одного элемента размер очереди будет изменяться.

Имейте в виду, что при каждом изменении размера очереди, вначале все
используемые элементы перемещаются в начало массива. При этом на
изменение размера очередей на основе массива уходит больше времени, чем
на изменение размера описанных выше связных списков и стеков.

=======54

Программа ArrayQ2 аналогична программе ArrayQ, но она использует для
управления очередью класс ArrayQueue.

Циклические очереди

Очереди, описанные в предыдущем разделе, требуется переупорядочивать
время от времени, даже если размер очереди почти не меняется. Даже при
неоднократном добавлении и удалении одного элемента будет необходимо
переупорядочивать очередь.

Если заранее известно, насколько большой может быть очередь, этого можно
избежать, создав XE “Очередь:циклическая” циклическую очередь
(circular queue XE “queue:circular” ). Идея заключается в том, чтобы
рассматривать массив очереди как будто он заворачивается, образуя круг.
При этом последний элемент массива как бы идет перед первым. На рис. 3.2
изображена циклическая очередь.

Программа может хранить в переменной QueueFront индекс элемента, который
дольше всего находится в очереди. Переменная QueueBack может содержать
конец очереди, в который добавляется новый элемент.

В отличие от предыдущей реализации, при обновлении значений переменных
QueueFront и QueueBack, необходимо использовать оператор Mod для того,
чтобы индексы оставались в границах массива. Например, следующий код
добавляет элемент к очереди:

Queue(QueueBack) = value

QueueBack = (QueueBack + 1) Mod QueueSize

На рис. 3.3 показан процесс добавления нового элемента к циклической
очереди, которая может содержать четыре записи. Элемент C добавляется в
конец очереди. Затем конец очереди сдвигается, указывая на следующую
запись в массиве.

Таким же образом, когда программа удаляет элемент из очереди, необходимо
обновлять указатель на начало очереди при помощи следующего кода:

value = Queue(QueueFront)

QueueFront = (QueueFront + 1) Mod QueueSize

@Рис. 3.2. Циклическая очередь

=======55

@Рис. 3.3. Добавление элемента к циклической очереди

На рис. 3.4 показан процесс удаления элемента из циклической очереди.
Первый элемент, в данном случае элемент A, удаляется из начала очереди,
и указатель на начало очереди обновляется, указывая на следующий элемент
массива.

Для циклических очередей иногда бывает сложно отличить пустую очередь от
полной. В обоих случаях значения переменных QueueBottom и QueueTop будут
равны. На рис. 3.5 показаны две циклические очереди, пустая и полная.

Простой вариант решения этой проблемы — сохранять число элементов в
очереди в отдельной переменной NumInQueue. При помощи этого счетчика
можно узнать, остались ли в очереди еще элементы, и осталось ли в
очереди место для новых элементов.

@Рис. 3.4. Удаление элемента из циклической очереди

@Рис. 3.5 Полная и пустая циклическая очереди

=========56

Следующий код использует все эти методы для управления циклической
очередью:

Queue() As String ‘ Массив очереди.

QueueSize As Integer ‘ Наибольший индекс в очереди.

QueueFront As Integer ‘ Начало очереди.

QueueBack As Integer ‘ Конец очереди.

NumInQueue As Integer ‘ Число элементов в очереди.

Sub NewCircularQueue(num_items As Integer)

QueueSize = num_items

ReDim Queue(0 To QueueSize – 1)

End Sub

Sub EnterQueue(value As String)

‘ Если очередь заполнена, выйти из процедуры.

‘ В настоящем приложении потребуется более сложный код.

If NumInQueue >= QueueSize Then Exit Sub

Queue(QueueBack) = value

QueueBack = (QueueBack + 1) Mod QueueSize

NumInQueue = NumInQueue + 1

End Sub

Sub LeaveQueue (value As String)

‘ Если очередь пуста, выйти из процедуры.

‘ В настоящем приложении потребуется более сложный код.

If NumInQueue = QueueSize Then ResizeQueue

Queue(QueueBack) = value

QueueBack = (QueueBack + 1) Mod QueueSize

NumInQueue = NumInQueue + 1

End Sub

Private Sub LeaveQueue(value As String)

If NumInQueue new_priority

cell = nxt

nxt = cell.NextCell

Loop

‘ Вставить элемент после ячейки в списке.

:

Для удаления из списка элемента с наивысшим приоритетом, просто
удаляется элемент после сигнальной метки начала. Так как список
отсортирован в порядке приоритетов, первый элемент всегда имеет
наивысший приоритет.

Добавление нового элемента в эту очередь занимает в среднем N/2 шагов.
Иногда новый элемент будет оказываться в начале списка, иногда ближе к
концу, но в среднем он будет оказываться где-то в середине. Простая
очередь на основе списка требовала O(1) шагов для добавления нового
элемента и O(N) шагов для удаления элементов с наивысшим приоритетом из
очереди. Версия на основе упорядоченного связного списка требует O(N)
шагов для добавления элемента и O(1) шагов для удаления верхнего
элемента. Обеим версиям требует O(N) шагов для одной из этих операций,
но в случае упорядоченного связного списка в среднем требуется только
(N/2) шагов.

Программа PriList использует упорядоченный связный список для работы с
приоритетной очередью. Вы можете задать приоритет и значение элемента
данных и нажать кнопку Enter для добавления его в приоритетную очередь.
Нажмите на кнопку Leave для удаления из очереди элемента с наивысшим
приоритетом.

Программа PriList2 аналогична программе PriList, но она использует для
управления очередью класс LinkedPriorityQueue.

========63

Затратив еще немного усилий, можно построить приоритетную очередь, в
которой добавление и удаление элемента потребуют порядка O(log(N))
шагов. Для очень больших очередей, ускорение работы может стоить этих
усилий. Этот тип приоритетных очередей использует структуры данных в
виде пирамиды, которые также применяются в алгоритме пирамидальной
сортировки. Пирамиды и приоритетные очереди на их основе обсуждаются
более подробно в 9 главе.

Интересной разновидностью очередей являются XE “Очередь:многопоточная”
многопоточные очереди (multi-headed queues XE “queue:multi-headed” ).
Элементы, как обычно, добавляются в конец очереди, но очередь имеет
несколько потоков (front end) или голов (heads). Программа может удалять
элементы из любого потока.

Примером многопоточной очереди в обычной жизни является очередь клиентов
в банке. Все клиенты находятся в одной очереди, но их обслуживает
несколько служащих. Освободившийся банковский работник обслуживает
клиента, который находится в очереди первым. Такой порядок обслуживания
кажется справедливым, поскольку клиенты обслуживаются в порядке
прибытия. Он также эффективен, так как все служащие остаются занятыми до
тех пор, пока клиенты ждут в очереди.

Сравните этот тип очереди с несколькими однопоточными очередями в
супермаркете, в которых покупатели не обязательно обслуживаются в
порядке прибытия. Покупатель в медленно движущейся очереди, может
прождать дольше, чем тот, который подошел позже, но оказался в очереди,
которая продвигается быстрее. Кассиры также могут быть не всегда заняты,
так как какая-либо очередь может оказаться пустой, тогда как в других
еще будут находиться покупатели.

В общем случае, многопоточные очереди более эффективны, чем несколько
однопоточных очередей. Последний вариант используется в супермаркетах
потому, что тележки для покупок занимают много места. При использовании
многопоточной очереди всем покупателям пришлось бы построиться в одну
очередь. Когда кассир освободится, покупателю пришлось бы переместиться
с громоздкой тележкой к кассиру. С другой стороны, в банке посетителям
не нужно двигать большие тележки для покупок, поэтому они легко могут
уместиться в одной очереди.

Очереди на регистрацию в аэропорту иногда представляют собой комбинацию
этих двух ситуаций. Хотя пассажиры имеют с собой большое количество
багажа, в аэропорту все-таки используются многопоточные очереди, при
этом приходится отводить дополнительное место, чтобы пассажиры могли
выстроиться в порядке очереди.

Многопоточную очередь просто построить, используя обычную однопоточную
очередь. Элементы, представляющие клиентов, хранятся в обычной
однопоточной очереди. Когда агент (кассир, банковский служащий и т.д.)
освобождается, первый элемент в начале очереди удаляется и передается
этому агенту.

Модель очереди

Предположим, что вы отвечаете за разработку счетчика регистрации для
нового терминала в аэропорту и хотите сравнить возможности одной
многопоточной очереди или нескольких однопоточных. Вам потребуется
какая-то модель поведения пассажиров. Для этого примера можно сделать
следующие предположения:

=====63

регистрация каждого пассажира занимает от двух до пяти минут;

при использовании нескольких однопоточных очередей, прибывающие
пассажиры встают в самую короткую очередь;

скорость поступления пассажиров примерно неизменна.

Программа HeadedQ моделирует эту ситуацию. Вы можете менять некоторые
параметры модели, включая следующие:

число прибывающих в течение часа пассажиров;

минимальное и максимальное затрачиваемое время;

число свободных служащих;

паузу между шагами программы в миллисекундах.

При выполнении программы, модель показывает прошедшее время, среднее и
максимальное время ожидания пассажирами обслуживания, и процент времени,
в течение которого служащие заняты.

При экспериментировании с различными значениями параметров, вы заметите
несколько любопытных моментов. Во-первых, для многопоточной очереди
среднее и максимальное время ожидания будет меньше. При этом, служащие
также оказываются немного более загружены, чем в случае однопоточной
очереди.

Для обоих типов очереди есть порог, при котором время ожидания
пассажиров значительно возрастает. Предположим, что на обслуживание
одного пассажира требуется от 2 до 10 минут, или в среднем 6 минут. Если
поток пассажиров составляет 60 человек в час, тогда персонал потратит
около 6*60=360 минут в час на обслуживание всех пассажиров. Разделив это
значение на 60 минут в часе, получим, что для обслуживания клиентов в
этом случае потребуется 6 клерков.

Если запустить программу HeadedQ с этими параметрами, вы увидите, что
очереди движутся достаточно быстро. Для многопоточной очереди время
ожидания составит всего несколько минут. Если добавить еще одного
служащего, чтобы всего было 7 служащих, среднее и максимальное время
ожидания значительно уменьшатся. Среднее время ожидания упадет примерно
до одной десятой минуты.

С другой стороны, если уменьшить число служащих до 5, это приведет к
большому увеличению среднего и максимального времени ожидания. Эти
показатели также будут расти со временем. Чем дольше будет работать
программа, тем дольше будут задержки.

@Таблица 3.1. Время ожидания в минутах для одно- и многопоточных
очередей

======64

@Рис. 3.9. Программа HeadedQ

В табл. 3.1 приведены среднее и максимальное время ожидания для 2 разных
типов очередей. Программа моделирует работу в течение 3 часов и
предполагает, что прибывает 60 пассажиров в час и на обслуживание
каждого из них уходит от 2 до 10 минут.

Многопоточная очередь также кажется более справедливой, так как
пассажиры обслуживаются в порядке прибытия. На рис. 3.9 показана
программа HeadedQ после моделирования чуть более, чем двух часов работы
терминала. В многопоточной очереди первым стоит пассажир с номером 104.
Все пассажиры, прибывшие до него, уже обслужены или обслуживаются в
настоящий момент. В однопоточной очереди, обслуживается пассажир с
номером 106. Пассажиры с номерами 100, 102, 103 и 105 все еще ждут своей
очереди, хотя они и прибыли раньше, чем пассажир с номером 106.

Резюме

Разные реализации стеков и очередей обладают различными свойствами.
Стеки и циклические очереди на основе массивов просты и эффективны, в
особенности, если заранее известно насколько большим может быть их
размер. Связные списки обеспечивают большую гибкость, если размер списка
часто изменяется.

Стеки и очереди на основе коллекций Visual Basic не так эффективны, как
реализации на основе массивов, но они очень просты. Коллекции могут
подойти для небольших структур данных, если производительность не
критична. После тестирования приложения, можно переписать код для стека
или очереди, если коллекции окажутся слишком медленными.

Глава 4. Массивы

В этой главе описаны структуры данных в виде массивов. С помощью Visual
Basic вы можете легко создавать массивы данных стандартных или
определенных пользователем типов. Если определить массив без границ,
затем можно изменять его размер при помощи оператора ReDim. Эти свойства
делают применение массивов в Visual Basic очень полезным.

Некоторые программы используют особые типы массивов, которые не
поддерживаются Visual Basic непосредственно. К этим типа относятся
треугольные массивы, нерегулярные массивы и разреженные массивы. В этой
главе объясняется, как можно использовать гибкие структуры массивов,
которые могут значительно снизить объем занимаемой памяти.

Треугольные массивы

Некоторым программам требуется только половина элементов в двумерном
массиве. Предположим, что мы располагаем картой, на которой 10 городов
обозначены цифрами от 0 до 9. Можно использовать массив для создания
XE “Матрица смежности” матрицы смежности (adjacency matrix XE
“adjacency matrix” ), показывающей наличие автострады между парами
городов. Элемент A(I,J) равен True, если между городами I и J есть
автострада.

В этом случае, значения в половине матрицы будут дублировать значения в
другой ее половине, так как A(I, J)=A(J, I). Также элемент A(I, I) не
имеет смысла, так как бессмысленно строить автостраду из города I в тот
же самый город. В действительности потребуются только элементы A(I,J) из
верхнего левого угла, для которых I > J. Вместо этого можно также
использовать элементы из верхнего правого угла. Поскольку эти элементы
образуют треугольник, этот тип массивов называется XE
“Массив:треугольный” треугольным массивом (triangular array XE
“array:triangular” ).

На рис. 4.1 показан треугольный массив. Элементы со значащими данными
обозначены буквой X, ячейки, соответствующие дублирующимся элементам,
оставлены пустыми. Незначащие элементы A(I,I) обозначены тире.

Для небольших массивов потери памяти при использовании обычных двумерных
массивов для хранения таких данных не слишком существенны. Если же на
карте много городов, потери памяти могут быть велики. Для N городов эти
потери составят N*(N-1)/2 дублирующихся элементов и N незначащих
диагональных элементов A(I,I). Если карта содержит 1000 городов, в
массиве будет более полумиллиона ненужных элементов.

====67

@Рис. 4.1. Треугольный массив

Избежать потерь памяти можно, создав одномерный массив B и упаковав в
него значащие элементы из массива A. Разместим элементы в массиве B по
строкам, как показано на рис. 4.2. Заметьте, что индексы массивов
начинаются с нуля. Это упрощает последующие уравнения.

Для того, чтобы упростить использование этого представления треугольного
массива, можно написать функции для преобразования индексов массивов A и
B. Уравнение для преобразования индекса A(I,J) в B(X) выглядит так:

X = I * (I – 1) / 2 + J ‘ Для I > J.

Например, для I=2 и J=1 получим X = 2 * (2 – 1) / 2 + 1 = 2. Это значит,
что A(2,1) отображается на 2 позицию в массиве B, как показано на рис.
4.2. Помните, что массивы нумеруются с нуля.

Уравнение остается справедливым только для I > J. Значения других
элементов массива A не сохраняются в массиве B, потому что они являются
избыточными или незначащими. Если вам нужно получить значение A(I,J) при
I ” & Format$(cell.ToCity)

Set cell = cell.NextInRow

Loop

End Sub

====74

@Рис. 4.9. Разреженная матрица смежности

Индексирование массива

Нормальное индексирование массива типа A(I, J) не будет работать с
такими структурами. Можно облегчить индексирование, написав процедуры,
которые извлекают и устанавливают значения элементов массива. Если
массив представляет матрицу, могут также понадобиться процедуры для
сложения, умножения, и других матричных операций.

Специальное значение NoValue представляет пустой элемент массива.
Процедура, которая извлекает элементы массива, должна возвращать
значение NoValue при попытке получить значение элемента, не
содержащегося в массиве. Аналогично, процедура, которая устанавливает
значения элементов, должна удалять ячейку из массива, если ее значение
установлено в NoValue.

Значение NoValue должно выбираться в зависимости от природы данных
приложения. Для матрицы смежности авиалинии пустые ячейки могут иметь
значение False. При этом значение A(I, J) может устанавливаться равным
True, если существует рейс между городами I и J.

Класс SparseArray определяет процедуру get для свойства Value для
возвращения значения элемента в массиве. Процедура начинает с первой
ячейки в указанной строке и затем перемещается по связному списку ячеек
строки. Как только найдется ячейка с нужным номером столбца, это и будет
искомая ячейка. Так как ячейки в списке строки расположены по порядку,
процедура может остановиться, если найдется ячейка, номер столбца
которой больше искомого.

=====75

Property Get Value(t As Integer, c As Integer) As Variant

Dim cell As SparseArrayCell

Value = NoValue ‘ Предположим, что мы не найдем элемент.

If r NumRows Or c > NumCols _

Then Exit Property

Set cell = RowHead(r).NextInRow ‘ Пропустить метку.

Do

If cell Is Nothing Then Exit Property ‘ Не найден.

If cell.Col > c Then Exit Property ‘ Не найден.

If cell.Col = c Then Exit Do ‘ Найден.

Set cell = cell.NextInRow

Loop

Value = cell. Data

End Property

Процедура let свойства value присваивает ячейке новое значение. Если
новое значение равно NoValue, процедура вызывает для удаления элемента
из массива. В противном случае, она ищет требуемое положение элемента в
нужной строке. Если элемент уже существует, процедура обновляет его
значение. Иначе, она создает новый элемент и добавляет его к списку
строки. Затем она добавляет новый элемент в правильное положение в
соответствующем списке столбцов.

Property Let Value (r As Integer, c As Integer, new_value As Variant)

Dim i As Integer

Dim found_it As Boolean

Dim cell As SparseArrayCell

Dim nxt As SparseArrayCell

Dim new_cell As SparseArrayCell

‘ Если value = MoValue, удалить элемент из массива.

If new_value = NoValue Then

RemoveEntry r, c

Exit Property

End If

‘ Если нужно, добавить строки.

If r > NumRows Then

ReDim Preserve RowHead(1 To r)

‘ Инициализировать метку для каждой новой строки.

For i = NumRows + 1 To r

Set RowHead(i) = New SparseArrayCell

Next i

End If

‘ Если нужно, добавить столбцы.

If c > NumCols Then

ReDim Preserve ColHead(1 To c)

‘ Инициализировать метку для каждой новой строки.

For i = NumCols + 1 To c

Set ColHead(i) = New SparseArrayCell

Next i

NumCols = c

End If

‘ Попытка найти элемент.

Set cell = RowHead(r)

Set nxt = cell.NextInRow

Do

If nxt Is Nothing Then Exit Do

If nxt.Col >= c Then Exit Do

Set cell = nxt

Set nxt = cell.NextInRow

Loop

‘ Проверка, найден ли элемент.

If nxt Is Nothing Then

found_it = False

Else

found_it = (nxt.Col = c)

End If

‘ Если элемент не найден, создать его.

If Not found_it Then

Set new_cell = New SparseArrayCell

‘ Поместить элемент в список строки.

Set new_cell.NextInRow = nxt

Set cell.NextInRow = new_cell

‘ Поместить элемент в список столбца.

Set cell = ColHead(c)

Set nxt = cell.NextInCol

Do

If nxt Is Nothing Then Exit Do

If nxt.Col >= c Then Exit Do

Set cell = nxt

Set nxt = cell.NextInRow

Loop

Set new_cell.NextInCol = nxt

Set cell.NextInCol = new_cell

new_cell.Row = r

new_cell.Col = c

‘ Поместим значение в элемент nxt.

Set nxt = new_cell

End If

‘ Установим значение.

nxt.Data = new_value

End Property

Программа Sparse, показанная на рис. 4.10, использует классы SparseArray
и SparseArrayCell для работы с разреженным массивом. Используя
программу, можно устанавливать и извлекать элементы массива. В этой
программе значение NoValue равно нулю, поэтому если вы установите
значение элемента равным нулю, программа удалит этот элемент из массива.

Очень разреженные массивы

Некоторые массивы содержат так мало непустых элементов, что многие
строки и столбцы полностью пусты. В этом случае, лучше хранить заголовки
строк и столбцов в связных списках, а не в массивах. Это позволяет
программе полностью пропускать пустые строки и столбцы. Заголовки строки
и столбцов указывают на связные списки элементов строк и столбцов. На
рис. 4.11 показан массив 100 на 100, который содержит всего 7 непустых
элементов.

@Рис. 4.10. Программа Sparse

=====76-78

@Рис. 4.11. Очень разреженный массив

Для работы с массивами этого типа можно довольно просто доработать
предыдущий код. Большая часть кода остается неизменной, и для элементов
массива можно использовать тот же самый класс SparseArray.Тем не менее,
вместо хранения меток строк и столбцов в массивах, они записываются в
связных списках.

Объекты класса HeaderCell представляют связные списки строк и столбцов.
В этом классе определяются переменные, содержащие число строк и
столбцов, которые он представляет, сигнальная метка в начале связного
списка элементов строк или столбцов, и объект HeaderCell, представляющий
следующий заголовок строки или столбца.

Public Number As Integer ‘ Номер строки или столбца.

Public Sentinel As SparseArrayCell ‘ Метка для строки или

‘ столбца.

Public NextHeader As HeaderCell ‘ Следующая строка или

‘ столбец.

Например, чтобы обратиться к строке I, нужно вначале просмотреть связный
список заголовков HeaderCells строк, пока не найдется заголовок,
соответствующий строке I. Затем продолжается работа со строкой I.

Private Sub PrintRow(r As Integer)

Dim row As HeaderCell

Dim cell As SparseArrayCell

‘ Найти правильный заголовок строки.

Set row = RowHead. NextHeader ‘ Список первой строки.

Do

If row Is Nothing Then Exit Sub ‘ Такой строки нет.

If row.Number > r Then Exit Sub ‘ Такой строки нет.

If row.Number = r Then Exit Do ‘ Строка найдена.

Set row = row.NextHeader

Loop

‘ Вывести элементы в строке.

Set cell = row.Sentinel. NextInRow ‘ Первый элемент в строке.

Do While Not (cell Is Nothing)

Print Format$(cell.FromCity) & ” -> ” & Format$(cell.ToCity)

Set cell = cell.NextInRow

Loop

End Sub

Резюме

Некоторые программы используют массивы, содержащие только небольшое
число значащих элементов. Использование обычных массивов Visual Basic
привело бы к большим потерям памяти. Используя треугольные,
нерегулярные, разреженные и очень разреженные массивы, вы можете
создавать мощные представления массивов, которые требуют намного меньших
объемов памяти.

=========80

Глава 5. Рекурсия

Рекурсия — мощный метод программирования, который позволяет разбить
задачу на части все меньшего и меньшего размера до тех пор, пока они не
станут настолько малы, что решение этих подзадач сведется к набору
простых операций.

После того, как вы приобретете опыт применения рекурсии, вы будете
обнаруживать ее повсюду. Многие программисты, недавно овладевшие
рекурсией, увлекаются, и начинают применять ее в ситуациях, когда она
является ненужной, а иногда и вредной.

В первых разделах этой главы обсуждается вычисление факториалов, чисел
Фибоначчи, и наибольшего общего делителя. Все эти алгоритмы являются
примерами плохого использования рекурсии — нерекурсивные версии этих
алгоритмов намного эффективнее. Эти примеры интересны и наглядны,
поэтому имеет смысл обсудить их.

Затем, в главе рассматривается несколько примеров, в которых применение
рекурсии более уместно. Алгоритмы построения кривых Гильберта и
Серпинского используют рекурсию правильно и эффективно.

В последних разделах этой главы объясняется, почему реализацию
алгоритмов вычисления факториалов, чисел Фибоначчи, и наибольшего общего
делителя лучше осуществлять без применения рекурсии. В этих параграфах
объясняется также, когда следует избегать рекурсии, и приводятся способы
устранения рекурсии, если это необходимо.

Что такое рекурсия?

Рекурсия происходит, если функция или подпрограмма вызывает сама себя.
XE “Рекурсия:прямая” Прямая рекурсия (direct recursion XE
“recursion:direct” ) выглядит примерно так:

Function Factorial(num As Long) As Long

Factorial = num * Factorial(num – 1)

End Function

В случае XE “Рекурсия:косвенная” косвенной рекурсии (indirect recursion
XE “recursion:indirect” ) рекурсивная процедура вызывает другую
процедуру, которая, в свою очередь, вызывает первую:

Private Sub Ping(num As Integer)

Pong(num – 1)

End Sub

Private Sub Pong(num As Integer)

Ping(num / 2)

End Sub

===========81

Рекурсия полезна при решении задач, которые естественным образом
разбиваются на несколько подзадач, каждая из которых является более
простым случаем исходной задачи. Можно представить дерево на рис. 5.1 в
виде «ствола», на котором находятся два дерева меньших размеров. Тогда
можно написать рекурсивную процедуру для рисования деревьев:

Private Sub DrawTree()

Нарисовать “ствол”

Нарисовать дерево меньшего размера, повернутое на -45 градусов

Нарисовать дерево меньшего размера, повернутое на 45 градусов

End Sub

Хотя рекурсия и может упростить понимание некоторых проблем, люди обычно
не мыслят рекурсивно. Они обычно стремятся разбить сложные задачи на
задачи меньшего объема, которые могут быть выполнены последовательно
одна за другой до полного завершения. Например, чтобы покрасить
изгородь, можно начать с ее левого края и продолжать двигаться вправо до
завершения. Вероятно, во время выполнения подобной задачи вы не думаете
о возможности рекурсивной окраски — вначале левой половины изгороди, а
затем рекурсивно — правой.

Для того чтобы думать рекурсивно, нужно разбить задачу на подзадачи,
которые затем можно разбить на подзадачи меньшего размера. В какой-то
момент подзадачи становятся настолько простыми, что могут быть выполнены
непосредственно. Когда завершится выполнение подзадач, большие
подзадачи, которые из них составлены, также будут выполнены. Исходная
задача окажется выполнена, когда будут все выполнены образующие ее
подзадачи.

Рекурсивное вычисление факториалов

Факториал XE “Факториал” XE “factorial” числа N записывается как
N! (произносится «эн факториал»). По определению, 0! равно 1. Остальные
значения определяются формулой:

N! = N * (N – 1) * (N – 2) * … * 2 * 1

Как уже упоминалось в 1 главе, эта функция чрезвычайно быстро растет с
увеличением N. В табл. 5.1 приведены 10 первых значений функции
факториала.

Можно также определить функцию факториала рекурсивно:

0! = 1

N! = N * (N – 1)! для N > 0.

@Рис. 5.1. Дерево, составленное из двух деревьев меньшего размера

===========82

@Таблица 5.1. Значения функции факториала

Легко написать на основе этого определения рекурсивную функцию:

Public Function Factorial(num As Integer) As Integer

If num A / 2. Первым рекурсивным
вызовом функции GCD будет GCD(B Mod A, A).

Подстановка в функцию значения B Mod A и A вместо A и B дает следующий
рекурсивный вызов GCD(B Mod A, A).

Но мы предположили, что B Mod A > A / 2. Тогда B Mod A разделится на A
только один раз, с остатком A – (B Mod A). Так как B Mod A больше, чем A
/ 2, то A – (B Mod A) должно быть меньше, чем A / 2. Значит, первый
параметр второго рекурсивного вызова функции GCD меньше, чем A / 2, что
и требовалось доказать.

Предположим теперь, что N — это исходное значение параметра A. После
двух вызовов функции GCD, значение параметра A должно уменьшится, по
крайней мере, до N / 2. После четырех вызовов, это значение будет не
больше, чем (N / 2) / 2 = N / 4. После шести вызовов, значение не будет
превосходить (N / 4) / 2 = N / 8. В общем случае, после 2 * K вызовов
функции GCD, значение параметра A будет не больше, чем N / 2K.

Поскольку алгоритм должен остановиться, когда значение параметра A
дойдет до 1, он может продолжать работу только до тех, пока не
выполняется равенство N/2K=1. Это происходит, когда N=2K или когда
K=log2(N). Так как алгоритм выполняется за 2*K шагов это означает, что
алгоритм остановится не более, чем через 2*log2(N) шагов. С точностью до
постоянного множителя, это означает, что алгоритм выполняется за время
порядка O(log(N)).

=======85

Этот алгоритм — один из множества рекурсивных алгоритмов, которые
выполняются за время порядка O(log(N)). При выполнении фиксированного
числа шагов, в данном случае 2, размер задачи уменьшается вдвое. В общем
случае, если размер задачи уменьшается, по меньшей мере, в D раз после
каждых S шагов, то задача потребует S*logD(N) шагов.

Поскольку при оценке по порядку величины можно игнорировать постоянные
множители и основания логарифмов, то любой алгоритм, который выполняется
за время S*logD(N), будет алгоритмом порядка O(log(N)). Это не
обязательно означает, что этими постоянными можно полностью пренебречь
при реализации алгоритма. Алгоритм, который уменьшает размер задачи при
каждом шаге в 10 раз, вероятно, будет быстрее, чем алгоритм, который
уменьшает размер задачи вдвое через каждые 5 шагов. Тем не менее, оба
эти алгоритма имеют время выполнения порядка O(log(N)).

Алгоритмы порядка O(log(N)) обычно выполняются очень быстро, и алгоритм
нахождения наибольшего общего делителя не является исключением из этого
правила. Например, чтобы найти, что наибольший общий делитель чисел
1.736.751.235 и 2.135.723.523 равен 71, функция вызывается всего 17 раз.
Фактически, алгоритм практически мгновенно вычисляет значения, не
превышающие максимального значения числа в формате long — 2.147.483.647.
Функция Visual Basic Mod не может оперировать значениями, большими
этого, поэтому это практический предел для данной реализации алгоритма.

Программа GCD использует этот алгоритм для рекурсивного вычисления
наибольшего общего делителя. Введите значения для A и B, затем нажмите
на кнопку Go, и программа вычислит наибольший общий делитель этих двух
чисел.

Рекурсивное вычисление чисел Фибоначчи

Можно рекурсивно определить числа Фибоначчи XE “Числа:Фибоначчи”
(Fibonacci numbers XE “Fibonacci numbers” ) при помощи уравнений:

Fib(0) = 0

Fib(1) = 1

Fib(N) = Fib(N – 1) + Fib(N – 2) для N > 1.

Третье уравнение рекурсивно дважды вызывает функцию Fib, один раз с
входным значением N-1, а другой — со значением N-2. Это определяет
необходимость 2 условий остановки рекурсии: Fib(0)=0 и Fib(1)=1. Если
задать только одно из них, рекурсия может оказаться бесконечной.
Например, если задать только Fib(0)=0, то значение Fib(2) могло бы
вычисляться следующим образом:

Fib(2) = Fib(1) + Fib(0)

= [Fib(0) + Fib(-1)] + 0

= 0 + [Fib(-2) + Fib(-3)]

= [Fib(-3) + Fib(-4)] + [Fib(-4) + Fib(-5)]

И т.д.

Это определение чисел Фибоначчи легко преобразовать в рекурсивную
функцию:

Public Function Fib(num As Integer) As Integer

If num  1, то функция рекурсивно вычисляет Fib(N-1) и Fib(N-2), и
завершает работу. При первом вызове функции, условие остановки не
выполняется — оно достигается только в следующих, рекурсивных вызовах.
Полное число выполнения условия остановки для входного значения N,
складывается из числа раз, которое оно выполняется для значения N-1 и
числа раз, которое оно выполнялось для значения N-2. Все это можно
записать так:

G(0) = 1

G(1) = 1

G(N) = G(N – 1) + G(N – 2) для N > 1.

Это рекурсивное определение очень похоже на определение чисел Фибоначчи.
В табл. 5.2 приведены некоторые значения функций G(N) и Fib(N). Легко
увидеть, что G(N) = Fib(N+1).

Теперь рассмотрим, сколько раз алгоритм достигает рекурсивного шага.
Если N1, функция достигает
этого шага 1 раз и затем рекурсивно вычисляет Fib(n-1) и Fib(N-2). Пусть
H(N) — число раз, которое алгоритм достигает рекурсивного шага для входа
N. Тогда H(N)=1+H(N-1)+H(N-2). Уравнения, определяющие H(N):

H(0) = 0

H(1) = 0

H(N) = 1 + H(N – 1) + H(N – 2) для N > 1.

В табл. 5.3 показаны некоторые значения для функций Fib(N) и H(N). Можно
увидеть, что H(N)=Fib(N+1)-1.

@Таблица 5.2. Значения чисел Фибоначчи и функции G(N)

======87

@Таблица 5.3. Значения чисел Фибоначчи и функции H(N)

Объединяя результаты для G(N) и H(N), получаем полное время выполнения
для алгоритма:

Время выполнения = G(N) + H(N)

= Fib(N + 1) + Fib(N + 1) – 1

= 2 * Fib(N + 1) – 1

Поскольку Fib(N + 1) >= Fib(N) для всех значений N, то:

Время выполнения >= 2 * Fib(N) – 1

С точностью до порядка это составит O(Fib(N)). Интересно, что эта
функция не только рекурсивная, но она также используется для оценки
времени ее выполнения.

Чтобы помочь вам представить скорость роста функции Фибоначчи, можно
показать, что Fib(M)>(M-2 где ( — константа, примерно равная 1,6. Это
означает, что время выполнения не меньше, чем значение экспоненциальной
функции O((M). Как и другие экспоненциальные функции, эта функция растет
быстрее, чем полиномиальные функции, но медленнее, чем функция
факториала.

Поскольку время выполнения растет очень быстро, этот алгоритм довольно
медленно выполняется для больших входных значений. Фактически, настолько
медленно, что на практике почти невозможно вычислить значения функции
Fib(N) для N, которые намного больше 30. В табл. 5.4 показано время
выполнения для этого алгоритма на компьютере с процессором Pentium с
тактовой частотой 90 МГц при разных входных значениях.

Программа Fibo использует этот рекурсивный алгоритм для вычисления чисел
Фибоначчи. Введите целое число и нажмите на кнопку Go для вычисления
чисел Фибоначчи. Начните с небольших чисел, пока не оцените, насколько
быстро ваш компьютер может выполнять эти вычисления.

Рекурсивное построение кривых Гильберта

Кривые Гильберта (Hilbert curves XE “Hilbert curves” ) XE
“Кривые:Гильберта”  — это самоподобные (self-similar) кривые, которые
обычно определяются при помощи рекурсии. На рис. 5.2. показаны кривые
Гильберта с 1, 2 или 3 порядка.

@Таблица 5.4. Время выполнения программы Fibonacci

=====88

@Рис. 5.2. Кривые Гильберта

Кривая Гильберта, как и любая другая самоподобная кривая, создается
разбиением большой кривой на меньшие части. Затем вы можете использовать
эту же кривую, после изменения размера и поворота, для построения этих
частей. Эти части можно разбить на более мелкие части, и так далее, пока
процесс не достигнет нужной глубины рекурсии. Порядок кривой
определяется как максимальная глубина рекурсии, которой достигает
процедура.

Процедура Hilbert управляет глубиной рекурсии, используя соответствующий
параметр. При каждом рекурсивном вызове, процедура уменьшает параметр
глубины рекурсии на единицу. Если процедура вызывается с глубиной
рекурсии, равной 1, она рисует простую кривую 1 порядка, показанную на
рис. 5.2 слева и завершает работу. Это условие остановки рекурсии.

Например, кривая Гильберта 2 порядка состоит из четырех кривых Гильберта
1 порядка. Аналогично, кривая Гильберта 3 порядка состоит из четырех
кривых 2 порядка, каждая из которых состоит из четырех кривых 1 порядка.
На рис. 5.3 показаны кривые Гильберта 2 и 3 порядка. Меньшие кривые, из
которых построены кривые большего размера, выделены полужирными линиями.

Следующий код строит кривую Гильберта 1 порядка:

Line -Step (Length, 0)

Line -Step (0, Length)

Line -Step (-Length, 0)

Предполагается, что рисование начинается с верхнего левого угла области
и что Length — это заданная длина каждого отрезка линий.

Можно набросать черновик метода, рисующего кривые Гильберта более
высоких порядков:

Private Sub Hilbert(Depth As Integer)

If Depth = 1 Then

Нарисовать кривую Гильберта 1 порядка

Else

Нарисовать и соединить 4 кривые порядка (Depth – 1)

End If

End Sub

====89

@Рис. 5.3. Кривые Гильберта, образованные меньшими кривыми

Этот метод требует небольшого усложнения для определения направления
рисования кривых. Это требуется для того, чтобы выбрать тип используемых
кривых Гильберта.

Эту информацию можно передать процедуре при помощи параметров Dx и Dy
для определения направления вывода первой линии в кривой. Для кривой 1
порядка, процедура рисует первую линию при помощи функции Line-Step(Dx,
Dy). Если кривая имеет более высокий порядок, процедура соединяет первые
две подкривых, используя функцию Line-Step(Dx, Dy). В любом случае,
процедура может использовать параметры Dx и Dy для выбора направления, в
котором она должна рисовать линии, образующие кривую.

Код на языке Visual Basic для рисования кривых Гильберта короткий, но
сложный. Вам может потребоваться несколько раз пройти его в отладчике
для кривых 1 и 2 порядка, чтобы увидеть, как изменяются параметры Dx и
Dy, при построении различных частей кривой.

Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)

If depth > 1 Then Hilbert depth – 1, Dy, Dx

HilbertPicture.Line -Step(Dx, Dy)

If depth > 1 Then Hilbert depth – 1, Dx, Dy

HilbertPicture.Line -Step(Dy, Dx)

If depth > 1 Then Hilbert depth – 1, Dx, Dy

HilbertPicture.Line -Step(-Dx, -Dy)

If depth > 1 Then Hilbert depth – 1, -????????

Анализ времени выполнения программы

Чтобы проанализировать время выполнения этой процедуры, вы можете
определить число вызовов процедуры Hilbert. При каждой рекурсии она
вызывает себя четыре раза. Если T(N) — это число вызовов процедуры,
когда она вызывается с глубиной рекурсии N, то:

T(1) = 1

T(N) = 1 + 4 * T(N – 1) для N > 1.

Если раскрыть определение T(N), получим:

T(N) = 1 + 4 * T(N – 1)

= 1 + 4 *(1 + 4 * T(N – 2))

= 1 + 4 + 16 * T(N – 2)

= 1 + 4 + 16 * (1 + 4 * T(N – 3))

= 1 + 4 + 16 + 64 * T(N – 3)

= …

= 40 + 41 + 42 + 43 + … + 4K * T(N – K)

Раскрыв это уравнение до тех пор, пока не будет выполнено условие
остановки рекурсии T(1)=1, получим:

T(N) = 40 + 41 + 42 + 43 + … + 4N-1

Это уравнение можно упростить, воспользовавшись соотношением:

X0 + X1 + X2 + X3 + … + XM = (XM+1 – 1) / (X – 1)

После преобразования, уравнение приводится к виду:

T(N) = (4(N-1)+1 – 1) / (4 – 1)

= (4N – 1) / 3

=====90

С точностью до постоянных, эта процедура выполняется за время порядка
O(4N). В табл. 5.5 приведены несколько первых значений функции времени
выполнения. Если вы внимательно посмотрите на эти числа, то увидите, что
они соответствуют рекурсивному определению.

Этот алгоритм является типичным примером рекурсивного алгоритма, который
выполняется за время порядка O(CN), где C — некоторая постоянная. При
каждом вызове подпрограммы Hilbert, она увеличивает размерность задачи в
4 раза. В общем случае, если при каждом выполнении некоторого числа
шагов алгоритма размер задачи увеличивается не менее, чем в C раз, то
время выполнения алгоритма будет порядка O(CN).

Это поведение противоположно поведению алгоритма поиска наибольшего
общего делителя. Процедура GCD уменьшает размерность задачи в 2 раза при
каждом втором своем вызове, и поэтому время ее выполнения порядка
O(log(N)). Процедура построения кривых Гильберта увеличивает размер
задачи в 4 раза при каждом своем вызове, поэтому время ее выполнения
порядка O(4N).

Функция (4N-1)/3 — это экспоненциальная функция, которая растет очень
быстро. Фактически, она растет настолько быстро, что вы можете
предположить, что это не слишком эффективный алгоритм. В
действительности работа этого алгоритма занимает много времени, но есть
две причины, по которым это не так уж и плохо.

Во-первых, ни один алгоритм для построения кривых Гильберта не может
быть намного быстрее. Кривые Гильберта содержат множество отрезков
линий, и любой рисующий их алгоритм будет требовать достаточно много
времени. При каждом вызове процедуры Hilbert, она рисует три линии.
Пусть L(N) — суммарное число линий, из которых состоит кривая Гильберта
порядка N. Тогда L(N) = 3 * T(N) = 4N – 1, поэтому L(N) также порядка
O(4N). Любой алгоритм, рисующий кривые Гильберта, должен вывести O(4N)
линий, выполнив при этом O(4N) шагов. Существуют другие алгоритмы
построения кривых Гильберта, но они занимают почти столько же времени,
сколько и этот алгоритм.

@Таблица 5.5. Число рекурсивных вызовов подпрограммы Hilbert

=====91

Второй факт, который показывает, что этот алгоритм не так уж плох,
заключается в том, что кривые Гильберта 9 порядка содержат так много
линий, что экран большинства компьютерных мониторов при этом оказывается
полностью закрашенным. Это неудивительно, так как эта кривая содержит
262.143 отрезков линий. Это означает, что вам вероятно никогда не
понадобится выводить на экран кривые Гильберта 9 или более высоких
порядков. На каком-то порядке вы столкнетесь с ограничениями языка
Visual Basic и вашего компьютера, но, скорее всего, вы еще раньше будете
ограничены максимальным разрешением экрана.

Программа Hilbert, показанная на рис. 5.4, использует этот рекурсивный
алгоритм для рисования кривых Гильберта. При выполнении программы не
задавайте слишком большую глубину рекурсии (больше 6) до тех пор, пока
вы не определите, насколько быстро выполняется эта программа на вашем
компьютере.

Рекурсивное построение кривых Серпинского

Как и кривые Гильберта, кривые Серпинского (Sierpinski curves XE
“Sierpinski curves” ) XE “Кривые:Серпинского”  — это самоподобные
кривые, которые обычно определяются рекурсивно. На рис. 5.5 показаны
кривые Серпинского 1, 2 и 3 порядка.

Алгоритм построения кривых Гильберта использует всего одну подпрограмму
для рисования кривых. Кривые Серпинского проще рисовать, используя
четыре отдельных процедуры, которые работают совместно. Эти процедуры
называются SierpA, SierpB, SierpC и SierpD. Это процедуры с косвенной
рекурсией — каждая процедура вызывает другие, которые затем вызывают
первоначальную процедуру. Они рисуют верхнюю, левую, нижнюю и правую
части кривой Серпинского, соответственно.

На рис. 5.6 показано, как эти процедуры работают совместно, образуя
кривую Серпинского 1 порядка. Подкривые изображены стрелками, чтобы
показать направление, в котором они рисуются. Отрезки, соединяющие
четыре подкривые, нарисованы пунктирными линиями.

@Рис. 5.4. Программа Hilbert

=====92

@Рис. 5.5. Кривые Серпинского

Каждая из четырех основных кривых состоит из диагонального отрезка,
затем вертикального или горизонтального отрезка, и еще одного
диагонального отрезка. Если глубина рекурсии больше единицы, каждая из
этих кривых разбивается на меньшие части. Это осуществляется разбиением
каждого из двух диагональных отрезков на две подкривые.

Например, для разбиения кривой типа A, первый диагональный отрезок
разбивается на кривую типа A, за которой следует кривая типа B. Затем
рисуется без изменений горизонтальный отрезок из исходной кривой типа A.
Наконец, второй диагональный отрезок разбивается на кривую типа D, за
которой следует кривая типа A. На рис. 5.7 показано, как кривая типа A
второго порядка образуется из нескольких кривых 1 порядка. Подкривые
изображены жирными линиями.

На рис. 5.8 показано, как полная кривая Серпинского 2 порядка образуется
из 4 подкривых 1 порядка. Каждая из подкривых обведена контурной линией.

Можно использовать стрелки ( и ( для обозначения типа линий, соединяющих
подкривые (тонкие линии на рис. 5.8), тогда можно будет изобразить
рекурсивные отношения между четырьмя типами кривых так, как это показано
на рис. 5.9.

@Рис. 5.6. Части кривой Серпинского

=====93

@Рис. 5.7. Разбиение кривой типа A

Все процедуры для построения подкривых Серпинского очень похожи, поэтому
мы приводим здесь только одну из них. Соотношения на рис. 5.9
показывают, какие операции нужно выполнить для рисования кривых
различных типов. Соотношения для кривой типа A реализованы в следующем
коде. Вы можете использовать остальные соотношения, чтобы определить,
какие изменения нужно внести в код для рисования кривых других типов.

Private Sub SierpA(Depth As Integer, Dist As Single)

If Depth = 1 Then

Line -Step(-Dist, Dist)

Line -Step(-Dist, 0)

Line -Step(-Dist, -Dist)

Else

SierpA Depth – 1, Dist

Line -Step(-Dist, Dist)

SierpB Depth – 1, Dist

Line -Step(-Dist, 0)

SierpD Depth – 1, Dist

Line -Step(-Dist, -Dist)

SierpA Depth – 1, Dist

End If

End Sub

@Рис. 5.8. Кривые Серпинского, образованные из меньших кривых
Серпинского

=====94

@Рис. 5.9. Рекурсивные соотношения между кривыми Серпинского

Кроме процедур, которые рисуют каждую из основных кривых, потребуется
еще процедура, которая по очереди вызывает их все для создания
законченной кривой Серпинского.

Sub Sierpinski (Depth As Integer, Dist As Single)

SierpB Depth, Dist

Line -Step(Dist, Dist)

SierpC Depth, Dist

Line -Step(Dist, -Dist)

SierpD Depth, Dist

Line -Step(-Dist, -Dist)

SierpA Depth, Dist

Line -Step(-Dist, Dist)

End Sub

Анализ времени выполнения программы

Чтобы проанализировать время выполнения этого алгоритма, необходимо
определить число вызовов для каждой из четырех процедур рисования
кривых. Пусть T(N) — число вызовов любой из четырех основных подпрограмм
основной процедуры Sierpinski при построении кривой порядка N.

Если порядок кривой равен 1, кривая каждого типа рисуется только один
раз. Прибавив сюда основную процедуру, получим T(1) = 5.

При каждом рекурсивном вызове, процедура вызывает саму себя или другие
процедуры четыре раза. Так как эти процедуры практически одинаковые, то
T(N) будет одинаковым, независимо от того, какая процедура вызывается
первой. Это обусловлено тем, что кривые Серпинского симметричны и
содержат одно и то же число кривых разных типов. Рекурсивные уравнения
для T(N) выглядят так:

T(1) = 5

T(N) = 1 + 4 * T(N-1) для N > 1.

Эти уравнения почти совпадают с уравнениями, которые использовались для
оценки времени выполнения алгоритма, рисующего кривые Гильберта.
Единственное отличие состоит в том, что для кривых Гильберта T(1) = 1.
Сравнение значений этих уравнений показывает, что
TSierpinski(N) = THilbert(N+1). В конце предыдущего раздела было
показано, что THilbert(N) = (4N – 1) / 3, поэтому TSierpinski(N) = (4N+1
– 1) / 3, что также составляет O(4N).

=====95

Так же, как и алгоритм построения кривых Гильберта, этот алгоритм
выполняется за время порядка O(4N), но это не так уж и плохо. Кривая
Серпинского состоит из O(4N) линий, поэтому ни один алгоритм не может
нарисовать кривую Серпинского быстрее, чем за время порядка O(4N).

Кривые Серпинского также полностью заполняют экран большинства
компьютеров при порядке кривой, большем или равном 9. При каком-то
порядке, большем 9, вы столкнетесь с ограничениями языка Visual Basic и
возможностей вашего компьютера, но, скорее всего, вы еще раньше будете
ограничены предельным разрешением экрана.

Программа Sierp, показанная на рис. 5.10, использует этот рекурсивный
алгоритм для рисования кривых Серпинского. При выполнении программы,
задавайте вначале небольшую глубину рекурсии (меньше 6), до тех пор,
пока вы не определите, насколько быстро выполняется эта программа на
вашем компьютере.

Опасности рекурсии

Рекурсия может служить мощным методом разбиения больших задач на части,
но она таит в себе несколько опасностей. В этом разделе мы пытаемся
охватить некоторые из этих опасностей и объяснить, когда стоит и не
стоит использовать рекурсию. В последующих разделах приводятся методы
устранения от рекурсии, когда это необходимо.

Бесконечная рекурсия

Наиболее очевидная опасность рекурсии заключается в бесконечной
рекурсии. Если неправильно построить алгоритм, то функция может
пропустить условие остановки рекурсии и выполняться бесконечно. Проще
всего совершить эту ошибку, если просто забыть о проверке условия
остановки, как это сделано в следующей ошибочной версии функции
факториала. Поскольку функция не проверяет, достигнуто ли условие
остановки рекурсии, она будет бесконечно вызывать сама себя.

@Рис. 5.10 Программа Sierp

=====96

Private Function BadFactorial(num As Integer) As Integer

BadFactorial = num * BadFactorial (num – 1)

End Function

Функция также может вызывать себя бесконечно, если условие остановки не
прекращает все возможные пути рекурсии. В следующей ошибочной версии
функции факториала, функция будет бесконечно вызывать себя, если входное
значение — не целое число, или если оно меньше 0. Эти значения не
являются допустимыми входными значениями для функции факториала, поэтому
в программе, которая использует эту функцию, может потребоваться
проверка входных значений. Тем не менее, будет лучше, если функция
выполнит эту проверку сама.

Private Function BadFactorial2(num As Double) As Double

If num = 0 Then

BadFactorial2 = 1

Else

BadFactorial2 = num * BadFactorial2(num-1)

End If

End Function

Следующая версия функции Fibonacci является более сложным примером. В
ней условие остановки рекурсии прекращает выполнение только нескольких
путей рекурсии, и возникают те же проблемы, что и при выполнении функции
BadFactorial2, если входные значения отрицательные или не целые.

Private Function BadFib(num As Double) As Double

If num = 0 Then

BadFib = 0

Else

BadFib = BadPib(num – 1) + BadFib (num – 2)

End If

End Function

И последняя проблема, связанная с бесконечной рекурсией, заключается в
том, что «бесконечная» на самом деле означает «до тех пор, пока не будет
исчерпано стековое пространство». Даже корректно написанные рекурсивные
процедуры будут иногда приводить к переполнению стека и аварийному
завершению работы. Следующая функция, которая вычисляет сумму N + (N –
1) + … + 2 +1, приводит к исчерпанию стекового пространства при больших
значениях N. Наибольшее возможное значение N, при котором программа еще
будет работать, зависит от конфигурации вашего компьютера.

Private Function BigAdd(N As Double) As Double

If N 1

value = value * N

N = N – 1 ‘ Подготовить аргументы для “рекурсии”.

Loop

Factorial = value

End Function

Private Function GCD(ByVal A As Double, ByVal B As Double) As Double

Dim B_Mod_A As Double

B_Mod_A = B Mod A

Do While B_Mod_A 0

‘ Подготовить аргументы для “рекурсии”.

B = A

A = B_Mod_A

B_Mod_A = B Mod A

Loop

GCD = A

End Function

Private Function BigAdd(ByVal N As Double) As Double

Dim value As Double

value = 1# ‘ ‘ Это будет значением функции.

Do While N > 1

value = value + N

N = N – 1 ‘ подготовить параметры для “рекурсии”.

Loop

BigAdd = value

End Function

=====101

Для алгоритмов вычисления факториала и наибольшего общего делителя
практически не существует разницы между рекурсивной и нерекурсивной
версиями. Обе версии выполняются достаточно быстро, и обе они могут
оперировать задачами большой размерности.

Для функции BigAdd, тем не менее, разница огромна. Рекурсивная версия
приводит к переполнению стека даже для довольно небольших входных
значений. Поскольку нерекурсивная версия не использует стек, она может
вычислять результат для значений N вплоть до 10154. После этого наступит
переполнение для данных типа double. Конечно, выполнение 10154 шагов
алгоритма займет очень много времени, поэтому возможно вы не станете
проверять этот факт сами. Заметим также, что значение этой функции
совпадает со значением более просто вычисляемой функции
N * N(N + 1) / 2.

Программы Facto2, GCD2 и BigAdd2 демонстрируют эти нерекурсивные
алгоритмы.

Нерекурсивное вычисление чисел Фибоначчи

К сожалению, нерекурсивный алгоритм вычисления чисел Фибоначчи не
содержит только хвостовую рекурсию. Этот алгоритм использует два
рекурсивных вызова для вычисления значения, и второй вызов следует после
завершения первого. Поскольку первый вызов не находится в самом конце
функции, то это не хвостовая рекурсия, и от ее нельзя избавиться,
используя прием устранения хвостовой рекурсии.

Это может быть связано и с тем, что ограничение рекурсивного алгоритма
вычисления чисел Фибоначчи связано с тем, что он вычисляет слишком много
промежуточных значений, а не глубиной вложенности рекурсии. Устранение
хвостовой рекурсии уменьшает глубину рекурсии, но оно не изменяет время
выполнения алгоритма. Даже если бы устранение хвостовой рекурсии было бы
применимо к алгоритму вычисления чисел Фибоначчи, этот алгоритм все
равно остался бы чрезвычайно медленным.

Проблема этого алгоритма в том, что он многократно вычисляет одни и те
же значения. Значения Fib(1) и Fib(0) вычисляются Fib(N + 1) раз, когда
алгоритм вычисляет Fib(N). Для вычисления Fib(29), алгоритм вычисляет
одни и те же значения Fib(0) и Fib(1) 832.040 раз.

Поскольку алгоритм многократно вычисляет одни и те же значения, следует
найти способ избежать повторения вычислений. Простой и конструктивный
способ сделать это — построить таблицу вычисленных значений. Когда
понадобится промежуточное значение, можно будет взять его из таблицы,
вместо того, чтобы вычислять его заново.

=====102

В этом примере можно создать таблицу для хранения значений функции
Фибоначчи Fib(N) для N, не превосходящих 1477. Для N >= 1477 происходит
переполнение переменных типа double, используемых в функции. Следующий
код содержит измененную таким образом функцию, вычисляющую числа
Фибоначчи.

Const MAX_FIB = 1476 ‘ Максимальное значение.

Dim FibValues(0 To MAX_FIB) As Double

Private Function Fib(N As Integer) As Double

‘ Вычислить значение, если оно не находится в таблице.

If FibValues(N)

Subr()

End Sub

Поскольку после рекурсивного шага есть еще операторы, вы не можете
использовать устранение хвостовой рекурсии для этого алгоритма.

=====105

Вначале пометим первые строки в 1 и 2 блоках кода. Затем эти метки будут
использоваться для определения места, с которого требуется продолжить
выполнение при возврате из «рекурсии». Эти метки используются только для
того, чтобы помочь вам понять, что делает алгоритм — они не являются
частью кода Visual Basic. В этом примере метки будут выглядеть так:

Sub Subr(num)

1

Subr()

2

End Sub

Используем специальную метку «0» для обозначения конца «рекурсии».
Теперь можно переписать процедуру без использования рекурсии, например,
так:

Sub Subr(num)

Dim pc As Integer ‘ Определяет, где нужно продолжить рекурсию.

pc = 1 ‘ Начать сначала.

Do

Select Case pc

Case 1

If (достигнуто условие остановки) Then

‘ Пропустить рекурсию и перейти к блоку 2.

pc = 2

Else

‘ Сохранить переменные, нужные после рекурсии.

‘ Сохранить pc = 2. Точка, с которой продолжится

‘ выполнение после возврата из “рекурсии”.

‘ Установить переменные, нужные для рекурсии.

‘ Например, num = num – 1.

:

‘ Перейти к блоку 1 для начала рекурсии.

pc = 1

End If

Case 2 ‘ Выполнить 2 блок кода

pc = 0

Case 0

If (это последняя рекурсия) Then Exit Do

‘ Иначе восстановить pc и другие переменные,

‘ сохраненные перед рекурсией.

End Select

Loop

End Sub

======106

Переменная pc, которая соответствует счетчику программы, сообщает
процедуре, какой шаг она должна выполнить следующим. Например, при
pc = 1, процедура должна выполнить 1 блок кода.

Когда процедура достигает условия остановки, она не выполняет рекурсию.
Вместо этого, она присваивает pc значение 2, и продолжает выполнение 2
блока кода.

Если процедура не достигла условия остановки, она выполняет «рекурсию».
Для этого она сохраняет значения всех локальных переменных, которые ей
понадобятся позже после завершения «рекурсии». Она также сохраняет
значение pc для участка кода, который она будет выполнять после
завершения «рекурсии». В этом примере следующим выполняется 2 блок кода,
поэтому она сохраняет 2 в качестве следующего значения pc. Самый простой
способ сохранения значений локальных переменных и pc состоит в
использовании стеков, подобных тем, которые описывались в 3 главе.

Реальный пример поможет вам понять эту схему. Рассмотрим слегка
измененную версию функции факториала. В нем переписана только
подпрограмма, которая возвращает свое значение при помощи переменной, а
не функции, для упрощения работы.

Private Sub Factorial(num As Integer, value As Integer)

Dim partial As Integer

1 If num 1 Then Hilbert depth – 1, Dy, Dx

HilbertPicture.Line -Step(Dx, Dy)

If depth > 1 Then Hilbert depth – 1, Dx, Dy

HilbertPicture.Line -Step(Dy, Dx)

If depth > 1 Then Hilbert depth – 1, Dx, Dy

HilbertPicture.Line -Step(-Dx, -Dy)

If depth > 1 Then Hilbert depth – 1, -Dy, -Dx

End Sub

В следующем фрагменте кода первые строки каждого блока кода между
рекурсивными шагами пронумерованы. Эти блоки включают первую строку
процедуры и любые другие точки, в которых может понадобиться продолжить
выполнение после возврата после «рекурсии».

Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)

1 If depth > 1 Then Hilbert depth – 1, Dy, Dx

2 HilbertPicture.Line -Step(Dx, Dy)

If depth > 1 Then Hilbert depth – 1, Dx, Dy

3 HilbertPicture.Line -Step(Dy, Dx)

If depth > 1 Then Hilbert depth – 1, Dx, Dy

4 HilbertPicture.Line -Step(-Dx, -Dy)

If depth > 1 Then Hilbert depth – 1, -Dy, -Dx

End Sub

Каждый раз, когда нерекурсивная процедура начинает «рекурсию», она
должна сохранять значения локальных переменных Depth, Dx, и Dy, а также
следующее значение переменной pc. После возврата из «рекурсии», она
восстанавливает эти значения. Для упрощения работы, можно написать пару
вспомогательных процедур для заталкивания и выталкивания этих значений
из нескольких стеков.

====109

Const STACK_SIZE =20

Dim DepthStack(0 To STACK_SIZE)

Dim DxStack(0 To STACK_SIZE)

Dim DyStack(0 To STACK_SIZE)

Dim PCStack(0 To STACK_SIZE)

Dim TopOfStack As Integer

Private Sub SaveValues (Depth As Integer, Dx As Single, _

Dy As Single, pc As Integer)

TopOfStack = TopOfStack + 1

DepthStack(TopOfStack) = Depth

DxStack(TopOfStack) = Dx

DyStack(TopOfStack) = Dy

PCStack(TopOfStack) = pc

End Sub

Private Sub RestoreValues (Depth As Integer, Dx As Single, _

Dy As Single, pc As Integer)

Depth = DepthStack(TopOfStack)

Dx = DxStack(TopOfStack)

Dy = DyStack(TopOfStack)

pc = PCStack(TopOfStack)

TopOfStack = TopOfStack – 1

End Sub

Следующий код демонстрирует нерекурсивную версию подпрограммы Hilbert.

Private Sub Hilbert(Depth As Integer, Dx As Single, Dy As Single)

Dim pc As Integer

Dim tmp As Single

pc = 1

Do

Select Case pc

Case 1

If Depth > 1 Then ‘ Рекурсия.

‘ Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 2

‘ Подготовиться к рекурсии.

Depth = Depth – 1

tmp = Dx

Dx = Dy

Dy = tmp

pc = 1 ‘ Перейти в начало рекурсивного вызова.

Else ‘ Условие остановки.

‘ Достаточно глубокий уровень рекурсии.

‘ Продолжить со 2 блоком кода.

pc = 2

End If

Case 2

HilbertPicture.Line -Step(Dx, Dy)

If Depth > 1 Then ‘ Рекурсия.

‘ Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 3

‘ Подготовиться к рекурсии.

Depth = Depth – 1

‘ Dx и Dy остаются без изменений.

pc = 1 Перейти в начало рекурсивного вызова.

Else ‘ Условие остановки.

‘ Достаточно глубокий уровень рекурсии.

‘ Продолжить с 3 блоком кода.

pc = 3

End If

Case 3

HilbertPicture.Line -Step(Dy, Dx)

If Depth > 1 Then ‘ Рекурсия.

‘ Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 4

‘ Подготовиться к рекурсии.

Depth = Depth – 1

‘ Dx и Dy остаются без изменений.

pc = 1 Перейти в начало рекурсивного вызова.

Else ‘ Условие остановки.

‘ Достаточно глубокий уровень рекурсии.

‘ Продолжить с 4 блоком кода.

pc = 4

End If

Case 4

HilbertPicture.Line -Step(-Dx, -Dy)

If Depth > 1 Then ‘ Рекурсия.

‘ Сохранить текущие значения.

SaveValues Depth, Dx, Dy, 0

‘ Подготовиться к рекурсии.

Depth = Depth – 1

tmp = Dx

Dx = -Dy

Dy = -tmp

pc = 1 Перейти в начало рекурсивного вызова.

Else ‘ Условие остановки.

‘ Достаточно глубокий уровень рекурсии.

‘ Конец этого рекурсивного вызова.

pc = 0

End If

Case 0 ‘ Возврат из рекурсии.

If TopOfStack > 0 Then

RestoreValues Depth, Dx, Dy, pc

Else

‘ Стек пуст. Выход.

Exit Do

End If

End Select

Loop

End Sub

======111

Время выполнения этого алгоритма может быть нелегко оценить
непосредственно. Поскольку методы преобразования рекурсивных процедур в
нерекурсивные не изменяют время выполнения алгоритма, эта процедура так
же, как и предыдущая версия, имеет время выполнения порядка O(N4).

Программа Hilbert2 демонстрирует нерекурсивный алгоритм построения
кривых Гильберта. Задавайте вначале построение несложных кривых (меньше
6 порядка), пока не узнаете, насколько быстро будет выполняться эта
программа на вашем компьютере.

Нерекурсивное построение кривых Серпинского

Приведенный ранее алгоритм построения кривых Серпинского включает в себя
косвенную и множественную рекурсию. Так как алгоритм состоит из четырех
подпрограмм, которые вызывают друг друга, то нельзя просто пронумеровать
важные строки, как это можно было сделать в случае алгоритма построения
кривых Гильберта. С этой проблемой можно справиться, слегка изменив
алгоритм.

Рекурсивная версия этого алгоритма состоит из четырех подпрограмм
SierpA, SierpB, SierpC и SierpD. Подпрограмма SierpA выглядит так:

Private Sub SierpA(Depth As Integer, Dist As Single)

If Depth = 1 Then

Line -Step(-Dist, Dist)

Line -Step(-Dist, 0)

Line -Step(-Dist, -Dist)

Else

SierpA Depth – 1, Dist

Line -Step(-Dist, Dist)

SierpB Depth – 1, Dist

Line -Step(-Dist, 0)

SierpD Depth – 1, Dist

Line -Step(-Dist, -Dist)

SierpA Depth – 1, Dist

End If

End Sub

Три другие процедуры аналогичны. Несложно объединить эти четыре
процедуры в одну подпрограмму.

Private Sub SierpAll(Depth As Integer, Dist As Single, Func As Integer)

Select Case Punc

Case 1 ‘ SierpA

Case 2 ‘ SierpB

Case 3 ‘ SierpC

Case 4 ‘ SierpD

End Select

End Sub

======112

Параметр Func сообщает подпрограмме, какой блок кода выполнять. Вызовы
подпрограмм заменяются на вызовы процедуры SierpAll с соответствующим
значением Func. Например, вызов подпрограммы SierpA заменяется на вызов
процедуры SierpAll с параметром Func, равным 1. Таким же образом
заменяются вызовы подпрограмм SierpB, SierpC и SierpD.

Полученная процедура рекурсивно вызывает себя в 16 различных точках. Эта
процедура намного сложнее, чем процедура Hilbert, но в других отношениях
она имеет такую же структуру и поэтому к ней можно применить те же
методы устранения рекурсии.

Можно использовать первую цифру меток pc, для определения номера блока
кода, который должен выполняться. Перенумеруем строки в коде SierpA
числами 11, 12, 13 и т.д. Перенумеруем строки в коде SierpB числами 21,
22, 23 и т.д.

Теперь можно пронумеровать ключевые строки кода внутри каждого из
блоков. Для кода подпрограммы SierpA ключевыми строками будут:

‘ Код SierpA.

11 If Depth = 1 Then

Line -Step(-Dist, Dist)

Line -Step(-Dist, 0)

Line -Step(-Dist, -Dist)

Else

SierpA Depth – 1, Dist

12 Line -Step(-Dist, Dist)

SierpB Depth – 1, Dist

13 Line -Step(-Dist, 0)

SierpD Depth – 1, Dist

14 Line -Step(-Dist, -Dist)

SierpA Depth – 1, Dist

End If

Типичная «рекурсия» из кода подпрограммы SierpA в код подпрограммы
SierpB выглядит так:

SaveValues Depth, 13 ‘ Продолжить с шага 13 после завершения.

Depth = Depth – 1

pc = 21 ‘ Передать управление на начало кода SierpB.

======113

Метка 0 зарезервирована для обозначения выхода из «рекурсии». Следующий
код демонстрирует нерекурсивную версию процедуры SierpAll. Код для
подпрограмм SierpB, SierpC, и SierpD аналогичен коду для SierpA, поэтому
он опущен.

Private Sub SierpAll(Depth As Integer, pc As Integer)

Do

Select Case pc

‘ **********

‘ * SierpA *

‘ **********

Case 11

If Depth ” & 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) 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

Полные деревья

XE “Деревья:полные” Полное дерево (complete tree XE “tree:complete”
) содержит максимально возможное число узлов на каждом уровне, кроме
нижнего. Все узлы на нижнем уровне сдвигаются влево. Например, каждый
уровень троичного дерева содержит в точности три дочерних узла, за
исключением листьев, и возможно, одного узла на один уровень выше
листьев. На рис. 6.9 показаны полные двоичное и троичное деревья.

Полные деревья обладают рядом важных свойств. Во-первых, это кратчайшие
деревья, которые могут содержать заданное число узлов. Например,
двоичное дерево на рис. 6.9 — одно из самых коротких двоичных деревьев с
шестью узлами. Существуют другие двоичные деревья с шестью узлами, но ни
одно из них не имеет высоту меньше 3.

Во-вторых, если полное дерево порядка D состоит из N узлов, оно будет
иметь высоту порядка O(logD(N)) и O(N) листьев. Эти факты имеют большое
значение, поскольку многие алгоритмы обходят деревья сверху вниз или в
противоположном направлении. Время выполнения алгоритма, выполняющего
одно из этих действий, будет порядка O(N).

Чрезвычайно полезное свойство полных деревьев заключается в том, что они
могут быть очень компактно записаны в массивах. Если пронумеровать узлы
в «естественном» порядке, сверху вниз и слева направо, то можно
поместить элементы дерева в массив в этом порядке. На рис. 6.10
показано, как можно записать полное дерево в массиве.

Корень дерева находится в нулевой позиции. Дочерние узлы узла I
находятся на позициях 2 * I + 1 и 2 * I + 2. Например, на рис. 6.10,
потомки узла в позиции 1 (узла B), находятся в позициях 3 и 4 (узлы D и
E).

Легко обобщить это представление на полные деревья более высокого
порядка D. Корень дерева также будет находиться в позиции 0. Потомки
узла I занимают позиции от D * I + 1 до D * I +(I – 1). Например, в
троичном дереве, потомки узла в позиции 2, будут занимать позиции 7, 8 и
9. На рис. 6.11 показано полное троичное дерево и его представление в
виде массива.

@Рис. 6.9. Полные деревья

=========127

@Рис. 6.10. Запись полного двоичного дерева в массиве

При использовании этого метода записи дерева в массиве легко и просто
получить доступ к потомкам узла. При этом не требуется дополнительной
памяти для коллекций дочерних узлов или меток в случае представления
нумерацией связей. Чтение и запись дерева в файл сводится просто к
сохранению или чтению массива. Поэтому это несомненно лучшее
представление дерева для программ, которые сохраняют данные в полных
деревьях.

Обход дерева

Последовательное обращение ко всем узлам называется XE “Деревья:обход”
обходом (traversing XE “tree:traversing” ) дерева. Существует
несколько последовательностей обхода узлов двоичного дерева. Три
простейших из них — XE “Деревья:прямой обход” прямой (preorder XE
“traversal:preorder” ), XE “Деревья:симметричный обход” симметричный
( XE “traversal:inorder” inorder), и XE “Деревья:обратный обход”
обратный (postorder XE “traversal:postorder” )обход, описываются
простыми рекурсивными алгоритмами. Для каждого заданного узла алгоритмы
выполняют следующие действия:

Прямой обход:

Обращение к узлу.

Рекурсивный прямой обход левого поддерева.

Рекурсивный прямой обход правого поддерева.

Симметричный обход:

Рекурсивный симметричный обход левого поддерева.

Обращение к узлу.

Рекурсивный симметричный обход левого поддерева.

Обратный обход:

Рекурсивный обратный обход левого поддерева.

Рекурсивный обратный обход правого поддерева.

Обращение к узлу.

@Рис. 6.11. Запись полного троичного дерева в массиве

=======128

Все три порядка обхода являются примерами XE “Деревья:обход в глубину”
обхода в глубину (depth-first traversal XE “traversal:depth-first” ).
Обход начинается с прохода вглубь дерева до тех пор, пока алгоритм не
достигнет листьев. При возврате из рекурсивного вызова подпрограммы,
алгоритм перемещается по дереву в обратном направлении, просматривая
пути, которые он пропустил при движении вниз.

Обход в глубину удобно использовать в алгоритмах, которые должны вначале
обойти листья. Например, метод ветвей и границ, описанный в 8 главе, как
можно быстрее пытается достичь листьев. Он использует результаты,
полученные на уровне листьев для уменьшения времени поиска в оставшейся
части дерева.

Четвертый метод перебора узлов дерева — это XE “Деревья:обход в
ширину” обход в ширину (breadth-first traversal XE
“traversal:breadth-first” ). Этот метод обращается ко всем узлам на
заданном уровне дерева, перед тем, как перейти к более глубоким уровням.
Алгоритмы, которые проводят полный поиск по дереву, часто используют
обход в ширину. Алгоритм поиска кратчайшего маршрута с установкой меток,
описанный в 12 главе, представляет собой обход в ширину, дерева
кратчайшего пути в сети.

На рис. 6.12 показано небольшое дерево и порядок, в котором перебираются
узлы во время прямого, симметричного и обратного обхода, а также обхода
в ширину.

@Рис. 6.12. Обходы дерева

======129

Для деревьев больше, чем 2 порядка, все еще имеет смысл определять
прямой, обратный обход, и обход в ширину. Симметричный обход
определяется неоднозначно, так как обращение к каждому узлу может
происходить после обращения к одному, двум, или трем его потомкам.
Например, в троичном дереве, обращение к узлу может происходить после
обращения к его первому потомку или после обращения ко второму потомку.

Детали реализации обхода зависят от того, как записано дерево. Для
обхода дерева на основе коллекций дочерних узлов, программа должна
использовать несколько другой алгоритм, чем для обхода дерева,
записанного при помощи нумерации связей.

Особенно просто обходить полные деревья, записанные в массиве. Алгоритм
обхода в ширину, который требует дополнительных усилий в других
представлениях деревьев, для представлений на основе массива тривиален,
так как узлы записаны в таком же порядке.

Следующий код демонстрирует алгоритмы обхода полного двоичного дерева:

Dim NodeLabel() As String ‘ Запись меток узлов.

Dim NumNodes As Integer

‘ Инициализация дерева.

:

Private Sub Preorder(node As Integer)

Print NodeLabel (node) ‘ Узел.

‘ Первый потомок.

If node * 2 + 1 0

node = queue.Item(1)

queue.Remove 1

‘ Обращение к узлу.

Print NodeLabel(node)

‘ Поместить в очередь потомков узла.

For Each child In node.Children

queue.Add child

Next child

Loop

End Sub

=====132

Программа Trav2 демонстрирует обход деревьев, использующих коллекции
дочерних узлов. Программа является объединением программ Nary, которая
оперирует деревьями порядка N, и программы Trav1, которая демонстрирует
обходы деревьев.

Выберите узел, и нажмите на кнопку Add Child (Добавить дочерний узел),
чтобы добавить к узлу потомка. Нажмите на кнопки Preorder, Inorder,
Postorder или Breadth First, чтобы увидеть примеры соответствующих
обходов. На рис. 6.14 показана программа Trav2, которая отображает
обратный обход.

Упорядоченные деревья

XE “Деревья:упорядоченные” Двоичные деревья часто являются
естественным способом представления и обработки данных в компьютерных
программах. Поскольку многие компьютерные операции являются двоичными,
они естественно преобразуются в операции с двоичными деревьями.
Например, можно преобразовать двоичное отношение «меньше» в двоичное
дерево. Если использовать внутренние узлы дерева для обозначения того,
что «левый потомок меньше правого» вы можете использовать двоичное
дерево для записи упорядоченного списка. На рис. 6.15 показано двоичное
дерево, содержащее упорядоченный список с числами 1, 2, 4, 6, 7, 9.

@Рис. 6.14. Пример обратного обхода дерева в программе Trav2

======133

@Рис. 6.15. Упорядоченный список: 1, 2, 4, 6, 7, 9.

Добавление элементов

Алгоритм вставки нового элемента в дерево такого типа достаточно прост.
Начнем с корневого узла. По очереди сравним значения всех узлов со
значением нового элемента. Если значение нового элемента меньше или
равно значению узла, перейдем вниз по левой ветви дерева. Если новое
значение больше, чем значение узла, перейдем вниз по правой ветви. Когда
этот процесс дойдет до листа, элемент помещается в эту точку.

Чтобы поместить значение 8 в дерево, показанное на рис. 6.15, мы
начинаем с корня, который имеет значение 4. Поскольку 8 больше, чем 4,
переходим по правой ветви к узлу 9. Поскольку 8 меньше 9, переходим
затем по левой ветви к узлу 7. Поскольку 8 больше 7, снова пытаемся
пойти по правой ветви, но у этого узла нет правого потомка. Поэтому
новый элемент вставляется в этой точке, и получается дерево, показанное
на рис. 6.16.

Следующий код добавляет новое значение ниже узла в упорядоченном дереве.
Программа начинает вставку с корня, вызывая процедуру InsertItem Root,
new_value.

Private Sub InsertItem(node As SortNode, new_value As Integer)

Dim child As SortNode

If node Is Nothing Then

‘ Мы дошли до листа.

‘ Вставить элемент здесь.

Set node = New SortNode

node.Value = new_value

MaxBox = MaxBox + 1

Load NodeLabel(MaxBox)

Set node.Box = NodeLabel(MaxBox)

With NodeLabel(MaxBox)

.Caption = Format$(new_value)

.Visible = True

End With

ElseIf new_value node.Value Then

‘ Продолжить для правого поддерева.

Set child = node.RightChild

DeleteItem child, target_value

Set node.RightChild = child

Else

‘ Искомый узел найден.

Set target = node

If target.LeftChild Is Nothing Then

‘ Заменить искомый узел его правым потомком.

Set node = node.RightChild

ElseIf target.RightChild Is Nothing Then

‘ Заменить искомый узел его левым потомком.

Set node = node.LeftChild

Else

‘ Вызов подпрограмы ReplaceRightmost для замены

‘ искомого узла самым правым узлом

‘ в его левой ветви.

Set child = node.LeftChild

ReplaceRightmost node, child

Set node.LeftChild = child

End If

End If

End Sub

Private Sub ReplaceRightmost(target As SortNode, repl As SortNode)

Dim old_repl As SortNode

Dim child As SortNode

If Not (repl.RightChild Is Nothing) Then

‘ Продолжить движение вправо и вниз.

Set child = repl.RightChild

ReplaceRightmost target, child

Set repl.RightChild = child

Else

‘ Достигли дна.

‘ Запомнить заменяющий узел repl.

Set old_repl = repl

‘ Заменить узел repl его левым потомком.

Set repl = repl.LeftChild

‘ Заменить искомый узел target with repl.

Set old_repl.LeftChild = target.LeftChild

Set old_repl.RightChild = target.RightChild

Set target = old_repl

End If

End Sub

======137-138

Алгоритм использует в двух местах прием передачи параметров в
рекурсивные подпрограммы по ссылке. Во-первых, подпрограмма DeleteItem
использует этот прием для того, чтобы родитель искомого узла указывал на
заменяющий узел. Следующие операторы показывают, как вызывается
подпрограмма DeleteItem:

Set child = node.LeftChild

DeleteItem child, target_value

Set node.LeftChild = child

Когда процедура обнаруживает искомый узел (узел 8 на рис. 6.19), она
получает в качестве параметра узла указатель родителя на искомый узел.
Устанавливая параметр на замещающий узел (узел 7), подпрограмма
DeleteItem задает дочерний узел для родителя так, чтобы он указывал на
новый узел.

Следующие операторы показывают, как процедура ReplaceRightMost
рекурсивно вызывает себя:

Set child = repl.RightChild

ReplaceRightmost target, child

Set repl.RightChild = child

Когда процедура находит самый правый узел в левой от удаляемого узла
ветви (узел 7), в параметре repl находится указатель родителя на самый
правый узел. Когда процедура устанавливает значение repl равным
repl.LeftChild, она автоматически соединяет родителя самого правого узла
с левым дочерним узлом самого правого узла (узлом 5).

Программа TreeSort использует эти процедуры для работы с упорядоченными
двоичными деревьями. Введите целое число, и нажмите на кнопку Add, чтобы
добавить элемент к дереву. Введите целое число, и нажмите на кнопку
Remove, чтобы удалить этот элемент из дерева. После удаления узла,
дерево автоматически переупорядочивается для сохранения порядка
«меньше».

Обход упорядоченных деревьев

Полезное свойство упорядоченных деревьев состоит в том, что их порядок
совпадает с порядком симметричного обхода. Например, при симметричном
обходе дерева, показанного на рис. 6.20, обращение к узлам происходит в
порядке 2-4-5-6-7-8-9.

@Рис. 6.20. Симметричный обход упорядоченного дерева: 2, 4, 5, 6, 7, 8,
9

=========139

Это свойство симметричного обхода упорядоченных деревьев приводит к
простому алгоритму сортировки:

Добавить элемент к упорядоченному дереву.

Вывести элементы, используя симметричный обход.

Этот алгоритм обычно работает достаточно хорошо. Тем не менее, если
добавлять элементы к дереву в определенном порядке, то дерево может
стать высоким и тонким. На рис. 6.21 показано упорядоченное дерево,
которое получается при добавлении к нему элементов в порядке 1, 6, 5, 2,
3, 4. Другие последовательности также могут приводить к появлению
высоких и тонких деревьев.

Чем выше становится упорядоченное дерево, тем больше времени требуется
для добавления новых элементов в нижнюю часть дерева. В наихудшем
случае, после добавления N элементов, дерево будет иметь высоту порядка
O(N). Полное время вставки всех элементов в дерево будет при этом
порядка O(N2). Поскольку для обхода дерева требуется время порядка O(N),
полное время сортировки чисел с использованием дерева будет равно
O(N2)+O(N)=O(N2).

Если дерево остается достаточно коротким, оно имеет высоту порядка
O(log(N)). В этом случае для вставки элемента в дерево потребуется всего
порядка O(log(N)) шагов. Вставка всех N элементов в дерево потребует
порядка O(N * log(N)) шагов. Тогда сортировка элементов при помощи
дерева потребует времени порядка O(N * log(N)) + O(N) = O(N * log(N)).

Время выполнения порядка O(N * log(N)) намного меньше, чем O(N2).
Например, построение высокого и тонкого дерева, содержащего 1000
элементов, потребует выполнения около миллиона шагов. Построение
короткого дерева с высотой порядка O(log(N)) займет всего около 10.000
шагов.

Если элементы первоначально расположены в случайном порядке, форма
дерева будет представлять что-то среднее между этими двумя крайними
случаями. Хотя его высота может оказаться несколько больше, чем log(N),
оно, скорее всего, не будет слишком тонким и высоким, поэтому алгоритм
сортировки будет выполняться достаточно быстро.

@Рис. 6.21. Дерево, полученное добавлением элементов в порядке 1, 6, 5,
2, 3, 4

==========140

В 7 главе описываются способы балансировки деревьев, для того, чтобы они
не становились слишком высокими и тонкими, независимо от того, в каком
порядке в них добавляются новые элементы. Тем не менее, эти методы
достаточно сложны, и их не имеет смысла применять в алгоритме сортировки
при помощи дерева. Многие из алгоритмов сортировки, описанных в 9 главе,
более просты в реализации и обеспечивают при этом лучшую
производительность.

Деревья со ссылками

Во 2 главе показано, как добавление ссылок к связным спискам позволяет
упростить вывод элементов в разном порядке. Вы можете использовать тот
же подход для упрощения обращения к узлам дерева в различном порядке.
Например, помещая ссылки в листья двоичного дерева, вы можете облегчить
выполнение симметричного и обратного обходов. Для упорядоченного дерева,
это обход в прямом и обратном порядке сортировки.

Для создания ссылок, указатели на предыдущий и следующий узлы в порядке
симметричного обхода помещаются в неиспользуемых указателях на дочерние
узлы. Если не используется указатель на левого потомка, то ссылка
записывается на его место, указывая на предыдущий узел при симметричном
обходе. Если не используется указатель на правого потомка, то ссылка
записывается на его место, указывая на следующий узел при симметричном
обходе. Поскольку ссылки симметричны, и ссылки левых потомков указывают
на предыдущие, а правых — на следующие узлы, этот тип деревьев
называется XE “Деревья:с симметричными ссылками” деревом с
симметричными ссылками (symmetrically threaded tree XE
“tree:symmetrically threaded” ). На рис. 6.22 показано дерево с
симметричными ссылками, которые обозначены пунктирными линиями.

Поскольку ссылки занимают место указателей на дочерние узлы дерева,
нужно как-то различать ссылки и обычные указатели на потомков. Проще
всего добавить к узлам новые переменные HasLeftChild и HasRightChild
типа Boolean, которые будут равны True, если узел имеет левого или
правого потомка соответственно.

Чтобы использовать ссылки для поиска предыдущего узла, нужно проверить
указатель на левого потомка узла. Если этот указатель является ссылкой,
то ссылка указывает на предыдущий узел. Если значение указателя равно
Nothing, значит это первый узел дерева, и поэтому он не имеет
предшественников. В противном случае, перейдем по указателю к левому
дочернему узлу. Затем проследуем по указателям на правый дочерний узел
потомков, до тех пор, пока не достигнем узла, в котором на месте
указателя на правого потомка находится ссылка. Этот узел (а не тот, на
который указывает ссылка) является предшественником исходного узла. Этот
узел является самым правым в левой от исходного узла ветви дерева.
Следующий код демонстрирует поиск предшественника:

@Рис. 6.22. Дерево с симметричными ссылками

==========141

Private Function Predecessor(node As ThreadedNode) As ThreadedNode Dim
child As ThreadedNode

If node.LeftChild Is Nothing Then

‘ Это первый узел в порядке симметричного обхода.

Set Predecessor = Nothing

Else If node.HasLeftChild Then

‘ Это указатель на узел.

‘ Найти самый правый узел в левой ветви.

Set child = node.LeftChild

Do While child.HasRightChild

Set child = child.RightChild

Loop

Set Predecessor = child

Else

‘ Ссылка указывает на предшественника.

Set Predecessor = node.LeftChild

End If

End Function

Аналогично выполняется поиск следующего узла. Если указатель на правый
дочерний узел является ссылкой, то она указывает на следующий узел. Если
указатель имеет значение Nothing, то это последний узел дерева, поэтому
он не имеет последователя. В противном случае, переходим по указателю к
правому потомку узла. Затем перемещаемся по указателям дочерних узлов до
тех, пор, пока очередной указатель на левый дочерний узел не окажется
ссылкой. Тогда найденный узел будет следующим за исходным. Это будет
самый левый узел в правой от исходного узла ветви дерева.

Удобно также ввести функции для нахождения первого и последнего узлов
дерева. Чтобы найти первый узел, просто проследуем по указателям на
левого потомка вниз от корня до тех пор, пока не достигнем узла,
значение указателя на левого потомка для которого равно Nothing. Чтобы
найти последний узел, проследуем по указателям на правого потомка вниз
от корня до тех пор, пока не достигнем узла, значение указателя на
правого потомка для которого равно Nothing.

Private Function FirstNode() As ThreadedNode

Dim node As ThreadedNode

Set node = Root

Do While Not (node.LeftChild Is Nothing)

Set node = node.LeftChild

Loop

Set PirstNode = node

End Function

Private Function LastNode() As ThreadedNode

Dim node As ThreadedNode

Set node = Root

Do While Not (node.RightChild Is Nothing)

Set node = node.RightChild

Loop

Set FirstNode = node

End Function

=========142

При помощи этих функций вы можете легко написать процедуры, которые
выводят узлы дерева в прямом или обратном порядке:

Private Sub Inorder()

Dim node As ThreadedNode

‘ Найти первый узел.

Set node = FirstNode()

‘ Вывод списка.

Do While Not (node Is Nothing)

Print node.Value

Set node = Successor(node)

Loop

End Sub

Private Sub PrintReverseInorder()

Dim node As ThreadedNode

‘ Найти последний узел

Set node = LastNode

‘ Вывод списка.

Do While Not (node Is Nothing)

Print node. Value

Set node = Predecessor(node)

Loop

End Sub

Процедура вывода узлов в порядке симметричного обхода, приведенная ранее
в этой главе, использует рекурсию. Для устранения рекурсии вы можете
использовать эти новые процедуры, которые не используют ни рекурсию, ни
системный стек.

Каждый указатель на дочерние узлы в дереве содержит или указатель на
потомка, или ссылку на предшественника или последователя. Так как каждый
узел имеет два указателя на дочерние узлы, то, если дерево имеет N
узлов, то оно будет содержать 2 * N ссылок и указателей. Эти алгоритмы
обхода обращаются ко всем ссылкам и указателям дерева один раз, поэтому
они потребуют выполнения O(2 * N) = O(N) шагов.

Можно немного ускорить выполнение этих подпрограмм, если отслеживать
указатели на первый и последний узлы дерева. Тогда вам не понадобится
выполнять поиск первого и последнего узлов перед тем, как вывести список
узлов по порядку. Так как при этом алгоритм обращается ко всем N узлам
дерева, время выполнения этого алгоритма также будет порядка O(N), но на
практике он будет выполняться немного быстрее.

========143

Работа с деревьями со ссылками

Для работы с деревом со ссылками, нужно, чтобы можно было добавлять и
удалять узлы из дерева, сохраняя при этом его структуру.

Предположим, что требуется добавить нового левого потомка узла A. Так
как это место не занято, то на месте указателя на левого потомка узла A
находится ссылка, которая указывает на предшественника узла A. Поскольку
новый узел займет место левого потомка узла A, он станет
предшественником узла A. Узел A будет последователем нового узла. Узел,
который был предшественником узла A до этого, теперь становится
предшественником нового узла. На рис. 6.23 показано дерево с рис. 6.22
после добавления нового узла X в качестве левого потомка узла H.

Если отслеживать указатель на первый и последний узлы дерева, то
требуется также проверить, не является ли теперь новый узел первым узлом
дерева. Если ссылка на предшественника для нового узла имеет значение
Nothing, то это новый первый узел дерева.

@Рис. 6.23. Добавление узла X к дереву со ссылками

=========144

Учитывая все вышеизложенное, легко написать процедуру, которая добавляет
нового левого потомка к узлу. Вставка правого потомка выполняется
аналогично.

Private Sub AddLeftChild(parent As ThreadedNode, child As ThreadedNode)

‘ Предшественник родителя становится предшественником нового узла.

Set child. LeftChild = parent.LeftChild

child.HasLeftChild = False

‘ Вставить узел.

Set parent.LeftChild = child

parent.HasLeftChild = True

‘ Родитель является последователем нового узла.

Set child.RightChild = parent

child.HasRightChild = False

‘ Определить, является ли новый узел первым узлом дерева.

If child.LeftChild Is Nothing Then Set FirstNode = child

End Sub

Перед тем, как удалить узел из дерева, необходимо вначале удалить всех
его потомков. После этого легко удалить уже сам узел.

Предположим, что удаляемый узел является левым потомком своего родителя.
Его указатель на левого потомка является ссылкой, указывающей на
предыдущий узел в дереве. После удаления узла, его предшественник
становится предшественником родителя удаленного узла. Чтобы удалить
узел, просто заменяем указатель на левого потомка его родителя на
указатель на левого потомка удаляемого узла.

Указатель на правого потомка удаляемого узла является ссылкой, которая
указывает на следующий узел в дереве. Так как удаляемый узел является
левым потомком своего родителя, и поскольку у него нет потомков, эта
ссылка указывает на родителя, поэтому ее можно просто опустить. На рис.
6.24 показано дерево с рис. 6.23 после удаления узла F. Аналогично
удаляется правый потомок.

Private Sub RemoveLeftChild(parent As ThreadedNode)

Dim target As ThreadedNode

Set target = parent.LeftChild

Set parent.LeftChild = target.LeftChild

End Sub

@Рис. 6.24. Удаление узла F из дерева со ссылками

=========145

XE “Деревья:квадродеревья” Квадродеревья (quadtrees XE “quadtree” )
описывают пространственные отношения между элементами на площади.
Например, это может быть карта, а элементы могут представлять собой
положение домов или предприятий на ней.

Каждый узел квадродерева представляет собой участок на площади,
представленной квадродеревом. Каждый узел, кроме листьев, имеет четыре
потомка, которые представляют четыре квадранта. Листья могут хранить
свои элементы в коллекциях связных списков. Следующий код показывает
секцию Declarations для класса QtreeNode.

‘ Потомки.

Public NWchild As QtreeNode

Public NEchild As QtreeNode

Public SWchild As QtreeNode

Public SEchild As QtreeNode

‘ Элементы узла, если это не лист.

Public Items As New Collection

Элементы, записанные в квадродереве, могут содержать пространственные
данные любого типа. Они могут содержать информацию о положении, которую
дерево может использовать для поиска элементов. Переменные в простом
классе QtreeItem, который представляет элементы, состоящие из точек на
местности, определяются так:

Public X As Single

Public Y As Single

Чтобы построить квадродерево, вначале поместим все элементы в корневой
узел. Затем определим, содержит ли этот узел достаточно много элементов,
чтобы его стоило разделить на несколько узлов. Если это так, создадим
четыре потомка узла и распределим элементы между четырьмя потомками в
соответствии с их положением в четырех квадрантах исходной области.
Затем рекурсивно проверяем, не нужно ли разбить на несколько узлов
дочерние узлы. Продолжим разбиение до тех пор, пока все листья не будут
содержать не больше некоторого заданного числа элементов.

На рис. 6.25 показано несколько элементов данных, расположенных в виде
квадродерева. Каждая область разбивается до тех пор, пока она не будет
содержать не более двух элементов.

Квадродеревья удобно применять для поиска близлежащих объектов.
Предположим, имеется программа, которая рисует карту с большим числом
населенных пунктов. После того, как пользователь щелкнет мышью по карте,
программа должна найти ближайший к выбранной точке населенный пункт.
Программа может перебрать весь список населенных пунктов, проверяя для
каждого его расстояние от заданной точки. Если в списке N элементов, то
сложность этого алгоритма порядка O(N).

====146

@Рис. 6.25. Квадродерево

Эту операцию можно выполнить намного быстрее при помощи квадродерева.
Начнем с корневого узла. При каждой проверке квадродерева определяем,
какой из квадрантов содержит точку, которую выбрал пользователь. Затем
спустимся вниз по дереву к соответствующему дочернему узлу. Если
пользователь выбрал верхний правый угол области узла, нужно спуститься к
северо-восточному потомку. Продолжим движение вниз по дереву, пока не
дойдем до листа, который содержит выбранную пользователем точку.

Функция LocateLeaf класса QtreeNode использует этот подход для поиска
листа дерева, который содержит выбранную точку. Программа может вызвать
эту функцию в строке Set the_leaf = Root.LocateLeaf(X, Y, Gxmin, Gxmax,
Gymax), где Gxmin, Gxmax, Gymin, Gymax — это границы представленной
деревом области.

Public Function LocateLeaf (X As Single, Y As Single, _

xmin As Single, xmax As Single, ymin As Single, ymax As Single) _

As QtreeNode

Dim xmid As Single

Dim ymid As Single

Dim node As QtreeNode

If NWchild Is Nothing Then

‘ Узел не имеет потомков. Искомый узел найден.

Set LocateLeaf = Me

Exit Function

End If

‘ Найти соответстующего потомка.

xmid = (xmax + xmin) / 2

ymid = (ymax + ymin) / 2

If X new_dist Then

best_dist = new_dist

Set best_item = new_item

End If

Next new_item

End Sub

======147-148

Элемент, который находит процедура NearPointLeaf, обычно и есть элемент,
который пользователь пытался выбрать. Тем не менее, если элемент
находится вблизи границы между двумя узлами, может оказаться, что
ближайший к выбранной точке элемент находится в другом узле.

Предположим, что Dmin — это расстояние между выбранной пользователем
точкой и ближайшим из найденных до сих пор населенных пунктов. Если Dmin
меньше, чем расстояние от выбранной точки до края листа, то поиск
закончен. Населенный пункт находится при этом слишком далеко от края
листа, чтобы в каком-либо другом листе мог существовать пункт,
расположенный ближе к заданной точке.

В противном случае нужно снова начать с корня и двигаться по дереву,
проверяя все узлы квадродеревьев, которые находятся на расстоянии
меньше, чем Dmin от заданной точки. Если найдутся элементы, которые
расположены ближе, изменим значение Dmin и продолжим поиск. После
завершения проверки ближайших к точке листьев, нужный элемент будет
найден. Подпрограмма CheckNearByLeaves использует этот подход для
завершения поиска.

Public Sub CheckNearbyLeaves(exclude As QtreeNode, _

X As Single, Y As Single, best_item As QtreeItem, _

best_dist As Single, comparisons As Long, _

xmin As Single, xmax As Single, ymin As Single, ymax As Single)

Dim xmid As Single

Dim ymid As Single

Dim new_dist As Single

Dim new_item As QtreeItem

‘ Если это лист, который мы должны исключить,

‘ ничего не делать.

If Me Is exclude Then Exit Sub

‘ Если это лист, проверить его.

If SWchild Is Nothing Then

NearPointInLeaf X, Y, new_item, new_dist, comparisons

If best_dist > new_dist Then

best_dist = new_dist

Set best_item = new_item

End If

Exit Sub

End If

‘ Найти потомков, которые удалены не больше, чем на best_dist

‘ от выбранной точки.

xmid = (xmax + xmin) / 2

ymid = (ymax + ymin) / 2

If X – Sqr(best_dist) ymid Then

‘ Проверить юго-западного потомка.

SWchiId.CheckNearbyLeaves _

exclude, X, Y, best_item, _

best_dist, comparisons, _

xmin, xmid, ymid, ymax

End If

End If

If X + Sqr(best_dist) > xmid Then

‘ Продолжить с потомками на востоке.

If Y – Sqr(best_dist) ymid Then

‘ Проверить юговосточного потомка.

SEchild.CheckNearbyLeaves _

exclude, X, Y, best_item, _

best_dist, comparisons, _

xmid, xmax, ymid, ymax

End If

End If

End Sub

=====149-150

Подпрограмма FindPoint использует подпрограммы LocateLeaf,
NearPointInLeaf, и CheckNearbyLeaves, из класса QtreeNode для быстрого
поиска элемента в квадродереве.

Function FindPoint(X As Single, Y As Single, comparisons As Long) _ As
QtreeItem

Dim leaf As QtreeNode

Dim best_item As QtreeItem

Dim best_dist As Single

‘ Определить, в каком листе находится точка.

Set leaf = Root.LocateLeaf( _

X, Y, Gxmin, Gxmax, Gymin, Gymax)

‘ Найти ближайшую точку в листе.

leaf.NearPointInLeaf _

X, Y, best_item, best_dist, comparisons

‘ Проверить соседние листья.

Root.CheckNearbyLeaves _

leaf, X, Y, best_item, best_dist, _

comparisons, Gxmin, Gxmax, Gymin, Gymax

Set FindPoint = best_item

End Function

Программа Qtree использует квадродерево. При старте программа
запрашивает число элементов данных, которое она должна создать, затем
она создает элементы и рисует их в виде точек. Задавайте вначале
небольшое (около 1000) число элементов, пока вы не определите, насколько
быстро ваш компьютер может создавать элементы.

Интересно наблюдать квадродеревья, элементы которых распределены
неравномерно, поэтому программа выбирает точки при помощи функции XE
“Странный аттрактор” странного аттрактора (strange attractor) из XE
“Теория:хаоса” теории хаоса (chaos theory). Хотя кажется, что элементы
следуют в случайном порядке, они образуют интересные кластеры.

При выборе какой-либо точки на форме при помощи мыши, программа Qtree
находит ближайший к ней элемент. Она подсвечивает этот элемент и выводит
число проверенных при его поиске элементов.

В меню Options (Опции) программы можно задать, должна ли программа
использовать квадродеревья или нет. Если поставить галочку в пункте Use
Quadtree (Использовать квадродерево), то программа выводит на экран
квадродерево и использует его для поиска элементов. Если этот пункт не
выбран, программа не отображает квадродерево и находит нужные элементы
путем перебора.

Программа проверяет намного меньшее число элементов и работает намного
быстрее при использовании квадродерева. Если этот эффект не слишком
заметен на вашем компьютере, запустите программу, задав при старте
10.000 или 20.000 входных элементов. Вы заметите разницу даже на
компьютере с процессором Pentium с тактовой частотой 90 МГц.

На рис. 6.26 показано окно программа Qtree на котором изображено 10.000
элементов. Маленький прямоугольник в верхнем правом углу обозначает
выбранный элемент. Метка в верхнем левом углу показывает, что программа
проверила всего 40 из 10.000 элементов перед тем, как найти нужный.

Изменение MAX_PER_NODE

Интересно поэкспериментировать с программой Qtree, изменяя значение
MAX_PER_NODE, определенное в разделе Declarations класса QtreeNode. Это
максимальное число элементов, которые могут поместиться в узле
квадродерева без его разбиения. Программа обычно использует значение
MAX_PER_NODE = 100.

======151

@Рис. 6.26. Программа Qtree

Если вы уменьшите это число, например, до 10, то в каждом узле будет
находиться меньше элементов, поэтому программа будет проверять меньше
элементов, чтобы найти ближайший к выбранной вами точке. Поиск будет
выполняться быстрее. С другой стороны, программе придется создать
намного больше узлов квадродерева, поэтому она займет больше памяти.

Наоборот, если вы увеличите MAX_PER_NODE до 1000, программа создаст
намного меньше узлов. При этом потребуется больше времени на поиск
элементов, но дерево будет меньше, и займет меньше памяти.

Это пример компромисса между временем и пространством. Использование
большего числа узлов квадродерева ускоряет поиск, но занимает больше
памяти. В этом примере, при значении переменной MAX_PER_NODE примерно
равном 100, достигается равновесие между скоростью и использованием
памяти. Для других приложений вам может потребоваться
поэкспериментировать с различными значениями переменной MAX_PER_NODE,
чтобы найти оптимальное.

Использование псевдоуказателей в квадродеревьях

Программа Qtree использует большое число классов и коллекций. Каждый
внутренний узел квадродерева содержит четыре ссылки на дочерние узлы.
Листья включают большие коллекции, в которых находятся элементы узла.
Все эти объекты и коллекции замедляют работу программы, если она
содержит большое числе элементов. Создание объектов отнимает много
времени и памяти. Если программа создает множество объектов, она может
начать обращаться к файлу подкачки, что сильно замедлит ее работу.

К сожалению, выигрыш от использования квадродеревьев будет максимальным,
если программа содержит много элементов. Чтобы улучшить
производительность больших приложений, вы можете использовать методы
работы с псевдоуказателями, описанные во 2 главе.

=====152

Программа Qtree2 создает квадродерево при помощи псевдоуказателей. Узлы
и элементы находятся в массивах определенных пользователем структур
данных. В качестве указателей, эта программа использует индексы массивов
вместо ссылок на объекты. В одном из тестов на компьютере с процессором
Pentium с тактовой частотой 90 МГц, программе Qtree потребовалось 25
секунд для построения квадродерева, содержащего 30.000 элементов.
Программе Qtree2 понадобилось всего 3 секунды для создания того же
дерева.

Восьмеричные деревья

XE “Деревья:восьмеричные” Восьмеричные деревья (octtrees XE
“octtree” ) аналогичны квадродеревьям, но они разбивают область не
двумерного, а трехмерного пространства. Восьмеричные деревья содержат не
четыре потомка, как квадродеревья, а восемь, разбивая объем области на
восемь частей — верхнюю северо-западную, нижнюю северо-западную, верхнюю
северо-восточную, нижнюю северо-восточную и так далее.

Восьмеричные деревья полезны при работе с объектами, расположенными в
пространстве. Например, робот может использовать восьмеричное дерево для
отслеживания близлежащих объектов. Программа рейтрейсинга может
использовать восьмеричное дерево для того, чтобы быстро оценить,
проходит ли луч поблизости от объекта перед тем, как начать медленный
процесс вычислений точного пересечения объекта и луча.

Восьмеричные деревья можно строить, используя примерно те же методы, что
и для квадродеревьев.

Резюме

Существует множество способов представления деревьев. Наиболее
эффективным и компактным из них является запись полных деревьев в
массивах. Представление деревьев в виде коллекций дочерних узлов
упрощает работу с ними, но при этом программа выполняется медленнее и
использует больше памяти. Представление нумерацией связей позволяет
быстро выполнять обход дерева и использует меньше памяти, чем коллекции
потомков, но его сложно модифицировать. Тем не менее, его важно
представлять, потому что оно часто используется в сетевых алгоритмах.

=====153

Глава 7. Сбалансированные деревья

При работе с упорядоченным деревом, вставке и удалении узлов, дерево
может стать несбалансированным. Когда это происходит, то алгоритмы,
работы с деревом становятся менее эффективными. Если дерево становится
сильно несбалансированным, оно практически представляет всего лишь
сложную форму связного списка, и программа, использующая такое дерево,
может иметь очень низкую производительность.

В этой главе обсуждаются методы, которые можно использовать для
балансировки деревьев, даже если узлы удаляются и добавляются с течением
времени. Балансировка дерева позволяет ему оставаться при этом
достаточно эффективным.

Глава начинается с описания того, что понимается под несбалансированным
деревом и демонстрации ухудшения производительности для
несбалансированных деревьев. Затем в ней обсуждаются АВЛ-деревья, высота
левого и правого поддеревьев в каждом узле которых отличается не больше,
чем на единицу. Сохраняя это свойство АВЛ-деревьев, можно поддерживать
такое дерево сбалансированным.

Затем в главе описываются Б-деревья и Б+деревья, в которых все листья
имеют одинаковую глубину. Если число ветвей, выходящих из каждого узла
находится в определенных пределах, такие деревья остаются
сбалансированными. Б-деревья и Б+деревья обычно используются при
программировании баз данных. Последняя программа, описанная в этой
главе, использует Б+дерево для реализации простой, но достаточно мощной
базы данных.

Сбалансированность дерева

Как упоминалось в 6 главе, форма упорядоченного дерева зависит от
порядка вставки в него новых узлов. На рис. 7.1 показано два различных
дерева, созданных при добавлении одних и тех же элементов в разном
порядке.

Высокие и тонкие деревья, такие как левое дерево на рис. 7.1, могут
иметь глубину порядка O(N). Вставка или поиск элемента в таком
несбалансированном дереве может занимать порядка O(N) шагов. Даже если
новые элементы вставляются в дерево в случайном порядке, в среднем они
дадут дерево с глубиной N / 2, что также порядка O(N).

Предположим, что строится упорядоченное двоичное дерево, содержащее 1000
узлов. Если дерево сбалансировано, то высота дерева будет порядка
log2(1000), или примерно равна 10. Вставка нового элемента в дерево
займет всего 10 шагов. Если дерево высокое и тонкое, оно может иметь
высоту 1000. В этом случае, вставка элемента в конец дерева займет 1000
шагов.

======155

@Рис. 7.1. Деревья, построенные в различном порядке

Предположим теперь, что мы хотим добавить к дереву еще 1000 узлов. Если
дерево остается сбалансированным, то все 1000 узлов поместятся на
следующем уровне дерева. При этом для вставки новых элементов
потребуется около 10 * 1000 = 10.000 шагов. Если дерево было не
сбалансировано и остается таким в процессе роста, то при вставке каждого
нового элемента оно будет становиться все выше. Вставка элементов при
этом потребует порядка 1000 + 1001 + … +2000 = 1,5 миллиона шагов.

Хотя нельзя быть уверенным, что элементы будут добавляться и удаляться
из дерева в нужном порядке, можно использовать методы, которые будут
поддерживать сбалансированность дерева, независимо от порядка вставки
или удаления элементов.

АВЛ-деревья

XE “Деревья:АВЛ-деревья” АВЛ-деревья (AVL trees XE “tree:AVL tree”
) были названы в честь русских математиков Адельсона-Вельского и
Лэндиса, которые их изобрели. Для каждого узла АВЛ-дерева, высота левого
и правого поддеревьев отличается не больше, чем на единицу. На рис. 7.2
показано несколько АВЛ-деревьев.

Хотя АВЛ-дерево может быть несколько выше, чем полное дерево с тем же
числом узлов, оно также имеет высоту порядка O(log(N)). Это означает,
что поиск узла в АВЛ-дереве занимает время порядка O(log(N)), что
достаточно быстро. Не столь очевидно, что можно вставить или удалить
элемент из АВЛ-дерева за время порядка O(log(N)), сохраняя при этом
порядок дерева.

======156

@Рис. 7.2. АВЛ-деревья

Процедура, которая вставляет в дерево новый узел, рекурсивно спускается
вниз по дереву, чтобы найти местоположение узла. После вставки элемента,
происходят возвраты из рекурсивных вызовов процедуры и обратный проход
вверх по дереву. При каждом возврате из процедуры, она проверяет,
сохраняется ли все еще свойство АВЛ-деревьев на верхнем уровне. Этот тип
обратной рекурсии, когда процедура выполняет важные действия при выходе
из цепочки рекурсивных вызовов, называется XE “Рекурсия:восходящая”
восходящей (bottom-up) рекурсией.

При обратном проходе вверх по дереву, процедура также проверяет, не
изменилась ли высота поддерева, с которым она работает. Если процедура
доходит до точки, в которой высота поддерева не изменилась, то высота
следующих поддеревьев также не могла измениться. В этом случае, снова
требуется балансировка дерева, и процедура может закончить проверку.

Например, дерево слева на рис. 7.3 является сбалансированным
АВЛ-деревом. Если добавить к дереву новый узел E, то получится среднее
дерево на рисунке. Затем выполняется проход вверх по дереву от нового
узла E. В самом узле E дерево сбалансировано, так как оба его поддерева
пустые и имеют одинаковую высоту 0.

В узле D дерево также сбалансировано, так как его левое поддерево
пустое, и имеет поэтому высоту 0. Правое поддерево содержит единственный
узел E, и поэтому его высота равна 1. Высоты поддеревьев отличаются не
больше, чем на единицу, поэтому дерево сбалансировано в узле D.

В узле C дерево уже не сбалансировано. Левое поддерево узла C имеет
высоту 0, а правое — высоту 2. Эти поддеревья можно сбалансировать, как
показано на рис. 7.3 справа, при этом узел C заменяется узлом D. Теперь
поддерево с корнем в узле D содержит узлы C, D и E, и имеет высоту 2.
Заметьте, что высота поддерева с корнем в узле C, которое ранее
находилось в этом месте, также была равна 2 до вставки нового узла. Так
как высота поддерева не изменилась, то дерево также окажется
сбалансированным во всех узлах выше D.

Вращения АВЛ-деревьев

При вставке узла в АВЛ-дерево, в зависимости от того, в какую часть
дерева добавляется узел, существует четыре варианта балансировки. Эти
способы называются правым и левым вращением, и вращением влево-вправо и
вправо-влево, и обозначаются R, L, LR и RL.

Предположим, что в АВЛ-дерево вставляется новый узел, и теперь дерево
становится несбалансированным в узле X, как показано на рис. 7.4. На
рисунке изображены только узел X и два его дочерних узла, а остальные
части дерева обозначены треугольниками, так как их не требуется
рассматривать подробно.

Новый узел может быть вставлен в любое из четырех поддеревьев узла X,
изображенных в виде треугольников. Если вы вставляете узел в одно из
этих поддеревьев, то для балансировки дерева потребуется выполнить
соответствующее вращение. Помните, что иногда балансировка не нужна,
если вставка нового узла не нарушает упорядоченность дерева.

Правое вращение

XE “Деревья:вращения” Вначале предположим, что новый узел вставляется
в поддерево R на рис. 7.4. В этом случае не нужно изменять два правых
поддерева узла X, поэтому их можно объединить, изобразив одним
треугольником, как показано на рис. 7.5. Новый узел вставляется в дерево
T1, при этом поддерево TA с корнем в узле A становится не менее, чем на
два уровня выше, чем поддерево T3.

На самом деле, поскольку до вставки нового узла дерево было АВЛ-деревом,
то TA должно было быть выше поддерева T3 не больше, чем на один уровень.
После вставки одного узла TA должно быть выше поддерева T3 ровно на два
уровня.

Также известно, что поддерево T1 выше поддерева T2 не больше, чем на
один уровень. Иначе узел X не был бы самым нижним узлом с
несбалансированными поддеревьями. Если бы T1 было на два уровня выше,
чем T2, то дерево было бы несбалансированным в узле A.

@Рис. 7.4. Анализ несбалансированного АВЛ-дерева

========158

@Рис. 7.5. Вставка нового узла в поддерево R

В этом случае, можно переупорядочить узлы при помощи правого вращения
(right rotation XE “tree:right rotation” ), как показано на рис. 7.6.
Это вращение называется правым, так как узлы A и X как бы вращаются
вправо.

Заметим, что это вращение сохраняет порядок «меньше» расположения узлов
дерева. При симметричном обходе любого из таких деревьев обращение ко
всем поддеревьям и узлам дерева происходит в порядке T1, A, T2, X, T3.
Поскольку симметричный обход обоих деревьев происходит одинаково, то и
порядок расположения элементов в них будет одинаковым.

Важно также заметить, что высота поддерева, с которым мы работаем,
остается неизменной. Перед тем, как был вставлен новый узел, высота
поддерева была равна высоте поддерева T2 плюс 2. После вставки узла и
выполнения правого вращения, высота поддерева также остается равной
высоте поддерева T2 плюс 2. Все части дерева, лежащие ниже узла X при
этом также остаются сбалансированными, поэтому не требуется продолжать
балансировку дерева дальше.

Левое вращение

Левое вращение (left rotation XE “tree:left rotation” ) выполняется
аналогично правому. Оно используется, если новый узел вставляется в
поддерево L, показанное на рис. 7.4. На рис. 7.7 показано АВЛ-дерево до
и после левого вращения.

@Рис. 7.6. Правое вращение

========159

@Рис. 7.7. До и после левого вращения

Вращение влево-вправо

Если узел вставляется в поддерево LR, показанное на рис. 7.4, нужно
рассмотреть еще один нижележащий уровень. На рис. 7.8. показано дерево,
в котором новый узел вставляется в левую часть T2 поддерева LR. Так же
легко можно вставить узел в правое поддерево T3. В обоих случаях,
поддеревья TA и TC останутся АВЛ-поддеревьями, но поддерево TX уже не
будет таковым.

Так как дерево до вставки узла было АВЛ-деревом, то TA было выше T4 не
больше, чем на один уровень. Поскольку добавлен только один узел, то TA
вырастет только на один уровень. Это значит, что TA теперь будет точно
на два уровня выше T4.

Также известно, что поддерево T2 не более, чем на один уровень выше, чем
T3. Иначе TC не было бы сбалансированным, и узел X не был бы самым
нижним в дереве узлом с несбалансированными поддеревьями.

Поддерево T1 должно иметь ту же глубину, что и T3. Если бы оно было
короче, то поддерево TA было бы не сбалансировано, что снова
противоречит предположению о том, что узел X — самый нижний узел в
дереве, имеющий несбалансированные поддеревья. Если бы поддерево T1
имело большую глубину, чем T3, то глубина поддерева T1 была бы на 2
уровня больше, чем глубина поддерева T4. В этом случае дерево было бы
несбалансированным до вставки в него нового узла.

Все это означает, что нижние части деревьев выглядят в точности так, как
показано на рис. 7.8. Поддерево T2 имеет наибольшую глубину, глубина T1
и T3 на один уровень меньше, а T4 расположено еще на один уровень выше,
чем T3 и T3.

@Рис. 7.8. Вставка нового узла в поддерево LR

==========160

@Рис. 7.9. Вращение влево-вправо

Используя эти факты, можно сбалансировать дерево, как показано на рис.
7.9. Это называется вращением влево-вправо (left-right rotation XE
“tree:left-right rotation” ), так как при этом вначале узлы A и C как
бы вращаются влево, а затем узлы C и X вращаются вправо.

Как и другие вращения, вращение этого типа не изменяет порядок элементов
в дереве. При симметричном обходе дерева до и после вращения обращение к
узлам и поддеревьям происходит в порядке: T1, A, T2, C, T3, X, T4.

Высота дерево после балансировки также не меняется. До вставки нового
узла, правое поддерево имело высоту поддерева T1 плюс 2. После
балансировки дерева, высота этого поддерева снова будет равна высоте T1
плюс 2. Это значит, что остальная часть дерева также остается
сбалансированной, и нет необходимости продолжать балансировку дальше.

Вращение вправо-влево

Вращение вправо-влево (right-left rotation) аналогично вращению
влево-вправо () XE “tree:right-left rotation” . Оно используется для
балансировки дерева после вставки узла в поддерево RL на рис. 7.4. На
рис. 7.10 показано АВЛ-дерево до и после вращения вправо-влево.

Резюме

На рис. 7.11 показаны все возможные вращения АВЛ-дерева. Все они
сохраняют порядок симметричного обхода дерева, и высота дерева при этом
всегда остается неизменной. После вставки нового элемента и выполнения
соответствующего вращения, дерево снова оказывается сбалансированным.

Вставка узлов на языке Visual Basic

Перед тем, как перейти к обсуждению удаления узлов из АВЛ-деревьев, в
этом разделе обсуждаются некоторые детали реализации вставки узла в
АВЛ-дерево на языке Visual Basic.

Кроме обычных полей LeftChild и RightChild, класс AVLNode содержит также
поле Balance, которое указывает, которое из поддеревьев узла выше. Его
значение равно -1, если левое поддерево выше, 1 — если выше правое, и
0 — если оба поддерева имеют одинаковую высоту.

======161

@Рис. 7.10. До и после вращения вправо-влево

Public LeftChild As AVLNode

Public RightChild As AVLNode

Public Balance As Integer

Чтобы сделать код более простым для чтения, можно использовать
постоянные LEFT_HEAVY, RIGHT_HEAVY, и BALANCED для представления этих
значений.

Global Const LEFT_HEAVY = -1

Global Const BALANCED = 0

Global Const RIGHT_HEAVY = 1

Процедура InsertItem, представленная ниже, рекурсивно спускается вниз по
дереву в поиске нового местоположения элемента. Когда она доходит до
нижнего уровня дерева, она создает новый узел и вставляет его в дерево.

Затем процедура InsertItem использует восходящую рекурсию для
балансировки дерева. При выходе из рекурсивных вызовов процедуры, она
движется назад по дереву. При каждом возврате из процедуры, она
устанавливает параметр has_grown, чтобы определить, увеличилась ли
высота поддерева, которое она покидает. В экземпляре процедуры
InsertItem, который вызвал этот рекурсивный вызов, процедура использует
этот параметр для определения того, является ли проверяемое дерево
несбалансированным. Если это так, то процедура применяет для
балансировки дерева соответствующее вращение.

Предположим, что процедура в настоящий момент обращается к узлу X.
Допустим, что она перед этим обращалась к правому поддереву снизу от
узла X и что параметр has_grown равен true, означая, что правое
поддерево увеличилось. Если поддеревья узла X до этого имели одинаковую
высоту, тогда правое поддерево станет теперь выше левого. В этой точке
дерево сбалансировано, но поддерево с корнем в узле X выросло, так как
выросло его правое поддерево.

Если левое поддерево узла X вначале было выше, чем правое, то левое и
правое поддеревья теперь будут иметь одинаковую высоту. Высота поддерева
с корнем в узле X не изменилась — она по-прежнему равна высоте левого
поддерева плюс 1. В этом случае процедура InsertItem установит значение
переменной has_grown равным false, показывая, что дерево сбалансировано.

========162

@Рис. 7.11 Различные вращения АВЛ-дерева

======163

В конце концов, если правое поддерево узла X было первоначально выше
левого, то вставка нового узла делает дерево несбалансированным в узле
X. Процедура InsertItem вызывает подпрограмму RebalanceRigthGrew для
балансировки дерева. Процедура RebalanceRigthGrew выполняет левое
вращение или вращение вправо-влево, в зависимости от ситуации.

Если новый элемент вставляется в левое поддерево, то подпрограмма
InsertItem выполняет аналогичную процедуру.

Public Sub InsertItem(node As AVLNode, parent As AVLNode, _

txt As String, has_grown As Boolean)

Dim child As AVLNode

‘ Если это нижний уровень дерева, поместить

‘ в родителя указатель на новый узел.

If parent Is Nothing Then

Set parent = node

parent.Balance = BALANCED

has_grown = True

Exit Sub

End If

‘ Продолжить с левым и правым поддеревьями.

If txt node.Box.Caption Then

Set child = node.RightChild

DeleteItem child, txt, shrunk

Set node.RightChild = child

If shrunk Then RebalanceRightShrunk node, shrunk

Else

Set target = node

If target.RightChild Is Nothing Then

‘ Потомков нет или есть только правый.

Set node = target.LeftChild

shrunk = True

ElseIf target.LeftChild Is Nothing Then

‘ Есть только правый потомок.

Set node = target.RightChild

shrunk = True

Else

‘ Есть два потомка.

Set child = target.LeftChild

ReplaceRightmost child, shrunk, target

Set target.LeftChild = child

If shrunk Then RebalanceLeftShrunk node, shrunk

End If

End If

End Sub

Private Sub ReplaceRightmost(repl As AVLNode, shrunk As Boolean, target
As AVLNode)

Dim child As AVLNode

If repl.RightChild Is Nothing Then

target.Box.Caption = repl.Box.Caption

Set target = repl

Set repl = repl.LeftChild

shrunk = True

Else

Set child = repl.RightChild

ReplaceRightmost child, shrunk, target

Set repl.RightChild = child

If shrunk Then RebalanceRightShrunk repl, shrunk