P->LEFT = TREE(P->LEFT, W);
ELSE /* GREATER INTO RIGHT SUBTREE */
P->RIGHT = TREE(P->RIGHT, W);
RETURN(P);
\)
Память для нового узла выделяется функцией TALLOC, явля-
ющейся адаптацией для данного случая функции ALLOC, написан-
ной нами ранее. Она возвращает указатель свободного прост-
ранства, пригодного для хранения нового узла дерева. (Мы
вскоре обсудим это подробнее). Новое слово копируется функ-
цией STRSAVE в скрытое место, счетчик инициализируется еди-
ницей, и указатели обоих потомков полагаются равными нулю.
Эта часть программы выполняется только при добавлении нового
узла к ребру дерева. Мы здесь опустили проверку на ошибки
возвращаемых функций STRSAVE и TALLOC значений (что неразум-
но для практически работающей программы).
Функция TREEPRINT печатает дерево, начиная с левого под-
дерева; в каждом узле сначала печатается левое поддерево
(все слова, которые младше этого слова), затем само слово, а
затем правое поддерево (все слова, которые старше). Если вы
неуверенно оперируете с рекурсией, нарисуйте дерево сами и
напечатайте его с помощью функции TREEPRINT ; это одна из
наиболее ясных рекурсивных процедур, которую можно найти.
TREEPRINT (P) /* PRINT TREE P RECURSIVELY */
STRUCT TNODE *P;
\(
IF (P != NULL) \(
TREEPRINT (P->LEFT);
PRINTF("%4D %S\N", P->COUNT, P->WORD);
TREEPRINT (P->RIGHT);
\)
\)
Практическое замечание: если дерево становится "несба-
лансированным" из-за того, что слова поступают не в случай-
ном порядке, то время работы программы может расти слишком
быстро. В худшем случае, когда поступающие слова уже упоря-
дочены, настоящая программа осуществляет дорогостоящую ими-
тацию линейного поиска. Существуют различные обобщения дво-
ичного дерева, особенно 2-3 деревья и AVL деревья, которые
не ведут себя так "в худших случаях", но мы не будем здесь
на них останавливаться.
Прежде чем расстаться с этим примером, уместно сделать
небольшое отступление в связи с вопросом о распределении па-
мяти. Ясно, что в программе желательно иметь только один
распределитель памяти, даже если ему приходится размещать
различные виды объектов. Но если мы хотим использовать один
распределитель памяти для обработки запросов на выделение
памяти для указателей на переменные типа CHAR и для указате-
лей на STRUCT TNODE, то при этом возникают два вопроса. Пер-
вый: как выполнить то существующее на большинстве реальных
машин ограничение, что объекты определенных типов должны
удовлетворять требованиям выравнивания (например, часто це-
лые должны размещаться в четных адресах)? Второй: как орга-
низовать описания, чтобы справиться с тем, что функция ALLOC
должна возвращать различные виды указателей ?
Вообще говоря, требования выравнивания легко выполнить
за счет выделения некоторого лишнего пространства, просто
обеспечив то, чтобы распределитель памяти всегда возвращал
указатель, удовлетворяющий всем ограничениям выравнивания.
Например, на PDP-11 достаточно, чтобы функция ALLOC всегда
возвращала четный указатель, поскольку в четный адрес можно
поместить любой тип объекта. единственный расход при этом -
лишний символ при запросе на нечетную длину. Аналогичные
действия предпринимаются на других машинах. Таким образом,
реализация ALLOC может не оказаться переносимой, но ее ис-
пользование будет переносимым. Функция ALLOC из главы 5 не
предусматривает никакого определенного выравнивания; в главе
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)));
\)
это более чем достаточно для работающих в настоящее время
компиляторов, но это и самый безопасный путь с учетом будую-
щего.
Упражнение 6-4
----------------
Напишите программу, которая читает "C"-программу и печа-
тает в алфавитном порядке каждую группу имен переменных, ко-
торые совпадают в первых семи символах, но отличаются где-то
дальше. (Сделайте так, чтобы 7 было параметром).
Упражнение 6-5
----------------
Напишите программу выдачи перекрестных ссылок, т.е.
Программу, которая печатает список всех слов документа и для
каждого из этих слов печатает список номеров строк, в кото-
рые это слово входит.
Упражнение 6-6
----------------
Напишите программу, которая печатает слова из своего
файла ввода, расположенные в порядке убывания частоты их по-
явления. Перед каждым словом напечатайте число его появле-
ний.
6.6. Поиск в таблице
Для иллюстрации дальнейших аспектов использования струк-
тур в этом разделе мы напишем программу, представляющую со-
бой содержимое пакета поиска в таблице. Эта программа явля-
ется типичным представителем подпрограмм управления символь-
ными таблицами макропроцессора или компилятора. Рассмотрим,
например, оператор #DEFINE языка "C". Когда встречается
строка вида
#DEFINE YES 1
то имя YES и заменяющий текст 1 помещаются в таблицу. Позд-
нее, когда имя YES появляется в операторе вида
INWORD = YES;
Oно должно быть замещено на 1.
Имеются две основные процедуры, которые управляют имена-
ми и заменяющими их текстами. Функция INSTALL(S,T) записыва-
ет имя S и заменяющий текст T в таблицу; здесь S и T просто
символьные строки. Функция LOOKUP(S) ищет имя S в таблице и
возвращает либо указатель того места, где это имя найдено,
либо NULL, если этого имени в таблице не оказалось.
При этом используется поиск по алгоритму хеширования -
поступающее имя преобразуется в маленькое положительное чис-
ло, которое затем используется для индексации массива указа-
телей. Элемент массива указывает на начало цепочных блоков,
описывающих имена, которые имеют это значение хеширования.
Если никакие имена при хешировании не получают этого значе-
ния, то элементом массива будет NULL.
Блоком цепи является структура, содержащая указатели на
соответствующее имя, на заменяющий текст и на следующий блок
в цепи. Нулевой указатель следующего блока служит признаком
конца данной цепи.
STRUCT NLIST \( /* BASIC TABLE ENTRY */
CHAR *NAME;
CHAR *DEF;
STRUCT NLIST *NEXT; /* NEXT ENTRY IN CHAIN */
\);
Массив указателей это просто
DEFINE HASHSIZE 100
TATIC STRUCT NLIST *HASHTAB[HASHSIZE] /* POINTER TABLE */
Значение функции хеширования, используемой обеими функ-
циями LOOKUP и INSTALL , получается просто как остаток от
деления суммы символьных значений строки на размер массива.
(Это не самый лучший возможный алгоритм, но его достоинство
состоит в исключительной простоте).
HASH(S) /* FORM HASH VALUE FOR STRING */
CHAR *S;
\(
INT HASHVAL;
FOR (HASHVAL = 0; *S != '\0'; )
HASHVAL += *S++;
RETURN(HASHVAL % HASHSIZE);
\)
В результате процесса хеширования выдается начальный ин-
декс в массиве HASHTAB ; если данная строка может быть
где-то найдена, то именно в цепи блоков, начало которой ука-
зано там. Поиск осуществляется функцией LOOKUP. Если функция
LOOKUP находит, что данный элемент уже присутствует, то она
возвращает указатель на него; если нет, то она возвращает
NULL.
STRUCT NLIST *LOOKUP(S) /* LOOK FOR S IN HASHTAB */
CHAR *S;
\(
STRUCT NLIST *NP;
FOR (NP = HASHTAB[HASH(S)]; NP != NULL;NP=NP->NEXT)
IF (STRCMP(S, NP->NAME) == 0)
RETURN(NP); /* FOUND IT */
RETURN(NULL); /* NOT FOUND */
Функция INSTALL использует функцию LOOKUP для определе-
ния, не присутствует ли уже вводимое в данный момент имя;
если это так, то новое определение должно вытеснить старое.
В противном случае создается совершенно новый элемент. Если
по какой-либо причине для нового элемента больше нет места,
то функция INSTALL возвращает NULL.
STRUCT NLIST *INSTALL(NAME, DEF) /* PUT (NAME, DEF) */
CHAR *NAME, *DEF;
\(
STRUCT NLIST *NP, *LOOKUP();
CHAR *STRSAVE(), *ALLOC();
INT HASHVAL;
IF((NP = LOOKUP(NAME)) == NULL) \( /* NOT FOUND */
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 /* ALREADY THERE */
FREE((NP->DEF);/* FREE PREVIOUS DEFINITION */
IF ((NP->DEF = STRSAVE(DEF)) == NULL)
RETURN (NULL);
RETURN(NP);
\)
Функция STRSAVE просто копирует строку, указанную в ка-
честве аргумента, в место хранения, полученное в результате
обращения к функции ALLOC. Мы уже привели эту функцию в гла-
ве 5. Так как обращение к функции ALLOC и FREE могут проис-
ходить в любом порядке и в связи с проблемой выравнивания,
простой вариант функции ALLOC из главы 5 нам больше не под-
ходит; смотрите главы 7 и 8.
Упражнение 6-7
---------------
Напишите процедуру, которая будет удалять имя и опреде-
ление из таблицы, управляемой функциями LOOKUP и INSTALL.
Упражнение 6-8
---------------
Разработайте простую, основанную на функциях этого раз-
дела, версию процессора для обработки конструкций #DEFINE ,
пригодную для использования с "C"-программами. Вам могут
также оказаться полезными функции GETCHAR и UNGETCH.
6.7. Поля
Когда вопрос экономии памяти становится очень существен-
ным, то может оказаться необходимым помещать в одно машинное
слово несколько различных объектов; одно из особенно расп-
росраненных употреблений - набор однобитовых признаков в
применениях, подобных символьным таблицам компилятора. внеш-
не обусловленные форматы данных, такие как интерфейсы аппа-
ратных средств также зачастую предполагают возможность полу-
чения слова по частям.
Представьте себе фрагмент компилятора, который работает
с символьной таблицей. С каждым идентификатором программы
связана определенная информация, например, является он или
нет ключевым словом, является ли он или нет внешним и/или
статическим и т.д. Самый компактный способ закодировать та-
кую информацию - поместить набор однобитовых признаков в от-
дельную переменную типа CHAR или INT.
Обычный способ, которым это делается, состоит в опреде-
лении набора "масок", отвечающих соответствущим битовым по-
зициям, как в
#DEFINE KEYWORD 01
#DEFINE EXTERNAL 02
#DEFINE STATIC 04
(числа должны быть степенями двойки). Тогда обработка битов
сведется к "жонглированию битами" с помощью операций сдвига,
маскирования и дополнения, описанных нами в главе 2.
Некоторые часто встречающиеся идиомы:
FLAGS \!= EXTERNAL \! STATIC;
включает биты EXTERNAL и STATIC в FLAGS, в то время как
FLAGS &= \^(еXTERNAL \! STATIC);
их выключает, а
IF ((FLAGS & (EXTERNAL \! STATIC)) == 0) ...
истинно, если оба бита выключены.
Хотя этими идиомами легко овладеть, язык "C" в качестве
альтернативы предлагает возможность определения и обработки
полей внутри слова непосредственно, а не посредством побито-
вых логических операций. Поле - это набор смежных битов
внутри одной переменной типа INT. Синтаксис определения и
обработки полей основывается на структурах. Например, сим-
вольную таблицу конструкций #DEFINE, приведенную выше, можно
бы было заменить определением трех полей:
STRUCT \(
UNSIGNED IS_KEYWORD : 1;
UNSIGNED IS_EXTERN : 1;
UNSIGNED IS_STATIC : 1;
\) FLAGS;
Здесь определяется переменная с именем FLAGS, которая содер-
жит три 1-битовых поля. Следующее за двоеточием число задает
