Используя указатели или их аналоги, из базовых структур данных можно строить более сложные.
*Линейные* структуры данных представляют собой одноуровневое соединение однородных элементов.
Примеры:
* двусвязный список (``list``);
* массив переменного (``vector``) или фиксированного размера (``array``).
*Нелинейные* структуры данных представляют собой многоуровневое соединение неоднородных элементов.
Примеры:
* матрица в С может быть реализована как массив указателей на строки (массивы чисел);
* множество (set) в C++ реализуется как бинарное дерево.
Замечания:
1. Матрица фиксированного размера может быть реализована и как одномерный массив, т.е. как линейная структура данных.
2. Хотя множество реализуется через нелинейную структуру данных, но с точки зрения АТД является линейной (одномерной).
3. Очередь с приоритетами является линейной с точки зрения АТД, для эффективности реализуется как бинарное дерево, то есть как нелинейная структура данных, но из-за свойств этого дерева его можно эффективно разместить на массиве переменного размера (``vector``), который является линейной структурой данных.
Начало
Учебные материалы
Структуры данных