霍夫曼编码及其应用

1、精选优质文档-倾情为你奉上毕 业 设 计（论文）题 目：霍夫曼编码及其应用学 院： 数 理 学 院 专业名称： 信息与计算科学 学 号： 学生姓名： 张 浩 指导教师： 韩 海 清 2011 年 4 月 20 日摘要本文首先对二元霍夫曼编码进行了细致研究，并对其算法进行扩展，得到了适用于多元霍夫曼编码的算法。然后，对霍夫曼编码的前缀性，最优性进行了证明。最后实现了霍夫曼编码在决策论中应用。关键词码 ； 熵 ； 霍夫曼编码 ； 决策树ABSTRACTThis paper first studied binary Huffman coding, and conducted a detailed s

2、tudy on its algorithm suitable for expansion, get multiple Huffman coding algorithm. Meanwhile, Huffman coding prefix sex, optimality proved. Finally realized Huffman coding applied in rigorous.KEYWORDS The Coding； The Entropy； Huffman Coding； Decision tree 目 录第一章 引言1948年，美国数学家香农（C.E.Shannon）在贝尔系统电话

3、杂志发表了题为“通信的数学理论”的长篇论文。这篇论文以概率论为工具，深刻阐述了通信工程的一系列基本理论问题，给出了计算信源信息量和信道容量的方法和一般公式，得到了一组表征信息传递重要关系的编码定理，从而创立了信息论。1959年，香农在发表的“保真度准则下的离散信源编码定理” （Coding theorems for a discrete source at the fidelity criterion）一文中系统的提出了信息率失真理论（rate-distortion theory）,为信源压缩编码的研究奠定了理论基础。在信息传输过程中，信源序列通过信源编码器实现对信源冗余度的压缩，变成编码序列

4、，编码序列通过信源译码器恢复成信源序列。根据恢复序列的效果，可把信源编译器分为两类，即无失真信源编码和限失真信源编码。在无失真信源编码的过程中，编、译码过程是可逆的，即信源符号可以通过编码序列无差错地恢复。为提高传输有效性，我们总是希望在保证无失真的条件下尽量压缩码率（编码后传输每信源符号所需的二元码符号数），但这种压缩是否有限度是一个必须要解决的理论问题。香农第一定理也就是无失真信源编码定理对这个问题做了明确回答。定理指出，只要信源编码码率不小于信源的熵就存在无失真信源编码，同时还指出如果信源编码的码率大于信源编码的熵就不存在无失真信源编码。同时，定理还给出了进行无失真信源编码的理论极值，论

5、证与指出了理想最佳信源编码是存在的。但是并没有给出信源编码的实际构造方法和实用码的结构。编码的目的就是为了优化通信系统。一般来说，通信系统的性能指标是有效性、可靠性、安全性和经济性。随着科学技术的发展和需求，人们广泛致力于对各种文本、图片、图形、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术研究，使信源的数据压缩技术得以蓬勃发展和逐渐走向成熟。霍夫曼在1952年提出了一种构造最佳码得方法，我们称之为霍夫曼编码。霍夫曼编码适用于多远独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。第二章 主要概念 香农定理作为信息

6、论的基础理论，我们有必要对进行简要介绍。下面我们给出香农三大定理：2.1香农三大定理香农三大定理是的。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。4香农第一定理是可变长无失真信源编码定理。香农第二定理是有噪信道编码定理。香农第三定理是保失真度准则下的有失真信源编码定理。具体如下:2.1.1香农第一定理(可变长无失真信源编码定理) 1设信源S的熵H(S),无噪离散信道的信道容量为C,于是,信源的输出可以进行这样的编码,使得信道上传输的为每秒个信源符号.其中a可以是任意小的正数, 要使传输的平均速率大于是不可能的。2.1.2香农第二定理（有噪信道编码定

7、理）1设某信道有r个输入符号,s个输出符号,信道容量为C,当信道的信息传输率R码长N足够长,总可以在输入的集合中(含有rN个长度为N的码符号序列),找到M （(,a为任意小的正数)个,分别代表M个等可能性的消息,组成一个码以及相应的译码规则,使信道输出端的最小平均错误译码概率Pmin达到任意小。2.1.3香农第三定理（保失真度准则下的有失真信源编码定理）1设R(D)为一离散无记忆信源的信息率失真函数,并且选定有限的失真函数,对于任意允许平均失真度,和任意小的,以及任意足够长的码长N,则一定存在一种信源编码W,其码字个数为，而编码后码的平均失真度。 2.2霍夫曼编码1952年David. A.

8、Huffman提出了一种构造最佳码的方法称之为霍夫曼码。霍夫曼码适用于多元独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。2第三章 二元霍夫曼编码及其算法二元霍夫曼编码方法的编码步骤如下：1） 将q个信源符号按概率分布的大小，以递减次序排列起来，设2） 用0和1码分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含q-1个符号的新信源，称为S信源的缩减信源。3） 把缩减信源的符号仍按概率大小以递减次序排列，再将最后两个概率最小的符号合并成一个新符号

9、，并分别用0和1码表示，这样又形成q-2个符号的缩减信源。4） 依次继续下去，直至缩减信源最后只剩两个符号为止。再将最后两个新符号分别用0和1码符号表示。最后这两个符号的概率之和比为1.然后从最后一级缩减信源开始，一编码路径右后向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。现在，给出一个具体的例子来说明这种编码方法。【例1】设单符号离散无记忆信源如下，要求对其进行二元霍夫曼编码。 =可以计算出该信源的熵为：H（X）= -=1.978b从而可以计算出每个符号的平均二元字符数为=10.46+20.30+30.12+40.06+50.03+60.02+60.01 =1.9900b该编

10、码的效率为=（1.9781/1.9900）=99.4%其编码过程如表3.1所示表3.1 二元霍夫曼编码（1）概率 码概率 码概率 码概率 码概率 码概率 码0.46 10.30 000.12 0100.06 01100.03 011100.02 0.01 0.46 10.30 000.12 0100.06 01100.03 011100.03 011110.46 10.30 000.12 0100.06 01100.06 01110.46 10.30 000.12 0100.12 0110.46 10.30 000.24 010.54 00.46 1现在将看到霍夫曼编码不是唯一的。考了最小两个

11、概率的组合（符号和），它们的和为0.03，等于与符号对应的下一个较高的概率。那么第二步，可以选择使这个组合搞了（比如说等于符号）高于或低于符号。假定把组合搞了放在下面，继续进行又将发现和组合后的概率为0.06，等于符号的概率。我们又一次可以选择是组合概率高于或低于。每次做出一种选择时，最后导致符号的码子改变。每次在有两个相同概率的情况下要做出一种选择时，我们把组合符号的概率放在上面。该信源的熵为H（X）= -=1.9781b而平均每个符号的比特数为=10.46+20.30+30.12+40.06+50.03+60.02+60.01 =1.990b该编码的效率为 =（1.9781/1.9900）

12、=99.4%因此两种编码同样有效。 表3.1 二元霍夫曼编码（2）概率 码概率 码概率 码概率 码概率 码概率 码0.46 10.30 000.12 0110.06 01010.03 010010.02 0.01 0.46 10.30 000.12 0100.06 0110.03 010000.03 010010.46 10.30 000.12 0100.6 01000.06 01010.46 10.30 000.12 0100.12 0110.46 10.30 000.24 010.54 00.46 1第四章 一般霍夫曼编码及其算法 下面我们再举个例子，讨论一下一般情况下霍夫曼编码算法的步骤

13、。由于信源字母的选取不影响对应编码方案的平均码字长度，它只与信源概率分布有关，因此在下文中用概率分布=（，）直接表示信源。【例2】已给信源概率分布为=(0.24,0.20,0.18,0.13,0.10,0.06,0.05,0.03,0.01)，信号字母表U=0,1,2,3求信源的霍夫曼编码。解 霍夫曼编码方案的主要运算步骤是构造霍夫曼数据压缩表与霍夫曼编码表。它的运算步骤如下。1. 参照表4.1构造霍夫曼数据压缩表（1）首先把概率分布的概率按降序排列，并把它们作为霍夫曼数据压缩表的第一列，该列长度为a=9。第二列、第四列、第六列为码元，暂空。（2）把第一列的三个最小概率相加，得到新的一列的概率

