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

Структура данных – способ представления информации.

Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними.

Понятие «физическаяструктура данных» отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.

Различаются простые структуры (типы) данных и интегрированные (структурированные, сложные).

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

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

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

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

По признаку изменчивости различают структуры статические, полустатические и динамические.

Классификация структур данных по признаку изменчивости приведена на рис. 1.:

Рис. 1

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

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

В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.

Информация по каждому типу однозначно определяет:

1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, и интерпретирование двоичного представления;

2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

3) множество допустимых операций, которые применимы к объекту описываемого типа.