Структуры данных

Используя указатели или их аналоги, из базовых структур данных можно строить более сложные.

Линейные структуры данных представляют собой одноуровневое соединение однородных элементов.

Примеры:

• двусвязный список (list);
• массив переменного (vector) или фиксированного размера (array).

Нелинейные структуры данных представляют собой многоуровневое соединение неоднородных элементов.

Примеры:

• матрица в С может быть реализована как массив указателей на строки (массивы чисел);
• множество (set) в C++ реализуется как бинарное дерево.

Замечания:

1. Матрица фиксированного размера может быть реализована и как одномерный массив, т.е. как линейная структура данных.
2. Хотя множество реализуется через нелинейную структуру данных, но с точки зрения АТД является линейной (одномерной).
3. Очередь с приоритетами является линейной с точки зрения АТД, для эффективности реализуется как бинарное дерево, то есть как нелинейная структура данных, но из-за свойств этого дерева его можно эффективно разместить на массиве переменного размера (vector), который является линейной структурой данных.