2022年哈夫曼树解压与压缩.pdf

《2022年哈夫曼树解压与压缩.pdf》由会员分享，可在线阅读，更多相关《2022年哈夫曼树解压与压缩.pdf（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、哈夫曼树解压与压缩哈夫曼树的压缩与解压1. 算法简要描述1、哈夫曼算法1. 哈弗曼算法就是根据给定的n 个权值 w1,w2,w3 、 、 、 、 、 、 、 wn, 构造由 n 棵二叉树构成的深林F=T1,T2, 。 。 。 。Tn, 其中每个二叉树 Ti 分别都就是只含有一个权值 wi 的根结点 ,其左右子树为空 (i=1,2)。2. 在深林 F 中选取其根结点的权值最小的两棵二叉树,分别作其左右子树构造一颗新的二叉树 ,并置这棵新的二叉树根结点的权值为其左右子树的根结点之与。3. 从 F 中删去这两棵二叉树 ,同时刚新生成的二叉树加入到深林F 中。4. 重复 2,3,步骤,直至深林 F 中

2、只含有一颗二叉树为止。2、哈夫曼树的实现函数 String EnCode(Char Type ch): 表示哈夫曼树已存在 ,返回字符 ch的编码。函数 LinkListUnCode(String strCode):表示对哈夫曼树进行译码 ,返回编码前的字符序列。根据算法可以瞧出,在具有 n 个结点权值的哈夫曼树的构造过程中,每次都就是从 F 中删去两棵树 ,增加一棵树 ,即每次结束后减少一棵树 ,经过 n-1 次处理后 ,F 中就只剩下一棵树了。另外,每次合并都要产生一个新的结点,合并 n-1次后共产生了 n-1个新结点 ,并且这 n-1个新节点都就是具有左右子树的分支结点。则最终得到的哈夫

3、曼树中共有2n-1 个结点 ,并且其中没有度为1 的分支结点 ,最后一次产生的新结点就就是哈夫曼树的根结点。源 代 码 中 创 建 了 一 个 哈 夫 曼 树 结 点 类 , 其 中 有 数 据 成 员weight,parent,leftChild,rightChild 分别代表了权值 ,双亲,左孩子 ,右孩子。在哈夫曼树类中有数据成员*nodes,*LeafChars,*LeafCharCodes,curPos,num, 分别用来存储结点信息,叶结点字符信息 ,叶结点字符编码信息,译码时从根结点到叶结点路径的当前结点,叶结点个数。哈夫曼树类中含有多个函数,有构造函数 ,析构函数等。由函数Hu

4、ffmanTree(CharType ch,WeightType w,int n) 来构造由字符,权值 ,与字符个数构造哈夫曼树,在根据哈夫曼算法很容易实现哈夫曼类的函数以及构造函数。在在算法中,求叶结点字符的编码时 ,需要从叶结点出发走一条从高叶结点到根结点的路径,而编码却就是从根结点出发到叶结点的路径,由左分支为编码 0,右分支为编码1,得到的编码 ,因此从叶结点出发到根结点的路径得到的编码就是实际编码的逆序,并且编码长度不确定 ,又由于可以再线性链表中构造串,因此将编码的信息储存在一个线性立案标准,每得到一位编码都将其插入在线性链表的最前面。在求某个字符的编码就是由函数EnCode(Ch

5、arType ch) 来求,返回字符编码。在进行译码时 ,用一个线性链表存储字符序列,由函数 Decode(String strCode) 来求,对编码串strCode进行译码 ,返回编码前的字符序列。函数Compress()用哈夫曼编码压缩文件 。函数 Decompress()解压缩用哈夫曼编码压缩的文件。在主函数中有两个选项 ,一个就是选择编码压缩 ,一个就是解压。在函数中使用了文件输入输出流 ,我们可以选择要压缩的文件名输入,在选出压缩文件保存的地方与文件类型 ,将压缩所得到的文件存储在另一个文件中,解压也就是如此。精品资料 - - - 欢迎下载 - - - - - - - - - -

6、- 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩2. 源代码#ifndef _HUFFMAN_TREE_NODE_H_ #define _HUFFMAN_TREE_NODE_H_ / 哈夫曼树结点类模板template struct HuffmanTreeNode WeightType weight; / 权数据域unsignedint parent, leftChild, rightChild; / 双亲 , 左右孩子域HuffmanTreeNode(); / 无参数的构造函数模板Huffman

