Читать фрагмент

книга

Усовершенствованные структуры данных

В книге приводится всесторонний анализ идей и деталей реализации структур данных как важнейшей составляющей прикладных алгоритмов. Обсуждаются не только эффективные способы реализации операций над множествами чисел, интервалов или строк, представленных в виде различных поисковых структур данных – деревьев, множеств интервалов, кусочно-постоянных функций, прямоугольных областей, непересекающихся подмножеств, куч, хеш-таблиц, но и динамизация и персистентность (сохраняемость) структур.Структуры данных впервые рассматриваются не просто как вспомогательный материал для иллюстрации методологии объектно-ориентированного программирования, а как ключевой вопрос разработки алгоритмов. Многочисленные примеры кода на языке C и более 500 ссылок на первоисточники делают книгу исключительно ценной.

Форматы: PDF

Издательство: ДМК Пресс

Год: 2023

Место издания: Москва

ISBN: 978-5-97060-873-9 (рус.). – ISBN 978-0-52188-037-4 (англ.)

Страниц: 428

Артикул: 108092

Возрастная маркировка: 16+

Электронная книга

1999 ₽

Купить и скачать

Содержание

Содержание книги "Усовершенствованные структуры данных "

От авторов перевода

Предисловие

Основные понятия

Примеры кода

Глава 1. Элементарные структуры

1.1. Стек

1.2. Очередь

1.3. Двусторонняя очередь

1.4. Динамическое выделение памяти для элементов

1.5. Теневые копии структур в массиве

Глава 2. Деревья поиска

2.1. Две модели деревьев поиска

2.2. Общие свойства и преобразования

2.3. Высота дерева поиска

2.4. Основные операции: поиск, добавление, удаление

2.5. Возврат от листа к корню

2.6. Повторяющиеся ключи

2.7. Интервалы ключей

2.8. Построение оптимальных деревьев поиска

2.9. Преобразование деревьев в списки

2.10. Удаление деревьев

Глава 3. Выровненные деревья поиска

3.1. Выровненные по высоте деревья

3.2. Выровненные по весу деревья

3.3. (a, b)- и B-деревья

3.4. Красно-черные деревья и деревья почти оптимальной высоты

3.5. Нисходящее выравнивание красно-черных деревьев

3.6. Деревья с постоянным временем обновления в заранее известном месте

3.7. Пальцевые деревья и поуровневое связывание

3.8. Деревья с частичной перестройкой: средняя оценка сложности

3.9. Дерево с всплывающими узлами: изменяемая структура данных

3.10. Списки с пропуском элементов: вероятностные структуры данных

3.11. Соединение и разделение выровненных деревьев поиска

Глава 4. Древовидные структуры на множестве интервалов

4.1. Деревья пересекающихся отрезков

4.2. Деревья полуоткрытых интервалов

4.3. Деревья объединения интервалов

4.4. Деревья сумм взвешенных интервалов

4.5. Деревья поиска интервалов с ограниченной максимальной суммой весов

4.6. Деревья прямоугольных областей

4.7. Деревья многомерных интервалов

4.8. Блочные структуры данных

4.9. Подсчет точек и модель полугруппы

4.10. kd-деревья и связанные с ними структуры

Глава 5. Кучи

5.1. Куча как выровненное дерево

5.2. Куча в массиве

5.3. Куча как упорядоченное и полуупорядоченное дерево

5.4. Левосторонние кучи

5.5. Косые кучи

5.6. Двоичные кучи

5.7. Изменение ключей в кучах

5.8. Кучи Фибоначчи

5.9. Кучи оптимальной сложности

5.10. Двусторонние и многомерные кучи

5.11. Связанные с кучей и постоянным временем обновления структуры

Глава 6. Системы непересекающихся множеств и связанные с ними структуры

6.1. Непересекающиеся множества: объединение классов разделов

6.2. Система непересекающихся множеств с поддержкой копирования и динамическими деревьями интервалов

6.3. Разделение списка

6.4. Проблемы ориентированных корневых деревьев

6.5. Поддержание линейного порядка

Глава 7. Преобразования структуры данных

7.1. Создание динамических структур

7.2. Динамические структуры с сохранением истории

Глава 8. Структуры данных для строк

8.1. Проверки и сжимаемые проверки

8.2. Словари, допускающие появление ошибок в запросах

8.3. Суффиксные деревья

8.4. Суффиксные массивы

Глава 9. Хеш-таблицы

9.1. Основные хеш-таблицы и разрешение конфликтов

9.2. Универсальные семейства хеш-функций

9.3. Идеальные хеш-функции

9.4. Хеш-деревья

9.5. Расширяемое хеширование

9.6. Проверка принадлежности ключей и фильтры Блума

Глава 10. Приложение

10.1. Ссылочная машина и другие модели вычислений

10.2. Модели внешней памяти и алгоритмы без учета кеш-памяти

10.3. Названия структур данных

10.4. Решение линейных рекуррентных соотношений

10.5. Медленно растущие функции

Глава 11. Список публикаций

Предметный указатель

Внимание!
При обнаружении неточностей или ошибок в описании книги "Усовершенствованные структуры данных (автор Петер Брасс)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!