TABLES7 (1131492), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

#define PRIME 211
#define EOS '\0'
int Hashpjw(char *s)
{ char *p;
unsigned H=0, g;
for (p=s; *p != EOS; p=p+1)
{H=(H<<4)+(*p);
if (g = H & 0xf0000000)
{H=H^(g>>24);
H=H^g;
} }
return H%PRIME;
}

Рис. 6.5

6.5. Таблицы на деревьях

Рассмотрим еще один способ организации таблиц с использованием двоичных деревьев. Будем считать, что на множестве идентификаторов задан некоторый линейный порядок (например, лексикографический), т.е. задано некоторое отношение '<', транзитивное, антисимметричное и антирефлексивное. Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставлен идентификатор. Вершина может иметь нуль, одного (правого или левого) или двух (правого и левого) потомков. Если вершина имеет левого потомка, то идентификатор, сопоставленный левому потомку, меньше идентификатора, сопоставленного самой вершине; если имеет правого потомка, то ее идентификатор больше. Элемент таблицы изображен на рис. 6.6.

TP Ident



Left Right

Рис. 6.6

struct TreElement
{struct TreElement * Left, * Right;
String IdenP;
};

Поиск в такой таблице может быть описан следующей процедурой:

TreElement * SearchTree(String Id,TreElement * TP)
{int comp;
if (TP==NULL) return NULL;
comp= IdComp(Id,TP->IdenP);
if (comp<0) return(SearchTree(Id,TP->Left));
if (comp>0) return(SearchTree(Id,TP->Right));
return TP;
}

Занесение в таблицу осуществляется функцией:

TreElement * InsertTree(String Id,TreElement * TP);
TreElement * fill(TreElement * P, String Id)
{ if (P==NULL)
{P=new TreElement();
P->IdenP=Include(Id);
P->Left=NULL;
P->Right=NULL;
return(P);
}
else return(InsertTree(Id,P));
}
TreElement * InsertTree(String Id,TreElement * TP)
{int comp= IdComp(Id,TP->IdenP);
if (comp<0) return(fill(TP->Left,Id));
if (comp>0) return(fill(TP->Right,Id));
return(TP);
}

Как показано в работе [7], среднее время поиска и занесения в таблицу размера n, организованную в виде двоичного дерева, при равной вероятности появления каждого объекта равно 2ln(2)log2(n)+C, что превышает на 40% среднее время поиска в упорядоченном массиве методом двоичного поиска. Это превышение обусловлено тем, что дерево неизбежно оказывается несбалансированным: имеются более длинные и более короткие ветви.

Чтобы ускорить среднее время поиска в двоичном дереве, можно в процессе построения дерева следить за тем, чтобы оно все время оставалось сбалансированным. А именно, назовем дерево сбалансированным, если ни для какой вершины высота правого поддерева не отличается от высоты левого более чем на 1. Ясно, что для того, чтобы достичь сбалансированности, в процессе построения дерево иногда приходится слегка перестраивать [8]. Определим для каждой вершины дерева характеристику, равную разности высот правого и левого ее потомков. Для сбалансированного дерева характеристика вершины может быть равной -1, 0 и 1, для листьев она равна 0). Пусть мы определили место новой вершины в дереве. Ее характеристика равна 0. Рассмотрим отрезок пути от новой вершины к корню, такой, что характеристики всех вершин на нем равны 0 (до перестраивания). Пусть A - верхний (ближайший к корню) конец этого отрезка. A - либо корень, либо имеет характеристику 0. Если A - корень, то дерево перестраивать не надо, достаточно лишь изменить характеристики вершин на нем на 1 или -1, в зависимости от того, влево или вправо пристроена новая вершина.

Если верхний конец A отрезка с характеристикой 0 не корень, то возможны следующие варианты. Если A имеет характеристику 1 (-1) и новая вершина добавляется в правое (левое) поддерево, то характеристика вершины A становится равной 0 и дерево перестраивать не надо.

Пусть теперь характеристика A до перестраивания равна -1 и новая вершина добавлена к левому поддереву A (аналогично - для случая 1 и добавления к правому поддереву). Возможны следующие варианты.

A(-2,n+3) B(0,n+2)




