huffman无损压缩编码实验报告.doc

无损压缩编码 （huffman编码）实验报告 作 者: 计一飞 学 号： 100座机电话号码 学院 系 : 电子工程与光电技术学院 专 业: 电子信息工程 题 目: 无损压缩编码 指导老师： 康其桔 摘要 本文介绍了无损压缩编码中的霍夫曼（huffman）编码。Huffman编码是可变字长编码的一种，该方法完全依据字符出现概率来构造最优二叉树（huffman树），故有时又称为最佳编码。在文中，我们使用C++语言进行编码，从下到上进行了熵编码。 关键词：huffman、最优二叉树、熵编码、C++ Abstract The huffman Huffman coding of Lossless coding were introduced in this paper . Huffman coding is a kind of variable-word- length coding.The method is completely based on the characters appear probability to construct the optimal binary tree Huffman tree , so it is sometimes referred to as the optimal coding. In this paper, we use c + + language to code, from bottom to top in the entropy coding. Key words: huffman、optimal binary tree、entropy coding、C++ 实验目的 理解无损压缩编码的优点和意义。 理解树、二叉树、huffman树的概念。 学会二叉树的C++编程，进行熵编码。 实验步骤 步骤①：按照符号出现概率大小的顺序对符号进行排序。 步骤②：把概率最小的两个符号组成一个节点P1。 步骤③：重复步骤②，得到节点P2，P3，P4，……，PN，形成一棵树，其中的PN称为根节点。 步骤④：从根节点PN开始到每个符号的树叶，从上到下标上0 上枝 和1 下枝 ，至于哪个为1哪个为0则无关紧要，但通常把概率大的标成1，概率小的标成0。 步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出每个符号的代码。 实验程序设计 输入字符，定义三个字符串，输入字符串到words数组，并且求得其长度length。 char words[500],wds[500],wd[500]; //定义三个字符串，长度都不超过500 cin words; //输入字符串 int length,len,m; length strlen words ; //计算words字符串长度 对words字符串进行从小到大冒泡排序，并且将words中的元素全部赋给wds字符串。 void maopao char wd[],int len //函数冒泡排序 int i,j; char t; for j 0;j len-1-1;j++ for i 0;i len-j-1;i++ if wd[i] wd[i+1] t wd[i]; wd[i] wd[i+1]; wd[i+1] t; 主函数： maopao words,length ; //定义冒泡函数 cout words '\n'; for int i 0;i length;i++ //将words中的内容赋给wds wds[i] words[i]; 将已经排序好的字符串中同种字符删除，使该字符在字符串中只剩下一个。得到wds的字符串长度len。 void typedelete char *a1,int len //删除字符串中的同类字符使该字符只剩一个 while *a1 if *a1 * a1+1 strcpy a1,a1+1 ; continue; a1++; 主函数： typedelete wds,length ; //定义同类删除函数 cout wds '\n'; //输出排序好且一组相异的字符串wds len strlen wds ; //字符串wds的长度 4、定义两个数组entr1、entr2，分别用于存放输入字符串words中出现每个字符的频率与频数。定义log2函数用于计算熵。 double log2 double x //定义log2函数计算熵值 double y; y log10 x /log10 2 ; return y; 主函数： double entr1[500] 0,0,0 ; //定义一个数组，存放每个字母出现的频率 int entr2[500] 0,0,0 ; //定义一个数组，存放每个字母出现的频数