哈夫曼110.txt

这是一个数据结构常用的算法叫huffman编码.是对一棵二叉树进行huffman编码的算法

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<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<=n) do（将读入的字母和数字赋值给树的结点和权）
             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 (f<>0) 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<=i)（求子串相应的字符）
                          then  while (j<=i)  do
                           begin
                            c:=m;
                            k:=0;
                            while (ht[c].lch<>0) do（找到密码响应的叶子接点）
                            begin
                             if j<=i
                              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<=i+1) then write (ht[c].data);（输出字母）
                     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.