哈夫曼编码课程设计.doc

Huffman编码的设计与实现 中南林业科技大学本科课程设计说明书学 院： 理学院 专业年级： 08信息与计算科学 课 程： 信息论与编码课程设计 设计题目： Huffman编码的设计与实现 指导教师： 龚志伟 2011年5月学生姓名： 夏文林 学 号：20083728分 工： 程序调试、资料收集 学生姓名： 易勋 学 号：20083730分 工： 源程序、算法分析 学生姓名： 游斌 学 号：20083731分 工： 文档整理、源程序 学生姓名： 余璐 学 号：20083732分 工： 源程序、总结 学生姓名： 朱健 学 号：20083736分 工： 源程序、流程分析与编写 中文摘要哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩通常在20%90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然，还有编码和译码部分。本系统的前端开发工具是Visual C+6.0。具有输入字符集大小及权值大小，构造哈夫曼树，并对用户输入的字符串进行编码以及译码还有退出四种功能。本程序经过测试后，功能均能实现，运行稳定。关键词：哈夫曼树，编码，权值 英文摘要 Huffman coding is widely used in data file compression coding method is very effective. The compression usually between 20% 90% in. Huffman use of the character encoding algorithm in the document appeared in frequency table with 0 to build a string of optimal each character said means. The algorithms construction huffman extended binary tree called huffman coding tree or huffman tree. Of course, there are coding and decoding parts. This system the front-end development tools is Visual c + + 6.0. With input character set size and weitht size, structure tree huffman, and user input string coding and decoding and exit four functions. This procedure after testing, functions are realized, steady operation.目 录引言31、问题分析42、算法设计53、算法实现63.1流程图63.2程序代码73.3调试结果103.3.1例题57的测试结果103.3.2习题5-12的调试结果114、结论135、参考文献13引言哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。利用哈夫曼算法的编码和译码功能，重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。软件运行环境及开发工具是Visual C+6.0。 1、问题分析 为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪录输入数据的多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。在算法执行中，哈夫曼树是由若干棵树组成的森林，通过不断地合作树，最后得到一棵哈夫曼树。为了便于实现哈夫曼树的建树运算，定义程序的哈夫曼树类HfmTree，它包括如下两个私有数据成员tree和weight：其中，tree是一个二叉树BinaryTree类型对象，是一棵哈夫曼树，weight是tree所代表的哈夫曼树的权值。在本课程设计中使用函数Huffman（）。构造哈夫曼树算法：（1） 用给定的一组权值W1,W2,Wn,生成一个有n棵树组成的森林F=T1,T2,Tn,其中每棵二叉树Ti只有一个结点，即权值为 Wi的根结点（也是叶子结点）；（2） 从F中选择两棵根结点权值最小的树，作为新树根的左右子树，新树根的权值是左右子树根结点的权值之和；（3） 从F中删除这两棵树，另将新二叉树加入F中；（4） 重复（2）和（3），直到F中只包含一棵树为止。本次程序设计的是哈夫曼编码。由建立好的哈夫曼树来进行编码，构造一个CodeNode结构体用来存储编码字符及各字符的编码，从根结点开始，左走一步为0，右走一步为1，并将编码结果存入文件中，译码过程为从文件中逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根从二进位串的下一位开始继续译码。使用transcode()函数即可完成。 2、算法设计Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子：比如有以下数据， ABFACGCAHGBBAACECDFGFAAEABBB先进行统计A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括号里面的是统计次数生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root) 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表。3、算法实现3.1流程图：3.2程序代码：#include#include#define N 15 /*最大符号数*/#define M 2*N-1 /*编码树最大节点数*/typedef struct /*编码树节点*/ float weight; int parent,lchild,rchild;HTNode;typedef structchar data;float weight;char codeN;HTCode;void Init(HTCode hc,int *n)int i; printf(n input n=); /*输入n的大小*/scanf(%d,&(*n); /*取n的地址值*/fflush(stdin); /*stdin是默认的输入流文件,对应输入缓冲区 fflush(stdin)的作用就是清空输入缓冲区,避免缓冲区内残存读取函数无法取走的内容!*/printf(n input %d character n,*n); /*输入各个字符的代号*/for(i=1;i=*n;i+) /*从1到n个*/printf(n the %d character is:,i); /*输出显示的信息提示*/scanf(%c,&(hci.data); /*取hci的地址所对应的data值*/fflush(stdin); /*同上*/for(i=1;i=*n;i+) /*从1到n输入它们各自所对应的概率大小，即重量weight*/printf(n the %d character weight is:,i); /*输出显示的信息提示*/scanf(%f,&(hci.weight); /*取hci的地址所对应的weight值*/void Select(HTNode ht,int k,int *s1,int *s2) /*定义Select选择函数*/ int i; /*定义一个整形数i*/ for(i=1;i=k;i+) if(hti.parent=0) /*i从1开始到k，如果i没有父节点，则把i赋给*s1，且跳出循环*/ *s1=i; break;for(i=1;i=k;i+) /*找任意不是第一次的节点*/if(hti.parent=0&hti.weightht*s1.weight) /*i再从1开始，如果此时的i没有父节点，且其重量小于*s1的重量，就把当前的i赋给*s1*/*s1=i;for(i=1;i=k;i+) /*i再从1开始，如果此时的i没有父节点，而且i不等于*s1的值，则把当前的i赋给*s2。跳出循环*/if(hti.parent=0&i!=*s1) *s2=i;break;for(i=1;i=k;i+)if(hti.parent=0&i!=*s1&hti.weightht*s2.weight)*s2=i;/*i再从1开始，如果此时的i没有父节点，而且i不等于*s1的值，其重量也小于*s2的重量，则把当前的i赋给*s2。*/printf(n this is *s1:%dn,*s1); /*输出*s1与*s2所指的内容*/printf(n this is *s2:%dn,*s2);void HuffmanCoding(HTNode ht,HTCode hc,int n)char cdN; int i,m,c,f,s1,s2,start;m=2*n-1;for(i=1;i=m;i+) /*初始化节点，其中1n个原始节点具有概率值*/if(i=n)hti.weight=hci.weight;else hti.weight=0.0;hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=m;i+) /*构造二叉树*/Select(ht,i-1,&s1,&s2); /*选择最小的两个概率节点，并且是没有编码过的*/hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;for(i=1;i=m;i+) /*调试二叉树*/printf(n the %d charactor weight is %f:,i,hti.weight);printf(n the %d charactor lchild is %d:,i,hti.lchild);printf(n the %d charactor rchild is %d:,i,hti.rchild);printf(n the %d charactor parent is %d:,i,hti.parent);for(i=0;iN;i+) /*编码初始化*/cdi= ;cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=hti.parent;f;c=f,f=htf.parent) /*遍历父节点*/if(htf.lchild=c)cd-start=1;else cd-start=0; /*提取码字*/strcpy(hci.code,&cdstart);void main()int i,n;float l=0.0; /*初始化l*/float arg,*point=&arg; /*定义指针类型平均码长arg*/HTNode htM+1; /*定义HTNode的数组*/HTCode hcN+1; /*定义HTNode的数组*/Init(hc,&n); /*调用Init函数*/HuffmanCoding(ht,hc,n); /*调用Huffman函数*/for