相关代码 |
|
program haffman(input,output);（利用哈夫曼树编码和译码）
const
p=30;
q=60-1;
type
nodetype=RECORD
weight:integer;(树的权值)
data: char;（结点元素）
parent,lch,rch:integer;
end;
codetype=RECORD
bits:ARRAY[1..p] of integer;（编码串）
start:integer;（起始字母）
end;
hufftree=ARRAY[1..q] OF nodetype;
huffcode=ARRAY[1..p] OF codetype;
var
bht, ht:hufftree;
bhcd, hcd:huffcode;
ch:char;
m,n:integer;
f:boolean;
FUNCTION select_s(t:integer):integer;（在结点中选择一个双亲为0权值最小的结点）
var
j,weight,min:integer;
BEGIN
weight:=1000;（权值最大不超过1000）
for j:=1 to t do
if ((ht[j].parent=0) AND(ht[j].weight then begin
min:=j;
weight:=ht[j].weight;
end;
ht[min].parent:=t+1;
select_s:=min
end;
PROCEDURE huffman_code(var ht:hufftree; var hcd:huffcode);（根据哈夫曼树编码）
var
i,j,c,f,x,s1,s2:integer;
cd:codetype;
ch:char;
begin
writeln('input the node number n');（叶子结点个数N）
readln(n);
m:=2*n-1;
i:=1;
while (i begin
readln(ch,x);
ht[i].data:=ch;
ht[i].weight:=x;
i:=i+1;
end;
for i:=1 to m do（编码初始化）
begin
ht[i].parent:=0;
ht[i].lch:=0;
ht[i].rch:=0;
end;
for i:= (n+1) to m do（进行N-1次和并，产生N-1个非叶子结点）
begin
s1:=select_s(i-1);
s2:=select_s(i-1);
ht[s1].parent:=i;
ht[s2].parent:=i;
ht[i].lch:=s1;
ht[i].rch:=s2;
ht[i].weight:=ht[s1].weight+ht[s2].weight;
end;
for i:=1 to n do
begin（编码表的初始化）
cd.start:=n;
c:=i;
f:=ht[c].parent;
while (f0) do
begin
if (ht[f].lch=c)（建立编码元素）
then cd.bits[cd.start]:=0
else cd.bits[cd.start]:=1;
c:=f;
f:=ht[f].parent;
cd.start:=cd.start-1;
end;
for j:=1 to cd.start do（读的初始化）
cd.bits[j]:=-1;
hcd[i]:=cd;（记录赋值）
end;
for i:= 1 to n do（输出编完的码元素）
begin
write(ht[i].data);
for j:= 1 to n do
if ( hcd[i].bits[j] -1 )（不同于0，1的结束符-1）
then write(hcd[i].bits[j]);
writeln;
end;
end;{huffman}
PROCEDURE huffman_yima(ht:hufftree;hcd :huffcode);（根据哈夫曼树及其编码来译码）
const
r=100;
var
i,j,k,c,m:integer;
ch:char;
a:array[1..r] of '0'..'1';
begin
i:=0;
m:=2*n-1;
writeln;（读入密码，并将其存入A[I]中。一个一个读）
writeln('input the code number **end with "?"**');
read(ch);
while ch'?' do
begin
if ((ch='0')or(ch='1'))
then begin
i:=i+1;
a[i]:=ch
end;
read(ch）
end;
j:=1;
if ((n=0)or(n=1)) then writeln('there was no huffman code')
else if (j then while (j begin
c:=m;
k:=0;
while (ht[c].lch0) do（找到密码响应的叶子接点）
begin
if j then if (a[j]='0')
then c:=ht[c].lch
else c:=ht[c].rch
else begin
writeln;
write ('the last ',k,'number are wrong');
ht[c].lch:=0;
end;
j:=j+1;
k:=k+1;（继续查找下一个结点）
end;
if (j end
else writeln('wrong input');
writeln;
end;{huffman_yima}
BEGIN
ch:='c';
f:=true;
repeat
if ch='c'
then begin
huffman_code( ht,hcd);
bht:=ht;
bhcd:=hcd;
writeln('well come to this program,please press --E -exit. C-bianma. T-yima');
read(ch);（建立操作菜单：E为退出；C为编码；T为译码）
end
else if ch='t'
then begin
huffman_yima(bht,bhcd);
writeln('well come to this program,please press --E -exit. C-bianma. T-yima');
readln;
read(ch);
end
else f:=false;
until (not (f));
end.
相关资源 |
|