哈夫曼编码课程设计

《哈夫曼编码课程设计》由会员分享，可在线阅读，更多相关《哈夫曼编码课程设计（12页珍藏版）》请在装配图网上搜索。

1、摘要哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩通常在 20%90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用 0,1串表示各字符的最优表示方式。哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然，还有编 码和译码部分。本系统的前端开发工具是Visual C+6.0。具有输入字符集大小 及权值大小，构造哈夫曼树，并对用户输入的字符串进行编码以及译码还有退出 四种功能。本程序经过测试后，功能均能实现，运行稳定。关键词：哈夫曼树，编码，译码，权值1问题描述12问题分析23算法设计34算法实现45测试分析7结论9参考文献91问题描述哈夫曼在上世纪五十年代初就

2、提出这种编码时，根据字符出现的概率来构造 平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中 就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概 率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根 据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方 法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈 夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来 那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符 的编码的前缀，否则，编码就不能进行翻译。利用哈夫曼算

3、法的编码和译码功能，重复地显示并处理以下项目，即构造哈 夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个 哈夫曼的编/译码器。哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度 的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则 编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫 描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上 标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出 了一个字符。再回到树根，从二进位串的下一位开始继续译码。软件运行环境及 开发工具是Visual

4、C+6.0。2问题分析为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构 体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪 录输入数据的多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼 算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。在算 法执行中，哈夫曼树是由若干棵树组成的森林，通过不断地合作树，最后得到一 棵哈夫曼树。为了便于实现哈夫曼树的建树运算，定义程序的哈夫曼树类 HfmTree，它包括如下两个私有数据成员tree和weight:其中，tree是一个二叉 树BinaryTree类型对象，是一棵哈夫曼树，weight是t

5、ree所代表的哈夫曼树的权 值。在本课程设计中使用函数Huffman（）。构造哈夫曼树算法：（1）用给定 的一组权值W1,W2,.,Wn,生成一个有n棵树组成的森林F=T1,T2,.Tn,其中 每棵二叉树Ti只有一个结点，即权值为Wi的根结点（也是叶子结点）；（2） 从F中选择两棵根结点权值最小的树，作为新树根的左右子树，新树根的权值是 左右子树根结点的权值之和；（3）从F中删除这两棵树，另将新二叉树加入F 中；（4）重复（2）和（3），直到F中只包含一棵树为止。本次程序设计的是哈夫曼编码及译码。由建立好的哈夫曼树来进行编码，构 造一个CodeNode结构体用来存储编码字符及各字符的编码，从根

6、结点开始，左 走一步为0，右走一步为1，并将编码结果存入文件中，译码过程为从文 件中逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与 哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶 子，则译出了一个字符。再回到树根从二进位串的下一位开始继续译码。使用 transcode（）函数即可完成。3算法设计Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立 的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成 长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可 解性。Huffman算法的最根

7、本的原则是：累计的(字符的统计数字*字符的编码长 度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子： 比如有以下数据，ABFACGCAHGBBAACECDFGFAAEABBB先进行统计A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1)括号里面的是统计次数生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)， 并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root)注： 列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的

8、节点不在 列表。4算法实现#include /*2009.10.25 白鹿原*/#include /*哈夫曼树建立、哈夫曼编码算法的实现*/#include typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/typedef structunsigned int weight ; /*用来存放各个结点的权值*/unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/HTNode, * HuffmanTree;/*动态分配数组，存储哈夫曼树*/void select(HuffmanTree *ht,int n,

9、 int *s1, int *s2)int i;int min;for(i=1; i=n; i+)if(*ht)i.parent = 0)min = i;i = n+1;for(i=1; i=n; i+)if(*ht)i.parent = 0)if(*ht)i.weight (*ht)min.weight)min = i;*s1 = min;for(i=1; i=n; i+)if(*ht)i.parent = 0 & i!=(*s1)min = i;i = n+1;for(i=1; i=n; i+)if(*ht)i.parent = 0 & i!=(*s1)if(*ht)i.weight (*

10、ht)min.weight)min = i;*s2 = min;void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) /* w存放已知的n个权值，构造哈夫曼树ht */int m,i;int s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /*0 号单元未使用 */for(i=1;i=n;i+)/*1-n号放叶子结点，初始化*/(*ht)i.weight = wi;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0;f

