哈弗曼编码 压缩技术.doc

《哈弗曼编码 压缩技术.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include#incIude#defineMax300〃故多设置的字符数，在哈夫曼树屮做叶了usingnamespacestd;typedefstruct{chardata;〃待编码的字符intweight;〃字符的权值intparent,lchild,rchild;}HTNode,*HuffmanTree;〃动态分配数组存储郝夫曼树〃动态分配数纽•存储郝夫曼编码typedefchar**HuffmanCode;//设置全局变量intn;//叶子结点个数boolopen;//open=l文件打开成功，否则打开失败intReacKH

2、uffmanTree&HT,charfilename[100])//读入文件，统计字符{inti=l,j,k,m=0;charch;HT=(HuffmanTree)malloc(Max*sizeof(HTNode));〃0号单元未用，预分配2*Max个单元for(j=0;jvMax;j++)HT[j].weight=0;ifstreaminfile(filename,ios::binary);//fflifstream类定义文件流对象infile,以输入方式打开进制文件，打开成功，贝坟件流对彖返回非0值，否则返回0if(!infile)//出错处理，向显示器输出岀错信息{

3、cout«n没有找到文件！”；open二false;exit(O);}//从文件data.txt屮把字符依次读入，并统计每个字体符出现的次数即是它们的权值，//——每出现一个新的字符就把它存到数组HT[i].data屮，如果以前已经出现了就在该字符的权值下加一cout«n待编码的字符为："；while(infile.get(ch)){if(ch=='*)break;cout«ch;for(k=l;k

4、ht++;m++;}//最后HT的数组的长度即统计的字符的个数即是叶了结点的个数n=i-l;infile.close();open=true;returnm;}voidInit(HuffmanTree&HT)〃初始化哈弗曼树{inti;//起初把左右孩子结点及双亲都赋为0for(i=l;i<2*n;i++){HT[i].parent=O;HT[i].lchild=O;HT[i].rchild=O;1for(i=n+1;i<2*n;i++)HT[i].weight=0;}〃选择n个(这里是k=n)节点屮权值最小的两个结点voidSelect(HuffmanTree&HT,i

5、ntk,int&si,int&s2){inti=l;while(i<=k&&HT[i].parent!=O)i++;〃下面选出权值最小的结点，用si指向其序号sl=i;for(i=l;i<=k;i++){if(HT[i].parent==O&&HT[i].weight

6、[s2].weight)s2=i;}}〃构造Huffman树，求出n个字符的编码voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC){intm,c,f,s1,s2,i,start;char*cd;m=2*n-l;//n个叶子2n-l个结点if(n!=l){for(i=n+1;iv=m;i++){Select(HT,i-l,s1,s2);〃选出当前权值最小的HT[sl].parent=i;HT[s2].parent=i;HT[i].lchild=sl;HT[i].rchild=s2;HT[i].weight=HT[s1].weig

7、ht+HT[s2].weight;}〃从叶子到根逆向求每个字符的郝夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针变量cd=(char*)malloc(n*sizeof(char));〃分配求编码的工作空间cd[n・l]-(y；〃编码结束符for(i=l;i<=n;i++)〃逐个字符求郝夫曼编码{start=n-1;〃编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)〃从叶子到根逆向求编码{i