哈夫曼编码教材课件.ppt

《哈夫曼编码教材课件.ppt》由会员分享，可在线阅读，更多相关《哈夫曼编码教材课件.ppt（56页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：霍霍 夫夫 曼曼 树树：HuffmanHuffman树及其应用树及其应用一、最优二叉树（一、最优二叉树（霍夫曼霍夫曼树）树）由一结点到另一结点间的分支所构成由一结点到另一结点间的分支所构成路径上的分支数目路径上的分支数目从树根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积结点到根的路径长度与结点上权的乘积预备知识：若干术语预备知识：若干术语debacf g树中所有树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度

2、最小的树。带权路径长度最小的树。aeae的路径长度的路径长度树长度树长度2 210101HuffmanHuffman树简介：树简介：树的带权路径长度如何计算？树的带权路径长度如何计算？WPLWPL=w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：经典之例：经典之例：经典之例：WPL=36WPL=46WPL=35哈夫曼树则是：哈夫曼树则是：WPL WPL 最小的树。最小的树。Huffman树树Weighted Path LengthWeighted Path Length2(1)(1)由给定的由给定的由给定的由给定的 n n

3、 个权值个权值个权值个权值 w w0 0,w w1 1,w w2 2,w wn n-1-1，构造具有构造具有构造具有构造具有 n n 棵扩充棵扩充棵扩充棵扩充二叉树的二叉树的二叉树的二叉树的森林森林森林森林F F=T T0 0,T T1 1,T T2 2,T Tn n-1-1 ，其中每一棵扩充二叉其中每一棵扩充二叉其中每一棵扩充二叉其中每一棵扩充二叉树树树树 T Ti i 只有一个带有权值只有一个带有权值只有一个带有权值只有一个带有权值 w wi i 的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。(2)(2)重复以下步骤

4、重复以下步骤重复以下步骤重复以下步骤,直到直到直到直到 F F 中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止：在在在在 F F 中中中中选取两棵根结点的权值最小选取两棵根结点的权值最小选取两棵根结点的权值最小选取两棵根结点的权值最小的扩充二叉树的扩充二叉树的扩充二叉树的扩充二叉树,做为左、做为左、做为左、做为左、右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为根结点的权值为根结点的权值为根结点的权值为其左、右子树上根结点的权值之和其左、

5、右子树上根结点的权值之和其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和。在在在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树加入把新的二叉树加入把新的二叉树加入 F F。构造霍夫曼树的基本思想：构造霍夫曼树的基本思想：构造构造HuffmanHuffman树的步骤（即树的步骤（即HuffmanHuffman算法）：算法）：权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径。先先举例！举例！3例

6、例1：设有设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别为出现的频度分别为7,5,2,47,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？，怎样编码才能使它们组成的报文在网络中传得最快？法法1 1：等长编码等长编码。例如用二进制编码来实现。例如用二进制编码来实现。取取 d=d=0000，i=i=0101，a=a=1010，n=n=1111怎样实现怎样实现HuffmanHuffman编码？编码？法法2 2：不等长编码不等长编码，例如用哈夫曼编码来实现。，例如用哈夫曼编码来实现。取取 d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111

7、最快的编码是哪个？最快的编码是哪个？是非等长的是非等长的HuffmanHuffman码！码！先要构造先要构造HuffmanHuffman树！树！4操作要点操作要点1 1：对权值的合并、删除与替换对权值的合并、删除与替换在权值集合在权值集合7,5,2,47,5,2,4中，总是合并中，总是合并当前值最小当前值最小的两个权的两个权构造构造HuffmanHuffman树的步骤：树的步骤：注：方框表示外结点（叶子，字符对应的权值注：方框表示外结点（叶子，字符对应的权值），），圆框表示内结点（合并后的权值）。圆框表示内结点（合并后的权值）。5操作要点操作要点2 2：按左按左0 0右右1 1对对Huffma

