47394 (Компрессия информации и упорядочение дерева по алгоритму Виттера), страница 2
Описание файла
Документ из архива "Компрессия информации и упорядочение дерева по алгоритму Виттера", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "47394"
Текст 2 страницы из документа "47394"
if P<>nil then
begin
if not P. Isleaf then
begin
Result: =CheckWiegth(P. left) +CheckWiegth(P. right);
P. Wiegth: =Result;
end else Result: =P. Wiegth;
end else
Result: =0;
end;
procedure Huffman(P: PTree);
var
i,j,k: integer;
t,tt: PTree;
tmp: TTree;
begin
k: =1;
t: =GetNodeByNumber(P,k);
while t<>nil do
begin
tt: =GetNodeByNumber(P,k+1);
if tt<>nil then
begin
if tt. Wiegth begin move(tt^,tmp,sizeof(tmp)); move(t^,tt^,sizeof(tmp)); move(tmp,t^,sizeof(tmp)); CheckWiegth(P); Enumerate(P); k: =1; end; end; inc(k); T: =GetNodeByNumber(P,k); end; end; procedure Vitter(P: PTree); var i,j,k,l: integer; t,tt,ttt: PTree; tmp: TTree; begin k: =1; t: =GetNodeByNumber(P,1); while t<>nil do begin if not T. IsLeaf then begin tt: =GetLeafByWiegthMax(P,t. wiegth); if(tt<>nil) then begin if(tt. Number>T. Number) then begin move(tt^,tmp,sizeof(tmp)); move(t^,tt^,sizeof(tmp)); move(tmp,t^,sizeof(tmp)); CheckWiegth(P); Enumerate(P); k: =1; end; end; end; inc(k); T: =GetNodeByNumber(P,k); end; end; function GetLeafByWiegthMax(P: PTree; wiegth: integer): PTree; var i: integer; Node: PTree; begin Result: =nil; i: =1; Node: =GetNodeByNumber(P, i); while Node<>nil do begin if Node. Wiegth > wiegth then exit; // ??????? if Node. IsLeaf and (Node. Wiegth=wiegth) then begin Result: =Node; end; inc(i); Node: =GetNodeByNumber(P, i); end; end; function GetNodeByNumber(P: PTree; number: integer): PTree; begin if(P<>nil) then begin if P. Number=number then result: =P else begin Result: =GetNodeByNumber(P. Left,number); if Result=nil then Result: =GetNodeByNumber(P. Right,number); end; end else Result: =nil; end; procedure Enumerate(P: PTree); var i,j,k,l,n,o,s: integer; T: PTree; begin n: =0; k: =MaxLevel(P); for i: =k downto 1 do begin o: =1; s: =1; l: =1; T: =GetNodeFromLevel(P, i,l,o,s); while T<>nil do begin inc(n); T. Number: =n; inc(l); o: =1; s: =1; T: =GetNodeFromLevel(P, i,l,o,s); end; end; end; function GetNodeFromLevel(P: PTREE; level,number: integer; var l,n: integer): PTree; var T: PTRee; begin result: =nil; if(P<>nil) then begin if(l begin inc(l); T: =GetNodeFromLevel(P. Left,level,number,l,n); dec(l); if(T=nil) then begin inc(l); Result: =GetNodeFromLevel(P. Right,level,number,l,n); dec(l); end else Result: =T; end else begin if(l=level) then begin if(n=number) then result: =P else begin result: =nil; end; inc(n); end else result: =nil; end; end else result: =nil; end; procedure NodesOnLevel(Top: PTree; var qol: integer; l,level: integer); begin if Top<>nil then begin if level=l then begin inc(qol); end else begin NodesOnLevel(top. Left,qol,l+1,Level); NodesOnLevel(top. Right,qol,l+1,Level); end; end; end; function MaxLevel(Top: PTree): integer; begin if(Top=nil) then begin Result: =0; end else begin Result: =Max(MaxLevel(Top. Left),MaxLevel(Top. Right)) +1; end; end; function AddSymbol(var Top: PTree; c: char): boolean; begin if(not AddSymbolToTree(Top,c)) then if(not AddNewSymbolToTree(Top,c)) then result: =false // Error else result: =true // Added else result: =false; // Updated end; function AddSymbolToTree(var Top: PTree; c: char): boolean; begin if Top=nil then Result: =False else begin if Top. IsLeaf then begin if Top. Symbol=c then begin inc(Top. Wiegth); result: =true; end else begin result: =false; end; end else begin if AddSymbolToTree(Top. left,c) or AddSymbolToTree(Top. right,c) then begin inc(Top. Wiegth); result: =true; end else result: =false; end; end; end; function AddNewSymbolToTree(var Top: PTree; c: char): boolean; begin if Top=nil then begin Top: =NewNode(nil,nil,nil,#0,1,0,false); Top. left: =NewNode(nil,nil,Top,#0,0,0,true); Top. Right: =NewNode(nil,nil,Top,c,1,0,true); result: =true; end else begin if (Top. Wiegth=0) and (top. Symbol=#0) then begin Top. Left: =NewNode(nil,nil,Top,#0,0,0,true); Top. Right: =NewNode(nil,nil,Top,c,1,0,true); Top. IsLeaf: =false; Top. Wiegth: =1; Result: =true; end else begin if (Top. Left<>nil) and AddNewSymbolToTree(Top. Left,c) then begin result: =true; exit; end; if (Top. Right<>nil) and AddNewSymbolToTree(Top. Right,c) then begin result: =true; exit; end; result: =false; end; end; end; procedure DeleteTree(var P: PTree); begin if P=nil then exit; DeleteTree(P. Left); DeleteTree(P. Right); Dispose(P); P: =nil; end; function NewNode(l,r,u: ptree; s: char; c,n: integer; i: boolean): PTree; var P: PTree; begin new(P); P. Left: =l; P. Right: =r; P. Up: =u; P. Symbol: =s; P. Wiegth: =c; P. Number: =n; P. IsLeaf: =i; result: =P; end; end.