В Камаев - Технологии программирования

Операция обновления позволяет изменить значения данных в структуре данных. Примером операции обновления является операция присваивания или более сложная форма — передача параметров.

Операция копирования создает копию данных в новом месте памяти.

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

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

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

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

Пример широко известных структур данных с разной упорядоченностью приведен на рис. 4.1.

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

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

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

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

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

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

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

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