§ 16. Списки и деревья

Определения и обозначения

Список — упорядоченная последовательность элементов, порядок которой задают связи между ними. В связанном списке порядок не обязательно совпадает с расположением элементов в памяти. Это позволяет соединять данные ссылками и менять состав последовательности.

Элемент списка — часть структуры, в которой хранятся данные и ссылка на следующий элемент. В двусвязном списке есть также ссылка на предыдущий элемент. Такие ссылки позволяют определить соседей элемента и направление перехода по списку.

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

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

Как это устроено

Чтобы получить связанный список из отдельных элементов, в каждом элементе сохраняют ссылку на следующий. Начало списка указывает на первый элемент, а ссылка последнего обычно не ведёт к другому элементу. Поэтому для поиска нужно идти от начала и переходить по очередной ссылке: отдельный элемент может не иметь известного адреса или номера, по которому к нему можно обратиться сразу.

В односвязном списке элемент хранит ссылку только на следующий элемент. По цепочке можно двигаться вперёд, но чтобы вернуться назад, придётся начинать сначала. В двусвязном списке есть ссылка и на предыдущий элемент, поэтому можно перемещаться в обе стороны; за эту возможность приходится хранить дополнительную ссылку.

У дерева есть корень, от которого начинается движение по структуре. Связи от родителя к детям образуют ветви, а узлы располагаются на уровнях: корень находится выше своих детей, те могут иметь собственных детей. У каждого узла, кроме корня, один родитель, потому что иначе связи могли бы соединить разные ветви в сеть, а не в дерево. Узлы без детей становятся листьями.

Дерево удобно, если данные естественно делятся на группы и подгруппы. Например, главная папка может быть корнем, вложенные папки — дочерними узлами, а файлы — узлами на нижних уровнях. Похожим образом можно представить понятие и его более частные разновидности: движение вниз по ветвям показывает, к какой группе относится каждый объект.

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

Сравнение списков и деревьев

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

Разбор задач

Односвязный список из пяти элементов

Условие. Для последовательности из пяти элементов нужно определить, какие ссылки задать, чтобы получить односвязный список. Обозначим элементы A, B, C, D и E в требуемом порядке. В односвязном списке у каждого элемента есть ссылка на следующий, поэтому важно сохранить последовательность и отметить её начало.

1. Укажите начало списка: оно должно ссылаться на A, первый элемент.
2. Задайте ссылку из A на B, из B на C, из C на D, а из D на E.
3. У элемента E следующего элемента нет, поэтому его ссылка на следующий обозначается как пустая.
4. Проверьте цепочку переходов от начала: по ней должны встретиться все пять элементов ровно в нужном порядке.

Ответ. Начало списка указывает на A; ссылки имеют вид A → B → C → D → E, а ссылка из E на следующий элемент пустая. Так каждый элемент, кроме последнего, ведёт к следующему.

Поиск частей дерева по схеме

Условие. По схеме дерева нужно определить корень, листья, родителей и детей заданного узла. Пусть на верхнем уровне находится R, под ним — A и B, а под A расположены C и D; у B детей нет. Нужно читать схему от верхнего узла вниз, не путать непосредственных детей с более далёкими потомками.

1. Найдите узел, у которого нет родителя: это верхний узел R, значит, он является корнем.
2. Проследите связи от R: его непосредственные дети — A и B.
3. Узел A является родителем C и D; для C и D родитель — A.
4. Проверьте, у каких узлов нет отходящих вниз связей: листья здесь C, D и B.

Ответ. Корень — R, дети R — A и B, дети A — C и D, а листья — B, C и D. Например, B — лист, хотя он не находится на самом нижнем уровне схемы отдельно от остальных: решает отсутствие детей.

Иерархия папок и путь к файлу

Условие. Представьте папку «Проекты», в которой есть папки «Информатика» и «Фото». В папке «Информатика» лежит папка «Сайт», а в ней — файл «главная.html». Требуется изобразить структуру деревом и указать путь к файлу. Папки и файл рассматриваются как узлы, а вложенность задаёт связь родителя и ребёнка.

1. Назначьте папку «Проекты» корнем: это верхний узел заданной структуры.
2. Добавьте к нему детей «Информатика» и «Фото», поскольку обе папки находятся внутри «Проектов».
3. К папке «Информатика» присоедините её дочернюю папку «Сайт», затем к «Сайту» — файл «главная.html».
4. Чтобы получить путь, начните с корня и последовательно перечислите узлы по ветви до файла.

Ответ. Структура имеет вид: «Проекты» → «Информатика» → «Сайт» → «главная.html», а папка «Фото» — другая ветвь от корня. Путь к файлу проходит через эти четыре узла, поскольку каждый следующий вложен в предыдущий.

Типичные ошибки

• Называть списком любую последовательность значений — значит забывать, что в связанной структуре порядок задаётся ссылками. Ошибка возникает потому, что привычный ряд чисел тоже выглядит упорядоченным. Проверьте себя: можете ли вы показать, какая ссылка ведёт от одного элемента к следующему?

• Считать, что к элементу связанного списка можно обратиться по номеру так же быстро, как в массиве, неверно. В массиве элементы доступны по позиции, а в списке часто нужно пройти цепочку от начала. Если для поиска вы перескакиваете сразу к нужному номеру, проверьте, предусмотрен ли такой прямой доступ.

• Путать корень и лист нельзя: корень не имеет родителя, а лист не имеет дочерних узлов. Ошибка появляется, когда «верхний» и «нижний» понимают только по расположению на рисунке. Проверяйте связи: у корня нет родителя, у листа — детей.

• Считать, что у узла дерева может быть несколько родителей, — значит смешивать дерево с сетью связей. Такое впечатление может возникнуть, если потомка принимают за непосредственного ребёнка или смотрят на схему невнимательно. Для проверки проследите связи вверх: у любого узла, кроме корня, должен быть ровно один родитель.

Связь с другими темами

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

Что запомнить

• Список — линейная структура, элементы которой связаны в определённом порядке.
• В связанном списке переход к следующему элементу выполняется по ссылке.
• Дерево состоит из узлов и связей между ними и не содержит циклов.
• Корень — узел без родителя.
• Лист — узел без дочерних узлов.
• Список описывает линейный порядок, дерево — иерархические связи.