8、nHuffman树的所有分支编号！树的所有分支编号！d da ai in n1 11 11 10 00 00 0HuffmanHuffman编码结果：编码结果：d=d=0 0,i=,i=1010,a=,a=110110,n=,n=111111WPL=1bitWPL=1bit7 72bit2bit5+3bit(2+4)=5+3bit(2+4)=3535特点：每一码都不是另一码的前缀，绝不会错译特点：每一码都不是另一码的前缀，绝不会错译!称为前缀码称为前缀码将将将将 HuffmanHuffman树树 与与 HuffmanHuffman编码编码 挂钩挂钩6例例2 2：假设用于通信的电文仅由假设用于通

9、信的电文仅由8 8个字母个字母 a,b,c,d,e,f,a,b,c,d,e,f,g,hg,h 构成，它们在电文中出现的概率分别为构成，它们在电文中出现的概率分别为 0.07,0.19,0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.100.02,0.06,0.32,0.03,0.21,0.10，试为这，试为这8 8个字母设计个字母设计哈夫曼哈夫曼编码。编码。如果用如果用0 07 7的二进制编码方案又如何？的二进制编码方案又如何？霍夫曼霍夫曼编码的基本思想是：编码的基本思想是：概率大的字符用短码，概率小的用概率大的字符用短码，概率小的用长码。由于长码。由于霍夫曼树的霍夫

10、曼树的WPLWPL最小，最小，说明编码所需要的比特数最说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。少。这种编码已广泛应用于网络通信中。解：解：先将概率放大先将概率放大100100倍，以方便构造哈夫曼树。倍，以方便构造哈夫曼树。权值集合权值集合 w=7,19,2,6,32,3,21,10w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。7w4=19,21,w4=19,21,28,28,32 32为清晰起见，重新排序为为清晰起见，重新排序为:w=2,3,6,7,10,19,21

11、,32w=2,3,6,7,10,19,21,322 23 35 56 6w1=w1=5,5,6,7,10,19,21,32 6,7,10,19,21,32w2=7,10,w2=7,10,11,11,19,21,32 19,21,32w3=w3=11,17,11,17,19,21,32 19,21,32111110107 717172828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼树哈夫曼树 8对应的哈夫曼编码（左对应的哈夫曼编

12、码（左0右右1）：）：2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 0符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的码的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.4

13、4+0.92+0.25=2.61 WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 11001100000011110111101110111010101111111111010111011101000001010011100101110111二进制码二进制码二进制码二进制码9另一种结果表示：另一种结果表示：10例例3 3：设字符集为设字符集为2626个英文字母，其出现频度如下表所个英文字母，其出现频度如下表所示。示。51481156357203251频度频度zyxwvut t字符字符11611882380频度频度p21fq15gr47hsonml

14、kj字符字符5710332221364186频度频度ie edcba空格空格空格空格字符字符先建哈夫曼树，再利用此树对报文先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。进行编码和译码。要求编程实现：要求编程实现：11提示提示1 1：霍夫曼树中各结点的结构霍夫曼树中各结点的结构可以定义为如下可以定义为如下5 5个分量：个分量：charweight parentlchildRchild将整个将整个霍夫曼树的霍夫曼树的结点结点存储在一个数组中：存储在一个数组中：HT1.n;HT1.n;将结点的将结点的编码编码存储在存储在HC1.nHC1.n中

15、。中。提示提示3 3：霍夫曼树如何构造？霍夫曼树如何构造？构造好之后又如何求得构造好之后又如何求得各结点对应的霍夫曼编码？各结点对应的霍夫曼编码？提示提示2 2：霍夫曼树的霍夫曼树的存储结构存储结构可采用可采用顺序存储顺序存储结构：结构：12需求分析需求分析1.1.写一个对写一个对txt文件压缩和解压的程序，使用动态编码。文件压缩和解压的程序，使用动态编码。2.2.使用使用Huffman编码压缩和解压时，编码压缩和解压时，Huffman树的存储可以直接树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建存储树结构，也可以存储所有字符的频度或权值，然后读取时建立立Huffma

