Простейшие статические структуры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В ряде существующих языков программирования высокого уровня имеются развитые средства для организации и обработки таблиц.

Таблица — весьма распространенная структура данных в большинстве программно-информационных систем. Их широко используют в компиляторах и ассемблерах.

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

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

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

Рассмотренные выше структуры (векторы, массивы, записи и таблицы) характеризуются следующими свойствами:

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

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

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

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