<<
>>

Структуры данных

В наиболее общем понимании данными считаются все факты и идеи, представленные в формализованном виде, позволяющем их передавать и обрабатывать с помощью некоторых процессов и соответствующих технических средств.
В более узком понимании данными можно считать любой набор знаков, независимо от их смысла. Во введении указывалось, что количество информации измеряется в битах. Применительно к данным используются также термины: символ, слово, запись и файл. Символ представляет собой любой знак, допустимый в избранном алфавите, и занимает несколько бит (обычно один байт). Слово состоит из нескольких символов, длина слова ограничивается разрядностью компьютера и составляет обычно 2 - 8 байт. Запись состоит из нескольких слов. Записью, например, может быть информация на перфокарте, строка на экране дисплея или на бумаге. Файл (file - досье, картотека) - это рассматриваемый как единое целое поименованный набор однотипных по структуре и использованию записей.

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

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

286


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

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

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

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

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

Стек функционирует по принципу «последним пришел - первым ушел», при этом удаление элементов производится со входного конца (рис. 8.1, б). При добавлении в стек нового элемента данных все ранее загруженные элементы сдвигаются на одну позицию в глубину стека, а при удалении элемента данных сдвиг производится на одну позицию ко входу в стек. По такому принципу используется, например, стопка бумаги (листы добавляются и удаля


287


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


Рис. 8.1. Очередь (а) и стек (б): г - вход, о - выход

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

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


288


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


Рис. 8.2. Списки: а — однонаправленный; б - двунаправленный; в - кольцевой; г - иерархический; Ь, Ьь Ь2 - заголовки списков; информационное поле заштриховано

К нелинейным структурам данных относятся графы, деревья, сплетения и сети фреймов. Граф - конечное множество точек (вершин) и отрезков линий, каждый из которых соединяет две вершины и называется ребром. Если на ребре указано направление (стрелкой), то это ориентированное ребро или дуга. Граф, содержащий только ребра, называется неориентированным (рис. 8.3, а); граф, содержащий только дуги, - ориентированным (рис. 8.3, б).

289



Рис. 8.3. Графы: а - неориентированный; б - ориентированный

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

Деревом называется связный неориентированный граф, не содержащий циклов, в том числе петель (рис. 8.4, а).

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


290


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


Рис. 8.4. Деревья: а - дерево; б - растущее дерево с корнем т0;

1, 2, ..., 6 - уровни вершин; в - поддерево растущего дерева


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

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

Однако кроме уровня фреймов, назначение которого - указание понятий предметной области и их связей, фрейм имеет более глу-


291


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

На рис. 8.5 показана типичная структура фрейма с пятью уровнями. За уровнем фреймов (1) следует уровень слотов (2).



Рис. 8.5. Структура фрейма: 1 - уровень фреймов; 2 - уровень слотов;

3 - уровень фасетов; 4 - уровень данных; 5 - уровень комментариев


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

Под уровнем слотов располагается уровень фасетов (3). Фасеты позволяют задавать модификации свойств, описываемых слотами. Такими модификациями могут быть:

1) явное задание характеристики;

2) задание характеристики по умолчанию;

3) действия при добавлении данных;

4) действия при удалении данных.

292



Из этих четырех фасетов, показанных на рис. 8.5, первые два фасета указывают способ задания описательной части слота.

Например, для фрейма «болт» характеристика «тип» по умолчанию может иметь значение «крепежный», а явно заданная - «установочный»; характеристика «материал» по умолчанию - «сталь», а явно заданная - «бронза» и т.д. Третий и четвертый фасеты составляют процедурную часть слота: они указывают, какие действия и где следует выполнить при изменениях описательной части слота для сохранения непротиворечивости всей сети данных.

Под уровнем фасетов размещается уровень собственно данных (4), на котором хранятся фактические данные, идентификаторы процедур и т.п. В качестве иллюстрации рассмотрим два примера:

1) имя фрейма - болт; 2) имя фрейма - болт;

имя слота - материал; имя слота - покрытие;

фасет - значение по умолчанию; фасет - явное задание;

значение данного - сталь. значение данного - хромированный.

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

8.2.

<< | >>

Еще по теме Структуры данных:

  1. Григорьев Ю.А., Ревунков Г.И.. Банки данных, 2002
  2. Оценка данных о личности.
  3. 18.4. Права субъекта персональных данных
  4. Банк данных
  5. 5.3. Графическое представление данных
  6. Анализ и интерпретация полученных данных
  7. Анализ и интерпретация полученных данных
  8. Подготовка исходных данных
  9. 4.5. Право изготовителя базы данных
  10. 12.4. Анализ эмпирических данных
  11. 3.3.4. Методы обработки и анализа данных
  12. 5.1. Табличное представление данных
  13. 18.7. Уполномоченный по правам субъектов персональных данных
  14. 3.3.2. Обоснование методов сбора эмпирических данных
  15. Глава 9 Создание экспертной базы данных
  16. 2. Регистрация программ, баз данных и охраняемых топологий
  17. 4.1. Общие принципы анализа данных
  18. Практическое использование виктимологических данных.