7、TreeNode(WeightType w, int p = 0, int lChild = 0, int rChild = 0); / 已知权 , 双亲及左右孩子构造结构; / 哈夫曼树结点类模板的实现部分template HuffmanTreeNode:HuffmanTreeNode()/ 操作结果 : 构造空结点 parent = leftChild = rightChild = 0; template HuffmanTreeNode:HuffmanTreeNode(WeightType w, int p, int lChild, int rChild) / 操作结果 : 构造一个权为

8、w,双亲为 p, 左孩子为 lChild,右孩子为 rChild 的结点 weight = w; / 权parent = p; / 双亲leftChild = lChild; / 左孩子rightChild = rChild; / 右孩子 #endif #ifndef _HUFFMAN_TREE_H_ #define _HUFFMAN_TREE_H_ #includestring、h/ 串类#includehuffman_tree_node、h/ 哈夫曼树结点类模板/ 哈夫曼树类模板template class HuffmanTree protected: HuffmanTreeNode *n

9、odes; / 存储结点信息 ,nodes0未用CharType *LeafChars; / 叶结点字符信息,LeafChars0未用String *LeafCharCodes; / 叶结点字符编码信息,LeafCharCodes0未用int curPos; / 译码时从根结点到叶结点路径的当前结点int num; / 叶结点个数精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩/ 辅助函数模板 : void Select(in

10、t cur, int &r1, int &r2); / nodes1 cur中选择双亲为 , 权值最小的两个结点 r1,r2 void CreatHuffmanTree(CharType ch, WeightType w, int n); / 由字符 , 权值与字符个数构造哈夫曼树public : / 哈夫曼树方法声明及重载编译系统默认方法声明: HuffmanTree(CharType ch, WeightType w, int n); / 由字符 , 权值与字符个数构造哈夫曼树virtual HuffmanTree(); / 析构函数模板String Encode(CharType ch)

11、; / 编码LinkList Decode(String strCode); / 译码HuffmanTree( const HuffmanTree ©); / 复制构造函数模板HuffmanTree &operator =(const HuffmanTree& copy); / 重载赋值运算符; / 孩子兄弟表示哈夫曼树类模板的实现部分template void HuffmanTree:Select(int cur, int &r1, int &r2) / 操作结果 :nodes1 cur中选择双亲为 , 权值最小的两个结点r1,r2 r1 = r2 = 0; / 0 表示空结点for

12、 ( int pos = 1; pos = cur; pos+) / 查找树值最小的两个结点if (nodespos、parent != 0) continue ; / 只处理双亲不为的结点if (r1 = 0) r1 = pos; / r1为空, 将pos赋值给 r1 elseif (r2 = 0) r2 = pos; / r2为空, 将pos赋值给 r2 elseif(nodespos、weight nodesr1、weight) r1 = pos; / nodespos权值比 nodesr1更小 ,将pos赋为 r1 elseif (nodespos、weight nodesr2、wei

13、ght) r2 = pos; / nodespos权值比 nodesr2更小 ,将pos赋为 r2 template void HuffmanTree:CreatHuffmanTree(CharType ch, WeightType w, int n) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩/ 操作结果 : 由字符 , 权值与字符个数构造哈夫曼树 num = n; / 叶结点个数int m = 2 * n - 1;

14、/ 结点个数nodes = new HuffmanTreeNodem + 1; / nodes0未用LeafChars = new CharTypen + 1; / LeafChars0未用LeafCharCodes = new Stringn + 1; / LeafCharCodes0未用int pos; / 临时变量for (pos = 1; pos = n; pos+) / 存储叶结点信息nodespos 、weight = wpos - 1; / 权值LeafCharspos = chpos - 1; / 字符 for (pos = n + 1; pos = m; pos+) / 建立

15、哈夫曼树int r1, r2; Select(pos - 1, r1, r2); / nodes1 pos - 1 中选择双亲为 ,权值最小的两个结点r1,r2 / 合并以 r1,r2 为根的树nodesr1 、parent = nodesr2、parent = pos; / r1,r2双亲为 pos nodespos 、leftChild = r1; / r1为pos的左孩子nodespos 、rightChild = r2; / r2为pos的右孩子nodespos 、weight = nodesr1、weight + nodesr2、weight;/pos 的权为 r1,r2 的权值之与

