Лекции по Вычислительным машинам   

4. Структуры данных и структурированная память

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

Возникающий идентификатор вида или , где i пробегает целые числа от т до п, идентифицирует упорядоченный набор данных, называемый обычно одномерным массивом. Двухиндексный идентификатор вида или идентифицирует двумерный массив, трехиндексный — трехмерный массив и т. д. В упорядоченных таким образом массивах возникает естественное отношение следования: так, следующим по индексу j для элемента будет элемент , а предыдущим — элемент . Если индекс j пробегает значения от р до q, то для р не существует предыдущего, а для q – следующего значения индекса.

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

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

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

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

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



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.