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

1. Постоянство структуры в течение всего времени ее существования.

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

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

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

Векторы

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

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

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

Над вектором также могут выполняться:

- операции определения нижней и верхней границ индекса по заданному имени вектора;

- операция, позволяющая получить описание элемента вектора (например, тип и длину).

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

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

Массивы

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

Если массив состоит из векторов, элементами которых являются простые данные (скаляры), то логическая структура такого массива может быть представлена прямоугольной матрицей, в которой любой ее элемент может быть однозначно идентифицирован указанием пары индексов, при этом первый индекс задает номер строки, а второй - номер столбца, на пересечении которых расположен элемент. Матрицу называют двумерным массивом. От двумерного массива нетрудно перейти к трехмерному массиву, в котором каждый скалярный элемент (или просто элемент массива) однозначно идентифицируется упорядоченной тройкой индексов. Формально можно определить массив произвольной конечной размерности, в котором каждый элемент однозначно определяется конечной упорядоченной последовательностью индексов, или селекторов, причем число таких индексов равно размерности массива. Из этого определения ясно, что вектор - одномерный массив. Кроме того, скалярную величину можно считать нуль-мерным массивом. Еще раз подчеркнем, что все элементы массива принадлежат одному и тому же типу данных.

Дадим еще одно формальное определение массива. Назовем k-мерным массивом, где k=1,2, ... , конечное упорядоченное множество (k-1)-мерных массивов, все элементы которых принадлежат одному и тому же типу. При k=1 получается вектор (если нуль-мерный массив считать скаляром).

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

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

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

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

Пусть задан произвольный n -мерный массив

,

в котором каждая пара величин целого типа  указывает верхнюю и нижнюю границы s-го индекса, где s=1,2, …, n ..

Пусть - произвольный элемент логической структуры вектора В. Определим функцию упорядочения в виде

,

где N – номер слота в физической структуре, соответствующий элементу .

Величина  в этом выражении зависит от способа отображения массива В. При отображении строками

а при отображении столбцами

Если длина слота равна l ячейкам памяти, то следующее выражение позволяет вычислить адрес произвольного элемента , если известен адрес первого элемента :

,

где величина  определяется в зависимости от способа отображения массива В, как описано выше.

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

Для ускорения доступа к каждому элементу массива можно заранее вычислить индексные множители  для m=1,2,…,n и запомнить их в дескрипторе массива.

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

Пример дескриптора трехмерного массива MATR(2:3,4:6,1:5) с элементами целого типа, для хранения каждого из которых отводится l=2 ячейки (байта) памяти, представлен на рис. 2.2.

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

Рис. 2.2 - Пример дескриптора трехмерного массива с элементами целого типа

Пятое поле дескриптора содержит значение размерности массива, следующие поля 6-11 – граничные значения индексов. В полях 12-14 записаны значения индексных множителей , используемых для убыстрения вычисления адреса элемента в памяти, а поле 15 содержит признак типа данных. И, наконец, последнее поле хранит значение длины слота.

Пусть начальный адрес массива MATR=1000. Тогда его элемент с индексами 2, 5, 4 будет располагаться по адресу

ADDR(MATR(2,5,4))=ADDR(MATR(2,4,1))-102+30*2+10*5+4*2=1000-102+118=1016.

Важный частный случай двумерного массива – симметричная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу. Такова, например, корреляционная матрица системы случайных величин. Если квадратная матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не , а лишь n ( n +1)/2 ее элементов, в том числе элементы главной диагонали, и, например, все элементы, расположенные над этой диагональю. Иными словами, в памяти достаточно представить лишь верхний (включая и диагональ) треугольник квадратной логической структуры, поэтому соответствующий двумерный массив часто называют треугольным массивом.

Записи

Запись - конечное упорядоченное множество элементов, характеризующихся в общем случае различным типом данных. Часто элементы записи называются также полями. Запись - такое обобщение понятия вектора (или одномерного массива), при котором не требуется однотипность, или однородность, элементов.

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

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

REC	STUDENT		7
I	2	NUM	·	ü
S	15	NANE	·	ê	Указатели значений элементов
S	3	FAC	·	ê
S	5	GROUP	·	ý
I	1	MATH	·	ê
I	1	COMP	·	ê
I	1	LANG	·	þ

Рис. 2.3 - Дескриптор записи с именем STUDENT, содержащий 7 полей. (REC - признак дескриптора записи, S -признак строки символов, I признак целого числа)

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

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

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

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

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

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

Таблицы

Таблица - конечное множество записей, имеющих одну и ту же организацию. Каждая запись, входящая в таблицу, называется элементом таблицы. Наиболее распространена форма таблицы, в которой элемент представляет собой одноуровневую запись, т.е. запись, состоящую из упорядоченной последовательности полей, имеющих в общем случае различный размер и соответствующих различным типам простых данных. При этом логическая структура таблицы обычно изображается в виде последовательности расположенных друг над другом строчек одинаковой длины, представляющих элементы таблицы и разделенных на графы. Каждая графа соответствует определенному полю элемента таблицы. Следовательно, в изображении логической структуры таблицы соответствующие поля ее элементов располагаются в одной графе и, по определению, предназначаются для представления данных одного и того же типа, в общем случае различного для разных граф. Обычно одно из полей всех элементов таблицы отводится для хранения ключа, являющегося уникальным для каждого элемента и используемого при доступе к соответствующему элементу. Поэтому таблицу иногда определяют в виде списка пар (K,V), где K -поле ключа; а V -упорядоченный набор полей, предназначенных для хранения любой другой информации. В некоторых случаях возникает необходимость применять таблицы с несколькими ключами.

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

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

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