哈弗曼编码的实现

《哈弗曼编码的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、如何实现哈夫曼编码 一、编码【题目描述】给定一篇用于通信的英文电文，统计该电文中每个字符出现的频率，按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树，并编出每个字符的哈夫曼树码，输出该电文的哈夫曼码译文。 【输入】输入文件huffman.in是一篇用于通信的英文电文。【输出】输出文件huffman.out输出该电文的哈夫曼码译文。 【输入输出样例1】huffman.in                             huffman.outaaccdddbacbcddddddd011011000

2、011101001100010001111111【数据限制】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   右孩子节点的数组下标r

3、ch0000   权值w32410   -》数组下标1234567父节点的数组下标parent55000  左孩子节点的数组下标lch00002  右孩子节点的数组下标rch00001  权值w324105  -》.。。。。。。。。数组下标1234567父节点的数组下标parent5567670左孩子节点的数组下标lch0000256右孩子节点的数组下标rch0000134权值w324105919 structnode2{ charch;//对应的字符abcd intstart;//编码的起始位置注意这个编码是倒着

4、的所以这里用start intcode[N0];//这个是编码数组}hc[N0+1];大概图如下面下面给出大家想要的程序部分viewplaincopytoclipboardprint?//#include "stdio.h"  //#include   "string.h "   #include   #include   const int N0=10;  const int N=100;  const int INF=1000000;  struct node1   { in

5、t 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( "huffman.in", "r", stdin);//读文本文件   while( (ch=getchar()) != EOF

6、 )    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]

7、.parent==0 )     if( ht[i].w

8、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;