ГоловнаЗворотній зв'язок

Алгоритмы структуры данных

Листинг 5.7. Процедура INSERT

procedure INSERT ( х: wordtype; var words: TRIE );

var

i: integer; { считает позиции в слове х }

t: TRIE; { используется для указания на узлы дерева,

соответствующие префиксу слова х }

begin

i:= 1;

t:= words;

while x[i] <> '$' do begin

if VALUEOF(t↑, x[i]) = nil then

{ если текущий узел не имеет сына для

символа х[і], то он создается }

GETNEW(t↑, x[i]);

t:= VALUEOF(t↑, x[i]);

{ продвижение к сыну узла t для символа х[1]}

і: = і + 1 { перемещение далее по слову х }

end;

{ в слове х достигнут первый символ '$' }

ASSIGN(t↑, '$' , t)

{ делает петлю на '$' для создания листа }

end; { INSERT }

Представление узлов нагруженного дерева посредством списков

Множество слов, которые имеют р различных префиксов и для хранения требуют 27р байт, можно представить посредством реализации узлов нагруженного дерева с помощью массивов фиксированной длины. Величина 27р байт может значительно превышать общую длину слов в множестве. Существует другая реализация нагруженных деревьев, которая экономит используемый объем памяти. Напомним, что мы рассматриваем каждый узел нагруженного дерева как отображение (см. раздел 2.6). В принципе, можно применить любую реализацию отображений, но мы хотим найти наиболее подходящую, область определения которых сравнительно мала. При таком условии наилучшим выбором будет реализация отображения посредством связанных списков. Здесь представлением отображения, т.е. узла нагруженного дерева, будет связанный список символов, для которых соответствующие значения не являются указателями nil. Такое представление можно сделать с помощью следующего объявления:

type

celltype  =  record

domain:   chars;

value:   ↑celltype;

{  указатель .на первую ячейку списка узла сына  }

next:   ↑celltype

{ указатель  на следующую ячейку списка  }

end;

Мы оставляем в качестве упражнений написание для данной реализации процедур ASSIGN, VALUEOF, MAKENULL и GETNEW. После создания этих процедур процедура INSERT из листинга 5.7 должна стать работоспособной программой.

 

71