14、分布，重新安降序排列，成为霍夫曼数据压缩表中的第三列。这时第三列的长度为7，相加后的数为0.09，我们将其用方框标出。（3）把第三列的4个最小的概率相加得到新的一列概率分布，重新安将序排列，成为霍夫曼数据压缩表中的第五列。这时的长度为4，相加后的数为0.38，我们用方框标出。这样霍夫曼数据压缩表构造完成，有关计算于列表结果见表4.1表4.1概率 码概率 码概率 码0.240.200.180.130.100.060.050.030.010.240.200.180.130.100.060.240.200.182. 用霍夫曼数据压缩表构造霍夫曼编码表（1）因霍夫曼数据压缩表1的第五列的概率分布只有4

15、行，因此他们的编码正好是0,1,2,3。把这四个数填入霍夫曼编码表的第六列。因此，第六列是一个码长为1的编码。（2）在第五列中，带方框的概率为0.38，它对应的第六列的编码为0，而0.38是由第三列的0.13,0.10,0.09,0.06这四个数相加而成。这样我们构造第三列概率分布的编码为：第三列的0.13,0.10,0.09,0.06这四个数的编码是在0.38的编码后边延长1个数，它们分别为00,01,02,03.第三列中0.24, 0.20, 0.18这三个数的编码与第五列的编码相同，仍为1, 2, 3,不变。把0.24, 0.20, 0.18, 0.13, 0.10, 0.19, 0.0

16、6这7个数的编码1,2,3,00,01,02,03列入霍夫曼编码表的第四列。（3）在表的第三列中，带方框的概率为0.09它对应的第四列的编码为02，而0.09是由第一列的0.05,0.03,0.01这三个数相加而成。这样我们构造第一列概率分布的编码为第一列的前六个数的编码与第三列所对应的编码相同。第一列中0.05,0.03,0.01这三个数的编码是在第三列的0.09的编码02后面延长1个数，因此他们分别为020,021,022.把第一列个概率的编码列入霍夫曼编码表的第二列，最终完成霍夫曼编码表，各项计算结果见表4.2表4.2概率 码概率 码概率 码0.24 10.20 20.18 30.13

17、000.10 010.06 030.05 0200.03 0210.01 0220.24 10.20 20.18 30.13 000.10 01 020.06 03 00.24 10.20 20.18 3 下面考虑一般情形。令码字母表为U=0，1,2,3，r-1，信源概率分布=（，），对此构造霍夫曼编码的运算步骤如下。1) 简单情形下的霍夫曼编码 如果ar，那么称信源为简单情形下的编码。这时直接取每个消息元的编码为信号元，如取，这样我们只考虑ar的情形。2) 霍夫曼数据压缩表a) 设计并构造霍夫曼压缩表如下。由ar确定霍夫曼数据压缩表的行、列数。如记2k+2是数据压缩表的列数，那么k为使的最大

18、值，因此取，其中Int（z）是正数z的整数部分，而数据压缩表的第1,2,3，2k-1，2k+1列的行数（或列的长度）分别为a,kr-k+1,(k-1)r-k+2,3r-2,2r-1,r.这时除了第1,3列之外，后一列比前一列的长度少r-1，因此它的行数可用公式表示。b) 霍夫曼压缩表的第一列由概率分布（，）确定，并按将序排列。c) 霍夫曼压缩表的第三列由第一列确定，它将第一列的最后a-kr+k-1=0,那么第三列与第一列相同。d) 霍夫曼压缩表的第五列由第三列确定，它将第三列的最后r-1个分量相加，并按大小次序重新排列，相加所得到的数框出。e) 霍夫曼压缩表的第七列由第五列确定，它将第五列的最

19、后r-1个分量相加，并按大小次序重新排列，相加所得到的数框出。f) 以此类推，由此得到霍夫曼压缩表的第九，十一，列，最后一列长度为r，它由前一列确定。依次构成霍夫曼压缩表。3) 霍夫曼压缩表的有关记号由以上霍夫曼压缩表的构造，引进一下记号。记 ， （4.01）为霍夫曼压缩表的第2j-1列概率分布，其中前面已给定。且记 （4.02）是2j-1列的最后r-1个分量之和，在第j列的行上。4) 霍夫曼编码表由霍夫曼压缩表及以上式子，用递推法可以构造霍夫曼编码表，在霍夫曼编码表中，奇数列为概率分布列，已由霍夫曼压缩表确定，因此只要确定霍夫曼编码表中的偶数列即可。3递推运算步骤如下。a) 霍夫曼压缩表的最

