哈夫曼树解压与压缩Word文档格式.docx

1、/ 哈夫曼树结点类模板template struct HuffmanTreeNode WeightType weight; / 权数据域 unsigned int parent, leftChild, rightChild; / 双亲,左右孩子域 HuffmanTreeNode（）; / 无参数的构造函数模板 HuffmanTreeNode（WeightType w, int p = 0, int lChild = 0, int rChild = 0）; / 已知权,双亲及左右孩子构造结构;/ 哈夫曼树结点类模板的实现部分HuffmanTreeNode:HuffmanTreeNode（）/ 操

2、作结果：构造空结点 parent = leftChild = rightChild = 0;HuffmanTreeNode（WeightType w, int 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

3、string.h / 串类huffman_tree_node.h / 哈夫曼树结点类模板/ 哈夫曼树类模板class CharType, class WeightTypeclass HuffmanTreeprotected: HuffmanTreeNode *nodes; / 存储结点信息,nodes0未用 CharType *LeafChars; / 叶结点字符信息,LeafChars0未用 String *LeafCharCodes; / 叶结点字符编码信息,LeafCharCodes0未用 int curPos; / 译码时从根结点到叶结点路径的当前结点 int num; / 叶结点个数

4、/ 辅助函数模板: void Select（int 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 Enc

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

6、= 1; pos = cur; pos+） / 查找树值最小的两个结点 if （nodespos.parent != 0） continue; / 只处理双亲不为的结点 if （r1 = 0） r1 = pos; / r1为空,将pos赋值给r1 else if （r2 = 0） r2 = pos; / r2为空,将pos赋值给r2 else if （nodespos.weight nodesr1.weight） / nodespos权值比nodesr1更小,将pos赋为r1 nodesr2.weight） / nodespos权值比nodesr2更小,将pos赋为r2 CreatHuffma

7、nTree（CharType ch, WeightType w, int n）由字符,权值和字符个数构造哈夫曼树 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;= n; / 存储叶结点信息 nodespos.weig

8、ht = wpos - 1; / 权值 LeafCharspos = chpos - 1; / 字符 for （pos = n + 1;= m; / 建立哈夫曼树 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的右孩

9、子 nodespos.weight = nodesr1.weight + nodesr2.weight;/pos的权为r1,r2的权值之和 / 求n个叶结点字符的编码 LinkList charCode; / 暂存叶结点字符编码信息 for （unsigned int child = pos, parent = nodeschild.parent; parent != 0; child = parent, parent = nodeschild.parent） / 从叶结点到根结点逆向求编码 if （nodesparent.leftChild = child） charCode.Insert（

10、1, 0）;/ 左分支编码为 else charCode.Insert（1, 1 / 右分支编码为 LeafCharCodespos = charCode; / charCode中存储字符编码 curPos = m; / 译码时从根结点开始,m为根HuffmanTreeHuffmanTree（CharType ch, WeightType w, int n） CreatHuffmanTree（ch, w, n）; / 由字符,权值和字符个数构造哈夫曼树HuffmanTree（）销毁哈夫曼树 if （nodes != NULL） delete nodes; / 释放结点信息 if （LeafCh

11、ars != NULL） delete LeafChars; / 释放叶结点字符信息 if （LeafCharCodes != NULL） delete LeafCharCodes; / 释放叶结点字符编码信息String HuffmanTreeEncode（CharType ch）返回字符编码= num; / 查找字符的位置 if （LeafCharspos = ch） return LeafCharCodespos;/ 找到字符,得到编码 throw Error（非法字符,无法编码! / 抛出异常LinkListDecode（String strCode）对编码串strCode进行译码,返

12、回编码前的字符序列 charList; / 编码前的字符序列 for （int pos = 0; strCode.Length（）; / 处理每位编码 if （strCodepos = ） curPos = nodescurPos.leftChild; / 表示左分支 else curPos = nodescurPos.rightChild; / if （nodescurPos.leftChild = 0 & nodescurPos.rightChild = 0） / 译码时从根结点到叶结点路径的当前结点为叶结点 charList.Insert（charList.Length（） + 1, L

13、eafCharscurPos）; curPos = 2 * num - 1; / curPos回归根结点 return charList; / 返回编码前的字符序列HuffmanTree（const HuffmanTreecopy）由哈夫曼树copy构造新哈夫曼树复制构造函数模板 num = copy.num; curPos = copy.curPos; / 译码时从根结点到叶结点路径的当前结点 int m = 2 * num - 1; / 结点总数 LeafChars = new CharTypenum + 1; LeafCharCodes = new Stringnum + 1; / Le

14、afCharCodes0未用 / 复制结点信息 nodespos = copy.nodespos; / 结点信息 / 复制叶结点字符信息与叶结点字符编码信息 LeafCharspos = copy.LeafCharspos; / 叶结点字符信息 LeafCharCodespos = copy.LeafCharCodespos;/ 叶结点字符编码信息 copy） 将哈夫曼树copy赋值给当前哈夫曼树重载赋值运算符 if （© != this） if （nodes ! if （LeafChars ! if （LeafCharCodes ! num = copy.num; curPos =

15、copy.curPos; / 译码时从根结点到叶结点路径的当前结点 int m = 2 * num - 1; / 结点总数 nodes = new HuffmanTreeNode *pHuffmanTree; FILE *infp,*outfp; / 输入/出文件 BufferType buf; / 字符缓存 void Write（unsigned int bit）; / 向目标文件中写入一个比特 void WriteToOutfp（）; / 强行将字符缓存写入目标文件 HuffmanCompress（）; / 无参数的构造函数 HuffmanCompress（）; / 析构函数 void C

16、ompress（）; / 压缩算法 void Decompress（）; / 解压缩算法 HuffmanCompress（const HuffmanCompress & / 复制构造函数 HuffmanCompress &operator=（const HuffmanCompress&/ 赋值运算符HuffmanCompress:HuffmanCompress（） pHuffmanTree = NULL; / 空哈夫曼树HuffmanCompress（） if （pHuffmanTree != NULL） delete pHuffmanTree; / 释放空间void HuffmanCompress:Write（unsigned int bit） / 操作结果：向目标文件中写入一个比特 buf.bits+; / 缓存比特数自增 buf.ch = （buf.ch 1） | bit; / 将bit加入到缓存字符中 if （buf.bits = 8） / 缓存区已满,写入目标文件 fputc（buf.ch, outfp）; / 写入目标文件 buf.bit