Нелинейные структуры данных

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

Отношения «один ко многим» носят иерархических характер и отображаются древовидными структурами (рис.2.6.9). В виде иерархии может быть, например, структура «компания – предприятие - цех – участок».

Рис. 2.6.9. Древовидные структуры

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

Рис. 2.6.10. Графовые структуры

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

7 запись 1

запись 2

4 6

запись 3

2 3 5.

1 запись 7

восходящий обход

Рис. 2.6.11. Двоичное дерево и его размещение в блоке памяти компьютера.

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

Для включения или исключения записей в структуре необходима перестройка дерева и массива.

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

Двоичное дерево отображается в памяти компьютера двухсвязным списком, оба указателя которого ведут в прямом направлении. Формат списка (рис. 2.6.12) состоит из информационного поля (DATA) и двух полей (LPTR и RPTR), содержащих левый и правый указатели соответственно.

LPTR DATA RPTR

Рис. 2.6.12. Формат элемента двухсвязанного списка.

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

Часто при построении деревьев принимают, что левый указатель задает направление к записи с меньшим значением ключа, а правый указатель - с большим. Такое дерево и структура его хранения изображены на рис. 2.6.13, откуда видно, что структура хранения дерева очень схожа с его логической структурой. Любой указатель может принимать значение nil. означающее, что

15 31

13 21 25 35

а)

17 28

15 31

13 21 25 35

nil nil nil nil nil nil

17 28

nil nil nil nil

б)

Рис. 2.6.13. Двоичное дерево и структура его хранения в виде двусвязного списка.

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

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

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

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

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

Дата добавления: 2014-10-17