Конспект "Структуры данных: графы, деревья, таблицы"

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

Граф

Элементарное описание структуры системы и ее связей.

Составными частями неориентированного графа являются вершины и ребра. Здесь вершины изображены кружками, обозначающие элементы системы, а ребра — линиями, показывающими симметричные связи (отношения) между элементами.

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

  

Также графы еще называют сетями.

Сеть

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

Дерево

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

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

Таблицы

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

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

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

Важной разновидностью таблиц типа «объект-объект» являются двоичные матрицы. Они отображают качественную связь между объектами – есть связь или нет связи. Единица – изучаемый предмет, а ноль – не изучаемый предмет.

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