Файл: ответы.doc

Рис. 6.20. Построение кодовой таблицы.

Для строки S будет получен следующий код b=11011110101000000. Длина кода составляет 17 бит, что меньше по сравнению с укороченным кодом. Алгоритм распаковки можно сформулировать следующим образом:

1. i:=0, j:=0;

2. если i > n, то стоп строка распакована, иначе i:=i+1;

3. node:= root;

4. если b(i) = 0, то node:=left(node), иначе node:=right(node)

5. если left(node) = 0 и right(node) = 0, то j:=j+1, s(j):= str(node),

перейти к шагу 2, иначе i:=i+1, перейти к шагу 4

В алгоритме корень дерева обозначен как root, а left(node) и right(node) обозначают левый и правый потомки узла node.

На практике такие способы упаковки используются не только для текстов, но и для произвольных двоичных данных. Любой файл можно рассматривать как последовательность байт. Тогда дерево кодирования можно построить не для символов, а для значений байт, встречающихся в кодируемом файле (рис. 6.21). Поскольку байт может принимать 256 значений, то соответствующее дерево будет иметь не более 256 листьев.

j

Рис. 6.21. Процесс распаковки кода.

В узлах дерева после его полного построения нет необходимости хранить несколько значений кодов и частоты повторения. Для кодирования и декодирования достаточно хранить только одно значение кода и только для листового узла. Поэтому такой способ представления кодовой таблицы является достаточно компактным. Схемы кодирования подобного типа используются в программах архивации данных и сжатия растровых изображений в форматах графических файлов.

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

С помощью деревьев можно представлять произвольные арифметические выражения (рис. 6.22-6.23). Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу - операция. В общем случае дерево при этом может оказаться не бинарным. Однако если число операндов любой операции будет меньше или равно двум, то дерево будет бинарным. Причем если все операции будут иметь два операнда, то дерево окажется строго бинарным.

-(A+B)*((C+cos(D+E)-f(a,b,c,d,e))

Рис. 6.22. Представление арифметического выражения произвольного вида в виде дерева.

f(a+b,sin c)

Рис. 6.23. Представление арифметического выражения в виде бинарного дерева.

Бинарные деревья могут быть использованы не только для представления выражений, но и для их вычисления (рис. 6.24). В листьях записываются значения операндов. Затем от листьев к корню производится выполнение операций. В процессе выполнения в узел операции записывается результат ее выполнения. В конце вычислений в корень будет записано значение, которое и будет являться результатом вычисления выражения.

(1+10)*5

Рис. 6.24. Вычисление арифметического выражения с помощью бинарного дерева.

Помимо арифметических выражений с помощью деревьев можно представлять выражения других типов, например, логические выражения (рис. 6.25). Поскольку функции алгебры логики определены над двумя или одним операндом, то дерево для представления логического выражения будет бинарным.

((aVb)&(cVd))&(e&fVa&b)

Рис. 6.25. Представление логического выражения в виде бинарного дерева.