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

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

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

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

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

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

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

Важным признаком структуры данных является ее изменчивость: изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражено свойство изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры статические, полустатические, динамические. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти. На рис. 1 приведена классификация структур данных.

		Структуры данных
Простые базовые структуры	Статические структуры	Полустатические структуры	Динамические структуры	Файловые структуры
Числовые; Символьные; Логические; Перечисление; Интервал; Указатели.	Векторы; Массивы; Множества; Записи; Таблицы.	Стеки; Очереди; Деки; Строки.	Линейные связанные списки; Разветвленные связанные списки; Деревья; Графы.	Последователь-ного, Прямого; Комбинирован­ного доступа; Организован­ные разделами; индексированные

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

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

В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Информация по каждому типу однозначно определяет:

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

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

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

Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурированное множество примитивных, базовых, структур. Например, вектор может быть представлен упорядоченным множеством чисел. Поскольку по определению статические структуры отличаются отсутствием изменчивости, память для них выделяется автоматически, как правило, на этапе компиляции или при выполнении в момент активизации того программного блока, в котором они описаны. Выделение памяти на этапе компиляции является столь удобным свойством статических структур, что в ряде задач программисты используют их даже для представления объектов, обладающих изменчивостью. Например, когда размер массива неизвестен заранее, для него резервируется максимально возможный размер.

Каждую структуру данных характеризуют её логическим и физическим представлениями. Очень часто говоря о той или иной структуре данных, имеют в виду её логическое представление. Физическое представление обычно не соответствует логическому, и, кроме того, может существенно различаться в разных программных системах. Нередко физической структуре ставится в соответствие дескриптор или заголовок, который содержит общие сведения о физической структуре. Дескриптор, как и сама физическая структура, хранится в памяти. Дескриптор структуры данных, поддерживаемый языками программирования, является «невидимым» для программиста; он создается компилятором и компилятор же, формируя объектные коды для доступа к структуре, включает в эти коды команды, обращающиеся к дескриптору.

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

Дата добавления: 2015-07-16