哈夫曼编码实验报告

1、哈夫曼编码实验报告实验一哈夫曼编码一、实验目的1、掌握哈夫曼编码原理;2、熟练掌握哈夫曼树的生成方法;3、理解数据编码压缩和译码输出编码的实现。二、实验要求实现哈夫曼编码和译码的生成算法。三、实验内容先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。五、实验原理1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树,每个叶子带权值为wi,其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树;2、哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立的HTNode对象中的data属性，即每一个HTNode对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HTNode,将他们的data相加，构造出新的HTNode作为他们的父节点,指针parent,leftchild,rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树o通过已经

2、构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子,来记录1或0,这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。六、实验流程初始化，统计文本文件中各字符的个数作为权值，生成哈夫曼树；根据符号概率的大小按由大到小顺序对符号进行排序；把概率最小的两个符号组成一个节点； 重复步骤(2)(3),直到概率和为1； 从根节点开始到相应于每个符号的“树叶”,概率大的标“0”，概率小的标“1”； 从根节点开始，对符号进行编码; 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。七、实验程序#include#include#include#includeusingnamespacestd;typedef struct节点结构char data;long int weight;/记录字符值/记录字符权重unsignedintparentjchild,rchild;JHTNode/HuffmanTree;动态分配数组存储哈夫曼树typed

3、efchar*HuffmanCode;动态分配数组存储哈夫曼编码表voidSelect(HuffmanTree&HT,intijnt&s1,int&s2)在HT1.t中选择parent不为0且权值最小的两个结点，其序号分别为si和s2s1=0;s2=0;intn1=300005n2=30000;for(intk=1;k=i;k+)if(HTk.parent=O)(if(HTk.weightn1)(n2=n1;n1=HTk.weight;s2=s1;s1=k;)elseif(HTk.weightn2)(n2=HTk.weight;s2=k;)voidHuffmanCoding(HuffmanTree&HT5HuffmanCode&HC,intn)将要编码的字符串存入空树中ifstreamfin1(,fzifu.txtM);ifstreamfin2(Mweight.txtn);if(n=1)return;intm=2*n-1;inti;HT=newHTNodem+1;char*zifu;int*weight;zifu=newcharn+1;weight=newintn+1;for(i=1;

4、iv=n;i+)/将待编码的字符放在zifu数组中charch;ch=fin1.get();zifui=ch;for(i=1;iv=n;i+)将带编码字符对应的权值放在weight数组中(fin2weighti;)for(i=1;i=n;i+)(HTi.data=zifui;HTi.weight=weighti;)for(i=n+1;i=m;i+)(HTi.data=,;)for(i=1;i=m;i+)HTi.parent=HTiJchild=HTi.rchild=O;)for(i=n+1;i=m;+i)ints1,s2;Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTiJchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weigh)HC=(HuffmanCode)malloc(n+1)*sizeof(char*);开辟一个求编码的工作空间char*cd;cd=(char*)malloc(n*sizeof(char);/开辟空间存放权值cdn.1=，(r；for(i=1;i=n;i

5、+)intstart=n-1;intc5f;for(f=HTi.parent;f!=O;c=f,f=HTf.parent)/IFf子到根逆向求编码if(HTf.lchild=c)cd7tart=U;若是左孩子编为Oelsecd“start=T;若是右孩子编为1HCi=(char为第i个*)malloc(n-start)*sizeof(char);编码分配空间strcpy(HCi,&cdstart);delete cd;释放工作空间#voidprintHuffmanTree(HuffmanTreeHTJntn)显示有n个叶子结点的哈夫曼树的编码表ofstreamfout(,hfmtree.txf,);将对应字符的的哈弗曼树存入coutMNUMnMMMdataMMM,weightMMMKparentMM,fHlchild,fMMrchlidMendl;for(inti=1;i=2*n-1;i+)foutHTi.weightsetw(3)HTi.parentsetw(3)HTi.lchildsetw(3)HTi.rchildendl;coutisetw(5)HTi.datasetw(3)HT

6、i.weightvvsetwvvHTi.parentvvsetw(3)HTi.lchildsetw(3)HTi.rchildendl;voidprintHuffmanCoding(HuffmanTreeHT,HuffmanCodeHCJntn)输出字符的对应哈弗曼编码并存入code.txt文件coutnHuffmancodeis:Hendl;ofstreamfout(Hcode.txtM)；for(inti=1;icout(HCi)endl;fout(HCi)endl;)voidcode_file(HuffmanTreeHT,HuffmanCodeHCJntn)/对文件tobetran.txt进行编码，并将编码存入codefile文件中ifstreamfin(,ftobetran.txtH);ofstreamfout(Mcodefile.txtM)；vectora;charch;while(ch=fin.get()!=*)a.pushback(ch);coutvv”待编码的字符串为：”;for(intk=O;ka.size();k+)coutak;coutendl;coutMn编码结果

7、:vvendl;for(inti=O;ia.size();i+)(for(intj=1;j=n;j+)(if(ai=HTj.data)(break;fin.closeQ;fout.closeQ;voidDecoding(HuffmanTreeHT,HuffmanCodeHCJntn)打开codefile文件并对文件内容进行译码intconstm=2*n-1;ifstreamfin(,codefile.txtM);ofstreamfout(Mtextfile.txtM);vectora;for(charc;finc;)a.push_back(c);intcount=0;for(intk=O;ka.size();k+)coutak;count+;if(count%50=0)coutendl;)inti=0;用p来记住m的值intp;coutendl;coutvv”n译码结果：vvendl;while(i111A1010B100000C00000D10110E010F110011g1nnaniH0001I0110J1100001000K11090011L10111M110010N011101001pQ1100001001R0018S0011rnetU00001U1100000W110001X1100001010V1RR011Z1100001011待编码的字符串为：ILOUEyou编码结果：0110111101111001110000001011

《哈夫曼编码实验报告》由会员人***分享，可在线阅读，更多相关《哈夫曼编码实验报告》请在金锄头文库上搜索。