B(-1,n+2)
C(n) D(n+1) A(0,n+1)

D(n+1) E(n)
E(n) C(n)



Новая вершина
(а) (б)

Рис. 6.7

A(-2,n+3)) E(0,n+2)



B(1,n+2) C(n)

D(n) B(0,n+1) A(1,n+1)
E(-1,n+1)

F(n) G(n-1) D(n) F(n)G(n-1) C(n)




Новая вершина
а) б)
Рис. 6.8

A(-2,n+3)) E(0,n+2)



B(1,n+2) C(n)

D(n) B(-1,n+1) A(0,n+1)
E(-1,n+1)


F(n-1) G(n) D(n) F(n-1) G(n) C(n)





Новая вершина
а) б)
Рис. 6.9

Рассмотрим вершину B - левого потомка A. Если характеристика B после добавления новой вершины в D стала равна -1, то дерево имеет структуру, изображенную на рис. 6.7(а). Перестроив дерево так, как это изображено на рис. 6.7(б), мы добьемся сбалансированности (в скобках указаны характеристики вершин, где это существенно, и соотношения высот после добавления).

A(-2,2) E(1,0)


B(1,1) B(0,0) A(0,0)


E(0,0)

Новая вершина

Рис. 6.10

Если характеристика вершины B после добавления новой вершины в E стала равна 1, то надо отдельно рассмотреть случаи, когда характеристика вершины E, следующей за B на выделенном пути, стала равна -1, 1 и 0 (в последнем случае вершина E - новая). Вид дерева до и после перестройки для этих случаев показан соответственно на рис. 6.8, 6.9 и 6.10.

6.6. Реализация блочной структуры

С точки зрения структуры программы блоки (и/или процедуры) образуют дерево. Каждой вершине дерева этого представления, соответствующей блоку, можно сопоставить свою таблицу объектов (и, возможно, одну общую таблицу идентификаторов). Работу с таблицами блоков можно организовать в магазинном режиме: при входе в блок создавать таблицу объектов, при выходе - уничтожать. При этом сами таблицы должны быть связаны в упорядоченный список, чтобы можно было просматривать их в порядке вложенности (рис. 6.11). Если таблицы организованы с помощью функций расстановки, это означает, что для каждой таблицы должна быть создана своя таблица расстановки.

T1 T2 Tn

Рис. 6.11

6.7. Сравнение различных методов реализации таблиц

Рассмотрим преимущества и недостатки тех или иных методов реализации таблиц с точки зрения техники использования памяти. Если таблица размещается в массиве, то, с одной стороны, отпадает необходимость использования динамической памяти, а с другой - появляется ряд осложнений. Использование динамической памяти, как правило, довольно дорогая операция, поскольку механизмы поддержания работы с динамической памятью довольно сложны. Необходимо поддерживать списки свободной и занятой памяти, выбирать наиболее подходящий кусок памяти при запросе, включать освободившийся кусок в список свободной памяти и, возможно, склеивать куски свободной памяти в списке. С другой стороны, использование массива требует отведения заранее довольно большой памяти, а это означает, что значительная память вообще не будет использоваться. Кроме того, часто приходится заполнять не все элементы массива (например, в таблице идентификаторов или в тех случаях, когда в массиве фактически хранятся записи переменной длины, например если в таблице символов записи для различных объектов имеют различный состав полей). Обращение к элементам массива может означать использование операции умножения при вычислении индексов, что может замедлить исполнение. Наилучшим, по-видимому, является механизм доступа по указателям и использование факта магазинной организации памяти в компиляторе. Для этого процедура выделения памяти выдает необходимый кусок из подряд идущей памяти, а при выходе из процедуры вся память, связанная с этой процедурой, освобождается простой перестановкой указателя свободной памяти в состояние перед началом обработки процедуры. В чистом виде это не всегда, однако, возможно. Например, локальный модуль в Модуле-2 может экспортировать некоторые объекты наружу. При этом схему реализации приходится "подгонять" под механизм распределения памяти. В данном случае, например, необходимо экспортированные объекты вынести в среду охватывающего блока и свернуть блок локального модуля.

112

Характеристики

Список файлов ответов (шпаргалок)