哈夫曼编码实验报告.doc
实验一 哈夫曼编码一、实验目的1、 掌握哈夫曼编码原理；2、 熟练掌握哈夫曼树的生成方法； 3、理解数据编码压缩和译码输出编码的实现。二、实验要求实现哈夫曼编码和译码的生成算法。三、实验容先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。五、实验原理1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；2、哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立的HTNode对象中的data属性，即每一个HTNode对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HTNode，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。 通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。六、实验流程 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树； 根据符号概率的大小按由大到小顺序对符号进行排序； 把概率最小的两个符号组成一个节点； 重复步骤（2）（3），直到概率和为1； 从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”； 从根节点开始，对符号进行编码； 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。七、实验程序#include<iostream>#include<fstream>#include<iomanip>#include<vector>using namespace std;typedef struct /节点结构char data; /记录字符值long int weight; /记录字符权重unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char * *HuffmanCode;/动态分配数组存储哈夫曼编码表void Select(HuffmanTree &HT,int i,int &s1,int &s2) /在HT1.t中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2 s1=0;s2=0;int n1=30000,n2=30000;for(int k=1;k<=i;k+)if(HTk.parent=0)if(HTk.weight<n1)n2=n1; n1=HTk.weight;s2=s1; s1=k;elseif(HTk.weight<n2)n2=HTk.weight;s2=k;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)/将要编码的字符串存入空树中ifstream fin1("zifu.txt");ifstream fin2("weight.txt");if(n<=1)return;int m=2*n-1;int i;HT=new HTNodem+1;char *zifu;int *weight; zifu= new charn+1;weight=new intn+1;for(i=1;i<=n;i+)/将待编码的字符放在zifu数组中char ch;ch=fin1.get();zifui=ch;for(i=1;i<=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=HTi.lchild=HTi.rchild=0;for(i=n+1;i<=m;+i)int s1,s2;Select(HT,i-1,s1,s2);HTs1.parent=i; HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);开辟一个求编码的工作空间char *cd;cd=(char *)malloc(n*sizeof(char);/开辟空间存放权值cdn-1='0'for(i=1;i<=n;i+)int start=n-1;int c,f;for( c=i, f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0'/若是左孩子编为'0'elsecd-start='1'/若是右孩子编为'1'HCi=(char *)malloc(n-start)*sizeof(char);/为第i个编码分配空间strcpy(HCi,&cdstart);delete cd;/释放工作空间void printHuffmanTree(HuffmanTree HT,int n) /显示有n个叶子结点的哈夫曼树的编码表 ofstream fout("hfmtree.txt"); /将对应字符的的哈弗曼树存入cout<<"NUM"<<" "<<"data"<<" "<<"weight"<<" "<<"parent"<<" "<<"lchild"<<" "<<"rchlid"<<endl;for(int i=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.weight<<setw(3)<<HTi.parent<<setw(3)<<HTi.lchild<<setw(3)<<HTi.rchild<<endl;void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)/输出字符的对应哈弗曼编码并存入code.txt文件cout<<"Huffman code is:"<<endl;ofstream fout("code.txt");for(int i=1;i<=n;i+)cout<<HTi.data<<" -> "cout<<(HCi)<<endl;fout<<(HCi)<<endl;void code_file(HuffmanTree HT,HuffmanCode HC,int n)/对文件tobetran.txt进行编码，并将编码存入codefile文件中ifstream fin("tobetran.txt");ofstream fout("codefile.txt");vector<char> a;char ch;while(ch=fin.get()!='*')a.push_back(ch); cout<<"待编码的字符串为："for(int k=0;k<a.size();k+)cout<<ak;cout<<endl;cout<<"n编码结果:"<<endl;for(int i=0;i<a.size();i+) for(int j=1;j<=n;j+)if(ai=HTj.data) fout<<HCj; break;fin.close();fout.close();void Decoding(HuffmanTree HT,HuffmanCode HC,int n)/打开codefile文件并对文件容进行译码int const m=2*n-1;ifstream fin("codefile.txt");ofstream fout("textfile.txt");vector<char> a;for(char c;fin>>c;) a.push_back(c); int count=0;for(int k=0;k<a.size();k+) cout<<ak;count+;if(count%50=0)cout<<endl;int i=0;int p; /用p来记住m的值cout<<endl;cout<<"n译码结果："<<endl;while(i<a.size()p=m; /从哈弗曼数的根开始遍历while(HTp.lchild) if(ai='1') p=HTp.rchild; else p=HTp.lchild; i+;fout<<HTp.data; cout<<HTp.data;void main()int n;cout<<"输入权值个数：" /设置权值数值cin>>n; printf("n");HuffmanTree HT; /哈夫曼树HTHuffmanCode HC; /哈夫曼编码表HCHuffmanCoding(HT,HC,n); /进行哈夫曼编码printHuffmanCoding(HT,HC,n); /显示编码的字符printf("n");code_file(HT,HC,n); /显示要编码的字符串，并把编码值显示出来Decoding(HT,HC,n); /译码并显示译码后的字符串printf("nnn");system("pause");八、结果分析哈夫曼编码是动态变长编码，临时建立概率统计表和编码树。概率小的码比较长，概率小的码比较长。概率大的码短，这样把一篇文件编码后，就会压缩许多。从树的角度看，哈夫曼编码方式是尽量把短码都利用上。首先，把一阶节点全都用上，如果码字不够时，然后，再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最正确码。九、实验总结通过这次实验，我对二叉树和哈希曼树有了更好的认识。在实验过程中，我掌握了哈曼树的构造方法，学会了如何将理论知识传换成实际应用。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。在实验中，我遇到了许多难点，比如：统计字符的权值，就需要我们有扎实的基础，需要有灵活的头脑，只有不断的练习，不断的训练，我们才能处理各种问题。在以后的学习中，我要不断的努力，多联系，多思考，我相信我能有所进步的。7 / 7
