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

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

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

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

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

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

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

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

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

По признаку изменчивости различают структуры статические, полустатические, динамические. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

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

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

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

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

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

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

При описании и конструировании структур данных будет использоваться язык Паскаль. Язык был создан Н.Виртом для иллюстрации структур данных и алгоритмов и традиционно используется для этих целей.