新建 文本文档.txt

建树方法：每次选取最小权建树

1：0110 2：0111 3：010 4：110 5：111 5^：00 7^：10
program haff(input,output);
var
  arr:array[1..100]of record  {用于存储哈夫曼树 cl,cr为左右儿子 pa为双亲节点}
    cl,cr,pa:integer;         {da：权 ch:字符} 
    da:integer;
    ch:char;
    end;
  rec:array[#1..#255]of record  {记录字符的哈夫曼编码}
    rd:array[1..10]of 0..1;
    st:integer;
    ar:integer;
    end;
  se:set of #1..#255;            {记录字符（即该字符是否出现过）}
  i,j,k,t:integer;
  m,n:integer;
  ch:char;
  mia,mib:integer;
begin
  {读字符计算出现次数}
  read(ch);
  i:=0;
  while ch<>'#' do
    begin
      if ch in se
         then arr[rec[ch].ar].da:=arr[rec[ch].ar].da+1
         else begin
              i:=i+1;
              rec[ch].ar:=i;
              arr[i].da:=1;
              arr[i].ch:=ch;
              se:=se+[arr[i].ch];
              end;
      read(ch);
    end;
  {根据次数（权）建二叉树}
  n:=i;
  m:=2*n-1;
  for i:=n+1 to m do
    begin
      arr[i].ch:=chr(i);
      mia:=1;
      while arr[mia].pa<>0 do mia:=mia+1;
      mib:=mia+1;
      while arr[mib].pa<>0 do mib:=mib+1;
      for j:=mib+1 to i-1 do
        if ((arr[j].da<arr[mib].da)and(arr[j].pa=0))
           then begin
             mib:=j;
             if (arr[mia].da>arr[mib].da)
                then begin
                  t:=mia;
                  mia:=mib;
                  mib:=t;
                  end;
             end;
      arr[mia].pa:=i;
      arr[mib].pa:=i;
      arr[i].cl:=mia;
      arr[i].cr:=mib;
      arr[i].da:=arr[mia].da+arr[mib].da;
  end;
  {根据二叉树建立哈夫曼编码}
  for j:=1 to n do
    begin
      i:=j;
      ch:=arr[i].ch;
      repeat
        if i=arr[arr[i].pa].cl
           then begin
             rec[ch].st:=rec[ch].st+1;
             rec[ch].rd[rec[ch].st]:=0;
             end;
        if i=arr[arr[i].pa].cr
           then begin
             rec[ch].st:=rec[ch].st+1;
             rec[ch].rd[rec[ch].st]:=1;
           end;
        i:=arr[i].pa;
      until i=0;
    end;
  {输出}
  for ch:=#1 to #255 do
   if ch in se then
   begin
    write(ch,': ');
    for k:=rec[ch].st downto 1 do
      write(rec[ch].rd[k]);
    writeln;
   end;

end