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

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

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

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

Рис. 4.1. Примеры широко известных структур данных

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

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

Физическое представление динамических переменных в памяти — это обычно последовательное, как и у статических структур, размещение значений элементов в памяти.

Динамические переменные размещаются в динамически распределяемой области памяти (ДРП). Область ДРП находится вне области кода программы. В зарубежных источниках ДРП обозначается термином "heap" — куча. Обычно заполнение области ДРП осуществляется при помощи стандартных процедур диспетчирования ДРП.

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

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

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

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

— информационного поля, или поля данных, в котором содержатся те данные (в том числе и интегрированные), ради которых оно и создается;

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

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