Классификация структур данных

С понятием структуры данных тесно связано понятие типа данных.

Различают физическую и логическую структуры данных. Физическая структура в отличие от логической отражает способ представления данных в памяти компьютера и называется еще

внутренней.

По составу различаются простые структуры (типы) данных и интегрированные (сложные). Простые структуры не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры для простого типа четко определен его размер и способ размещения в памяти компьютера. С точки зрения логической структуры простые структуры являются неделимыми единицами. Интегрированные структуры данных включают в себя другие структуры данных — простые или интегрированные.

Между отдельными элементами структур могут наличествовать или отсутствовать явно заданные связи. В зависимости от этого следует различать: несвязные структуры (векторы, массивы,

строки, стеки, очереди) и связные структуры (связные списки).

По признаку изменчивости различают структуры статические, полустатические, динамические. Под изменчивостью понимают изменение числа элементов структуры или связей между этими элементами. Классификация структур данных по признаку изменчивости приведена на рис. 3.1.

По признаку упорядоченности элементов структуры можно делить на линейные и нелинейные. Пример нелинейных структур — многосвязные списки, деревья, графы.

Линейные структуры, в свою очередь, делятся на структуры с последовательным распределением (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением (односвязные, двусвязные списки) по характеру распределения элементов в памяти.

Указание типа данных четко определяет:

• размер памяти, отведенной под данную структуру и способ

ее размещения в памяти;

• значения, допустимые для данного типа данных;

• операции, которые возможно над этими данными выполнять.