20、后一列r个分量，因此赋予他们的编码是（0,1,，r-1），而且可自上而下排列，并填写在第2k+2列的空格内，因此霍夫曼编码表的第2k+1，2k+2列确定。b) 如果第2j+1，2j+2列确定，其中2j+1列是概率分布列，而2j+2列是编码列，记第2j+2列的码元分别为，其中是不定长码元。c) 在2j+1列中，是由式（1.02）所给定的数，他相应的编码确定为，这时第2j列的编码确定为前个的码元与第2j+2列说对应的概率的码元相同。最后r个的码元分别为（，0），（，1），.，（，r-1）。其中（，u）表示在码元后面增加一个信号字符u。这样第2j-1,2j列的概率分布与它的编码完全确定。d) 以此类

21、推，得到霍夫曼编码表中的全体编码，这时第二列的编码由第四列的编码确定，他的最后b个概率的码元由做延伸，相应的码元为 （，0），（，1），.（，b-1）其中b=a-(kr-k+1)。第五章 霍夫曼编码的性能分析5.1霍夫曼编码的前缀性定理4.1（霍夫曼码的前缀性）由霍夫曼编码算法所得到的霍夫曼码是前缀码。证明 由霍夫曼编码算法中的各步骤所知，第2k+2列中各码元各不相同，且第2k列中各码元与第2k+2列中码元相同或是某各码元的延伸，因此第2k列中各码元互不相同，且每个码元不能成为另一码元的前缀。一般情形，如果第t列中各码元各不相同，且第t-1列中各码元与第t列中码元相同或是某个码元的延伸，那么第

22、t-1列中各码元互不相同，且每个码元不能成为另一个码元的前缀。由此递推，最后得到第一列中各码元互不能成为另一码元的前缀。由此定理得证。5.2 霍夫曼编码的最优性定理定理4.2 （霍夫曼编码的最优性定理）由霍夫曼编码算法所得到的霍夫曼编码一定是最优码。对同一信源，分别是霍夫曼码与任一前缀码，那么必有成立。4第六章 霍夫曼编码的应用上面讨论了霍夫曼码，并且证明了霍夫曼码是最佳码。当N不是很大时，它能使无失真编码的效率接近于1.但霍夫曼码是分组码（或称块码），在实际应用时设备较复杂。首先，每个信源符号所对应的码长不同。一般情况下，信源符号以恒速输出，信道也是恒速传输的。通过编码后，会造成编码输出每秒

23、的比特数不是常量，因而不能直接由信道来传送。其次，信源符号与码字之间不能用某种有规律的数学方法对应起来。在对信源进行霍夫曼编码后，形成一个霍夫曼编码表，必须通过查表的方法来进行编、译码5。在信源存储与传输过程中必须首先存储这一霍夫曼编码表，这样就会影响实际信源的压缩效率。有时为了实用，尝尝先基于大量概率统计，建好霍夫曼编码表。这样编码时不需进行概率统计和建立编码表；另外在接收端和发送端可以先固定建好的霍夫曼码表，传输时也不用传输编码表。但当N增大时，信源符号数目增多，所需存储码表的容量增大，使设备复杂化，同时也是编、译码时查表搜索时间增大。6尽管如此，霍夫曼方法还是一种较具体和有效的无失真信源

24、编码方法，它便于硬件实现和计算机上软件实现。所以它仍应用于文件传真，语声处理和图像处理的数据压缩中。（霍夫曼编码在线性表中的编程实现见附录1）而今，霍夫曼编码还可以用来做决策树。如果有n个互斥随机事件，概率分别为，现用某种测试方法分步对所选择的目标事件进行识别，要求具有最小的决策平均次数，可以通过对这些事件进行霍夫曼编码来实现，因为霍夫曼编码具有最小平均码长。霍夫曼编码形成的码树可以视为决策树，方向从根到叶，其中每个节点都是决策节点。决策树被广泛应用在企业数据处理、系统分析以及数据挖掘等领域中。下面我们举个例子说明。【例3】甲手中有4张纸牌，点数分别为1,2,3,4，要求乙猜：乙可以向甲提问题

