Читайте данную работу прямо на сайте или скачайте
VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
TOC \o "1-3" Введение.................................................................................................. 8
Целевая аудитория.............................................................................. 10
Глава 1. Основные понятия.................................................................. 15
Что такое алгоритмы?........................................................................ 15
анализ скорости выполнения алгоритмов...................................... 16
Пространство Ч время..................................................................... 17
Оценка с точностью до порядка....................................................... 17
Поиск сложных частей алгоритма................................................... 19
Сложность рекурсивных алгоритмов............................................... 20
Многократная рекурсия.................................................................... 21
Косвенная рекурсия.......................................................................... 22
Требования рекурсивных алгоритмов к объему памяти................. 22
Наихудший и средненный случай.................................................. 23
Часто встречающиеся функции оценки порядка сложности....... 24
Логарифмы........................................................................................ 25
Реальные словия Ч насколько быстро?........................................ 25
Обращение к файлу подкачки.......................................................... 26
Псевдоуказатели, ссылки на объекты и коллекции......................... 27
Резюме................................................................................................... 29
Глава 2. Списки..................................................................................... 30
Знакомство со списками.................................................................... 31
Простые списки................................................................................... 31
Коллекции.......................................................................................... 32
Список переменного размера........................................................... 33
Класс SimpleList................................................................................ 36
Неупорядоченные списки.................................................................. 37
Связные списки................................................................................... 41
Добавление элементов к связному списку....................................... 43
Удаление элементов из связного списка.......................................... 44
Уничтожение связного списка.......................................................... 44
Сигнальные метки............................................................................. 45
Инкапсуляция связных списков........................................................ 46
Доступ к ячейкам.............................................................................. 47
Разновидности связных списков...................................................... 49
Циклические связные списки............................................................ 49
Проблема циклических ссылок........................................................ 50
Двусвязные списки............................................................................ 50
Потоки............................................................................................... 53
Другие связные структуры................................................................ 56
Псевдоуказатели................................................................................. 56
Резюме................................................................................................... 59
Глава 3. Стеки и очереди...................................................................... 60
Стеки..................................................................................................... 60
Множественные стеки....................................................................... 62
Очереди................................................................................................. 63
Циклические очереди........................................................................ 65
Очереди на основе связных списков................................................ 69
Применение коллекций в качестве очередей................................... 70
Приоритетные очереди..................................................................... 70
Многопоточные очереди.................................................................. 72
Резюме................................................................................................... 74
Глава 4. Массивы.................................................................................. 75
Треугольные массивы........................................................................ 75
Диагональные элементы................................................................... 77
Нерегулярные массивы...................................................................... 78
Прямая звезда.................................................................................... 78
Нерегулярные связные списки.......................................................... 79
Разреженные массивы........................................................................ 80
Индексирование массива.................................................................. 82
Очень разреженные массивы............................................................ 85
Резюме................................................................................................... 86
Глава 5. Рекурсия.................................................................................. 86
Что такое рекурсия?........................................................................... 87
Рекурсивное вычисление факториалов........................................... 88
анализ времени выполнения программы........................................ 89
Рекурсивное вычисление наибольшего общего делителя............. 90
анализ времени выполнения программы........................................ 91
Рекурсивное вычисление чисел Фибоначчи................................... 92
анализ времени выполнения программы........................................ 93
Рекурсивное построение кривых Гильберта................................... 94
анализ времени выполнения программы........................................ 96
Рекурсивное построение кривых Серпинского.............................. 98
анализ времени выполнения программы...................................... 100
Опасности рекурсии......................................................................... 101
Бесконечная рекурсия..................................................................... 101
Потери памяти................................................................................. 102
Необоснованное применение рекурсии......................................... 103
Когда нужно использовать рекурсию............................................ 104
Хвостовая рекурсия.......................................................................... 105
Нерекурсивное вычисление чисел Фибоначчи............................. 107
Устранение рекурсии в общем случае............................................ 110
Нерекурсивное построение кривых Гильберта............................ 114
Нерекурсивное построение кривых Серпинского....................... 117
Резюме................................................................................................. 121
Глава 6. Деревья.................................................................................. 121
Определения...................................................................................... 122
Представления деревьев................................................................... 123
Полные злы.................................................................................... 123
Списки потомков............................................................................. 124
Представление нумерацией связей................................................ 126
Полные деревья............................................................................... 129
Обход дерева...................................................................................... 130
Упорядоченные деревья................................................................... 135
Добавление элементов.................................................................... 135
Удаление элементов........................................................................ 136
Обход порядоченных деревьев.................................................... 139
Деревья со ссылками........................................................................ 141
Работа с деревьями со ссылками.................................................... 144
Квадродеревья................................................................................... 145
Изменение MAX_PER_NODE......................................................... 151
Использование псевдоуказателей в квадродеревьях..................... 151
Восьмеричные деревья................................................................... 152
Резюме................................................................................................. 152
Глава 7. Сбалансированные деревья.................................................. 153
Сбалансированность дерева............................................................ 153
ВЛ‑деревья....................................................................................... 154
Удаление зла из АВЛ‑дерева........................................................ 161
Б‑деревья............................................................................................ 166
Производительность Б‑деревьев.................................................... 167
Вставка элементов в Б‑дерево........................................................ 167
Удаление элементов из Б‑дерева.................................................... 168
Разновидности Б‑деревьев.............................................................. 169
Улучшение производительности Б‑деревьев................................. 171
Балансировка для странения разбиения блоков.......................... 171
Вопросы, связанные с обращением к диску.................................. 173
База данных на основе Б+дерева.................................................... 176
Резюме................................................................................................. 179
Глава 8. Деревья решений.................................................................. 179
Поиск в деревьях игры..................................................................... 180
Минимаксный поиск........................................................................ 181
Улучшение поиска в дереве игры.................................................. 185
Поиск в других деревьях решений................................................. 187
Метод ветвей и границ.................................................................... 187
Эвристики........................................................................................ 191
Другие сложные задачи.................................................................... 207
Задача о выполнимости.................................................................. 207
Задача о разбиении......................................................................... 208
Задача поиска Гамильтонова пути................................................. 209
Задача коммивояжера..................................................................... 210
Задача о пожарных депо................................................................. 211
Краткая характеристика сложных задач........................................ 212
Резюме................................................................................................. 212
Глава 9. Сортировка........................................................................... 213
Общие соображения......................................................................... 213
Таблицы казателей........................................................................ 213
Объединение и сжатие ключей....................................................... 215
Примеры программ........................................................................... 217
Сортировка выбором........................................................................ 219
Рандомизация.................................................................................... 220
Сортировка вставкой....................................................................... 221
Вставка в связных списках..............................................................
Пузырьковая сортировка................................................................. 224
Быстрая сортировка......................................................................... 227
Сортировка слиянием....................................................................... 232
Пирамидальная сортировка............................................................ 234
Пирамиды........................................................................................ 235
Приоритетные очереди................................................................... 237
лгоритм пирамидальной сортировки.......................................... 240
Сортировка подсчетом..................................................................... 241
Блочная сортировка.......................................................................... 242
Блочная сортировка с применением связного списка................... 243
Блочная сортировка на основе массива......................................... 245
Резюме................................................................................................. 248
Глава 10. Поиск................................................................................... 248
Примеры программ........................................................................... 249
Поиск методом полного перебора................................................... 249
Поиск в порядоченных списках.................................................... 250
Поиск в связных списках................................................................ 251
Двоичный поиск................................................................................ 253
Интерполяционный поиск............................................................... 255
Строковые данные............................................................................ 259
Следящий поиск................................................................................ 260
Интерполяционный следящий поиск............................................. 261
Резюме................................................................................................. 262
Глава 11. Хеширование...................................................................... 263
Связывание........................................................................................ 265
Преимущества и недостатки связывания....................................... 266
Блоки.................................................................................................. 268
Хранение хеш‑таблиц на диске...................................................... 270
Связывание блоков.......................................................................... 274
Удаление элементов........................................................................ 275
Преимущества и недостатки применения блоков......................... 277
Открытая адресация......................................................................... 277
Линейная проверка.......................................................................... 278
Квадратичная проверка................................................................... 284
Псевдослучайная проверка............................................................. 286
Удаление элементов........................................................................ 289
Резюме................................................................................................. 291
Глава 12. Сетевые алгоритмы............................................................ 292
Определения...................................................................................... 292
Представления сети.......................................................................... 293
Оперирование злами и связями.................................................... 295
Обходы сети....................................................................................... 296
Наименьшие остовные деревья...................................................... 298
Кратчайший маршрут...................................................................... 302
Установка меток.............................................................................. 304
Коррекция меток............................................................................. 308
Другие задачи поиска кратчайшего маршрута.............................. 311
Применения метода поиска кратчайшего маршрута.................... 316
Максимальный поток...................................................................... 319
Приложения максимального потока.............................................. 325
Резюме................................................................................................. 327
Глава 13. Объектно‑ориентированные методы................................. 327
Преимущества ООП......................................................................... 328
Инкапсуляция.................................................................................. 328
Полиморфизм.................................................................................. 330
Наследование и повторное использование....................................
Парадигмы ООП............................................................................... 335
Управляющие объекты................................................................... 335
Контролирующий объект............................................................... 336
Итератор.......................................................................................... 337
Дружественный класс..................................................................... 338
Интерфейс....................................................................................... 340
Фасад............................................................................................... 340
Порождающий объект..................................................................... 340
Единственный объект...................................................................... 341
Преобразование в последовательную форму................................ 341
Парадигма Модель/Вид/Контроллер............................................. 344
Резюме................................................................................................. 346
Требования к аппаратному обеспечению...................................... 346
Выполнение программ примеров.................................................... 346
Далее следуета лтекст, который любой важающий себя программист должен прочесть хотя бы один раз. (Это наше субъективное мнение)
Многие алгоритмы предоставляют выбор между скоростью выполнения и используемыми программой ресурсами. Задача может выполняться
быстрее, используя больше памяти, или наоборот, медленнее, заняв меньший объем памяти.
===========2
Хорошим примером в данном случае может служить алгоритм нахождения кратчайшего пути. Задав карту лиц города в виде сети, можно написать алгоритм, вычисляющий кратчайшее расстояние между любыми двумя точками в этой сети. Вместо того чтобы каждый раз заново пересчитывать кратчайшее расстояние между двумя заданными точками, можно заранее просчитать его для всех пар точек и сохранить результаты в таблице. Тогда, чтобы найти кратчайшее расстояние для двух заданных точек, достаточно будет просто взять готовое значение из таблицы.
При этом мы получим результат практически мгновенно, но это потребует большого объема памяти. Карта лиц для большого города, такого как Бостон или Денвер, может содержать сотни тысяч точек. Для такой сети таблица кратчайших расстояний содержала бы более 10 миллиардов записей. В этом случае выбор между временем исполнения и объемом требуемой памяти очевиден: поставив дополнительные 10 гигабайт оперативной памяти, можно заставить программу выполняться гораздо быстрее.
Из этой связи вытекает идея пространственно‑временной сложности алгоритмов. При этом подходе сложность алгоритма оценивается в терминах времени и пространства, и находится компромисс между ними.
В этом материале основное внимание деляется временной сложности, но мы также постарались обратить внимание и на особые требования к объему памяти для некоторых алгоритмов. Например, сортировка слиянием (mergesort), обсуждаемая в 9 главе, требует больше временной памяти. Другие алгоритмы, например пирамидальная сортировка (heapsort), которая также обсуждается в 9 главе, требует обычного объема памяти.
С Здесь находится код для создания и настройки списка и т.д.
:
С Напечатать календарь на месяц.
С
С 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
Многопоточные очереди[RV6]
Интересной разновидностью очередей являются 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.
Квадродеревья[RP12]
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 <= xmid Then
If Y <= ymid Then
Set LocateLeaf = NWchild.LocateLeaf( _
X, Y, xmin, xmid, ymin, ymid)
Else
Set LocateLeaf = SWchild.LocateLeaf _
X, Y, xmin, xmid, ymid, ymax)
End If
Else
If Y <= ymid Then
Set LocateLeaf = NEchild.LocateLeaf( _
X, Y, xmid, xmax, ymin, ymid)
Else
Set LocateLeaf = SEchild.LocateLeaf( _
X, Y, xmid, xmax, ymid, ymax)
End If
End If
End Function
После нахождения листа, который содержит точку, проверяем населенные пункты в листе, чтобы найти, который из них ближе всего от выбранной точки. Это делается при помощи процедуры NearPointInLeaf.
Public Sub NearPointInLeaf (X As Single, Y As Single, _
best_item As QtreeItem, best_dist As Single, comparisons As Long)
Dim new_item As QtreeItem
Dim Dx As Single
Dim Dy As Single
Dim new_dist As Single
' Начнем с заведомо плохого решения.
best_dist = 1
Set best_item = Nothing
' Остановиться если лист не содержит элементов.
If Items.Count < 1 Then Exit Sub
For Each new_item In Items
comparisons = comparisons + 1
Dx = new_item.X - X
Dy = new_item.Y - Y
new_dist =Dx * Dx + Dy * Dy
If best_dist > 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) <= xmid Then
' Продолжаем с потомками на западе.
If Y - Sqr(best_dist) <= ymid Then
' Проверить северо-западного потомка.
NWchild.CheckNearbyLeaves _
exclude, X, Y, best_item, _
best_dist, comparisons, _
xmin, xmid, ymin, ymid
End If
If Y + 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
' Проверить северо-восточного потомка.
NEchild.CheckNearbyLeaves _
exclude, X, Y, best_item, _
best_dist, comparisons, _
xmid, xmax, ymin, ymid
End If
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 использует квадродерево. При старте программа запрашивает число элементов данных, которое она должна создать, затем она создает элементы и рисует их в виде точек. Задавайте вначале небольшое (около 1) число элементов, пока вы не определите, насколько быстро ваш компьютер может создавать элементы.
Интересно наблюдать квадродеревья, элементы которых распределены неравномерно, поэтому программа выбирает точки при помощи функции XE "Странный аттрактор" странного аттрактора (strange attractor) из XE "Теория:хаоса" теории хаоса (chaos theory). Хотя кажется, что элементы следуют в случайном порядке, они образуют интересные кластеры.
При выборе какой‑либо точки на форме при помощи мыши, программа Qtree находит ближайший к ней элемент. Она подсвечивает этот элемент и выводит число проверенных при его поиске элементов.
В меню Options (Опции) программы можно задать, должна ли программа использовать квадродеревья или нет. Если поставить галочку в пункте Use Quadtree (Использовать квадродерево), то программа выводит на экран квадродерево и использует его для поиска элементов. Если этот пункт не выбран, программа не отображает квадродерево и находит нужные элементы путем перебора.
Программа проверяет намного меньшее число элементов и работает намного быстрее при использовании квадродерева. Если этот эффект не слишком заметен на вашем компьютере, запустите программу, задав при старте 10. или 20. входных элементов. Вы заметите разницу даже на компьютере с процессором Pentium с тактовой частотой 90 Гц.
На рис. 6.26 показано окно программа Qtree на котором изображено 10. элементов. Маленький прямоугольник в верхнем правом глу обозначает выбранный элемент. Метка в верхнем левом глу показывает, что программа проверила всего 40 из 10. элементов перед тем, как найти нужный.
Открытая адресация
[RV19] XE "Адресация:открытая"
XE "Хеширование:открытая адресация" open addressing XE "addressing:open" K индекс массива, равный K Mod 100. При этом элемент со значением 1723 окажется в таблице на 23 позиции. Затем, когда понадобится найти элемент 1723, проверяется 23 позиция в массиве.
==========295
Различные схемы открытой адресации используют разные методы для формирования тестовых последовательностей. В следующих разделах рассматриваются три наиболее важных метода: линейная, квадратичная и псевдослучайная проверка.
PAGE
\# "'Стр: '#'
'"а Стр: 19
[RP1]Вариант - временная и
ёмкостная сложность
PAGE
\# "'Page: '#'
'"а Page: 31
[RP2]Вариант - перегрузкой памяти.
PAGE
\# "'Стр: '#'
'"а Стр: 43
[RP3]Вероятно, жаргонизм,
может выбросить вообще?
PAGE
\# "'Стр: '#'
'"а Стр: 43
[RP4]Вариант: сборка мусора
PAGE
\# "'Стр: '#'
'"а Стр: 44
[RP5]Исправлена опечатка в книге - см. ссылка более недоступнаvbaupd.htm
PAGE
\# "'Ñòð: '#'
'"а Ñòð: 83
[RV6]Может есть более удачный вариант термина?
PAGE
\# "'Ñòð: '#'
'"а Ñòð: 138
[RV7]Вариант: многопоточные деревья.
PAGE
\# "'Ñòð: '#'
'"а Ñòð: 138
[RV8]Варианты:
TRIE-структуры, ТРАЙ-структуры
PAGE
\# "'Ñòð: '#'
'"а Ñòð: 138
[RV9]Варианты: деревья квадрантов,
Q-деревья.
PAGE
\# "'Ñòð: '#'
'"а Ñòð: 140
[RV10]Вариант: тернарными
PAGE
\# "'Ñòð: '#'
'"а Ñòð: 141
[RV11]Исправлена ошибка в исходном листинге - Left заменено на Right
PAGE
\# "'Стр: '#'
'"а Стр: 165
[RP12]Варианты: деревья квадратов, Q-деревья
PAGE
\# "'Стр: '#'
'"а Стр: 190
[RV13]Исправлена ошибка - в оригинале буквы элементов не соответствуют рисунку.
PAGE
\# "'Стр: '#'
'"а Стр: 212
[RV14]Вариант: задача о ранце
PAGE
\# "'Стр: '#'
'"а Стр: 214
[RV15]Исправлена смысловая ошибка в оригинале - вместо зла B в нем написано зел C.
PAGE
\# "'Стр: '#'
'"а Стр: 300
[RV16]Варианты ‑
последовательностью проверок, последовательностью проб
PAGE
\# "'Стр: '#'
'"а Стр: 303
[RV17]Ошибка в оригинале -
на рисунке приведен скриншот другой программы, искомое значение не соответствует тексту.
PAGE
\# "'Стр: '#'
'"а Стр: 304
[RV18]Ошибка в оригинале -
на рисунке приведен скриншот другой программы.
PAGE
\# "'Стр: '#'
'"а Стр: 314
[RV19]Возможно, имеется в виду хеш‑адресация.
PAGE
\# "'Стр: '#'
'"а Стр: 339
[RV20]Вариант - жадными алгоритмами.
PAGE
\# "'Стр: '#'
'"а Стр: 352
[RV21]Вариант: кратчайший маршрут между двумя точками
PAGE
\# "'Стр: '#'
'"а Стр: 361
[RV22]Вариант: потоковой сетью (flow network)
PAGE
\# "'Стр: '#'
'"а Стр: 378
[RP23]Не верен в точности терминов.