Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Представление данных
Структура данных
· Структура данных связана с присутствием различных компонент, различными отношениями между ними, порядком следования компонент, установленных отношением.
· Структуру данных можно определить как множество компонент и отношений между ними, задающих порядок подчинённости и связи компонент.
· Если множество компонент полностью определено и конечно, то структура называется абсолютной или финитной.
· Все структуры данных могут быть разделены на иерархические, неиерархические и смешанные.
· В иерархических структурах каждая компонента является либо главной, определяющей, либо зависимой, подчинённой. Любая зависимая компонента связана только с одной операцией.
· Иерархическую структуру, у которой хотя бы одна компонента является одновременно и главной и зависимой по отношению к некоторым другим компонентам, называют многоуровневой.
· Порядок следования компонет определяется множеством иерархических отношений между ними, т.е. порядок подчинения.
· В неиерархических структурах любая зависимая компонента непосредственно связана с несколькими главными компонентами. В них не существует только зависимых или только определяющих компонент.
· Смешанные структуры являются комбинацией иерархических и неиерархических структур.
Иерархические структуры
· Иерархические структуры данных и связи между ними отображаются в виде схем, называющихся деревьями.
· Дерево представляет собой иерархию элементов, называемых узлами.
· На самом верхнем ее уровне имеется только один главный узел — корень дерева.
· Любой узел, кроме корня, связан с одним узлом на более высоком уровне. Этот узел называется исходным.
· Ни один узел не имеет более одного исходного. Любой рассмотренный узел может быть связан с одним или несколькими элементами на более низком уровне. Эти элементы называются порожденными.