25、，甲只能用是否来回答。求乙平均最少问几个问题可以猜到纸牌的点数和相应的策略。（1）1,2,3,4,的概率均为1/4的决策树（2）1,2,3,4,的概率分别为1/2,1/4，1/8,1/8的决策树。解对于决策树问题，我们要首先进行霍夫曼编码，然后将霍夫曼编码码树变成决策树决策的设计方法：没步决策结果应该与节点分支的概率匹配。（1） 由于各点数概率相同，因此得到如图6.1所示的决策树（2） 各点数概率不同，依据霍夫曼编码得到如图6.2所示的决策树。n2? n3? n1? n=1 n=2 n=3 n=4N(1/2)Y(1/2)N(1/4)Y(1/4)N(1/4)Y(1/4)图6.1决策树n2? n3

26、? n1? n=1 n=2 n=3 n=4Y(1/2)Y(1/8)N(1/2)N(1/4)N(1/8)Y(1/8)图6.2决策树第七章 总结与展望本文先通过对二元霍夫曼编码进行研究，得出了二元霍夫曼编码算法：将q个信源符号按概率分布的大小，以递减次序排列起来，设；用0和1码分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含q-1个符号的新信源，称为S信源的缩减信源。把缩减信源的符号仍按概率大小以递减次序排列，再将最后两个概率最小的符号合并成一个新符号，并分别用0和1码表示，这样又形成q-2个符号的缩减信源。依次

27、继续下去，直至缩减信源最后只剩两个符号为止。再将最后两个新符号分别用0和1嘛符号表示。最后这两个符号的概率之和比为1.然后从最后一级缩减信源开始，一编码路径右后向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。再推广至一般霍夫曼编码即多元霍夫曼编码并得到多元霍夫曼编码算法：将q个信源符号按概率分布的大小，以递减次序排列起来，设；用0，1,2.m-1码分别分配给概率最小的m个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这m个最小概率之和作为新符号的概率，从而得到只包含q-（m-1）个符号的新信源，称为S信源的缩减信源。把缩减信源的符号仍按概率大小以递减次序排列，再将最

28、后m个概率最小的符号合并成一个新符号，并分别用0，1,2.m-1码表示，这样又形成q-2（m-1）个符号的缩减信源。依次继续下去，直至缩减信源最后只剩m个符号为止。再将最后两个新符号分别用0，1,2.m-1嘛符号表示。最后这m个符号的概率之和比为1.然后从最后一级缩减信源开始，一编码路径右后向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。霍夫曼编码广泛应用于文件传真，语声处理和图像处理的数据压缩中。但是霍夫曼算法的应用却更为广泛，例如上面提到的霍夫曼编码在决策中的应用，以及我最初的设想：将霍夫曼编码应用到生命科学中，使有上百万个脱氧核糖核酸构成的DNA序列存储起来更为迅速，更为节

29、约空间，但是由于种种原因只停留在设想阶段。未来如有幸接触到这方面的工作，我将努力将这个设想变为现实。参考文献1 Shannon, Claude. A Mathematical Theory of Communication. Bell System Technical Journal 27 (July and October, 1948): 379-423 and 623-656.2陈运. 信息论与编码M. 北京：电子工业出版社，20073 Richard B Wells. Applied Coding and Information Theory for EngineersM. Person

30、 Education North Asia Limited and China Machine Press, 20034关可，王建新，亓淑敏. 信息论与编码技术M.北京：清华大学出版社，20095曹雪虹，张宗橙.信息论与编码M.北京：清华大学出版社20096田宝玉，杨洁，贺志强，王晓湘.信息论基础M.北京：人民邮电出版社，20087 沈世镒，陈鲁生. 编码理论基础M.北京：科学出版社，20028 Robort J.McEliece. Information theory and coding theory . Beijing publishing house of electronics in

31、dustry .2007附录1#include#include#include#include#include#define LIST_INT_SIZE 100/线性表储存空间的初始分配量#define LISTINCREMENT 10/线性表储存空间的分配增量typedef struct/读取的字母的结构体，包含字母及频率char data;int ASCII;int rate;ELEM;char RFC; /保存文件中所有内容的字符串double CD=0;/*=读取文件=*/void readfile()FILE *fp;fp=fopen(RFCdoc.txt,r);char ch;in