16、n树；树；3.3.使用使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为为1，需要在建立，需要在建立Huffman树时把它看作一个独立的字符进行建树。树时把它看作一个独立的字符进行建树。4.4.使用使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集

17、的比特数满码比特流，每当收集的比特数满8时，可以把这时，可以把这8比特通过位操作比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。再写入文件）。写入文件的最小信息单位为字节。应用：压缩程序 哈弗曼编码算法13概要分析概要分析采用顺序表实现对采用顺序表实现对Huffman树的存储树的存储 /-Huffman /-Huffman树存储结树存储结构构-typedef structtypedef struct int weight;int weight;int lchild,rchi

18、ld,parent;int lchild,rchild,parent;HuffmanTree;HuffmanTree;typedef HuffmanTree HTreem;typedef HuffmanTree HTreem;weightweight域存有该节点字符的权值，域存有该节点字符的权值，lchild、rchild、parent分别存放该节点的左孩子、分别存放该节点的左孩子、右孩子和双亲节点在顺序表中的位置。右孩子和双亲节点在顺序表中的位置。14采用顺序表实现对采用顺序表实现对Huffman编码的存储编码的存储 /-Huffman编码存储结构编码存储结构-typedef struct

19、char ch;int start;char bitsn+1;HuffmanCode;typedef HuffmanCode HCoden;ch存放对应的字符，存放对应的字符，start存放存放Huffman编码在字符数编码在字符数组组bits中开始的位置。中开始的位置。15抽象数据抽象数据抽象数据类型定义：抽象数据类型定义：ADT ADT 数据对象：数据对象：txt文档文档基本操作：基本操作：FileRead(int count,char s,char filename)FileRead(int count,char s,char filename)初始条件：压缩文档存在。初始条件：压缩文档

20、存在。操作结果：对该文档进行读取，求其所有出现的字符和字符的权值。操作结果：对该文档进行读取，求其所有出现的字符和字符的权值。CreateHuffmanTree(HTree T,int N,int count,char s)CreateHuffmanTree(HTree T,int N,int count,char s)初始条件：以求得该文档的字符和权值。初始条件：以求得该文档的字符和权值。操作结果：建立操作结果：建立Huffman树。树。HuffmanCoding(HTree T,HCode H,int N,char s)HuffmanCoding(HTree T,HCode H,int N

21、,char s)初始条件：初始条件：Huffman树。树。操作结果：求各个字符的操作结果：求各个字符的Huffman编码。编码。16FilePrint(HTree T,HCode H,int N)FilePrint(HTree T,HCode H,int N)初始条件：求得初始条件：求得Huffman编码以及编码以及 各节点的权值。各节点的权值。操作结果：将求得的数据分别存放在操作结果：将求得的数据分别存放在HuffmanCode.txt、Char.txt、Weight.txt中。中。FileWrite(HCode H,int N,char filename)FileWrite(HCode H

22、,int N,char filename)初始条件：求得初始条件：求得Huffman编码以及编码以及 各节点的权值。各节点的权值。操作结果：将文档翻译成操作结果：将文档翻译成Huffman编码以字符形式存放在编码以字符形式存放在File.txt中。中。FileConvert(void)FileConvert(void)初始条件：初始条件：File.txt存在。存在。操作结果：将字符形式的操作结果：将字符形式的Huffman编码翻译成二进制形式，每首季编码翻译成二进制形式，每首季8比特比特就通过位操作合并成一个字节写入文件就通过位操作合并成一个字节写入文件code.txt中，最后不足中，最后不足

23、8 位时将最位时将最后的几位存放在后的几位存放在Tail.txt中。中。FileRead(HTree T,HCode H)初始条件：压缩生成的HuffmanCode.txt、Char.txt、Weight.txt存在。操作结果：读取字符及其权值和其Huffman编码。17FileExtract(void)初始条件：压缩结果文件Code.txt和tail.txt存在。操作结果：将code.txt和tail.txt中的字符写成编码的二进制字符形式，写进file00.txt。FileTrans(HTree T,HCode H,int N)初始条件：已生成File00,txt并已求得各个字符的Huff

