Классические структуры данных: массивы, списки, деревья

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

Связанные списки имеют два преимущества перед массивами:

- они динамично могут изменять свои размеры,

- позволяют легко реорганизовать порядок элементов, добавлять и удалять элементы, путем редактирования небольшого числа ссылок.

Существует несколько видов связанных списков, в зависимости от ссылок: односвязные, двухсвязные, кольцевые.

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

Деревья одна из наиболее распространенных динамических структур в вычислительных алгоритмах. Деревья впервые появились для манипуляции с формулами при развитии компиляторов в 1951, 1952-54гг. Первый обзор был сделан в 1961 г. в Исследовательском отчете корпорации IBM.

Определим дерево, как конечное множество Т, которое либо пусто, либо в нем имеется один специально обозначенный узел, называемый корнем, а все остальные узлы содержатся в непересекающихся множествах T₁, T₂,..., T_m, каждое из которых является деревом. Деревья T₁, T₂,..., T_m называют поддеревьями данного корня.