Рис. 8.18. Структурное представление бинарного дерева, полученное
врезультате сортировки строк
2)если введенная строка (слово) в алфавитном отношении расположена выше, то следует двигаться по левой ветви к вершине нижнего уровня, иначе,- по правой ветви, тоже вниз;
3)если достигли конца пути, т.е. указатель, на вершину нижнего уровня равен NULL, то надо выполнить опера ции по созданию и подключению к дереву новой верши ны, а именно:
•с помощью функции malloc() запросить память для вершины в виде структуры типа struct node;
Глава 8. Примеры разработки программ
433
•с помощью функции malloc() запросить память для представления очередного слова в виде строки;
•записать в полученный участок памяти введенную стро ку (слово);
•установить значения указателей новой вершины (в структуре типа struct node):
-указатель str - на участок памяти, выделенный для очередной строки со словом;
-указателям left и right присвоить значение NULL, так как ни один из них пока не адресует вершину нижне го уровня;
•записать в указатель left или right предыдущей вершины (на пройденном от начальной вершины пути) адрес уча стка памяти, выделенного под новую вершину дерева.
Объединим действия, описанные выше в пункте 3, в функ цию new_node() - "Создать новую вершину". Алгоритм в це лом, т.е. действия пунктов 1-нЗ, оформим в виде функции add_node(), которая будет вызывать функцию new_node().
Главная функция, в которой будет вызываться функция add_node( ), должна выполнить следующие действия:
•получить имя файла с данными для сортировки;
•открыть файл для чтения;
•инициализировать нулевым значением (NULL) указатель root на начальную вершину дерева;
•в цикле (до исчерпания данных из файла): читать очеред
ную строку (слово) из файла и вызывать для каждой стро ки функцию add_node( ). -
Теперь можно приступить к написанию текстов всех указан ных функций. Начнем с функции main( ):
#include <stdio.h> Яdefine MAXLINE 80
/* Определение структурного типа "node" */ struct node
while (fgets(line, MAXLINE, fp)) root = add_node(root,'line);
}
else
{
perror( argv[l]); return -1;
)
print(root); return 0;
}
Текст функции m ain() не сложен и не требует пояснений. Функция print(), вызываемая перед оператором return, предна значена для печати результатов сортировки; она рассматривает ся ниже.
Функции add_node( ), которая вызывается в теле цикла while, необходимо передать два параметра: прочитанную из файла строку (слово) line[ ] и указатель root на корневую вершину в дереве, так как при включении в дерево новой вершины про смотр дерева каждый раз начинается с корневой вершины.
Если указатель root на корневую вершину дерева имеет зна чение NULL (дерево пустое), то вызывается функция new_node( ), которая создает первую (корневую) вершину дере ва и записывает в указатель root адрес этой вершины.
Если же указатель root имеет значение, отличное от NULL (в дереве существует хотя бы одна вершина), то выполняется цикл спуска по ветвям дерева до вершины, содержащей нулевой ад рес в соответствующей ветви, и вызывается функция new_node(). для создания новой вершины. Рассмотрим подроб-
28*
436
Программирование на языке Си
нее этот процесс для случая, когда в дереве присутствуют две вершины (рис. 8.19) и "подключается" слово "array".
Цифрами 1 и 2 показаны те вершины и указатели ветвей, ад реса которых содержат указатели ptr и prior, соответственно, после первого (1) и второго (2) выполнение цикла while. Указа тель ptr содержит адрес текущей вершины.
root
Рис. 8.19. Подключение кдереву новой вершины
Конструкция **prior определяет переменную prior как указа тель на указатель. Перед чтением третьего слова из файла ука затель prior будет содержать адрес элемента ptr—>lefit, в который вместо NULL необходимо записать адрес новой вершины дере ва, так как введенное слово (array) находится выше в алфавит ном порядке, чем слово из второй вершины дерева (comma). Указателю ptr присваивается после второго выполнения цикла значение NULL, так как ниже второй вершины других вершин нет.
Глава 8. Примеры разработки программ
437
Напомним, что функция new_node( ) должна выполнить сле дующие действия:
•запросить динамическую память для новой вершины дере ва (для структуры struct node);
•проинициализировать указатели left и right созданной структуры значениями NULL;
•запросить память в виде массива типа char[ ] для сохране ния введенной из файла строки (слова);
•вернуть в функцию add_node() адрес участка памяти, где размещена новая вершина.
Вфункцию new_node( ) необходимо передать один аргумент
-вновь введенную строку из файла. Текст функции new_node() приводится ниже.
Операция sizeof, используемая при вызове функции malloc(), вычисляет в байтах длину структуры, описывающей вершину дерева. Выражение (strlen(line)+l) в следующей строке в каче стве параметра функции malloc() задает размер необходимой для хранения введенной строки, добавляя один байт для записи в конце строки '\0'.
438
Программирование на языке Си
Печать результатов сортировки. Для того чтобы напеча тать в алфавитном порядке результаты сортировки слов, вклю ченных в вершины дерева, необходима функция обхода дерева по определенному маршруту. Сначала рассмотрим пример не большого бинарного дерева, приведенный на рис. 8.20.
Такое дерево легко получится при вводе, например, такой последовательности букв латинского алфавита: D, В, С, F, А, Е, G (введены все буквы в диапазоне от А до G). Рассматривая это дерево, можно заметить, что буквы А и G (открывающая и за крывающая отсортированную последовательность) расположе ны на третьем (нижнем) уровне, соответственно слева и справа. Для того чтобы напечатать буквы в алфавитном порядке, необ ходимо спуститься от корня дерева по левым ветвям до самой нижней вершины. Там и будет первый элемент отсортирован ной последовательности букв. Увидев, что левый указатель ра вен NULL, напечатаем А и проверим указатель правой ветви. Он также равен NULL, поэтому поднимемся к предыдущей вершине и напечатаем В. Спускаемся от В по правой ветви к С и видим, что вниз по левой ветви от С указатель равен NULL, следовательно, печатаем С. Далее идем вверх к В (эта буква уже напечатана), поднимаемся к D и печатаем ее.
r o o t
I
D
/\
ВF
/
\
/
\
А
С
Е
G
/ \
/ \ /
\
/ \
Рис. 8.20. Пример бинарного дерева
Аналогичным образом обходим правое от D поддерево. В итоге получается маршрут, изображенный на рис. 8.21.
Глава 8. Примеры разработки программ
439
Ниже приводится текст функции print( ), осуществляющей обход дерева и печать строк из вершин в алфавитном порядке. Для запоминания указателей на предыдущие узлы в функции организован стек глубиной 10 элементов в виде массива из 10 указателей на структуру типа struct node.
Оператор stack[i++] = ptr; заносит в стек значение указателя ptr и затем (постфиксная операция ++) увеличивает значение индекса (i) массива на 1. После этого stack[i] становится первым свободным элементом стека. Для выборки из стека значения указателя необходимо сначала уменьшить индекс i на единицу, с тем, чтобы stack[i] был не первым свободным элементом мас сива, а последним записанным:
ptr=stack[— i] ;
Root
Рис. 8.21. Обход бинарного дерева при печати
Текст функции print():
# in c lu d e < s td io .h > s t r u c t , n o d e
{
c h a r * s t r ;
s t r u c t n o d e * l e f t ; s t r u c t n o d e * r i g h t ;
> ;
void print(struct node *ptr)
440 Программирование на языке Си
{
int i = 0;
struct node *stack[10]; /* Внимание: число уровней, на которых расположены вершины в бинарном дереве, - не более 10
(в рассматриваемом примере 3 уровня */ while(1)
{ •
while (ptr != NULL)
{
stack[i++] = ptr; ptr = ptr->left;
}
ptr = stack[— i]; if (i < 0) break;
printf("%s", ptr->str); ptr = ptr->right;
}
}
Подробно процесс подготовки и выполнение программы сортировки на основе бинарного дерева в операционных систе мах UNIX, MS-DOS и Windows обсуждаются в главе 9.