24、man编码，Huffman树已建立。操作结果：将Huffman编码翻译成原文件，写入translated.txt。ADT还需要包含调用若干库文件：stdio.h,malloc.h,string.h。18主函数 统计字符，得出统计出的字符的权值n编码解码退出根据权值进行建立哈夫曼树输出哈夫曼树输出编码压缩编码生成二进制文件解压生成新的文本文档19采用C语言的编程方法在VC+6.0环境下实现本题目的要求。主程序流程图建立哈夫曼树输出哈夫曼树 输出编码根据哈夫曼树编码对编码进行压缩根据哈夫曼树解码生成二进制文件对二进制文件进行解压生成文本文档20#include#include#include#de

25、fine MAX_SIZE 1000000#define n 150#define m 2*n-1 typedef struct char ch;int weight;int lchild,rchild,parent;HuffmanTree;typedef HuffmanTree HTreem;typedef struct char ch;char bitsn+1;HuffmanCode;typedef HuffmanCode HCoden;一.宏定义及节点定义压缩部分21 由于文档限于英文文章，所以字符的由于文档限于英文文章，所以字符的ASC II码限于码限于0150。依次读取文。依次读取文

26、档的各个字符，计算每个字符出现的次数为权值，再将数组压缩：没有出现档的各个字符，计算每个字符出现的次数为权值，再将数组压缩：没有出现的字符从数组中删去。返回文档出现不同字符的个数的字符从数组中删去。返回文档出现不同字符的个数算法如下：算法如下：1 1、统计字符出现的频率，即权值的函数、统计字符出现的频率，即权值的函数int apprate(char*s,int cnt,char str);方法具体实现如下：方法具体实现如下：定义两个数组，分别存放大写和小写英文字母。定义两个数组，分别存放大写和小写英文字母。a.将两个数组初始化都为将两个数组初始化都为0.b.如果取出的字符是小写字母，则将小写字

27、母转换为数字，每一个字符对应如果取出的字符是小写字母，则将小写字母转换为数字，每一个字符对应一个数字，同一个字符出现一次频率就加一个数字，同一个字符出现一次频率就加1，直到全部统计出为止，如果取，直到全部统计出为止，如果取出的是大写字母，方法如小写字母的实现方法。出的是大写字母，方法如小写字母的实现方法。c.再将转换都的数字再转换为相应的字符，以便为下面的建树方便调用。再将转换都的数字再转换为相应的字符，以便为下面的建树方便调用。具体代码如下：具体代码如下：二二 读取原文档函数读取原文档函数22int FileRead(int count,char s,char filename)int i=

