哈夫曼树解压与压缩_第1页
哈夫曼树解压与压缩_第2页
哈夫曼树解压与压缩_第3页
哈夫曼树解压与压缩_第4页
哈夫曼树解压与压缩_第5页
已阅读5页,还剩9页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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.哈夫曼树的实现函数String EnCode(Char Type ch):表示

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

3、eight,parent,leftChild,rightChild分别代表了权值,双亲,左孩子,右孩子。在哈夫曼树类中有数据成员*nodes,*LeafChars,*LeafCharCodes,curPos,num,分别用来存储结点信息,叶结点字符信息,叶结点字符编码信息,译码时从根结点到叶结点路径的当前结点,叶结点个数。哈夫曼树类中含有多个函数,有构造函数,析构函数等。由函数HuffmanTree(CharType ch,WeightType w,int n)来构造由字符,权值,和字符个数构造哈夫曼树,在根据哈夫曼算法很容易实现哈夫曼类的函数以及构造函数。在在算法中,求叶结点字符的编码时,需

4、要从叶结点出发走一条从高叶结点到根结点的路径,而编码却是从根结点出发到叶结点的路径,由左分支为编码0,右分支为编码1,得到的编码,因此从叶结点出发到根结点的路径得到的编码是实际编码的逆序,并且编码长度不确定,又由于可以再线性链表中构造串,因此将编码的信息储存在一个线性立案标准,每得到一位编码都将其插入在线性链表的最前面。在求某个字符的编码是由函数EnCode(CharType ch)来求,返回字符编码。在进行译码时,用一个线性链表存储字符序列,由函数Decode(String strCode)来求,对编码串strCode进行译码,返回编码前的字符序列。函数Compress()用哈夫曼编码压缩文

5、件。函数Decompress()解压缩用哈夫曼编码压缩的文件。在主函数中有两个选项,一个是选择编码压缩,一个是解压。在函数中使用了文件输入输出流,我们可以选择要压缩的文件名输入,在选出压缩文件保存的地方和文件类型,将压缩所得到的文件存储在另一个文件中,解压也是如此。2. 源代码#ifndef _HUFFMAN_TREE_NODE_H_#define _HUFFMAN_TREE_NODE_H_/ 哈夫曼树结点类模板template struct HuffmanTreeNodeWeightType weight;/ 权数据域unsigned int parent, leftChild, right

6、Child;/ 双亲,左右孩子域HuffmanTreeNode();/ 无参数的构造函数模板HuffmanTreeNode(WeightType w, int p = 0, int lChild = 0, int rChild = 0);/ 已知权,双亲及左右孩子构造结构;/ 哈夫曼树结点类模板的实现部分template HuffmanTreeNode:HuffmanTreeNode()/ 操作结果:构造空结点parent = leftChild = rightChild = 0;template HuffmanTreeNode:HuffmanTreeNode(WeightType w, in

7、t p, int lChild, int rChild)/ 操作结果:构造一个权为w,双亲为p,左孩子为lChild,右孩子为rChild的结点weight = w;/ 权parent = p;/ 双亲leftChild = lChild;/ 左孩子rightChild = rChild;/ 右孩子#endif#ifndef _HUFFMAN_TREE_H_#define _HUFFMAN_TREE_H_#include string.h/ 串类#include huffman_tree_node.h/ 哈夫曼树结点类模板/ 哈夫曼树类模板template class HuffmanTreep

8、rotected:HuffmanTreeNode *nodes;/ 存储结点信息,nodes0未用CharType *LeafChars;/ 叶结点字符信息,LeafChars0未用String *LeafCharCodes;/ 叶结点字符编码信息,LeafCharCodes0未用int curPos;/ 译码时从根结点到叶结点路径的当前结点int num;/ 叶结点个数/辅助函数模板:void Select(int cur, int &r1, int &r2);/ nodes1 cur中选择双亲为,权值最小的两个结点r1,r2void CreatHuffmanTree(CharType ch

9、, WeightType w, int n);/ 由字符,权值和字符个数构造哈夫曼树public:/ 哈夫曼树方法声明及重载编译系统默认方法声明:HuffmanTree(CharType ch, WeightType w, int n);/ 由字符,权值和字符个数构造哈夫曼树virtual HuffmanTree();/ 析构函数模板String Encode(CharType ch);/ 编码LinkList Decode(String strCode);/ 译码HuffmanTree(const HuffmanTree ©);/ 复制构造函数模板HuffmanTree &opera

