Заглушка (stub) 134 Задача 200, 321, 450

Бозе-Нельсона 450

голландского национального флага 321

занятости 580

Иосифа 97

коллекционера карточек 581

о дне рождения 580

о ранце 212, 214

о ханойских башнях 200

связности 23, 26

сложность 71 Запись 142

инфиксная 142

Польская 142

постфиксная 142 Звезда Коха 207 Золотая пропорция 210 Золотое сечение (golden ratio) 55, 572 Зондирование 583, 647

линейное 583

Инверсия 265 Индекс 508, 643

текстовой строки 509 Индексный элемент 170 Интерфейс 82, 127

Array.h 280

непрозрачный 127 Инфиксная запись 142

Каталог 650

Класс 83, 127. 138

Complex 174

Item 136

POINT 128

QUEUE 176

string 114, 180

Vector 90

абстрактный 156

контейнерный 138

производный 156

кластер 585 Кластеризация 588 Клиент 127

Клиентская программа 82

Ключ 251, 259, 321, 406, 475, 602

дублированный 321

поиска 475

сигнальный 259. См. также Сортировка: вставками

Ключевое слово 130

private 130

public 130

static 130, 131

this 130 Коллекция объектов 136 Компаратор 439, 445

слияния 469 Комплексные корни из единицы 174 Компоненты 26

связанные 26 Константа 54

Эйлера 54 Конструирование 564 Конструктор 95, 129

копирования 175, 178

списка пропусков 558 Контейнерный класс 138 Корень (root) 30, 220 Корзина 412

Линейное зондирование 583 Листья 220 Логарифм 53, 54

двоичный 53, 54

натуральный 53

Марковская цепь 660 Массив 27, 83, 86, 87

двумерный 116 Матрица 116

разреженная 120

смежности 121 Медиана 326 Мемуаризация 212

Метод 27, 197, 295. 300, 418, 438. 578 быстрого объединения См. Алгоритм: быстрого

объединения быстрого поиска 27. См. также Алгоритм:

быстрого поиска

Метод

быстрой сортировки 300. См. также Алгоритм:

быстрой сортировки выборки 326

медианы из трех элементов 316 раздельного связывания 578 разделяй и властвуй 197 распределяющего подсчета 295 самоорганизующегося поиска 514 сжатия пути (path compression) 34 сортировки специального назначения 248, 438 Флойда 379

эвристика в масштабах корзины 418 Моделирование неупорядоченной очереди 176 Модульное

программирование 133

хеширование 570 Мультисписок 120

Натуральный логарифм 53 Нормальная аппроксимация 91

0-нотация 49 Обход графа 240 Общедоступный (public) 130 Объединение 26

двух BST-деревьев 520

дерева 530 Объект 129, 136

абстрактный 136

коллекция 136

Объектно-ориентированное программирование

(ООП) 130 Объявление typedef 80 Оператор delete 108 new 108 new[] 90 return 79 Операции 26 абстрактные 26 find (поиск) 26, 32, 36 union (объединение) 33, 36 со строками 112

Операция 132, 148, 326, 439, 479, 646 132 == 132,478 count 485

insert 167, 393, 500, 581, 646 join 520, 560 partition 517

remove (удаление) 481,488, 593 search (поиск) 481, 490, 581, 529, 646 select (выбор) 480, 515 sort (сортировка) 480 выборки (selection) 326 вытолкнуть 148 записи (write) 454 затолкнуть 148

идеального обратного тасования (perfect

unshuffle) 440 идеального тасования (perfect-shuffle) 439 нахождения медианы 326 объединить (join) 479 поиск (find) 153 соединение (union) 153 создать 148, 153 сравнения 113

сравнения обмена (compare-exchange) 440 считывания (read) 454 Оптимизация 525

Остовное дерево (spanning tree) 26 Очередь 137, 159, 355 FIFO 159

без повторяющихся элементов 168

на базе массива 162

на базе связного списка 161 биномиальная 358, 389, 392 двухсторонняя 164. См. также Абстрактный тип

данных: дек (double-ended queue) неупорядоченная 163 обобщенная 137, 163

объединение двух биномиальных очередей 397 по приоритетам 355

в виде двухсвязного списка 383

для индексных элементов 385

на базе индексного сортирующего дерева 387

на базе сортирующего дерева 368

неупорядоченная 382

Пакет 333 Память 476

автоматическое распределение памяти 181

ассоциативная 476

виртуальная 465, 646

утечка 177 Параметры функции 79 Перегруз 466 Перегрузка (overloading) 83 Перегрузка операций (operator overloading) 131 Пирамидальная сортировка 331 Поиск

26, 28, 65, 190, 474, 475, 602, 645, 646

бинарный 66, 68, 493

ближайшего соседа 482

быстрый (quick-find) 28

в В-дереве 657

в глубину 190, 240

в диапазоне 482, 495

в списках пропусков 557

в таблице расширяемого хеширования 668

в ширину 243

внешний 645

интерполяционный 496

неуспешный 489

от метки 482

поразрядный 602

последовательный 65, 68, 486

с использованием индексации по ключам 483

строки 114

успешный 489 Полином 182 Польская запись 142 Попытка Бернулли 90 Поразрядная сортировка 401

LSD 403, 425

MSD 403, 412

обменная 407 Постоянная См. Константа Постоянная Эйлера 54 Постфиксная запись 142 Потеря быстродействия 114 Представление 62

двоичное 62 Преобразование типов 78 78

Префиксная запись 142 Приватный (private) 130 Приведение типов 78 Программа 82, 145, 189, 205, 240

PostScript 145

клиентская 82

поиск в глубину 240

рекурсивная 189

рисования линейки 205 Программирование 211

динамическое 216 восходящее 211 нисходящее 212

модульное 133 Пропорция 210

золотая 210 Простые числа Мерсенне 571 Процедура

fixDown 370

fixUp 370 nyrb(path) 219

длина 227

простой 225

сжатие 34

Разделение

каталога 669

страницы 669 Раздельное связывание 578 Разрешение конфликтов 568 Рандомизация 525, 573 Распределение памяти 108, 181

автоматическое 181

динамическое 108

под двумерный массив 117 Расширяемое хеширование 665 Реализация 127 Ребра 120 Ребро (edge) 219 Рекуррентные соотношенияи 60 Рекурсия 60, 189, 340, 353

глубина рекурсии 195

листовая (оконечная) 196

разделяй и властвуй 197 Решето Эратосфена 88 Ротация 512