《哈夫曼编码课程设计》由会员分享，可在线阅读，更多相关《哈夫曼编码课程设计（15页珍藏版）》请在金锄头文库上搜索。
1、中南林业科技大学本科课程设计说明书学 院：理学院专业年级：08信息与计算科学课 程：信息论与编码课程设计设计题目：Huffman编码的设计与实现指导教师：龚志伟2011年5月学生姓名：夏文林学号：20083728分工：程序调试、资料收集学生姓名：易勋 学号：20083730分工：源程序、算法分析学生姓名：游斌学号：20083731分工：文档整理、源程序学生姓名：余璐 学 号：20083732分工：源程序、总结学生姓名：朱健 学 号：20083736分工：源程序、流程分析与编写中文摘要哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩通常在 20 %90%之间。哈夫曼编码算法使用字符在
2、文件中出现的频率表来建立一个用 0,1串表示各字符的最优表示方式。哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然，还有编 码和译码部分。本系统的前端开发工具是Visual C+6.0。具有输入字符集大小 及权值大小，构造哈夫曼树，并对用户输入的字符串进行编码以及译码还有退出 四种功能。本程序经过测试后，功能均能实现，运行稳定。关键词：哈夫曼树，编码，权值英文摘要Huffman coding is widely used in data file compression coding met hod is very effec ti ve. The compression usual
3、ly bet ween 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 construetion huffman extended binary tree called huffman coding tree or huffman tree. Of course, there are
4、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 inp ut st ring coding and decoding and exi t four func tio ns. This procedure after testing, functions are realized, steady oper
5、ation.引言41、问题分析52、算法设计63、算法实现63.1流程图63.2程序代码.73.3调试结果103.3.1例题57的测试结果103.3.2习题5-12的调试结果114、结论135、参考文献13引言哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造 平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中 就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概 率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根 据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方 法就是哈夫曼算法。字符根据其出现
6、的概率作为权值构造一棵哈夫曼树后，经哈 夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来 那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符 的编码的前缀，否则，编码就不能进行翻译。利用哈夫曼算法的编码和译码功能，重复地显示并处理以下项目，即构造哈 夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个 哈夫曼的编/译码器。哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度 的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则 编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫 描码
7、文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上 标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出 了一个字符。再回到树根，从二进位串的下一位开始继续译码。软件运行环境及 开发工具是Visual C+6.0。1、问题分析为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构 体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪 录输入数据的多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼 算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。在算 法执行中，哈夫曼树是由若干棵树组成的森林，通过不断地合作
8、树，最后得到一 棵哈夫曼树。为了便于实现哈夫曼树的建树运算，定义程序的哈夫曼树类 HfmTree，它包括如下两个私有数据成员tree和weight:其中，tree是一个二叉 树BinaryTree类型对象，是一棵哈夫曼树，weight是tree所代表的哈夫曼树的权 值。在本课程设计中使用函数Huffman ()。构造哈夫曼树算法：(1) 用给定的一组权值Wl,W2,.,Wn,生成一个有n棵树组成的森林 F=Tl,T2,.Tn,其中每棵二叉树Ti只有一个结点，即权值为Wi的根结点(也 是叶子结点)；(2) 从F中选择两棵根结点权值最小的树，作为新树根的左右子树，新树 根的权值是左右子树根结点的权
9、值之和；(3) 从F中删除这两棵树，另将新二叉树加入F中；(4) 重复(2)和(3)，直到F中只包含一棵树为止。本次程序设计的是哈夫曼编码。由建立好的哈夫曼树来进行编码，构造一个 CodeNode结构体用来存储编码字符及各字符的编码，从根结点开始，左走一步 为0，右走一步为 1，并将编码结果存入文件中，译码过程为从文件中逐 一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼 树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则 译出了一个字符。再回到树根从二进位串的下一位开始继续译码。使用transcode() 函数即可完成。2、算法设计Huffman编码
10、是一种可变长编码方式，是由美国数学家David Huffman创立 的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成 长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可 解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长 度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子： 比如有以下数据，ABFACGCAHGBBAACECDFGFAAEABBB 先进行统计 A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1
11、)括号里面的是统计次数生成Huffman树：每次取最 小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接 点的累计数值，最顶层的是根节点(root)注：列表中最小节点的是指包括合并 了的节点在内的所有节点，已经合并的节点不在列表。3、算法实现31流程图：3.2程序代码:/*最大符号数*/*编码树最大节点数*/*编码树节点*/#includestdio.h #includestring.h #define N 15 #define M 2*N-1 typedef structfloat weight;int parent, lchild,rchild; HTNod
12、e;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)的作用就是清空输入缓冲区,避免缓冲区内残存读取函数无法取走的内 容!*/prin tf(n input %d charac ter n,*n);/*输入各个字符的代号 */for(i=l;i=*n
13、;i+)/*从 1 到 n 个*/prin tf(n the %d charac ter is:,i);/*输出显示的信息提示*/scanf(%c,&(hci.data);/*取 hci的地址所对应的 data值*/fflush(s tdin);/* 同上 */for(i=l;i=*n;i+)/*从1到n输入它们各自所对应的概率大小，即重量weight*/prin tf(n the %d charac ter weight is:,i);/ 输出显示的信息提示 */scanf(%f,&(hci.weight);/* 取 hci的地址所对应的weight 值*/void Select(HTNod
14、e 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+)/*找任意不是第一次的节点*/辻(hti.parent=0&hti.weightht*s1.weight)/*i再从 1 开始，如 果此时的i没有父节点，且其重量小于*sl的重量，就把当前的i赋给*sl*/*s1=i;for(i=l;i二k;i+)/*i再从1开始，如果此时的i没有父节
15、点，而且i不等于*s1的值，则把当前的i赋给*s2。跳出循环*/if(hti.parent=O&i!=*s1)*s2=i;break;for(i=1;i=k;i+)if(hti.parent=O&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
