Язык С




Структуры, ссылающиеся на себя - часть 3


Память для нового узла выделяется функцией 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 в виде




Содержание  Назад  Вперед