资源描述：
《用c实现完整的哈夫曼编码系统》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2004年12月河 北 工 程 技 术 高 等 专 科 学 校 学 报Dec.2004第4期JOURNALOFHEBEIENGINEERINGANDTECHNICALCOLLEGENo.4文章编号:1008-3782(2004)04-0041-05用C实现完整的哈夫曼编码系统陈桂琴(河北工程技术高等专科学校计算中心,河北沧州 061001)摘要:给出了一个用C程序自动产生哈夫曼树叶结点及对应权值的哈夫曼编码系统。关键词:哈夫曼树;结点;权值;哈夫曼编码中图分类号:TP312C 文献标识码:A哈夫曼编码,常用于通信及数据传送中的二进制编码。如在进行快速远距离电报通信中,
2、它能将传送的文字信息转换成由二进制字符0和1组成的二进制串,且能使电文编码最短、最合理,从而最经济。要实现哈夫曼编码,应先构造哈夫曼树,而在构造哈夫曼树之前,必须由用户输入电文中字符的种类及各字符在电文中出现的次数,即需要用户提供哈夫曼树叶结点个数及各叶结点对应的权值。如何计算出这些数据,是在实际中不能避开的课题。本文就是为解决此问题而设计的一个完整的哈夫曼编码系统。运行该系统,用户只需输入电报文,系统就能迅速输出对应电文的准确二进制编码,而其中哈夫曼树叶结点及对应权值则由系统自动提供。1 哈夫曼编码系统111 压缩电文,提取哈夫曼树叶结点构造哈夫曼树,需要的数据之一就是
3、叶结点,而电文中所有可能出现的字符种类正是哈夫曼树叶结点。根据电报内容提取出文中出现的字符种类,是一个较复杂的字符串处理问题。在本系统中,巧妙地使用了strstr()函数,通过对字串的反复截取和拼接,去掉重复出现的字符,从而提取出电文中字符种类集合。该功能由getcode()函数完成,在getcode()函数中用字串S5保存该哈夫曼树上所有叶结点。112 统计哈夫曼树上各叶结点的权值构造哈夫曼树,需要的数据之二是各叶结点的权值。在本系统中,笔者先去掉电文中的空格,然后再对电文各类字符按出现顺序逐一进行统计,将统计出的各权值存放到结构体HNODETYPE的变量huffnod
4、e[i].weight中,该功能由huffmantree()函数完成。1.3 构造哈夫曼树,完成每个叶结点的编码有了叶结点和对应权值,就可以依据哈夫曼算法理论,实现构造哈夫曼树及完成对哈夫曼树上每个叶结点的编码。例如:当我们输入电文“callofnonfunction",其字符种类集合应为c、a、l、o、f、u、t、i,各字符在电文中出现的次数集合为2、1、2、3、2、4、1、1、1,每个字符的哈夫曼编码分别为:c=010,a=1010,l=011,o=111,f=100,n=00,u=1011,t=1100,i=1101,构造出的哈夫曼树如图1所示。1.4 输出电文编码
5、有了每个字符的哈夫曼编码,再按电文内容可得到电文的全部二进制编码,如我们可得到电文“callof收稿日期:2004209215作者简介:陈桂琴(19482),女,河北东光人,河北工程技术高等专科学校副教授。研究方向:计算机基础教育。©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.42河 北 工 程 技 术 高 等 专 科 学 校 学 报 2004nonfunction”的二进制哈夫曼编码是:01010100110111111000011100100101100010110
6、0110111100。图1 哈夫曼树及各叶结点115 哈夫曼编码系统下面是系统程序片段:#include"string.h”#include"stdio.h"#defineMAXVALUE1000ö3定义最大权值3ö#defineMAXLEAF30ö3定义哈夫曼树叶结点个数3ö#defineMAXNODEMAXLEAF32-1#defineMAXBIT30ö3定义哈夫曼编码的最大长度ötypedefstruct{intbit[MAXBIT],intstart;}HCODETYPE;typedefstruct{intweight;intparent;intlchild;in
7、trchild;}HNODETYPE;char3getcodel(char3sl,chars2,chars3)ö3去掉电文中的空格3ö{chartemp[200]="",3p,3q;p=sl;while((q=strstr(p,s2))!=NULL){3q='ø0';strcat(temp,p);strcat(temp,s3);p=q+strlen(s2);}strcat(temp,p);strcpy(sl,temp);©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrights
