Урок 3
Структура информации (простые структуры). Деревья. Графы
§4. Структура информации
Содержание урока
Зачем структурировать информацию?
Иерархия (дерево)
Практическая работа № 1 «Оформление документа»
Практическая работа № 2 «Структуризация информации (таблица, списки)»
Практическая работа № 3 «Структуризация информации (деревья)»
Практическая работа № 4 «Графы»
Иерархия (дерево)
Линейных списков и таблиц иногда недостаточно для того, чтобы представить все связи между элементами. Например, в некоторой фирме есть директор, ему подчиняются главный инженер и главный бухгалтер, у каждого из них есть свои подчинённые. Если мы захотим нарисовать схему управления этой фирмы, она получится многоуровневой (рис. 1.11, а).
Такая структура, в которой одни элементы «подчиняются» другим, называется иерархией (от древнегреческого fepap%ta — священное правление). В информатике иерархическую структуру называют деревом. Дело в том, что, если перевернуть схему на рис. 1.11 вверх ногами, она становится похожа на дерево (точнее, на куст, см. рис. 1.11, б).
Рис. 1.11
Дерево состоит из узлов и связей между ними (они называются дугами). Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка-дуга), — это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев, — промежуточные.
Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.
Используются также понятия предок и потомок. Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.
В дереве на рис. 1.12 родитель узла Е — это узел В, а предки узла Е — это узлы А я В, для которых узел Е — потомок. Потомками узла А (корня) являются все остальные узлы.
Рис. 1.12
Типичный пример иерархии — различные классификации (животных, растений, минералов, химических соединений). Например, отряд Хищные делится на два подотряда: Псообразные и Кошкообразные. В каждом из них выделяют несколько семейств (рис. 1.13).
Рис. 1.13
Конечно, на рис. 1.13 показаны не все семейства, остальные обозначены многоточиями.
В текстах иерархию часто представляют в виде многоуровневого списка. Например, оглавление книги о хищниках может выглядеть так:
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
...
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
...
Работая с файлами и папками, мы тоже встречаемся с иерархией: классическая файловая система имеет древовидную структуру 1. Вход в папку — это переход на следующий (более низкий) уровень иерархии (рис. 1.14).
1 В современных файловых системах (NTFS, ext3) файл может «принад¬лежать» нескольким каталогам одновременно. При этом древовидная структура, строго говоря, нарушается.
Рис. 1.14
Алгоритм вычисления арифметического выражения тоже может быть представлен в виде дерева (рис. 1.15).
(а + 3) * 5 - 2 * b
Рис. 1.15
Здесь листья — это числа и переменные, тогда как корень и промежуточные вершины — знаки операций. Вычисления идут «снизу вверх», от листьев — к корню. Показанное дерево можно записать так:
(-(*(+ (а,3),5),*(2,b)))
Самое интересное, что скобки здесь необязательны; если их убрать, то выражение всё равно может быть однозначно вычислено:
* + а35 * 2b
Такая запись, которая называется префиксной (операция записывается перед данными), просматривается с конца. Как только встретится знак операции, эта операция выполняется с двумя значениями, записанными справа. В рассмотренном выражении сначала выполняется умножение:
- * + а 3 5 (2*b)
затем — сложение:
- * (а + 3) 5 (2 * b)
и ещё одно умножение:
- (а + 3) * 5 (2*b)
и наконец, вычитание:
(а + 3) * 5 - (2 * b)
Для получения префиксной записи мы обходили все узлы дерева в порядке «корень — левое поддерево — правое поддерево». Действительно, сначала записана метка корня («-»), затем все метки левого поддерева, а затем — все метки правого поддерева. Для поддеревьев используется тот же порядок обхода. Если же обойти дерево в порядке «левое поддерево — правое поддерево — корень», получается постфиксная форма (операция после данных). Например, рассмотренное выше выражение может быть записано в виде
аЗ+5*2b*-
Для вычисления такого выражения скобки также не нужны, и это очень удобно для автоматических расчётов. Когда программа на языке программирования высокого уровня переводится в машинные коды, часто все выражения записываются в бесскобочной постфиксной форме и именно так и вычисляются. Постфиксная форма для компьютера удобнее, чем префиксная, потому что, когда программа доходит до знака операции, все данные для выполнения этой операции уже готовы.
Следующая страница 
Графы
Cкачать материалы урока