16、 for (pos = 1; pos = n; pos+) / 求n个叶结点字符的编码LinkList charCode; / 暂存叶结点字符编码信息for ( unsignedint child = pos, parent = nodeschild、parent; parent != 0; child = parent, parent = nodeschild、parent) / 从叶结点到根结点逆向求编码if (nodesparent、leftChild = child) charCode、Insert(1, 0 ); / 左分支编码为0 else charCode 、Insert(1,

17、1 ); / 右分支编码为 1 LeafCharCodespos = charCode; / charCode中存储字符编码 curPos = m; / 译码时从根结点开始,m为根 template HuffmanTree:HuffmanTree(CharType ch, WeightType w, int n) / 操作结果 : 由字符 , 权值与字符个数构造哈夫曼树 CreatHuffmanTree(ch, w, n); / 由字符 , 权值与字符个数构造哈夫曼树 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - -

18、 - -第 4 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩template HuffmanTree:HuffmanTree() / 操作结果 : 销毁哈夫曼树 if (nodes != NULL) delete nodes; / 释放结点信息if (LeafChars != NULL) delete LeafChars; / 释放叶结点字符信息if (LeafCharCodes != NULL) delete LeafCharCodes; / 释放叶结点字符编码信息 template String HuffmanTree:Encode(CharType ch)

19、 / 操作结果 : 返回字符编码 for ( int pos = 1; pos = num; pos+) / 查找字符的位置if (LeafCharspos = ch) return LeafCharCodespos;/ 找到字符 , 得到编码 throw Error( 非法字符 , 无法编码 ! ); / 抛出异常 template LinkList HuffmanTree:Decode(String strCode) / 操作结果 : 对编码串 strCode 进行译码 , 返回编码前的字符序列 LinkList charList; / 编码前的字符序列for ( int pos = 0;

20、 pos strCode、Length(); pos+) / 处理每位编码if (strCodepos = 0 ) curPos = nodescurPos、leftChild; / 0表示左分支else curPos = nodescurPos、rightChild; / 1表示左分支if (nodescurPos、leftChild = 0 & nodescurPos、rightChild = 0) / 译码时从根结点到叶结点路径的当前结点为叶结点charList、Insert(charList、Length() + 1, LeafCharscurPos); curPos = 2 * nu

21、m - 1; / curPos回归根结点 return charList; / 返回编码前的字符序列 template HuffmanTree:HuffmanTree(const HuffmanTree ©) / 操作结果 : 由哈夫曼树 copy构造新哈夫曼树复制构造函数模板 num = copy 、num; / 叶结点个数curPos = copy、curPos; / 译码时从根结点到叶结点路径的当前结点int m = 2 * num - 1; / 结点总数nodes = new HuffmanTreeNodem + 1; / nodes0未用精品资料 - - - 欢迎下载 - -

22、 - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩LeafChars = new CharTypenum + 1; / LeafChars0未用LeafCharCodes = new Stringnum + 1; / LeafCharCodes0未用int pos; / 临时变量for (pos = 1; pos = m; pos+) / 复制结点信息nodespos = copy、nodespos; / 结点信息 for (pos = 1; pos = num;

23、pos+) / 复制叶结点字符信息与叶结点字符编码信息LeafCharspos = copy、LeafCharspos; / 叶结点字符信息LeafCharCodespos = copy、LeafCharCodespos;/ 叶结点字符编码信息 template HuffmanTree &HuffmanTree:operator=(constHuffmanTree& copy) / 操作结果 : 将哈夫曼树 copy赋值给当前哈夫曼树重载赋值运算符 if (© != this ) if (nodes != NULL) delete nodes; / 释放结点信息if (LeafChar

24、s != NULL) delete LeafChars; / 释放叶结点字符信息if (LeafCharCodes != NULL) delete LeafCharCodes; / 释放叶结点字符编码信息num = copy 、num; / 叶结点个数curPos = copy 、curPos; / 译码时从根结点到叶结点路径的当前结点int m = 2 * num - 1; / 结点总数nodes = new HuffmanTreeNodem + 1; / nodes0未用LeafChars = new CharTypenum + 1; / LeafChars0未用LeafCharCodes