10、tor=(const HuffmanTree& copy);/ 重载赋值运算符;/ 孩子兄弟表示哈夫曼树类模板的实现部分template void HuffmanTree:Select(int cur, int &r1, int &r2)/ 操作结果:nodes1 cur中选择双亲为,权值最小的两个结点r1,r2r1 = r2 = 0;/ 0表示空结点for (int pos = 1; pos = cur; pos+)/ 查找树值最小的两个结点if (nodespos.parent != 0) continue;/ 只处理双亲不为的结点if (r1 = 0)r1 = pos; / r1为空,将

11、pos赋值给r1else if (r2 = 0)r2 = pos; / r2为空,将pos赋值给r2else if(nodespos.weight nodesr1.weight)r1 = pos; / nodespos权值比nodesr1更小,将pos赋为r1else if (nodespos.weight nodesr2.weight)r2 = pos; / nodespos权值比nodesr2更小,将pos赋为r2template void HuffmanTree:CreatHuffmanTree(CharType ch, WeightType w, int n)/ 操作结果:由字符,权值

12、和字符个数构造哈夫曼树num = n;/ 叶结点个数int m = 2 * n - 1;/ 结点个数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;/ 字符f

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

14、pos的权为r1,r2的权值之和for (pos = 1; pos = n; pos+)/ 求n个叶结点字符的编码LinkList charCode;/ 暂存叶结点字符编码信息for (unsigned int child = pos, parent = nodeschild.parent; parent != 0; child = parent, parent = nodeschild.parent)/ 从叶结点到根结点逆向求编码if (nodesparent.leftChild = child) charCode.Insert(1, 0);/ 左分支编码为0else charCode.In

15、sert(1, 1);/ 右分支编码为1LeafCharCodespos = charCode;/ charCode中存储字符编码curPos = m;/ 译码时从根结点开始,m为根template HuffmanTree:HuffmanTree(CharType ch, WeightType w, int n)/ 操作结果:由字符,权值和字符个数构造哈夫曼树CreatHuffmanTree(ch, w, n);/ 由字符,权值和字符个数构造哈夫曼树template HuffmanTree:HuffmanTree()/ 操作结果:销毁哈夫曼树if (nodes != NULL) delete

16、nodes;/ 释放结点信息if (LeafChars != NULL) delete LeafChars;/ 释放叶结点字符信息if (LeafCharCodes != NULL) delete LeafCharCodes;/ 释放叶结点字符编码信息template String HuffmanTree:Encode(CharType ch)/ 操作结果:返回字符编码for (int pos = 1; pos = num; pos+)/ 查找字符的位置if (LeafCharspos = ch) return LeafCharCodespos;/ 找到字符,得到编码throw Error(非

17、法字符,无法编码!);/ 抛出异常template LinkList HuffmanTree:Decode(String strCode)/ 操作结果:对编码串strCode进行译码,返回编码前的字符序列LinkList charList;/ 编码前的字符序列for (int pos = 0; pos strCode.Length(); pos+)/ 处理每位编码if (strCodepos = 0) curPos = nodescurPos.leftChild;/ 0表示左分支else curPos = nodescurPos.rightChild;/ 1表示左分支if (nodescurP

18、os.leftChild = 0 & nodescurPos.rightChild = 0)/ 译码时从根结点到叶结点路径的当前结点为叶结点charList.Insert(charList.Length() + 1, LeafCharscurPos);curPos = 2 * num - 1;/ curPos回归根结点return charList;/ 返回编码前的字符序列template HuffmanTree:HuffmanTree(const HuffmanTree ©)/ 操作结果:由哈夫曼树copy构造新哈夫曼树复制构造函数模板num = copy.num;/ 叶结点个数cu

