Речь пойдет про структуры данных, используемых для представления специализированных типов объектов, таких как точки, строки или графы

Специализированные структуры данных

Принципы создания этих структур данных те же, что и для основных типов структур: имеется набор основных многократно исполняемых операций, и нам нужна структура данных, позволяющая очень эффективное исполнение этих операций. Такие специализированные структуры данных весьма важны для создания высокопроизводительных алгоритмов работы с графами и геометрическими объектами, поэтому нужно знать об их существовании. Далее приводится краткое описание нескольких таких специализированных структур данных.

• Строки. Строки обычно представляются в виде массивов символов с использованием специального символа для обозначения конца строки. Примером таких структур данных является суффиксное дерево/массив, в котором выполняется предварительная обработка строк для ускорения операции поиска подстрок.

• Геометрические структуры данных. Геометрические данные обычно представляют собой коллекцию точек и областей данных. Плоскость можно представить в виде многоугольника с границей, состоя- щей из замкнутой цепочки отрезков. Многоугольник Р можно представить с помощью массива точек $(v_1, ... , v_n, v_1)$ , где $(v_i, v_{i+1})$ является сегментом границы многоугольника Р.

• Графы. Графы обычно представляются посредством матриц или списков смежных вершин графа. Выбор конкретного типа представления может существенно повлиять на структуру конечных алгоритмов для работы с графом, см структуры данных для графов.

• Множества. Подмножества элементов - для обеспечения быстроты поиска - обычно представляются посредством словаря. Кроме того, могут использоваться двоичные векторы, которые представляют собой булевы массивы, в которых установленный (имеющий значение 1) i-й бит означает, что і является членом подмножества.

Литература

[ Скиена 2022 с. 126]