哈弗曼编码实现.doc

文档介绍：如何实现哈夫曼编码 一、编码【题目描述】给定一篇用于通信的英文电文,统计该电文中每个字符出现的频率,按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树,并编出每个字符的哈夫曼树码,输出该电文的哈夫曼码译文。 【输入】。【输出】。 【输入输出样例1】                             **********【数据限制】2<=英文电文字符数<=10000000统计以上abcd出现的个数。a:3   b:2   c:4   d:10构造出哈夫曼树a:011        b:010    c  :00         d:1下面主要通过两个结构体数组来实现:structnode1{ intw,lch,rch,parent;}ht[2*N0-1+1];数组下标1234567父节点的数组下标parent0000   左孩子节点的数组下标lch0000   右孩子节点的数组下标rch0000   权值w32410   -》数组下标1234567父节点的数组下标parent55000  左孩子节点的数组下标lch00002  右孩子节点的数组下标rch00001  权值w324105  -》.。。。。。。。。数组下标1234567父节点的数组下标parent5567670左孩子节点的数组下标lch0000256右孩子节点的数组下标rch0000134权值w324105919 structnode2{ charch;//对应的字符abcd intstart;//编码的起始位置注意这个编码是倒着的所以这里用start intcode[N0];//这个是编码数组}hc[N0+1];大概图如下面下面给出大家想要的程序部分viewplaincopytoclipboardprint?//#include ""  //#include   " "   #include <iostream>  #include <string>  const int N0=10;  const int N=100;  const int INF=1000000;  struct node1   { int w, lch, rch, parent;  }ht[2*N0-1+1];  struct node2  { char ch;   int start;   int code[N0];  }hc[N0+1];  int n,root;//n为叶子的个数  void readData()  { char ch;  int num[256]={ 0 };   n=0;   freopen( "", "r", stdin);//读文本文件   while( (ch=getchar()) != EOF )    num[ch]++;   for( int i=0; i<=255; i++ )   { if( num[i] )    { n++;     ht[n].w=num[i];     hc[n].ch=i;    }   }  }  void select1( int t, int *s1, int *s2)//用两个数来记录没有在树上的最小的两个值,从而进一步生成树。  { int w1,w2;   w1=w2=INF;   for( int i=1; i<=t; i++ )    if( ht[i].parent==0 )     if( ht[i].w<w1 )     { w2=w1;      *s2=*s1;      w1=ht[i].w;      *s1=i;     }     else if( ht[i].w<w2 )     { w2=ht[i].w;      *s2=i;     }  }   void createHufTreeHuCode()  { int i, s1, s2;   int child, parent;   root=2*n-1;   for( i=n+1; i<=root; i++)   { select1(i-1, &s1, &s2 );    ht[i].w=ht[s1].w+ht[s2].w;    ht[i].lch=s1;    ht[i].rch=s2;    ht[s1].parent=ht[s2].parent=i;   }   for(  i=1; i<=n; i++)   { child=i;    while( child != root )    {