文档介绍：格
本科生课程论文
题目: Huffman编码的编码与译码
姓名:
学院: 理学与信息学院
专业: 信息与计算科学专业
班级:
学号:
指导教师:
完成时间: 2011年6月29 日
2011年6月29日
目录
摘要 1
1. 概念解释 1
2. 程序设计算法 2
3. 程序调试窗 3
4. 致谢 5
参考文献 5
附录 6
Huffman编码的编码与译码
信息与计算科学
指导教师
摘要:在这个信息高速发展的时代,每时每刻都在进行着大量信息的传递,到处都离不开信息,它贯穿在人们日常的生活生产之中,对人们的影响日趋扩大,而利用哈夫曼编码进行通信则可以大大提高信道利用率,缩短信息传输时间,降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润,这也是信息时代发展的趋势所在。
文字处理是现代计算机应用的重要领域。文本由字符组成,字符以某种编码形式存储在计算机中。每个字符的编码可以是相等长度的,也可以是不等长度的。ASCII编码是等长编码。为了提高存储和处理文本的效率,在一些计算机应用场合,如数据通信,常采用不等长的编码,对常用的字符用较少的码位,不常出现的字符用较多的码位编码,从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等长编码方法。
关键词:Huffman编码编码译码 VC++ 程序代码哈夫曼树
一概念解释:
1、哈夫曼树
,可以构造出不同的二叉树,,叶子结点的权值(weight),从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度(weighted path length),记为:
WPL=,wk为第k个叶子结点的权值,lk为从根结点到第k个叶子结点的路径长度.
2、哈夫曼算法
根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,,其基本思想是:
初始化:由预先给定的n个权值{w1, w2,…, wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F={ T1,T2,…,Tn};
选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;
二设计方案:哈夫曼编码/译码程序主要由主函数、哈夫曼树类和各种功能函数组成,程序运行时首先进入主函数,对各种功能函数进行调用,从而实现了整个程序的运行。将各种不同的函数分别包含在各自的结构体中,使整个程序结构更加的清晰明了,各功能相互独立且紧密联系,有利于编程的实现,同时也体现了面向对象设计语言的封装性。在主菜单中运用了switch()函数和“case”语句,便于对整个程序操作和控制;对数据保存在文档中,则运用了文件I/O流和C语言的文件处理方式,进行文件与内存之间输入,输出数据。
程序的主要功能:
1、Huffman编码(void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n))
a)先将每个字符的出现概率存在数组HT[1-n]的weight中,并将每个数组元素的rchild,lchild,parent都置为0。
b)每次对数组中的parent值为0的元素的weight值进行堆排序,取出两个最小的值相加加入HT[]中。新加入的元素的weight值为两个weight值相加,parent值为0,lchild,rchild为选出来的两个最小值的数组序号,两个选出来的最小值的parent值为新存入的元素的数组序号。重复操作,直至数组存满
c)HC为char **类型,HC[i]里存放着第i个字符串的首地址。cd[]存放编码,最后一个元素存放字符串截止符‘\0’,采用倒序存储,从叶子节点往上寻找,若是lchild,则从后往前在cd[]内存入0。若是rchild,则从后往前在cd[]内存入1。直至找到根节点。将cd[]中存储的字符串拷贝到HC[i]指向的数组中。
d)重复c),直至所有字符都存入HC[i]指向的数组中,即编码成功。
2、堆排序(函数1、void HeapAdjust(SqList &L, int s, int m),函数2、void select(HuffmanTree t, int i, int &s1, int &s2))
a)函数2是在函数1的基础上实现的,函数1的功能是已知