Предположим, что нам надо справиться с более общей зада-чей, состоящей в подсчете числа появлений всех слов в неко-тором файле ввода. Так как список слов заранее не известен,мы не можем их упорядочить удобным образом и использоватьбинарный поиск. Мы даже не можем осуществлять последователь-ный просмотр при поступлении каждого слова, с тем чтобы ус-тановить, не встречалось ли оно ранее; такая программа будетработать вечно. (Более точно, ожидаемое время работы растеткак квадрат числа вводимых слов). Как же нам организоватьпрограмму, чтобы справиться со списком произвольных слов? Одно из решений состоит в том, чтобы все время хранитьмассив поступающих до сих пор слов в упорядоченном виде, по-мещая каждое слово в нужное место по мере их поступления.OДнако это не следует делать, перемещая слова в линейноммассиве, - это также потребует слишком много времени. Вместоэтого мы используем структуру данных, называемую доичным де-ревом. Каждому новому слову соответствует один "узел" дерева;каждый узел содержит:указатель текста слова----------------------счетчик числа появлений-----------------------указатель узла левого потомка-----------------------------указатель узла правого потомка------------------------------Никакой узел не может иметь более двух детей; возможно от-сутсвие детей или наличие только одного потомка. Узлы создаются таким образом, что левое поддерево каждо-го узла содержит только те слова, которые меньше слова вэтом узле, а правое поддерево только те слова, которые боль-ше. Чтобы определить, находится ли новое слово уже в дереве,начинают с корня и сравнивают новое слово со словом, храня-щимся в этом узле. Если слова совпадают, то вопрос решаетсяутвердительно. Если новое слово меньше слова в дереве, топереходят к рассмотрению левого потомка; в противном случаеисследуется правый потомок. Если в нужном направлении пото-мок отсутствует, то значит новое слово не находится в деревеи место этого недостающего потомка как раз и является мес-том, куда следует поместить новое слово. Поскольку поиск излюбого узла приводит к поиску одного из его потомков, то сампроцесс поиска по существу является рекурсивным. В соответс-твии с этим наиболее естественно использовать рекурсивныепроцедуры ввода и вывода. Возвращаясь назад к описанию узла, ясно, что это будетструктура с четырьмя компонентами: STRUCT TNODE \( /* THE BASIC NODE */ CHAR *WORD; /* POINTS TO THE TEXT */ INT COUNT; /* NUMBER OF OCCURRENCES */ STRUCT TNODE *LEFT; /* LEFT CHILD */ STRUCT TNODE *RIGHT; /* RIGHT CHILD */\); Это "рекурсивное" описание узла может показаться рискован-ным, но на самом деле оно вполне корректно. Структура неимеет права содержать ссылку на саму себя, но STRUCT TNODE *LEFT; описывает LEFT как указатель на узел, а не как сам узел. Текст самой программы оказывается удивительно маленьким,если, конечно, иметь в распоряжении набор написанных намиранее процедур, обеспечивающих нужные действия. Мы имеем ввиду функцию GETWORD для извлечения каждого слова из файлаввода и функцию ALLOC для выделения места для хранения слов. Ведущая программа просто считывает слова с помощью функ-ции GETWORD и помещает их в дерево, используя функцию TREE. #DEFINE MAXWORD 20MAIN() /* 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 просачиваетсявниз либо к левому, либо к правому поддереву. В конце концовэто слово либо совпадает с каким-то словом, уже находящимсяв дереве (в этом случае счетчик увеличивается на единицу),либо программа натолкнется на нулевой указатель, свидетель-ствующий о необходимости создания и добавления к дереву но-вого узла. В случае создания нового узла функция TREE возв-ращает указатель этого узла, который помещается в родитель-ский узел. STRUCT TNODE *TREE(P, W) /* INSTALL W AT OR BELOW P */ STRUCT TNODE *P; CHAR *W; \( STRUCT TNODE *TALLOC(); CHAR *STRSAVE(); INT COND; IF (P == NULL) \( /* A NEW WORD HAS ARRIVED */ P == TALLOC(); /* MAKE A NEW NODE */ P->WORD = STRSAVE(W); P->COUNT = 1; P->LEFT = P->RIGHT = NULL; \) ELSE IF ((COND = STRCMP(W, P->WORD)) == 0) P->COUNT++; /* REPEATED WORD */ ELSE IF (COND < 0)/* LOWER GOES INTO LEFT SUBTREE */ 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 ---------------- Напишите программу, которая печатает слова из своегофайла ввода, расположенные в порядке убывания частоты их по-явления. Перед каждым словом напечатайте число его появле-ний.
