哈夫曼编码实验报告
哈夫曼编码实验报告实验一哈夫曼编码一、实验目的1、掌握哈夫曼编码原理;2、熟练掌握哈夫曼树的生成方法;3、理解数据编码压缩和译码输出编码的实现。二、实验要求实现哈夫曼编码和译码的生成算法。三、实验内容先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。五、实验原理1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树,每个叶子带权值为wi,其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树;2、哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立的HTNode对象中的data属性，即每一个HTNode对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HTNode,将他们的data相加，构造出新的HTNode作为他们的父节点,指针parent,leftchild,rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树o通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子,来记录1或0,这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。六、实验流程初始化，统计文本文件中各字符的个数作为权值，生成哈夫曼树；根据符号概率的大小按由大到小顺序对符号进行排序；把概率最小的两个符号组成一个节点； 重复步骤(2)(3),直到概率和为1； 从根节点开始到相应于每个符号的“树叶”,概率大的标“0”，概率小的标“1”； 从根节点开始，对符号进行编码; 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。七、实验程序#include<iostream>#include<fstream>#include<iomanip>#include<vector>usingnamespacestd;typedef struct节点结构char data;long int weight;/记录字符值/记录字符权重unsignedintparentjchild,rchild;JHTNode/HuffmanTree;动态分配数组存储哈夫曼树typedefchar*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.weight<n1)(n2=n1;n1=HTk.weight;s2=s1;s1=k;)elseif(HTk.weight<n2)(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;iv=n;i+)/将待编码的字符放在zifu数组中charch;ch=fin1.get();zifui=ch;for(i=1;iv=n;i+)将带编码字符对应的权值放在weight数组中(fin2»weighti;)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+)intstart=n-1;intc5f;for(f=HTi.parent;f!=O;c=f,f=HTf.parent)/IFf子到根逆向求编码if(HTf.lchild=c)cd7tart=U;若是左孩子编为O'elsecd“start=T;若是右孩子编为1'HCi=(char为第i个*)malloc(n-start)*sizeof(char);编码分配空间strcpy(HCi,&cdstart);delete cd;释放工作空间#voidprintHuffmanTree(HuffmanTreeHTJntn)显示有n个叶子结点的哈夫曼树的编码表ofstreamfout(,hfmtree.txf,);将对应字符的的哈弗曼树存入cout«MNUMn«MM«MdataM«MM«,weightM«MM«KparentM«M,f«Hlchild,«,fM«MrchlidM«endl;for(inti=1;i<=2*n-1;i+)fout<<HTi.weight«setw(3)«HTi.parent<<setw(3)«HTi.lchild«setw(3)«HTi.rchild«endl;cout<<i«setw(5)«HTi.data«setw(3)<<HTi.weightvvsetwvvHTi.parentvvsetw(3)<<HTi.lchild«setw(3)«HTi.rchild«endl;voidprintHuffmanCoding(HuffmanTreeHT,HuffmanCodeHCJntn)输出字符的对应哈弗曼编码并存入code.txt文件cout«nHuffmancodeis:H«endl;ofstreamfout(Hcode.txtM)；for(inti=1;i<=n;i+)(cout«HTi.data«M->cout«(HCi)«endl;fout«(HCi)«endl;)voidcode_file(HuffmanTreeHT,HuffmanCodeHCJntn)/对文件tobetran.txt进行编码，并将编码存入codefile文件中ifstreamfin(,ftobetran.txtH);ofstreamfout(Mcodefile.txtM)；vector<char>a;charch;while(ch=fin.get()!='*')a.pushback(ch);coutvv”待编码的字符串为：”;for(intk=O;k<a.size();k+)cout«ak;cout«endl;cout«Mn编码结果:"vvendl;for(inti=O;i<a.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);vector<char>a;for(charc;fin»c;)a.push_back(c);intcount=0;for(intk=O;k<a.size();k+)cout«ak;count+;if(count%50=0)cout«endl;)inti=0;用p来记住m的值intp;cout«endl;coutvv”n译码结果："vvendl;while(i<a.size()P=m;从哈弗曼数的根开始遍历while(HTpJchild)(H(ai='r)p=HTp.rchild;elsep=HTp.lchild;i+；)fout«HTp.data;cout«HTp.data;voidmain()intn;coutvv”输入权值个数：”;/设置权值数值cin»n;HuffmanTree HT;哈夫曼树HTHuffmanCode HC;哈夫曼编码表HCHuffmanCoding(HT5HC,n);进行哈夫曼编码printHuffmanCoding(HT,HC5n);显示编码的字符printf(MnM);显示要编码的字codeJile(HT5HC,n);符串，并把编码值显示出来码后的字符串Decoding(HT,HC5n);/译码并显示译printf("nnrT);system(Mpausen);,CAUsersXAdministratorXDesktopXXDebugXl.exeHuffmancodeis：>111A>1010B>100000C>00000D>10110E>010F>110011g>1nnaniH>0001I>0110J>1100001000K>11090011L>10111M>110010N>01110>1001p>Q>1100001001R>0018S>0011r>netU>00001U>1100000W>110001X>1100001010V>1RR011Z>1100001011待编码的字符串为：ILOUEyou编码结果：0110111101111001110000001011
