哈夫曼编码实验报告

实验1哈夫曼编码实验目的掌握哈夫曼编码原理，掌握哈夫曼树的生成方法。了解数据压缩。实验要求实现哈夫曼编解码生成算法。3、实验内容首先统计要压缩的文件中出现的字符和字母的数量，根据字符字母和空格的概率进行编码，然后读取要编码的文件并存储到另一个文件中；然后调出编码的文件，解码输出，最后存储到另一个文件中。5、实验原理1,哈夫曼树的定义：假设有n个权值，试着构造一个有n个叶子节点的二叉树，每个有权的叶子都是wi,其中权值路径最小的二叉树成为Huffman树或最优二叉树；2、Huffman树的构造：权值为输入频率数组，并且这些值在node对象中按data属性依次分配给HT,即每个HT节点对应一个输入频率。然后，根据数据属性，从最小值到最大值取两个最小值和这个小的HT节点，将它们的数据相加，构造一个新的htnode作为它们的父节点。指针parentleftchild,rightchild被分配了相应的值。将这个新节点插入最小堆。按照这个步骤，我们可以建造一棵树吗？通过构造的树，从下至上，从频率节点开始搜索父节点，直到父节点是树的顶点。这样，每次向上搜索后，根据原始节点是父节点的左子节点还是右子节点来记录I或0。这样，每个频率都有一个唯一对应的01码，任何没有前端的码都和其他完整码一样。初始化，以文本文件中的字符数为权值，生成Huffman树，按符号概率由大到小对符号进行排序，概率最小的两个符号形成一个节点。重复步骤()()，直到概率和为1,从根节点到每个符号对应的〃叶〃，概率高的符号标为，概率低的符号从根节点开始，对符号7进行编码。实验程序Sinclude<iostream>coinclude<iomanip>o:)include<iomanip>使用命名空间STD；typedefstruct〃节点结构{chardata；〃记录字符值longintweight；〃记录字符权重unsignedintparent,Ichild,rchild；}Htnode,*HuffmanTree；typedefchar**huffmancode；//dynamiclyallocatearraytostoreHuffmancodetablevoidselect(HuffmanTree&HT,inti,int&Sl,int&S2)〃选择HT[1中权重最小且父节点不为。的两个节点。。。T],它们的序列号是S1和S2{S1=O；S2=0；intNl=30000,N2=30000；for(intk=l；k<=l；k++){if(HT[k]\父项=0{if(HT[k])o重量<N1){N2=N1；Nl=HT[k]o重量；S2=S1；Sl=k；}否则(HT[k]o重量<N2){N2=HT[k]oWeight；S2=k；}}}}}voidhuffmancoding(HuffmanTree&HT,huffmancode&HCzintn)〃将要编码的字符串保存到空树中{ifstreamfinl(〃子夫txt〃)；ifstreamfin2("重量.txt")；if(n<=l)返回；intm=2*n-l；inti；HT=newhtnode[m+l]；char*Zifu；int*weight；weight=newchar[n+l]；weight=Newlnt[n+l]；for(1=1；l<=n；I++I++)〃将要编码的字符放入Zifu数组，{charch；ch=ch=finl.get()；Zifu[l]=ch=ch=finl.get()；Zifu[l]=ch；}for(1=1；l<=n；I++)〃/将编码字符对应的权重放入权重数组{fin2»weight[l]；}for(l=l=l»weight[l]；}{l=n=l=n(l=n=l+)；l=n=。数据=Zifu[i]；HT[i]o(i=n+l；i<=m;i++++++(i=i=n+l；i<=m；i++){HT[i].数据='@';}为(i=l;i<=m；i++){HT[i].父母=HT[i[i].lchild=HT[i[i].lchild=HT[i].rchild=O；}为(i=n+l;i<=m；m；++i){intsi,s2；选择(HT,i-1,sl,s2附选择(HTj-1花)；HT[sl]父母=i；HT[s2]父母=i[s2]父母=i；H[i[i[i[i]H[i]LCHIL[=s2；HT[i].Weight=HT[sl].Weight+HT[s2].Weight；}HC=(HuffmanCode)malloc((n+1)*sizeof(char*)；打开工作区进行编码：char*CD；CD=(char*)malloc(n*sizeof(char))；〃打开工作区存储权重：CD[n-l]='\0,；for(1=1；l<=n；I++){intstart=n-l；intc,f；for(c=l,f=HT[l]o家长；F!=0；C=fzf=HT[f]oParent)〃从叶到根的反向编码{if(HT[f[