Open Library - открытая библиотека учебной информации

Открытая библиотека для школьников и студентов. Лекции, конспекты и учебные материалы по всем научным направлениям.

Категории

Изобретательство Нелинейные структуры данных
просмотров - 249

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

Отношения «один ко многим» носят иерархических характер и отображаются древовидными структурами (рис.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, то данный узел является висячим.

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

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

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

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


Читайте также


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

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


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

    Глава 10. Объектно-ориентированное программирование 166 10.1. Объекты. Основные понятия 166 10.2. Наследование и переопределение 168 10.3. Виртуальные методы 171 10.4. Конструкторы и деструкторы. Динамические объекты 172 10.5. Классы 173 Приложение А. 176 Коды клавиш ПК 176 Расширенные... [читать подробенее]