Главная Промышленная автоматика.

record

weight: real,-root: integer

Начальные значения всех трех массивов, соответствующих данным на рис. 3.15,а, показаны на рис. 3.16. Эскиз программы (псевдопрограмма, т.е. программа на псевдоязыке, как описано в главе 1) построения дерева Хаффмана представлен в листинге 3.8.

0.12

0.12

0.40

0.40

0.15

0.15

о.оа

0.08

0.25

0.25

Поля

weight root

symbol proba bility

- leaf

left-child

right-child

paren

Массивы FOREST

ALPHABET

TREE

Рис. 3.16. Исходное состояние массивов

Листинг 3.8. Программа построения дерева Хаффмана

(1) while существует более одного дерева в лесу do

begin

(2) i:= индекс дерева в WREST с наименьшим весом;

(3) j:= индекс дерева в FOREST со вторым наименьшим весом;

(4) Создание нового узла с левым сыном FOREST[ 1] . гооШ

правым сьшом FOREST[j].root;

(5) Замена в FOREST церева i деревом, чьим корнем является

новый узел и чей вес равен FORESTli] .weight + FOREST[j] . weight; (в) Удаление дерева j из массива WREST

end;

Для реализации строки (4) листинга 3.8, где увеличивается количество используемых ячеек массива TREE, и строк (5) и (6), где уменьшается количество ячеек массива FOREST, мы будем использовать курсоры lasttree (последнее дерево) и last node (последний узел), указываюшие соответственно на массив FOREST и массив TREE. Предполагается, что эти курсоры располагаются в первых ячейках соответствуюших массивов. Мы также предполагаем, что все массивы имеют определенную объявленную длину, но здесь мы не будем проводить сравнение этих ограничиваю-ших значений со значениями курсоров.

В листинге 3.9 приведены коды двух полезных процедур. Первая из них, lightones, выполняет реализацию строк (2) и (3) листинга 3.8 по выбору индексов двух деревьев с наименьшими весами. Вторая процедура, функция create(ni, Лг), создает новый узел и делает заданные узлы rai и пг левым и правым сыновьями этого узла.

Для этапа чтения данных, который мы опускаем, необходим таюке курсор для массива ALPHABET, который бы "следил" за заполнением данными этого массива.



Листинг 3.9. Две процедуры

procedure lightones { var least, second: integer ) ,-

{ присваивает переменным least и second индексы массива

FOREST, соответствующие деревьям с наименьшими весами. Предполагается, что lasttree > 2. }

i: integer; begin { инициализация least и second,

рассматриваются первые два дерева } if FORESTll] .weight <= FOREST[2] . weight then begin ieast;= 1; second:= 2 end

else

begin least:= 2; second:= 1 end for 1:= 3 to lasttree do

if EORESTli] .weight < FOREST[least] . weight then

begin second:= least; least: = i end else if FORESTli] .weight < FOREST[second] . weight then second: = i end; { lightones }

function create ( lefttree, rlghttree: integer ): integer;

{ возвращает новый узел, у которого левым и правым сыновь51ми становятся FOfi£Sr[ left tree] . root и FOR£Sr[rig/ittree] . root }

begin

Jastnode:= lastnode + 1;

{ ячейка ТД-Е-Е[Jastnode] для нового узла } TREE[lastnode].leftchild:= FORESTilefttree] .root; TREE[lastnode] . rightchild: = FORESTIrighttree] .root;

{ теперь введем указатели для нового узла и его сыновей } TREE[lastnode] .parent:= 0;

TREE[FOREST[lefttree] .root] .parent:= lastnode; TREE[FOREST[.righttree] .root] .parent: = lastnode; return (lastnode)

end; { create }

Теперь все неформальные операторы листинга 3.8 можно описать подробнее. В листинге 3.10 приведен код процедуры Huffman, которая не осуществляет ввод и вывод, а работает со структурами, показанными на рис. 3.16, которые объявлены как глобальные.

Листинг 3.10. Реализация алгоритма Хаффмана

procedure Huffman; var

i, j: integer; {два дерева с наименьшими весами из FOREST) newroot: integer; begin

while lasttree > 1 do begin lightonesd, j) ; newroot:= created, j) ;

{ далее дерево i заменяется деревом с корнем newroot } FOREST[i] .weight:=FOREST[i] .weight + FOREST[j] .weight; FORESTIi] .root: = newroot;

{ далее дерево j заменяется на дерево lasttree, массив EOREST уменьшается на одну запись }



FORESTfjJ := FOREST[lasttree] ; lasttree:= lasttree - 1

end,- { Huffman }

Ha рис. 3.17 показана структура данных из рис. 3.16 после того, как значение переменной lasttree умеяъшеяо до 3, т.е. лес имеет вид, показанный на рис. 3.15,в.

0.25

0,40

0,35

weight root FOREST

0.12

0.40

-* 2

0.15

-► 3

0.08

» 4

0.25

ymbol

proba

- leaf

bility

ALPHABET

Рис. 3.17. Структура данных после двух итераций

left- right- parent child child

TREE

После завершения работы алгоритма код каждого символа можно определить сле-дуюшим образом. Найдем в массиве ALPHABET запись с нужным символ в поле symbol. Затем по значению поля leaf эпоя же записи определим местоположение записи в массиве TREE, которая соответствует листу, помеченному рассматриваемым символом. Далее последовательно переходим по указателю parent от текушей записи, например соответствуюшей узлу п, к записи в массиве TREE, соответствуюшей его родителю р. По родителю р определяем, в каком его поле, leftchildvuivi rightchild, находится указатель на узел п, т.е. является ли узел га левым или правым сыном, и в соответствии с этим печатаем О (для левого сына) или 1 (для правого сына). Затем переходим к родителю узла р и определяем, является ли его сын р правым или левым, и в соответствии с эти печатаем следующую 1 или О, и т. д. до самого корня дерева. Таким образом, код символа будет напечатан в виде последовательности битов, но в обратном порядке. Чтобы распечатать эту последовательность в прямом порядке, надо каждый очередной бит помешать в стек, а затем распечатать содержимое стека в обычном порядке.

Реализация двоичных деревьев с помощью указателей

Для указания на правых и левых сыновей (и родителей, если необходимо) вместо курсоров можно использовать настояшие указатели языка Pascal. Например, можно сделать объявление

type

node = record

leftchild: Т node; rightchild: t node; parent: t node





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 [28] 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0015