Название: Усовершенствованные структуры данных
Автор: Петер Брасс
Издательство: ДМК Пресс
Год: 2023
Страниц: 428
Язык: русский
Формат: pdf
Размер: 11.9 MB

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

Структуры данных впервые рассматриваются не просто как вспомогательный материал для иллюстрации методологии объектно ориентированного программирования, а как ключевой вопрос разработки алгоритмов. Многочисленные примеры кода на языке C и более 500 ссылок на первоисточники делают книгу исключительно ценной.

Сегодня нет недостатка в книгах, в названии которых есть словосочетание «структуры данных», но они лишь поверхностно касаются этой темы, затрагивая только простейшие структуры – стек, очередь и некоторые виды выровненных деревьев поиска с изрядным количеством пафоса (handwaving). В последнее время были подробно изучены строковые структуры данных, востребованные в первую очередь приложениями биоинформатики. Не иссякает поток публикаций по теории структур данных для вычислительной геометрии и комбинаторики. Однако во многих учебниках структуры данных рассматриваются только как примеры для объектно ориентированного программирования, исключая их важнейший алгоритмический аспект – как реализовать нетривиальные структуры данных, не выходя при этом за пределы худших оценок вычислительной сложности. Цель этой книги – сосредоточиться на структуре данных как основе любого алгоритма.