32、t i=0;while(!feof(fp)ch=fgetc(fp);RFCi=ch;i+;CD+;fclose(fp);/*=线性表=*/typedef structELEM *elem; /储存空间基址int length; /当前长度int listsize; /当前分配的储存容量Sqlist;int SearchBin(Sqlist ST,int key,int &flag) /折半查找int low,high,mid;low=0;high=ST.length-1;mid=(low+high)/2;while(lowkey)high=mid-1;else if(ST.elemmid.AS

33、CIIkey)low=mid+1;return low;void CreatList(Sqlist &L) /创建一个顺序表int flag,xb,asc;char ch;L.elem=(ELEM *)malloc(LIST_INT_SIZE*sizeof(ELEM);if(!L.elem)printf(分配空间失败!);exit(0);L.length=0; /空表长度为0L.listsize=LIST_INT_SIZE;for(int i=0;i=L.listsize)/判断空间是否足够ELEM *newbase=(ELEM *)realloc(L.elem,(L.listsize+LIS

34、TINCREMENT)*sizeof(ELEM);if(!newbase)printf(分配空间失败!);exit(0);L.elem=newbase;L.listsize+=LISTINCREMENT;Elsefor(int j=L.length-1;j=xb;j-)L.elemj+1=L.elemj;L.elemxb.data=ch; L.elemxb.ASCII=asc;L.elemxb.rate=1;L.length+;ElseL.elemxb.rate+;void PrintList(Sqlist L) /输出顺序表for(int i=0;iL.length;i+)printf( %

35、c,%d ,L.elemi.data,L.elemi.rate);/*=赫夫曼编码=*/typedef structchar data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;void Select(HuffmanTree HT,int n,int &s1,int &s2)int i,j;int temp;for(j=1;j=n;j+)for(i=1;iHTi+1.weight)temp=HTi.weight;HTi.weight=HTi+1.weight;HTi+1.w

36、eight=temp;for(i=1,j=1;i0)，构造哈夫曼树HT， / 并求出n个字符的哈夫曼编码HC int i, j, n,m, s1, s2, start; char *cd; int c, f; n=L.length; if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0号单元未用 for (i=1; i=n; i+) /初始化HTi.weight=L.elemi-1.rate;HTi.data=L.elemi-1.data; HTi.parent=0; HTi.lc

37、hild=0; HTi.rchild=0; for (i=n+1; i=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; printf(n哈夫曼树的构造过程如下所示：n); printf(HT初态:n 结点 weight parent lchild rchild); for (i=1; i=m; i+) printf(n%4d%8d%8d%8d%8d,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild); printf( 按任意键，继续 .); getch(); f

38、or (i=n+1; i=m; i+) / 建哈夫曼树 / 在HT1.i-1中选择parent为0且weight最小的两个结点， / 其序号分别为s1和s2。 Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf(nselect: s1=%d s2=%dn, s1, s2); printf( 结点 weight parent lchild rchild); for (j=

39、1; ji; j+) printf(n%4d%8d%8d%8d%8d%8c,j,HTj.weight, HTj.parent,HTj.lchild, HTj.rchild,HTj.data); printf( 按任意键，继续 .); getch(); /- 从叶子到根逆向求每个字符的哈夫曼编码 - HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd = (char *)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1 = 0; / 编码结束符。 for (i=1; i=n; +i) / 逐个字符求哈夫曼编码start

40、= n-1; / 编码结束符位置 for (c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) / 从叶子到根逆向求编码 if (HTf.lchild=c) cd-start = 0; else cd-start = 1; HCi = (char *)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi, &cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间 / HuffmanCoding/*=保存编码=*/typedef struct/读取的字母的结构体，包含字

41、母及频率char data;char *code;int ASCII;CODE;CODE *list;int Search(Sqlist ST,int key)int low,high,mid;low=0;high=ST.length-1;mid=(low+high)/2;while(lowkey)high=mid-1;else if(listmid.ASCIIkey)low=mid+1;return -1;void save(HuffmanTree HT, HuffmanCode HC,Sqlist L)int i,n,k;list=(CODE *)malloc(L.length*sizeof(CODE);for(i=0;iL.length;i+)/初始化listi.data=L.elemi.data;listi.ASCII=L.elemi.ASCII;for(i=1;i=L.length;i+)k=(int)HTi.data;n=Search