25、 = new Stringnum + 1; / LeafCharCodes0未用int pos; / 临时变量for (pos = 1; pos = m; pos+) / 复制结点信息nodespos = copy、nodespos; / 结点信息 for (pos = 1; pos = num; pos+) / 复制叶结点字符信息与叶结点字符编码信息LeafCharspos = copy、LeafCharspos; / 叶结点字符信息LeafCharCodespos = copy、LeafCharCodespos;/ 叶结点字符编码信息 return * this ; #endif #ifn

26、def _HUFFMAN_COMPRESS_H_ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩#define _HUFFMAN_COMPRESS_H_ #includehuffman_tree、h/ 哈夫曼树类struct BufferType/ 字符缓存器 char ch; / 字符unsignedint bits; / 实际比特数; class HuffmanCompress / 哈夫曼压缩类 protected: H

27、uffmanTree *pHuffmanTree; FILE *infp,*outfp; / 输入 / 出文件BufferType buf; / 字符缓存void Write(unsignedint bit); / 向目标文件中写入一个比特void WriteToOutfp(); / 强行将字符缓存写入目标文件public : HuffmanCompress(); / 无参数的构造函数HuffmanCompress(); / 析构函数void Compress(); / 压缩算法void Decompress(); / 解压缩算法HuffmanCompress(const HuffmanCom

28、press ©); / 复制构造函数HuffmanCompress &operator =(const HuffmanCompress& copy);/ 赋值运算符; HuffmanCompress:HuffmanCompress() pHuffmanTree = NULL; / 空哈夫曼树 HuffmanCompress:HuffmanCompress() if (pHuffmanTree != NULL) delete pHuffmanTree; / 释放空间 void HuffmanCompress:Write(unsignedint bit) / 操作结果 : 向目标文件中写入

29、一个比特 buf 、bits+; / 缓存比特数自增buf 、ch = (buf、ch 0) / 缓存非空 , 将缓存的比特个数增加到, 自动写入目标文件for ( unsignedint i = 0; i 8 - len; i+) Write(0); void HuffmanCompress:Compress()/ 操作结果 : 用哈夫曼编码压缩文件 char infName256, outfName256; / 输入 ( 源)/ 出(目标 ) 文件名cout infName; / 输入源文件名if (infp = fopen(infName, r+b ) = NULL) throw Err

