Структуры данных. Назовем структурой данных совокупность элементов данных, между которыми существуют некоторые отношения

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

S=(D,R),

где D—множество элементов данных;R—множество отношений между элементами данных.

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

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

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

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

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

Выше обобщенная структура данных рассматривалась без учета ее представления в машинной памяти. Такая структура данных называется абстрактной или логической. Однако ЭВМ может обрабатывать только такую структуру данных, которая тем или иным способом представлена в машинной памяти. Такая структура данных называется физической структурой, структурой хранения, внутренней структурой или структурой памяти. Таким образом, понятие «физическая структура данных» отражает способ физического представления данных в машинной памяти. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той физической среды, в которой она должна быть отражена. Например, с точки зрения пользователя языка ФОРТРАН двумерный массив—это прямоугольная таблица, содержащая определенное число строк и столбцов. Но в машинной памяти этот массив представляется линейной последовательностью ячеек, в каждой из которых хранится значение одного элемента массива, причем элементы массива в памяти ЭВМ упорядочены по столбцам. Это означает, что в памяти в начале линейной последовательности ячеек, хранящих массив, располагаются элементы первого столбца логической структуры массива, за ним—элементы второго столбца и т. д.

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

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

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

Структуры данных могут быть классифицированы по нескольким признакам.

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

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

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

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

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