28、0,N=0,k=0,tempn;char c;FILE*rf;rf=fopen(filename,r);if(rf=NULL)printf(cannot open filen);exit(0);for(i=0;in;i+)tempi=0;counti=0;while(!feof(rf)c=fgetc(rf);k=c;tempk+;i+;fclose(rf);for(i=0;in;i+)if(tempi!=0)sN=i;countN=tempi;N+;return N;/FileRead23三三 生成Huffman树函数 选取字符中权值最小的两个节点建树，将权值相加放在根节点中，将原节点删除，新

29、节点放入数组。递归进行上述操作直到数组中只有一个节点为止。算法如下：2、建立哈夫曼树构造哈夫曼数时，首先将n个权值的叶子结点存放到数组huffTree2*num的前n个分量中，然后不断的将两棵子树合并为一棵子树，并将新子树的根结点顺序存放到数组huffTree2*num的前n个分量的后面。设n个叶子的权值保存在数组cntn中，哈夫曼树的存储主要是利用数组存储，例如将已知字符窜s为abcdeacedaeadcedabadadaead统计出的字符频率分别为a:9,b:2,c:3,d:7,e:5则构造哈夫曼树的存储空间的初始状态最后状态如图：24序号序号字符名字符名称称weightweightpar

30、entparentlchildlchildrchildrchild1 1a a9 90 00 00 02 2b b2 20 00 00 03 3c c3 30 00 00 04 4d d7 70 00 00 05 5e e5 50 00 00 06 60 00 00 07 70 00 00 08 80 00 00 09 90 00 00 0初始状态初始状态25序号序号字符名字符名称称weightweightparentparentlchildlchildrchildrchild1 1A9 98 80 00 02 2B2 26 60 00 03 3C3 36 60 00 04 4D7 78 80

31、 00 05 5E5 57 70 00 06 65 57 72 23 37 710109 95 56 68 816169 94 41 19 926260 07 78 8最后状态最后状态26 伪代码描述为:1.数组哈夫曼树HuffmanTree初始化，所有元素结点的双亲、左右孩子都置为0；2.数组哈夫曼树HuffmanTree的前n个元素的权值给定权值cntn；3.进行n-1次合并c.1、在二叉树集合中选取两个权值最小的根结点，其下标分别为i1和i2；c.2、将二叉树i1和i2合并为一棵新的二叉树k27void CreateHuffmanTree(HTree T,int N,int count,

32、char s)void CreateHuffmanTree(HTree T,int N,int count,char s)int i,j,p1=0,p2=0,l1,l2;int i,j,p1=0,p2=0,l1,l2;for(i=0;i2*N-1;i+)for(i=0;i2*N-1;i+)Ti.lchild=0;Ti.lchild=0;Ti.rchild=0;Ti.rchild=0;Ti.parent=0;Ti.parent=0;for(i=0;iN;i+)for(i=0;iN;i+)Ti.weight=counti;Ti.weight=counti;for(i=N;i2*N-1;i+)for

33、(i=N;i2*N-1;i+)l1=l2=1000000;l1=l2=1000000;for(j=0;ji;j+)for(j=0;ji;j+)if(Tj.parent=0)if(Tj.parent=0)if(Tj.weightl1)if(Tj.weightl1)l1=Tj.weight l1=Tj.weight,p1=j;p1=j;for(j=0;ji;j+)for(j=0;ji;j+)if(Tj.parent=0)if(Tj.parent=0)if(Tj.weightl2)&(j!=p1)if(Tj.weightl2)&(j!=p1)l2=Tj.weight l2=Tj.weight,p2=

34、j;p2=j;Tp1.parent=i;Tp1.parent=i;Tp2.parent=i;Tp2.parent=i;Ti.lchild=p1;Ti.lchild=p1;Ti.rchild=p2;Ti.rchild=p2;Ti.weight=Tp1.weight+Tp2.weight;Ti.weight=Tp1.weight+Tp2.weight;T2*N-2.parent=0;/CreateHuffmanTree T2*N-2.parent=0;/CreateHuffmanTree28四 求Huffman编码函数：从叶子节点找到根节点，若该节点是双亲节点的左孩子为1，反之为0，直到根节点为止

35、求得该节点Huffman编码的逆序列;1.、对哈夫曼树进行编码函数voidHuffmancoding(element huffTree,Code CodeNode,char str,int n);主要思想：规定哈夫曼编码树的左分支代表0，右分支代表1，则从根结点对应的字符的编码，称为哈夫曼编码。例如上面所举例子的哈夫曼编码构造树及哈夫曼编码2926101655792330字符字符频率频率编码编码a a9 91111b b2 2010010c c3 3011011d d7 71010E5 5000031 对每个叶子结点进行编码：a.1初始化编码深度为0，将孩子结点的双亲结点付给一个变量，双亲结点

36、不为空时，深度加1，继续向上查找，这时该双亲结点已变成孩子结点，循环知道双亲结点为空，求出每一个叶子结点的深度。a.2将编码初始结点初始化为深度+1，将孩子结点的双亲结点付给一个变量，双亲结点不为空时，初始结点-1，如果此孩子为双亲的左孩子，则置为0，否则置为1，循环知道双亲结点为空。编码完毕！32函数C代码：void HuffmanCoding(HTree T,HCode H,int N,char s)int c,p,i,start;char cdn+1;cdN+1=0;for(i=0;iN;i+)Hi.ch=si;start=N;c=i;p=Tc.parent;while(p)if(Tp.

37、lchild=c)cd-start=0;else cd-start=1;c=p;p=Tp.parent;Hi.start=start;strcpy(Hi.bits,cd);/HuffmanCoding33五.输出解压信息函数：将求得的数据分别存放在HuffmanCode.txt、Char.txt、Weight.txt中函数C代码：void FilePrint(HTree T,HCode H,int N)int i,j=0;FILE*rf,*fp,*rp;rf=fopen(HuffmanCode.txt,w);fp=fopen(Char.txt,w);rp=fopen(Weight.txt,w)

38、;while(jN)for(i=Hj.start;iN;i+)fprintf(rf,%c,Hj.bitsi);fprintf(rf,n);j+;for(i=0;iN;i+)fputc(Hi.ch,fp);for(i=0;iN;i+)fprintf(rp,%dn,Ti.weight);fclose(rf);fclose(fp);fclose(rp);/FilePrint34六.翻译成Huffman编码函数：读取原文件，将每个字符翻译成Huffman编码，以字符形式输导File.txt中。读取原文件，将每个字符翻译成Huffman编码，以字符形式输导File.txt中。函数C代码：35void F

39、ileWrite(HCode H,int N,char filename)int i,k,p=0;char c;FILE*rf,*fp;rf=fopen(filename,r);fp=fopen(File.txt,w);if(rf=NULL)printf(cannot open filenn );exit(0);while(!feof(rf)c=fgetc(rf);for(i=0;iN;i+)if(Hi.ch=c)for(k=Hi.start;kN;k+)fputc(Hi.bitsk,fp)，p+;if(p=8)fprintf(fp,);p=0;fclose(rf);fclose(fp);/F

40、ileWrite36七.压缩函数函数读取File.txt文档，每8位子符翻译成二进制，在转化成十进制在翻译成字符，输出到Code.txt中，最后不足8位的部分不翻译，直接写入Tail.txt中，最后将中间文档File.txt删除。主要思想：主要采用二进制转换为十进制的方法进行解压处理。代码如下：37void FileConvert(void)void FileConvert(void)int i=0,k=0,temp=0,l;int i=0,k=0,temp=0,l;char st10;char st10;FILE*rf,*fp,*rp;FILE*rf,*fp,*rp;rf=fopen(Fil

41、e.txt,r);rf=fopen(File.txt,r);fp=fopen(Code.txt,wb);fp=fopen(Code.txt,wb);rp=fopen(Tail.txt,w);rp=fopen(Tail.txt,w);if(rf=NULL)if(rf=NULL)printf(cannot open filenn );printf(cannot open filenn );exit(0);exit(0);while(!feof(rf)while(!feof(rf)sti=fgetc(rf);sti=fgetc(rf);switch(sti)switch(sti)case0:case

42、0:k=2*k+0;k=2*k+0;i+;break;i+;break;case1:case1:k=2*k+1;k=2*k+1;i+;break;i+;break;case:case:fwrite(&k,1,1,fp);fwrite(&k,1,1,fp);temp+;temp+;k=0;k=0;i=0;break;i=0;break;default:default:fprintf(rp,%d,temp);fprintf(rp,%d,temp);for(k=0;ki;k+)fprintf(rp,%c,stk);break;for(k=0;ki;k+)fprintf(rp,%c,stk);brea

43、k;fclose(rf);fclose(rf);fclose(fp);fclose(fp);fclose(rp);fclose(rp);l=remove(File.txt);l=remove(File.txt);/FileConvert/FileConvert38八 压缩程序main函数部分代码如下：void main()HTree T;HCode H;nt N;int countn;char sn,filename10;printf(n);printf(Input Filenamen);scanf(%s,filename);printf(n);printf(Encoding.n);N=Fil

44、eRead(count,s,filename);printf(CharacterIn Char.txtn);printf(CharacterWeight In Weight.txtn);CreateHuffmanTree(T,N,count,s);HuffmanCoding(T,H,N,s);FilePrint(T,H,N);printf(Huffman Code In HuffmanCode.txtn);FileWrite(H,N,filename);FileConvert();printf(Code File In Code.txtn);printf(Tail File In Tail.t

45、xtn);39压缩部分：主要思想为：对字符窜编码的解码是将编码窜从左到右逐为判别，直到确定一个字符。这可以用生成哈夫曼的逆过程实现。从根结点开始，根据每一位的值是0还是1确定选择左分支还是右分支，直到到达一个叶子结点，然后再从根结点出发，开始下一个字符的翻译。如根据上面的（a）哈夫曼编码树对生成的(b)字符编码表进行解码，从根结点开始，由于第一位是1，所以选择右分支，下一位又是1，又选择右分支，到达叶子结点对应的字符a。再从根结点出发，下一位是0，选择左分支，再下一位是1，则选择右分支，再下一结点为0，选择左分支，到达叶子结点对应的字符c，同理，知道所有的字符都被解出伪代码如下：创建新的文本文

46、档b、读取压缩的二进制文件：按照编码的先后顺序进行读取编码，当文件没结束时，读取编码，从根结点开始，如果此结点有子结点，如果读取的编码为0并且是根结点的左孩子，则将此左孩子置为根结点，如果读取的编码为1并且是根结点的右孩子，则将此右孩子置为根结点，否则的话说明已经有一个字符和编码对应了,输出，再从根结点开始，重复上述过程，知道读取的文件为空，解码完毕。c、关闭文件40#include/#include/预处理及相关结构变量声明部分预处理及相关结构变量声明部分#include#include#include#include#define MAX_SIZE 1000000#define MAX_S

47、IZE 1000000#define n 150#define n 150#define m 2*n-1#define m 2*n-1typedef structtypedef struct char ch;char ch;int weight;int weight;int lchild,rchild,parent;int lchild,rchild,parent;HuffmanTree;HuffmanTree;typedef HuffmanTree HTreem;typedef HuffmanTree HTreem;typedef structtypedef struct char ch;c

48、har ch;char bitsn+1;char bitsn+1;HuffmanCode;HuffmanCode;typedef HuffmanCode HCoden;typedef HuffmanCode HCoden;41一.读取解压信息函数：读取字符及其权值和其Huffman编码。函数C代码：int i=0,j=0,N=0;char c,*p;char strMAX_SIZE;FILE*rf,*fp,*rp;rf=fopen(Char.txt,r);fp=fopen(HuffmanCode.txt,r);rp=fopen(Weight.txt,r);if(rf=NULL)printf(c

49、annot open filen);exit(0);if(fp=NULL)printf(cannot open filen);exit(0);if(rp=NULL)printf(cannot open filen);exit(0);42while(!feof(rf)HN.ch=fgetc(rf);TN.ch=HN.ch;N+;while(!feof(fp)c=fgetc(fp);switch(c)casen:i+;j=0;break;default:Hi.bitsj=c;j+;Hi.bitsj=0;break;for(i=0;iN;i+)Ti.weight=0;i=0;j=0;while(!f

50、eof(rp)c=fgetc(rp);switch(c)casen:for(p=str;*p!=0;p+)Ti.weight=Ti.weight*10+*p-48;i+;j=0;break;default:strj=c;j+;strj=0;break;fclose(rf);fclose(fp);fclose(rp);return N-1;/FileRead43二翻译为Huffman编译文档函数：将Code.txt重新翻译成二进制，在以字符形式输入到File00.txt中，再将Tail.txt中的最后编码复制到File.txt的最后。函数C代码：int FileExtract(void)int