Структуры и алгоритмы обработки данных, часть 3

7.  Расскажите о представлении линейных структур данных в ЭВМ

   Наиболее простой формой хранения данных в памяти ЭВМ является одномерный линейный список. Линейный список-это множество n>=0 объектов (узлов) Х(1), Х(2), Х(3)... Х(n) структурные свойства которого связаны только с линейным (одномерным) относительным расположением узлов. Если n>0, то X(1) является первым узлом; для 1<i<n узел X(i-1) предшествует узлу X(i), а узел X(i+1) следует за ним, X(n) является последним узлом, т. е. линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных.

  Линейный список X рассматривают как последовательность Х(1), Х(2), Х(3)... Х(n) компоненты которой идентифициро­ваны порядковым номером, указывающим их относительное расположение в X.

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

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

    При реализации адресной функции используют два основных метода: последовательное распределение памяти; связанное распределение памяти.

8. Расскажите о представлении нелинейных структур данных в ЭВМ

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

  Отношения "многие-ко-многим" носят более универсальный характер и отображается структурами графов. Пример такого отношения. Каждый ВУЗ распределяет своих выпускников на различные предприятия. В то же время предприятие поучает специалистов из различных ВУЗов.

     Граф общего вида состоит из ряда вершин (узлов) и ребер, связывающих пары вершин. Если в понятия "ребро" и "вершина" вложить определенную смысловую нагрузку, то графы можно использовать для представления данных. Так вершинам графа можно сопоставить определенные объекты, тогда ребра будут соответствовать отношениям между объектами. В литературе по структурам баз данных модель данных, имеющую вид ориентированного графа, называют сетью.

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