19、rPos = copy.curPos;/ 译码时从根结点到叶结点路径的当前结点int m = 2 * num - 1;/ 结点总数nodes = new HuffmanTreeNodem + 1;/ nodes0未用LeafChars = new CharTypenum + 1;/ LeafChars0未用LeafCharCodes = new Stringnum + 1;/ LeafCharCodes0未用int pos;/ 临时变量for (pos = 1; pos = m; pos+)/ 复制结点信息nodespos = copy.nodespos;/ 结点信息for (pos = 1;

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

21、ars != 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 = new

22、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#ifndef _HUFFMAN_COMPRE

23、SS_H_#define _HUFFMAN_COMPRESS_H_#include huffman_tree.h/ 哈夫曼树类struct BufferType/ 字符缓存器char ch;/ 字符unsigned int bits;/ 实际比特数 ;class HuffmanCompress/ 哈夫曼压缩类protected:HuffmanTree *pHuffmanTree;FILE *infp,*outfp;/ 输入/出文件BufferType buf;/ 字符缓存void Write(unsigned int bit);/ 向目标文件中写入一个比特void WriteToOutfp()

24、;/ 强行将字符缓存写入目标文件public:HuffmanCompress();/ 无参数的构造函数HuffmanCompress();/ 析构函数void Compress();/ 压缩算法void Decompress();/ 解压缩算法HuffmanCompress(const HuffmanCompress ©);/ 复制构造函数HuffmanCompress &operator=(const HuffmanCompress& copy);/ 赋值运算符;HuffmanCompress:HuffmanCompress()pHuffmanTree = NULL;/ 空哈夫曼树H

25、uffmanCompress:HuffmanCompress()if (pHuffmanTree != NULL) delete pHuffmanTree;/ 释放空间void HuffmanCompress:Write(unsigned int bit)/ 操作结果:向目标文件中写入一个比特buf.bits+;/ 缓存比特数自增buf.ch = (buf.ch 0)/ 缓存非空, 将缓存的比特个数增加到, 自动写入目标文件for (unsigned int i = 0; i 8 - len; i+) Write(0);void HuffmanCompress:Compress()/ 操作结果

26、:用哈夫曼编码压缩文件char infName256, outfName256;/ 输入(源)/出(目标)文件名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 正在处理

27、,请稍候. endl;const unsigned long n = 256;/ 字符个数 char chn;/ 字符数组unsigned long wn;/ 字符出现频度(权)unsigned long i, size = 0;char cha;for (i = 0; i n; i+)/ 初始化ch和wchi = (char)i;/ 初始化chiwi = 0;/ 初始化wirewind(infp);/ 使源文件指针指向文件开始处cha = fgetc(infp);/ 取出源文件第一个字符while (!feof(infp)/ 统计字符出现频度w(unsigned char)cha+;/ 字符

28、cha出现频度自加size+;/ 文件大小自加cha=fgetc(infp);/ 取出源文件下一个字符if (pHuffmanTree != NULL) delete pHuffmanTree;/ 释放空间pHuffmanTree = new HuffmanTree(ch, w, n); / 生成哈夫曼树 rewind(outfp);/ 使目标文件指针指向文件开始处fwrite(&size, sizeof(unsigned long), 1, outfp);/ 向目标文件写入源文件大小for (i = 0; i Encode(cha);/ 字符编码for (i = 0; istrTmp.Len

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

30、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;const unsigned long n = 256;/ 字符个数 char chn;/ 字符数组unsigned lon

31、g wn;/ 权unsigned long i, size = 0;char cha;rewind(infp);/ 使源文件指针指向文件开始处fread(&size, sizeof(unsigned long), 1, infp);/ 读取目标文件的大小for (i = 0; i n; i+)chi = (char)i;/ 初始化chifread(&wi, sizeof(unsigned long), 1, infp);/ 读取字符频度if (pHuffmanTree != NULL) delete pHuffmanTree;/ 释放空间pHuffmanTree = new HuffmanTr

32、ee(ch, w, n); / 生成哈夫曼树unsigned long len = 0;/ 解压的字符数cha = fgetc(infp);/ 取出源文件的第一个字符while (!feof(infp)/ 对压缩文件字符进行解码,并将解码的字符写入目标文件String strTmp = ;/ 将cha转换二进制形式的串unsigned char c = (unsigned char)cha;/ 将cha转换成unsigned char类型for (i = 0; i 8; i+)/ 将c转换成二进制串if (c 128) Concat(strTmp, 0);/ 最高位为else Concat(s

33、trTmp, 1);/ 最高位为c = c 1;/ 左移一位LinkList lkText = pHuffmanTree-Decode(strTmp);/ 译码String strTemp(lkText);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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论