Ведущая программа просто считывает слова с помощью функции getword и помещает их в дерево, используя функцию tree.
#define maxword 20
main() /* word freguency count */
{
struct tnode *root, *tree();
char word[maxword];
int t;
root = null;
while ((t = getword(word, maxword)) != eof)
if (t == letter)
root = tree(root, word);
treeprint(root);
}
Функция tree сама по себе проста. Слово передается функцией main к верхнему уровню (корню) дерева. На каждом этапе это слово сравнивается со словом, уже хранящимся в этом узле, и с помощью рекурсивного обращения к tree просачивается вниз либо к левому, либо к правому поддереву. В конце концов это слово либо совпадает с каким-то словом, уже находящимся в дереве (в этом случае счетчик увеличивается на единицу), либо программа натолкнется на нулевой указатель, свидетельствующий о необходимости создания и добавления к дереву нового узла. В случае создания нового узла функция main возвращает указатель этого узла, который помещается в родительский узел.
// tree: Добавляет узел со словом w в p или ниже него
struct tnode *tree(struct tnode *p, char *w)
{
struct tnode *talloc();
char *strsave();
int cond;
if (p == null)
{ //Если слово встречается впервые
p == talloc(); //Создается новый узел
p->word = strsave(w);
p->count = 1;
p->left = p->right = null;
}
else if ((cond = strcmp(w, p->word)) == 0)
p->count++; //Это слово уже встречалось
else if (cond < 0) //Меньше корня левого поддерева
p->left = tree(p->left, w);
else //Больше корня правого поддерева
p->right = tree(p->right, w);
return(p);
}
Память для нового узла выделяется функцией talloc, являющейся адаптацией для данного случая функции alloc, написанной нами ранее. Она возвращает указатель свободного пространства, пригодного для хранения нового узла дерева. (Мы вскоре обсудим это подробнее). Новое слово копируется функцией strsave в скрытое место, счетчик инициализируется единицей, и указатели обоих потомков полагаются равными нулю. Эта часть программы выполняется только при добавлении нового узла к ребру дерева. Мы здесь опустили проверку на ошибки возвращаемых функций strsave и talloc значений (что неразумно для практически работающей программы).
Функция treeprint печатает дерево, начиная с левого поддерева; в каждом узле сначала печатается левое поддерево (все слова, которые младше этого слова), затем само слово, а затем правое поддерево (все слова, которые старше). Если вы неуверенно оперируете с рекурсией, нарисуйте дерево сами и напечатайте его с помощью функции treeprint; это одна из наиболее ясных рекурсивных процедур, которую можно найти.
// treeprint: напечатать дерево p рекурсивно
treeprint (struct tnode *p)
{
if (p != null)
{
treeprint (p->left);
printf("%4d %s\n", p->count, p->word);
treeprint (p->right);
}
}
Практическое замечание: если дерево становится «несбалансированным» из-за того, что слова поступают не в случайном порядке, то время работы программы может расти слишком быстро. В худшем случае, когда поступающие слова уже упорядочены, настоящая программа осуществляет дорогостоящую имитацию линейного поиска. Существуют различные обобщения двоичного дерева, но мы не будем здесь на них останавливаться.
Прежде чем расстаться с этим примером, уместно сделать небольшое отступление в связи с вопросом о распределении памяти. Ясно, что в программе желательно иметь только один распределитель памяти, даже если ему приходится размещать различные виды объектов. Но если мы хотим использовать один распределитель памяти для обработки запросов на выделение памяти для указателей на переменные типа char и для указателей на struct tnode, то при этом возникают два вопроса.
Первый: как выполнить то существующее на большинстве реальных машин ограничение, что объекты определенных типов должны удовлетворять требованиям выравнивания (например, часто целые должны размещаться в четных адресах)?
Второй: как организовать описания, чтобы справиться с тем, что функция alloc должна возвращать различные виды указателей?
Вообще говоря, требования выравнивания легко выполнить за счет выделения некоторого лишнего пространства, просто обеспечив то, чтобы распределитель памяти всегда возвращал указатель, удовлетворяющий всем ограничениям выравнивания. Например, на PDP-11 достаточно, чтобы функция alloc всегда возвращала четный указатель, поскольку в четный адрес можно поместить любой тип объекта. единственный расход при этом лишний символ при запросе на нечетную длину. Аналогичные действия предпринимаются на других машинах. Таким образом, реализация alloc может не оказаться переносимой, но ее использование будет переносимым. Функция alloc из главы 6 не предусматривает никакого определенного выравнивания. В главе 8 мы продолжим обсуждение темы, связанной с динамическим распределением памяти.
Вопрос описания типа функции alloc является мучительным для любого языка, который серьезно относится к проверке типов. Лучший способ в языке «C» – объявить, что alloc возвращает указатель на переменную типа char, а затем явно преобразовать этот указатель к желаемому типу с помощью операции перевода типов. Таким образом, если описать p в виде:
char *p;
то
(struct tnode *) p
преобразует его в выражениях в указатель на структуру типа tnode . Следовательно, функцию talloc можно записать в виде:
struct tnode *talloc()
{
char *alloc();
return((struct tnode *) alloc(sizeof(struct tnode)));
}
Это более чем достаточно для работающих в настоящее время компиляторов, но это и самый безопасный путь с учетом будущего.
Упражнение 7-4. Напишите программу, которая читает «C»-программу и печатает в алфавитном порядке каждую группу имен переменных, которые совпадают в первых семи символах, но отличаются где-то дальше. (Сделайте так, чтобы 7 было параметром).
Упражнение 7-5. Напишите программу выдачи перекрестных ссылок, т.е. программу, которая печатает список всех слов документа и для каждого из этих слов печатает список номеров строк, в которые это слово входит.
Упражнение 7-6. Напишите программу, которая печатает слова из своего файла ввода, расположенные в порядке убывания частоты их появления. Перед каждым словом напечатайте число его появлений.
Пример 7-5. Для иллюстрации дальнейших аспектов использования структур в этом разделе мы напишем программу, представляющую собой содержимое пакета поиска в таблице. Эта программа является типичным представителем подпрограмм управления символьными таблицами макропроцессора или компилятора. Рассмотрим, например, оператор #define языка «C». Когда встречается строка вида:
#define yes 1
то имя yes и заменяющий текст 1 помещаются в таблицу. Позднее, когда имя yes появляется в операторе вида:
inword = yes;
оно должно быть замещено на 1.
Имеются две основные процедуры, которые управляют именами и заменяющими их текстами. Функция install(s,t) записывает имя s и заменяющий текст t в таблицу; здесь s и t просто символьные строки. Функция lookup(s) ищет имя s в таблице и возвращает либо указатель того места, где это имя найдено, либо null, если этого имени в таблице не оказалось.
При этом используется поиск по алгоритму хеширования – поступающее имя преобразуется в маленькое положительное число, которое затем используется для индексации массива указателей. Элемент массива указывает на начало цепочных блоков, описывающих имена, которые имеют это значение хеширования. Если никакие имена при хешировании не получают этого значения, то элементом массива будет null.
Блоком цепи является структура, содержащая указатели на соответствующее имя, на заменяющий текст и на следующий блок в цепи. Нулевой указатель следующего блока служит признаком конца данной цепи.
struct nlist
{ // Основной элемент таблицы
char *name;
char *def;
struct nlist *next; // Следующий элемент таблицы
};
Массив указателей – это просто:
#define hashsize 100 // hashtab: Таблица указателей
static struct nlist *hashtab[hashsize]
Значение функции хеширования, используемой обеими функциями lookup и install, получается просто как остаток от деления суммы символьных значений строки на размер массива. (Это не самый лучший возможный алгоритм, но его достоинство состоит в исключительной простоте).
// hash: Получает хэш-код для строки s
unsigned hash(char *s)
{
int hashval;
for (hashval = 0; *s != '\0'; )
hashval += *s++;
return(hashval % hashsize);
}
В результате процесса хеширования выдается начальный индекс в массиве hashtab; если данная строка может быть где-то найдена, то именно в цепи блоков, начало которой указано там. Поиск осуществляется функцией lookup. Если функция lookup находит, что данный элемент уже присутствует, то она возвращает указатель на него; если нет, то она возвращает null.
// lookup: Ищет s в hashtab
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np=hashtab[hash(s)]; np != null; np=np->next)
if (strcmp(s, np->name) == 0)
return(np); // Нашли
return(null); // Не нашли
}
Функция install использует функцию lookup для определения, не присутствует ли уже вводимое в данный момент имя; если это так, то новое определение должно вытеснить старое. В противном случае создается совершенно новый элемент. Если по какой-либо причине для нового элемента больше нет места, то функция install возвращает null.
// install: Заносит имя и текст (name, def) в таблицу
struct nlist *install(char *name, char *def)
{
struct nlist *np, *lookup();
char *strsave(), *alloc();
int hashval;
if((np = lookup(name)) == null)
{ // Не найден
np = (struct nlist *) alloc(sizeof(*np));
if (np == null)
return(null);
if ((np->name = strsave(name)) == null)
return(null);
hashval = hash(np->name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
}
else // Уже имеется
free((np->def); // Освобождаем прежний defn
if ((np->def = strsave(def)) == null)
return (null);
return(np);
}
Функция strsave просто копирует строку, указанную в качестве аргумента, в место хранения, полученное в результате обращения к функции alloc. Мы уже привели эту функцию в главе 6. Так как обращение к функции alloc и free могут происходить в любом порядке и в связи с проблемой выравнивания, простой вариант функции alloc из главы 6 нам больше не подходит (смотрите главу 8).