Sedgewick R. / Седжвик Р. - Algorithms in C, Third Edition / Фундаментальные алгоритмы на C (3-я редакция, части 1-5, 1 книга) [2003, DjVu, RUS]

Часть 1. Анализ 17
Глава 1. Введение 18
1.1 Алгоритмы 19
1.2 Пример задачи связности 21
1.3 Алгоритмы объединения-поиска 25
1.4 Перспективы 36
1.5 Обзор тем 38
Глава 2. Принципы анализа алгоритмов 40
2.1 Реализация и эмпирический анализ 41
2.2 Анализ алгоритмов 45
2.3 Рост функций 48
2.4 О-нотация 54
2.5 Простейшие рекурсии 59
2.6 Примеры анализа алгоритмов 63
2.7 Гарантии, предсказания и ограничения 68
Ссылки к части 1 72
Часть 2. Структуры данных 74
Глава 3. Элементарные структуры данных 75
3.1 Строительные блоки 76
3.2 Массивы 86
3.3 Связные списки 92
3.4 Обработка простых списков 98
3.5 Распределение памяти под списки 106
3.6 Строки 109
3.7 Составные структуры данных 114
Глава 4. Абстрактные типы данных 124
4.1 Абстрактные объекты и коллекции объектов 128
4.2 АТД стека магазинного типа 131
4.3 Примеры клиентских программ, использующих АТД стека 134
4.4 Реализации АТД стека 140
4.5 Создание нового АТД 144
4.6 Очереди FIFO и обобщенные очереди 147
4.7 Повторяющиеся и индексные элементы 155
4.8 АТД первого класса 160
4.9 Пример использования АТД в приложениях 170
4.10 Перспективы 175
Глава 5. Рекурсия и деревья 177
5.1 Рекурсивные алгоритмы 178
5.2 Разделяй и властвуй 185
5.3 Динамическое программирование 199
5.4 Деревья 206
5.5 Математические свойства бинарных деревьев 215
5.6 Обход дерева 218
5.7 Рекурсивные алгоритмы бйнарных деревьев , 224
5.8 Обход графа 229
5.9 Перспективы 235
Ссылки к части 2 236
Часть 3. Сортировка 237
Глава 6. Элементарные методы сортировки 238
6.1 Правила игры 240
6.2 Сортировка выбором 246
6.3 Сортировка вставками 247
6.4 Пузырьковая сортировка 250
6.5 Характеристики производительности элементарных методов сортировки 252
6.6 Сортировка методом Шелла 258
6.7 Сортировка других типов данных 267
6.8 Сортировка по индексам и указателям 271
6.9 Сортировка связных списков 278
6.10 Метод распределяющего подсчета 282
Глава 7. Быстрая сортировка 285
7.1 Базовый алгоритм 286
7.2 Характеристики производительности быстрой сортировки 291
7.3 Размер стека 295
7.4 Подфайлы небольших размеров 299
7.5 Метод разделения с вычислением медианы из трех элементов 302
7.6 Дублированные ключи 307
7.7 Строки и векторы 310
7.8 Выборка 312
Глава 8. Слияние и сортировка слиянием 316
8.1 Двухпутевое слияние 318
8.2 Абстрактное обменное слияние 320
8.3 Нисходящая сортировка слиянием 322
8.4 Усовершенствования базового алгоритма 325
8.5 Восходящая сортировка слиянием 328
8.6 Производительность сортировки слиянием 331
8.7 Реализация сортировки слиянием, ориентированная на связные списки 335
8.8 Возврат к рекурсии 338
Глава 9. Очереди по приоритетам и пирамидальная сортировка 340
9.1 Элементарные реализации 344
9.2 Пирамидальная структура данных 347
9.3 Алгоритмы для сортирующих деревьев 349
9.4 Пирамидальная сортировка 356
9.5 Абстрактный тип данных очереди по приоритетам 363
9.6 Очередь по приоритетам для индексных элементов 368
9.7 Биномиальные очереди 372
Глава 10. Поразрядная сортировка 383
10.1 Биты, байты и слова 385
10.2 Бинарная быстрая сортировка 388
10.3 Поразрядная сортировка*MSD 394
10.4 Трехпутевая поразрядная быстрая сортировка 402
10.5 Поразрядная сортировка LSD 406
10.6 Рабочие характеристики поразрядных сортировок 410
10.7 Сортировки с сублинейным временем выполнения 414
Глава 11. Методы сортировки специального назначения 419
11.1 Четно-нечетная сортировка слиянием Бэтчера 421
11.2 Сети сортировки 426
11.3 Внешняя сортировка 434
11.4 Различные реализации сортировки слиянием 441
11.5 Параллельная процедура сортировки слиянием 448
Ссылки к части 3 453
Часть 4. Поиск 455
Глава 12. Таблицы символов и деревья бинарного поиска 456
12.1 Абстрактный тип данных таблицы символов 458
12.2 Поиске использованием индексации по ключам 463
12.3 Последовательный поиск 466
12.4 Бинарный поиск 472
12.5 Деревья бинарного поиска 477
12.6 Характеристики производительности деревьев бинарного поиска 483
12.7 Реализация индексов при помощи таблиц символов 486
12.8 Вставка в корень в деревьях бинарного поиска 490
12.9 Реализации других функций АТД с помощью BST-дерева 495
Глава 13. Сбалансированные деревья 504
13.1 Рандомизированные BST-деревья 508
13.2 Расширенные деревья бинарного поиска 514
13.3 Нисходящие 2-3-4-деревья 520
13.4 Красно-черные, или RB-деревья 525
13.5 Списки пропусков 535
13.6 Характеристики производительности 543
Глава 14. Хеширование 547
14.1 Хеш-функции 548
14.2 Раздельное связывание 558
14.3 Линейное зондирование 562
14.4 Двойное хеширование 567
14.5 Динамические хеш-таблицы 573
14.6 Перспективы 577
Глава 15. Поразрядный поиск 582
15.1 Деревья цифрового поиска 583
15.2 Trie-д еревья 588
15.3 Patricia-деревья 597
15.4 Многопутевые trie-деревья и TST-деревья *. 605
15.5 Алгоритмы индексирования текстовых строк 652
Глава 16. Внешний поиск 627
16.1 Правила игры 629
16.2 Индексно-последовательный доступ 631
16.3 В-деревья 634
16.4 Расширяемое хеширование 646
16.5 Перспективы 657
Ссылки к части 4 660
Предметный указатель к частям 1-4 663
Часть 5. Алгоритмы на графах 673
Глава 17. Свойства и типы графов 674
17.1 Глоссарий 678
17.2 АТД графа 687
17.3 Представление графа в виде матрицы смежности 691
17.4 Представление графа в виде списка смежных вершин 697
17.5 Вариации, расширения и затраты 700
17.6 Генераторы графов 709
17.7 Простые, эйлеровы и гамильтоновы пути 720
17.8 Задачи обработки графов 734
Глава 18. Поиск на графах 744
18.1 Исследование лабиринта 745
18.2 Поиск в глубину 750
18.3 АТД-функции поиска на графе 755
18.4 Свойства лесов DFS 760
18.5 Алгоритмы DFS 767
18.6 Отделимость и бисвязность 774
18.7 Поиск в ширину 782
18.8 Обобщенный поиск на графах 792
18.9 Анализ алгоритмов на графах 800
Глава 19. Орграфы и ориентированные ациклические графы 807
19.1 Глоссарий и правила игры 810
19.2 Анатомия поиска DFS в орграфах 819
19.3 Достижимость и транзитивное замыкание 828
19.4 Отношения эквивалентности и частичные порядки 840
19:5 Графы DAG 844
19.6 Топологическая сортировка 849
19.7 Достижимость в графе DAG 859
19.8 Сильные компоненты в орграфах 862
19.9 Еще раз о транзитивном замыкании 872
19.10 Перспективы 876
Глава 20. Минимальные остовные деревья 880
20.1 Представления 883
20.2 Принципы, положенные в основу алгоритмов построения дерева MST 889
20.3 Алгоритм Прима и поиск по приоритету 896
20.4 Алгоритм Крускала 907
20.5 Алгоритм Борувки 913
20.6 Сравнения и усовершенствования 916
20.7 Эвклидово дерево MST 922
Глава 21. Кратчайшие пути 925
21.1 Основные принципы 933
21.2 Алгоритм Дейкстры 938
21.3 Все кратчайшие пути 948
21.4 Кратчайшие пути в ациклических сетях 956
21.5 Эвклидовы сети 964
21.6 Сведение 969
21.7 Отрицательные веса 984
21.8 Перспективы 1001
Глава 22. Потоки в сетях 1003
22.1 Транспортные сети 1010
22.2 Алгоритм поиска максимального потока методом аугментального пути 1022
22.3 Алгоритмы определения максимальных потоков
методом выталкивания превосходящего потока 1047
22.4 Сведение к максимальному потоку 1061
22.5 Потоки минимальной стоимости 1079
22.6 Сетевой симплексный алгоритм 1089
22.7 Сведение к задаче о потоке минимальной стоимости 1108
22.8 Перспективы 1117
Ссылки, использованные в пятой части 1121
Предметный указатель к части 5 1123