30、or(打开源文件失败! ); / 抛出异常 fgetc(infp); / 取出源文件第一个字符if (feof(infp) throw Error(空源文件 ! ); / 抛出异常cout outfName; if (outfp = fopen(outfName, w+b) = NULL) throw Error(打开目标文件失败! ); / 抛出异常cout 正在处理 , 请稍候、 endl; constunsignedlong n = 256; / 字符个数char chn; / 字符数组unsignedlong wn; / 字符出现频度 ( 权) unsignedlong i, size

31、 = 0; char cha; for (i = 0; i n; i+) / 初始化 ch 与w chi = (char )i; / 初始化 chi wi = 0; / 初始化 wi rewind(infp); / 使源文件指针指向文件开始处cha = fgetc(infp); / 取出源文件第一个字符while (!feof(infp) / 统计字符出现频度w( unsignedchar )cha+; / 字符 cha出现频度自加size+; / 文件大小自加cha=fgetc(infp); / 取出源文件下一个字符 if (pHuffmanTree != NULL) delete pHuf

32、fmanTree; / 释放空间pHuffmanTree = new HuffmanTree(ch, w, n); / 生成哈夫曼树 rewind(outfp); / 使目标文件指针指向文件开始处fwrite(&size, sizeof ( unsignedlong ), 1, outfp); / 向目标文件写入源文件大小精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩for (i = 0; i Encode(cha);/ 字

33、符编码for (i = 0; istrTmp、Length(); i+) / 向目标文件写入编码if (strTmpi = 0 ) Write(0); / 向目标文件写入else Write(1); / 向目标文件写入 cha = fgetc(infp); / 取出源文件的下一个字符 WriteToOutfp(); / 强行写入目标文件fclose(infp); fclose(outfp); / 关闭文件cout 处理结束、 endl; void HuffmanCompress:Decompress()/ 操作结果 : 解压缩用哈夫曼编码压缩的文件 char infName256, outfN

34、ame256; / 输入 ( 压缩 )/ 出( 目标 ) 文件名cout infName; if (infp = fopen(infName, r+b ) = NULL) throw Error(打开压缩文件失败! ); / 抛出异常 fgetc(infp); / 取出压缩文件第一个字符if (feof(infp) throw Error(压缩文件为空 ! ); / 抛出异常cout outfName; if (outfp = fopen(outfName, w+b) = NULL) throw Error(打开目标文件失败! ); / 抛出异常cout 正在处理 , 请稍候、 endl; c

35、onstunsignedlong n = 256; / 字符个数char chn; / 字符数组unsignedlong wn; / 权unsignedlong i, size = 0; char cha; rewind(infp); / 使源文件指针指向文件开始处精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩fread(&size, sizeof ( unsignedlong ), 1, infp); / 读取目标文件的大

36、小for (i = 0; i n; i+) chi = (char )i; / 初始化 chi fread(&wi, sizeof ( unsignedlong ), 1, infp); / 读取字符频度 if (pHuffmanTree != NULL) delete pHuffmanTree; / 释放空间pHuffmanTree = new HuffmanTree(ch, w, n); / 生成哈夫曼树unsignedlong len = 0; / 解压的字符数cha = fgetc(infp); / 取出源文件的第一个字符while (!feof(infp) / 对压缩文件字符进行解码

37、, 并将解码的字符写入目标文件String strTmp = ; / 将cha转换二进制形式的串unsignedchar c = (unsignedchar )cha; / 将cha转换成 unsigned char类型for (i = 0; i 8; i+) / 将c转换成二进制串if (c 128) Concat(strTmp, 0 ); / 最高位为else Concat(strTmp, 1 ); / 最高位为c = c 1; / 左移一位 LinkList lkText = pHuffmanTree-Decode(strTmp);/ 译码String strTemp(lkText);

38、for (i = 1; i=strTemp、Length(); i+) / 向目标文件写入字符len+; / 目标文件长度自加fputc(strTempi-1, outfp); / 将字符写入目标文件中if (len = size) break ; / 解压完毕退出内循环 if (len = size) break ; / 解压完毕退出外循环cha = fgetc(infp); / 取出源文件的下一个字符 fclose(infp); fclose(outfp); / 关闭文件cout 处理结束、 endl; HuffmanCompress:HuffmanCompress(const Huffm

39、anCompress ©) / 操作结果 : 由哈夫曼压缩类对象copy构造新哈夫曼压缩类对象复制构造函数 if (copy 、pHuffmanTree != NULL) / copy为非空哈夫曼压缩类对象pHuffmanTree = new HuffmanTree(*copy 、pHuffmanTree); / 生成哈夫曼树 else pHuffmanTree = NULL; / 生成空哈夫曼压缩类对象 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 13 页 - - - - -

40、- - - - - 哈夫曼树解压与压缩HuffmanCompress &HuffmanCompress: operator =( const HuffmanCompress& copy) / 操作结果 : 将哈夫曼压缩类对象copy赋值给当前哈夫曼压缩类对象赋值运算符 if (© != this ) if (pHuffmanTree != NULL) delete pHuffmanTree; / 释放空间if (copy 、pHuffmanTree != NULL) / copy为非空哈夫曼压缩类对象pHuffmanTree = new HuffmanTree(*copy 、pHuff

41、manTree); / 生成哈夫曼树 else pHuffmanTree = NULL; / 生成空哈夫曼压缩类对象 return * this ; #endif #includeutility、h/ 实用程序软件包#includehuffman_compress 、h/ 哈夫曼压缩算法int main( void ) try/ 用try 封装可能出现异常的代码 HuffmanCompress obj; int select = 0; while (select != 3) cout endl 1 、 压缩 ; cout endl 2 、 解压 ; cout endl 3 、 退出 ; cou

42、t endl select; / 输入选择while (cin、get() != n); / 忽略用户输入的其她字符switch (select) case 1: obj 、Compress(); / 压缩break ; case 2: obj 、Decompress(); / 解压缩 catch (Error err) / 捕捉并处理异常 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩err 、Show(); / 显示异

43、常信息 system( PAUSE); / 调用库函数 system() return 0; / 返回值 , 返回操作系统 3. 测试结果由于测试的文件字符太多,则就截下来一部分的压缩后的编码。下面的就是压缩过后的编码截图。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 13 页 - - - - - - - - - - 哈夫曼树解压与压缩下面为解压后的文件截图,解压后与压缩前的就是一样的。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 13 页 - - - - - - - - - -