Сортировка с помощью бинарного дерева.

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

1. Структуры данных типа "дерево" являются динамическими и важны при построении информационных и телекоммуникационных систем.

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

данных, подлежащих сортировке, и объемом статически выделенной памяти.

3. Выбранный способ сортировки позволяет освоить столь важные при работе с деревьями операции, как построение дерева и его обход, например, для печати содержимого его вершин.

Описание методов сортировки и работы с динамическими структурами данных можно найти в приведенной выше работе Н. Вирта. В качестве метода для программной реализации определим бинарную сортировку включением. Этот метод сортировки предполагает, что вводимые данные запоминаются в виде бинарного дерева (рис. 8.12). Дерево начинается с корня (root), который указывает на первую вершину. Из каждой вершины дерева выходят две ветви, связывающие ее с вершинами нижнего уровня.

Рис. 8.12. Пример заполненного бинарного дерева

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

Выбранный метод сортировки определяет следующую процедуру формирования дерева. На первом от корня месте располагается первое слово, введенное из исходного файла. От него проводятся две ветви (левая и правая), ведущие к двум вершинам нижнего уровня. Если следующее слово в алфавитном порядке выше первого слова, то оно располагается в вершине нижнего уровня, к которой ведет левая ветвь (рис. 8.13).

Рис. 8.13. Размещение в дереве нового слова

Следующий этап построения дерева вновь начинаем с корневой вершины. Сравниваем слова "array" и "line". Строка "array" выше в алфавитном порядке строки "line", поэтому переходим к вершине нижнего уровня по левой ветви. Сравниваем строки "array" и "comma". Строка "array" также выше в алфавитном порядке строки "comma", поэтому от вершины, содержащей строку "comma", вновь спускаемся к вершине нижнего уровня по левой ветви. Итог третьего этапа показан на рис. 8.14.

Рис. 8.14. Дерево после трех включений

Результат ввода следующей строки "name" приведен на рис. 8.15.

Рис. 8.15. Дерево после четырех включений

Первое же сравнение строк "line" и "name" показывает, что "name" располагается в алфавитном порядке ниже "line", поэтому из вершины "line" необходимо выйти по правой ветви. Эта ветвь не ведет ни к какой вершине, поэтому к ней и присоединяется вершина нижнего уровня со строкой "name" (см. рис. 8.15).

Итогом описанного процесса будет бинарное дерево, показанное на рис. 8.12.

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

С учетом приведенного определения структурного типа вершину дерева можно изобразить графически (рис. 8.16).

Рис. 8.16. Структурное представление вершины бинарного дерева

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

Модифицируем описание структурного типа, соответствующего вершине дерева, следующим образом:

Теперь в структуре типа struct node вместо массива символов фиксированной длины для слова из сортируемого файла используется указатель на строку. Память для каждой строки (массива типа char [ ]) необходимо запрашивать у операционной системы в соответствии с длиной конкретного слова.

Приведенному описанию соответствует графическое представление, изображенное на рис. 8.17.

Рис. 8.17. Модифицированное структурное представление вершины бинарного дерева

С учетом приведенного определения структурного типа для вершин бинарного дерева нарисуем еще раз (рис. 8.18) дерево, приведенное выше на рис. 8.12.

На рис. 8.18 указателям, не содержащим адреса какой-либо вершины, присвоено значение NULL; указатель root типа struct node * содержит адрес начальной вершины дерева.

Рис. 8.18. Структурное представление бинарного дерева, полученное в результате сортировки строк

Уточним алгоритм ввода очередного слова и построения соответствующей вершины.

Введя слово, необходимо, двигаясь от начальной вершины:

1) сравнить введенное слово со словом, хранящимся в данной вершине дерева (на него указывает str);

2) если введенная строка (слово) в алфавитном отношении расположена выше, то следует двигаться по левой ветви к вершине нижнего уровня, иначе - по правой ветви, тоже вниз;

3) если достигли конца пути, т.е. указатель, на вершину нижнего уровня равен NULL, то надо выполнить операции по созданию и подключению к дереву новой вершины, а именно:

• с помощью функции malloc( ) запросить память для вершины в виде структуры типа struct node;

• с помощью функции malloc( ) запросить память для представления очередного слова в виде строки;

• записать в полученный участок памяти введенную строку (слово);

• установить значения указателей новой вершины (в структуре типа struct node):

- указатель str - на участок памяти, выделенный для очередной строки со словом;

- указателям left и right присвоить значение NULL, так как ни один из них пока не адресует вершину нижнего уровня;

• записать в указатель left или right предыдущей вершины (на пройденном от начальной вершины пути) адрес участка памяти, выделенного под новую вершину дерева.

Объединим действия, описанные выше в пункте 3, в функцию new_node( ) - "Создать новую вершину". Алгоритм в целом, т.е. действия пунктов 1  3, оформим в виде функции add_node( ), которая будет вызывать функцию new_node( ).

Главная функция, в которой будет вызываться функция add_node( ), должна выполнить следующие действия:

• получить имя файла с данными для сортировки;

• открыть файл для чтения;

• инициализировать нулевым значением (NULL) указатель root на начальную вершину дерева;

• в цикле (до исчерпания данных из файла): читать очередную строку (слово) из файла и вызывать для каждой строки функцию add_node( ).

Теперь можно приступить к написанию текстов всех указанных функций. Начнем с функции main( ):

Текст функции main( ) не сложен и не требует пояснений. Функция print( ), вызываемая перед оператором return, предназначена для печати результатов сортировки; она рассматривается ниже.

Функции add_node( ), которая вызывается в теле цикла while, необходимо передать два параметра: прочитанную из файла строку (слово) line[ ] и указатель root на корневую вершину в дереве, так как при включении в дерево новой вершины просмотр дерева каждый раз начинается с корневой вершины.

Ниже приводится текст функции add_node( ).

Если указатель root на корневую вершину дерева имеет значение NULL (дерево пустое), то вызывается функция new_node( ), которая создает первую (корневую) вершину дерева и записывает в указатель root адрес этой вершины.

Если же указатель root имеет значение, отличное от NULL (в дереве существует хотя бы одна вершина), то выполняется цикл спуска по ветвям дерева до вершины, содержащей нулевой адрес в соответствующей ветви, и вызывается функция new_node( ) для создания новой вершины. Рассмотрим подробнее этот процесс для случая, когда в дереве присутствуют две вершины (рис. 8.19) и "подключается" слово "array".

Рис. 8.19. Подключение к дереву новой вершины

Цифрами 1 и 2 показаны те вершины и указатели ветвей, адреса которых содержат указатели ptr и prior, соответственно, после первого (1) и второго (2) выполнение цикла while. Указатель ptr содержит адрес текущей вершины.

Конструкция **prior определяет переменную prior как указатель на указатель. Перед чтением третьего слова из файла указатель prior будет содержать адрес элемента ptr->left, в который вместо NULL необходимо записать адрес новой вершины дерева, так как введенное слово (array) находится выше в алфавитном порядке, чем слово из второй вершины дерева (comma). Указателю ptr присваивается после второго выполнения цикла значение NULL, так как ниже второй вершины других вершин нет.

Напомним, что функция new_node( ) должна выполнить следующие действия:

• запросить динамическую память для новой вершины дерева (для структуры struct node);

• проинициализировать указатели left и right созданной структуры значениями NULL;

• запросить память в виде массива типа char[ ] для сохранения введенной из файла строки (слова);

• вернуть в функцию add_node( ) адрес участка памяти, где размещена новая вершина.

В функцию new_node( ) необходимо передать один аргумент - вновь введенную строку из файла. Текст функции new_node( ) приводится ниже.

Операция sizeof, используемая при вызове функции malloc( ), вычисляет в байтах длину структуры, описывающей вершину дерева. Выражение (strlen(line)+l) в следующей строке в качестве параметра функции malloc( ) задает размер необходимой для хранения введенной строки, добавляя один байт для записи в конце строки '\0'.