Структуры данных и алгоритмы в Java

Дополнительные темы......Page 18
О чем написана эта книга......Page 19
Доступность......Page 20
Примеры кода Java......Page 21
Как организован материал книги......Page 22
Вперед!......Page 24
Зачем нужны структуры данных и алгоритмы?......Page 25
Инструментарий программиста......Page 26
Обзор структур данных......Page 27
Определения......Page 28
Поле......Page 29
Недостатки процедурных языков......Page 30
Объекты в двух словах......Page 31
Создание объектов......Page 32
Пример объектно-ориентированной программы......Page 33
Наследование и полиморфизм......Page 36
В Java нет указателей......Page 37
Вывод......Page 41
Итоги......Page 44
Вопросы......Page 45
Приложение Array Workshop......Page 46
Поиск......Page 48
Удаление......Page 49
Проблема дубликатов......Page 50
Не слишком быстро......Page 51
Обращение к элементам массива......Page 52
Пример массива......Page 53
Деление программы на классы......Page 56
Интерфейсы классов......Page 58
Кто чем занимается?......Page 59
Пример highArray.java......Page 60
Приложение Ordered Workshop......Page 63
Линейный поиск......Page 64
Двоичный поиск......Page 65
Двоичный поиск с методом find()......Page 67
Класс OrdArray......Page 69
Логарифмы......Page 72
Формула......Page 73
Операция, обратная возведению в степень......Page 74
Класс Person......Page 75
Программа classDataArray.java......Page 76
O-синтаксис......Page 79
Двоичный поиск: сложность пропорциональна log(N)......Page 80
Константа не нужна......Page 81
Почему бы не использовать только массивы?......Page 82
Итоги......Page 83
Вопросы......Page 84
Программные проекты......Page 85
Как это делается?......Page 87
Пример пузырьковой сортировки......Page 89
Приложение BubbleSort Workshop......Page 91
Реализация пузырьковой сортировки
на языке Java......Page 94
Сложность пузырьковой сортировки......Page 97
Пример сортировки методом выбора......Page 98
Приложение SelectSort Workshop......Page 100
Реализация сортировки методом выбора на языке Java......Page 101
Сложность сортировки методом выбора......Page 103
Пример сортировки методом вставки......Page 104
Сортировка 10 столбцов......Page 106
Реализация сортировки методом вставки на языке Java......Page 108
Сложность сортировки методом вставки......Page 111
Реализация сортировки объектов на языке Java......Page 112
Устойчивость сортировки......Page 115
Итоги......Page 116
Вопросы......Page 117
Упражнения......Page 118
Программные проекты......Page 119
Ограничение доступа......Page 121
Стеки......Page 122
Почтовая аналогия......Page 123
Приложение Stack Workshop......Page 124
Реализация стека на языке Java......Page 126
Пример использования стека №1: Перестановка букв в слове......Page 129
Пример №2: поиск парных скобок......Page 132
Очереди......Page 136
Приложение Queue Workshop......Page 137
Циклическая очередь......Page 140
Реализация очереди на языке Java......Page 141
Приоритетные очереди......Page 146
Приложение The PriorityQ Workshop......Page 148
Реализация приоритетной очереди на языке Java......Page 150
Разбор арифметических выражений......Page 152
Постфиксная запись......Page 153
Как мы вычисляем результаты инфиксных выражений......Page 154
Вычисление результата постфиксного выражения......Page 170
Итоги......Page 175
Вопросы......Page 176
Программные проекты......Page 178
Строение связанного списка......Page 180
Ссылки и базовые типы......Page 181
Отношения вместо конкретных позиций......Page 182
Вставка......Page 183
Удаление......Page 184
Класс Link......Page 185
Класс LinkList......Page 186
Программа linkList.java......Page 190
Поиск и удаление заданных элементов......Page 192
Метод delete()......Page 195
Двусторонние списки......Page 196
Абстрактные типы данных......Page 200
Реализация стека на базе связанного списка......Page 201
Реализация очереди на базе связанного списка......Page 204
Типы данных и абстракция......Page 207
Списки ADT......Page 208
Сортированные списки......Page 209
Реализация вставки элемента в сортированный список на языке Java......Page 211
Программа sortedList.java......Page 212
Эффективность сортированных списков......Page 214
Сортировка методом вставки......Page 215
Двусвязные списки......Page 217
Вставка......Page 219
Удаление......Page 221
Программа doublyLinked.java......Page 222
Итераторы......Page 226
Итератор......Page 227
Другие возможности итераторов......Page 228
Методы итераторов......Page 229
Программа interIterator.java......Page 230
Итеративные операции......Page 236
Итоги......Page 238
Вопросы......Page 239
Упражнения......Page 240
Программные проекты......Page 241
Треугольные числа......Page 243
Вычисление n-го треугольного числа в цикле......Page 244
Вычисление n-го треугольного числа с применением рекурсии......Page 245
Программа triangle.java......Page 247
Что реально происходит?......Page 248
Характеристики рекурсивных методов......Page 249
Факториал......Page 250
Анаграммы......Page 252
Рекурсивный двоичный поиск......Page 257
Замена цикла рекурсией......Page 258
Ханойская башня......Page 262
Приложение Towers Workshop......Page 263
Рекурсивный алгоритм......Page 264
Программа towers.java......Page 266
Сортировка слиянием......Page 267
Слияние двух отсортированных массивов......Page 268
Сортировка слиянием......Page 270
Приложение MergeSort Workshop......Page 273
Программа mergeSort.java......Page 274
Устранение рекурсии......Page 281
Что дальше?......Page 287
Возведение числа в степень......Page 289
Задача о рюкзаке......Page 291
Комбинации и выбор команды......Page 292
Итоги......Page 294
Вопросы......Page 295
Программные проекты......Page 297
Сортировка Шелла......Page 299
N-сортировка......Page 300
Сокращение интервалов......Page 302
Приложение Shellsort Workshop......Page 303
Реализация сортировки Шелла на языке Java......Page 305
Другие интервальные последовательности......Page 307
Эффективность сортировки Шелла......Page 308
Приложение Partition Workshop......Page 309
Остановка и перестановка......Page 313
Быстрая сортировка......Page 316
Алгоритм быстрой сортировки......Page 317
Выбор опорного значения......Page 318
Приложение QuickSort1 Workshop......Page 323
Вырожденное быстродействие O(N2)......Page 327
Определение медианы по трем точкам......Page 328
Обработка малых подмассивов......Page 333
Устранение рекурсии......Page 336
Поразрядная сортировка......Page 339
Эффективность поразрядной сортировки......Page 340
Итоги......Page 341
Вопросы......Page 343
Программные проекты......Page 344
Медленная вставка в упорядоченном массиве......Page 346
Что называется деревом?......Page 347
Терминология......Page 348
Аналогия......Page 351
Приложение Binary Tree Workshop......Page 352
Представление деревьев в коде Java......Page 354
Поиск узла в приложении Workshop......Page 356
Эффективность поиска по дереву......Page 358
Реализация вставки на языке Java......Page 359
Симметричный обход......Page 361
Обход дерева из трех узлов......Page 362
Обход дерева в приложении Workshop......Page 363
Симметричный и обратный обход......Page 365
Поиск минимума и максимума......Page 367
Случай 1: Удаляемый узел не имеет потомков......Page 368
Эффективность двоичных деревьев......Page 379
Представление дерева в виде массива......Page 381
Дубликаты ключей......Page 382
Полный код программы tree.java......Page 383
Коды символов......Page 391
Декодирование по дереву Хаффмана......Page 393
Построение дерева Хаффмана......Page 394
Кодирование сообщения......Page 396
Итоги......Page 397
Вопросы......Page 399
Упражнения......Page 400
Программные проекты......Page 401
Наш подход к изложению темы......Page 403
Сбалансированные и несбалансированные деревья......Page 404
Вырождение до O(N)......Page 405
Характеристики красно-черного дерева......Page 406
Работа с приложением RBTree Workshop......Page 408
Кнопка Del......Page 409
Где кнопка Find?......Page 410
Эксперимент 1: вставка двух красных узлов......Page 411
Эксперимент 3: переключение цветов......Page 412
Эксперимент 4: несбалансированное дерево......Page 413
Красно-черные правила и сбалансированные деревья......Page 414
Повороты......Page 415
Переходящий узел......Page 416
Перемещения поддеревьев......Page 417
Общая схема процесса вставки......Page 419
Переключения цветов при перемещении вниз......Page 420
Повороты после вставки узла......Page 422
Повороты при перемещении вниз......Page 427
Удаление......Page 430
Реализация красно-черного дерева......Page 431
Другие сбалансированные деревья......Page 432
Вопросы......Page 433
Упражнения......Page 435
Знакомство с деревьями 2-3-4......Page 436
Почему деревья 2-3-4 так называются?......Page 437
Структура дерева 2-3-4......Page 438
Вставка......Page 439
Разбиение узлов......Page 440
Разбиение корневого узла......Page 441
Приложение Tree234 Workshop......Page 442
Кнопка Find......Page 443
Кнопка Zoom......Page 444
Просмотр разных узлов......Page 445
Эксперименты......Page 446
Класс Node......Page 447
Класс Tree234......Page 448
Класс Tree234App......Page 449
Полный код программы tree234.java......Page 450
Преобразование деревьев 2-3-4 в красно-черные деревья......Page 457
Эквивалентность операций......Page 459
Скорость......Page 461
Деревья 2-3......Page 462
Разбиение узлов......Page 463
Реализация......Page 465
Обращение к внешним данным......Page 466
Последовательное хранение......Page 469
B-деревья......Page 471
Индексирование......Page 476
Сложные критерии поиска......Page 478
Сортировка внешних файлов......Page 479
Итоги......Page 482
Вопросы......Page 484
Программные проекты......Page 485
Хеширование......Page 487
Индексы как ключи......Page 488
Словарь......Page 489
Хеширование......Page 492
Коллизии......Page 494
Линейное пробирование......Page 495
Реализация хеш-таблицы с линейным пробированием на языке Java......Page 500
Квадратичное пробирование......Page 507
Двойное хеширование......Page 509
Приложение HashChain Workshop......Page 517
Реализация метода цепочек на языке Java......Page 520
Хеш-функции......Page 525
Неслучайные ключи......Page 526
Хеширование строк......Page 528
Открытая адресация......Page 530
Метод цепочек......Page 532
Сравнение открытой адресации с методом цепочек......Page 534
Неполные блоки......Page 535
Полные блоки......Page 536
Итоги......Page 537
Вопросы......Page 538
Программные проекты......Page 540
Пирамиды......Page 542
Общие сведения......Page 543
Слабая упорядоченность......Page 544
Удаление......Page 545
Вставка......Page 547
Условные перестановки......Page 548
Приложение Heap Workshop......Page 549
Реализация пирамиды на языке Java......Page 550
Вставка......Page 551
Удаление......Page 552
Изменение ключа......Page 553
Программа heap.java......Page 554
Пирамидальное дерево......Page 560
Ускоренное смещение вниз......Page 562
Сортировка «на месте»......Page 564
Программа heapSort.java......Page 565
Эффективность пирамидальной сортировки......Page 569
Итоги......Page 570
Вопросы......Page 571
Программные проекты......Page 572
Знакомство с графами......Page 574
Определения......Page 575
Немного истории......Page 577
Представление графа в программе......Page 578
Добавление вершин и ребер в граф......Page 580
Класс Graph......Page 581
Обход......Page 582
Обход в глубину......Page 583
Обход в ширину......Page 592
Минимальные остовные деревья......Page 599
Реализация построения минимального остовного дерева на языке Java......Page 600
Топологическая сортировка с направленными графами......Page 604
Направленные графы......Page 605
Топологическая сортировка......Page 606
Приложение GraphD Workshop......Page 607
Циклы и деревья......Page 608
Реализация на языке Java......Page 609
Алгоритм Уоршелла......Page 615
Итоги......Page 618
Вопросы......Page 619
Программные проекты......Page 620
Пример: кабельное телевидение в джунглях......Page 622
Приложение GraphW Workshop......Page 623
Рассылка инспекторов......Page 624
Создание алгоритма......Page 628
Реализация на языке Java......Page 630
Программа mstw.java......Page 632
Задача выбора кратчайшего пути......Page 637
Железная дорога......Page 638
Агенты и поездки......Page 639
Приложение GraphDW Workshop......Page 644
Реализация на языке Java......Page 648
Программа path.java......Page 652
Поиск кратчайших путей между всеми парами вершин......Page 656
Эффективность......Page 658
Неразрешимые задачи......Page 659
Задача коммивояжера......Page 660
Итоги......Page 661
Вопросы......Page 662
Упражнения......Page 663
Программные проекты......Page 664
Структуры данных общего назначения......Page 666
Скорость и алгоритмы......Page 667
Библиотеки......Page 668
Связанные списки......Page 669
Хеш-таблицы......Page 670
Специализированные структуры данных......Page 671
Очередь......Page 672
Сортировка......Page 673
Графы......Page 674
Последовательное хранение......Page 675
Виртуальная память......Page 676
Итоги......Page 677
Приложения Workshop......Page 678
Программы командной строки......Page 679
Работа с приложениями Workshop......Page 680
Компилирование примеров......Page 681
Другие системы разработки......Page 682
Структуры данных и алгоритмы......Page 683
Объектно-ориентированное проектирование и разработка......Page 684
Ответы на вопросы......Page 686
Об авторе......Page 694