Язык программирования C



         

Структуры, ссылающиеся на себя - часть 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




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