11、or(i=n+1;i=m;i+)(*ht)i.weight = 0;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0;/*非叶子结点初始化*/*/*初始化完毕！对应算法步骤1for(i=n+1;i=m;i+)/*创建非叶子结点，建哈夫曼树*/select(ht,i-1,&s1,&s2);(*ht)s1.parent=i;(*ht)s2.parent=i;(*ht)i.LChild=s1;(*ht)i.RChild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight;/*哈夫曼树建立完毕*/voi

12、d outputHuffman(HuffmanTree HT, int m)if(m!=0)printf(%d , HTm.weight);outputHuffman(HT,HTm.LChild);outputHuffman(HT,HTm.RChild); void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/char *cd;int i;unsigned int c;int start;int p;hc=(HuffmanCode *)malloc(n+1)*sizeof

13、(char *); /*分配 n 个编码的头指针*/ cd=(char * )malloc(n * sizeof(char ); /* 分配求当前编码的工作空间 */ cdn-1=0;/*从右向左逐位存放编码，首先存放编码结束符*/for(i=1;i=n;i+) /*求n个叶子结点对应的哈夫曼编码*/ start=n-1;/*初始化编码起始指针*/for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) /*从叶子到根结点求编码 */ if( (*ht)p.LChild = c)cd-start=0; /*左分支标 0*/elsecd-start=

14、1; /* 右分支标 1*/hci=(char *)malloc(n-start)*sizeof(char); /*为第 i 个编码分配空间*/ strcpy(hci,&cdstart);free(cd);for(i=1;i=n;i+)printf(%d 编码 为%sn”,(*ht)i.weight,hci); void main()HuffmanTree HT;HuffmanCode HC;int *w;int i,n; / the number of elements;int wei; / the weight of a element;int m;printf(input the tot

15、al number of the Huffman Tree:);scanf(%d”,&n);w=(int *)malloc(n+1)*sizeof(int);for(i=1;iinist r at orIry HuffMauXDebugXhurffaan* -=I，1 0 I TT-r-.T/n LJn-rJ- -up error-rnr. b TfllHIUTHHIH1* .h s Lil P 项.盘 首B-CDEFH Dxrrxxrx子拖 rc-rE个/卜个辄 L # 3 4 s G女 至芳-|=玉二1,罗B11 lelnuu1 1 1 M- 1 lli - rnli wn - r,如业住

16、剃曼漏玛辞氏系统1 .生成hmF mM村 队HuFfiiw 褊留 3rHuFfnan 解码4. F.山请选择操作类型真,直置）（置1（苴1（1（姓11：直置星置星竟1（统KWMKMMKMXJtWJC34X4KCXa4MKWMSCKWJCatIBCPEF续或退出0 or n：图5.3哈夫曼译码结果通过这次课程设计，让我对一个程序的算法有更全面更进一步的认识，根据 不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有 时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这 次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效 率。在编写这个程序

17、的过程中，我复习了之前学的基本语法，哈弗曼树最小路径 的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对 程序算法改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及 综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中 发现自己平时学习的不足和薄弱环节，从而加以弥补。参考文献1苏仕华.数据结构课程设计.北京：机械工业出版社，2005 陈慧南.数据结构一C+语言描述.北京：人民邮电出版社，2005. 033 严蔚敏，吴伟民.数据结构.北京：清华大学出版社，19974 王成端，徐翠霞.数据结构上机实验与习题解析北京-中国电力出版社，20065 Adam Drozdek.数据结构与算法，北京：清华大学出版社，20066 李春葆，金晶.数据结构教程.北京：清华大学出版社，2006