利用哈夫曼编码实现压缩和解压缩.doc

《利用哈夫曼编码实现压缩和解压缩.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、利用哈夫曼编码实现压缩和解压缩1.问题描述利用哈夫曼编码，实现压缩和解压缩的数据元素具有如下形式:结点：weightparentlchildrchildweight:存储结点的权值parent:是结点双亲在向量中的下标lchild:结点的左儿子向量下标rchild:结点右儿子向量下标编码：bitschstartbits:位串，存放编码ch:字符start:编码在位串中的起始位置文件操作记录：bcountlchparentbitsrchb:记录字符在数组中的位置count:字符出现频率（权值）lch、rch、pa

2、rent:定义哈夫曼树指针变量bits[256]:定义存储哈夫曼编码的数组2.功能需求对于给定的一组字符，可以根据其权值进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。能够分析文件，统计文件中出现的字符，再对文件进行编码，实现文件的压缩和解压缩，能够对于文件的压缩，比例进行统计，能够打印文件。3.实现要点（1）构造哈弗曼树过程中，首先将初始森林的各根结点的双亲和左、右儿子指针置-1；叶子在向量T的前n个分量中，构成初始森林的n个结点；对森林中的树进行n次合并，并产生n-1个新结点，依次放入向

3、量T的第i个分量中。（2）编码过程中，从叶子T[i]出发，利用双亲的指针找到双亲T[p]；再根据T[p]的孩子指针可以知道T[i]是T[p]的左儿子还是右儿子，若是左儿子，则生成代码0，否则生成代码1；（3）在文件压缩和解压过程中，主要参考网上资料，每个步骤都基本理解，并注上了详细解析。4．函数定义功能：输入权重，构造一棵哈弗曼树voidhuffman(hftreeT){if(n<1

4、

5、n>m)return;inti,j,p1,p2;floatsmall1,small2;//初始化cout<<"请输入叶子权重(

6、5个)："<>T[i].weight;}for(i=n;i

7、[j].weight;p2=p1;p1=j;}elseif(T[j].weight

8、cout<<"请输入需要编码的字符(5个)："<>codes[i].ch;start=n;c=i;p=T[i].parent;while(p!=-1){start--;if(T[p].lchild==c)codes[i].bits[start]='0';elsecodes[i].bits[start]='1';c=p;p=T[p].parent;}codes[i].start=start;}cout<<"输入成功！："<

9、>b,b!=endflag){if(b==0)i=T[i].lchild;elsei=T

10、[i].rchild;if(T[i].lchild==-1){cout<