Технологии программирования
Шрифт:
Операция выбора используется программистами для доступа к данным внутри самой структуры. Форма операции доступа зависит от типа структуры данных, к которой осуществляется обращение. При выполнении операций выбора используются указатели. В широком смысле слова указатель — это переменная, определяющая место конкретной информации в структуре данных, например, переменная, содержащая значение индекса статического массива. В узком смысле слова указатель указывает на физический адрес чего-то. В последнем случае указатель — это переменная, которая является носителем адреса другой простой или структурированной переменной, а также процедуры.
Операция обновления позволяет изменить значения данных в структуре данных. Примером операции обновления является операция присваивания или более сложная форма — передача параметров.
Операция копирования создает копию данных в новом месте памяти.
Вышеуказанные пять операций обязательны для всех структур и типов данных. Помимо этих общих операций для каждой структуры данных могут быть определены операции специфические, работающие только с данными указанного типа (данной структуры).
4.3. ОБЩАЯ КЛАССИФИКАЦИЯ ЛОГИЧЕСКИХ СТРУКТУР ДАННЫХ
Упорядоченность элементов структуры данных является важным ее признаком.
Программисты могут по своему усмотрению упорядочить данные разных программ бесчисленным множеством способов. Даже в одной и той же структуре данных программист может по-разному разместить одну и ту же информацию. Так, в списке студентов фамилия может предшествовать имени и отчеству и, наоборот, имя и отчество могут предшествовать фамилии. Максимальный элемент в отсортированном массиве может быть как первым, так и последним. Поэтому характер упорядоченности элементов структуры, определенный программистом, необходимо комментировать с той или иной тщательностью, определяемой здравым смыслом и мнемоникой имен.
Существует бесконечное множество способов упорядочения информации, но среди них имеются и общие, наиболее часто встречаемые и известные большинству программистов.
Пример широко известных структур данных с разной упорядоченностью приведен на рис. 4.1.
Структуры по признаку характера упорядоченности их элементов можно делить на линейные и нелинейные. Примеры линейных структур — массивы, строки, стеки, очереди, линейные одно- и двухсвязные списки. Примеры нелинейных структур — многосвязные списки, деревья, графы.
Простые и интегрированные структуры данных. Простые — это встроенные, стандартные, базовые, примитивные структуры данных, интегрированные — структурированные, производные, композитные, сложные структуры данных. Интегрированные структуры данных обычно относят к типам данных, определяемых программистом.
Простые структуры не могут быть расчленены на составные части, большие, чем биты и байты. С точки зрения физической структуры, важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования всегда можно заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами. В языках программирования простые структуры описываются простыми (базовыми) типами. Простые структуры данных служат основой для построения более сложных интегрированных структур.
Интегрированными называют такие структуры данных, составными частями которых являются другие структуры данных — простые или, в свою очередь,
Изменчивость структур данных также является весьма важным признаком. Изменчивость — изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры статические и динамические.
Рис. 4.1. Примеры широко известных структур данных
Поскольку по определению статические структуры отличаются отсутствием изменчивости, память для них выделяется автоматически, — как правило, на этапе компиляции или при выполнении — в момент активизации того программного блока, в котором они описаны. Выделение памяти на этапе компиляции является столь удобным свойством статических структур, что в ряде задач программисты используют их даже для представления объектов, обладающих изменчивостью. Например, когда размер массива неизвестен заранее, для него резервируется максимально возможный размер.
В ряде языков программирования наряду со статическими переменными могут использоваться динамические переменные. Динамическая переменная — это как бы статическая переменная, но размещаемая в особой области памяти вне кода программы. В любой момент времени память для размещения динамических переменных может как выделяться, так и освобождаться. Следует отметить, что память для размещения динамической переменной выделяется по команде программы сразу в заранее указанном объеме и далее не может быть изменена, т. е. структуры данных, построенные на использовании динамических переменных, имеют ту же логическую структуру и обладают такой же самой изменчивостью, как и статические структуры данных. Поэтому далее динамические переменные будем относить к статическим структурам данных.
Физическое представление динамических переменных в памяти — это обычно последовательное, как и у статических структур, размещение значений элементов в памяти.
Динамические переменные размещаются в динамически распределяемой области памяти (ДРП). Область ДРП находится вне области кода программы. В зарубежных источниках ДРП обозначается термином "heap" — куча. Обычно заполнение области ДРП осуществляется при помощи стандартных процедур диспетчирования ДРП.
Связные динамические структуры данных. Связность — особое продуманное логическое устройство сохранения целостности структуры данных, элементы которой могут находиться в произвольных, несмежных, неконтролируемых по адресации участках ДРП.
Конечно, динамические структуры данных создаются с использованием динамических переменных, но их логическое устройство такое, что до выполнения процедур доступа в программе нет переменных, значения которых соответствуют значениям элементов динамической структуры.
Динамические связные структуры, или динамические структуры, по определению характеризуются отсутствием физической смежности элементов структуры в памяти, непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.