哈夫曼树解压与压缩.docx

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 Ty

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

3、结点类,其中有数据成员weight,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进行译码,返回编码前的字符序列。函数Comp

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

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

7、anTreeNode(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 string、h / 串类#include huffman_tree_node、h / 哈夫曼树结点类

8、模板/ 哈夫曼树类模板template class HuffmanTreeprotected: HuffmanTreeNode *nodes; / 存储结点信息,nodes0未用 CharType *LeafChars; / 叶结点字符信息,LeafChars0未用 String *LeafCharCodes; / 叶结点字符编码信息,LeafCharCodes0未用 int curPos; / 译码时从根结点到叶结点路径的当前结点 int num; / 叶结点个数/ 辅助函数模板: void Select(int cur, int &r1, int &r2); / nodes1 cur中选择

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

10、manTree(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 (int pos = 1; pos = cur; pos+) / 查找树值最小的两个结点 if (nod

11、espos、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) r1 = pos; / nodespos权值比nodesr1更小,将pos赋为r1 else if (nodespos、weight nodesr2、weight) r2 = pos; / nodespos权值比nodesr2更小,将pos赋为r2 template

12、void HuffmanTree:CreatHuffmanTree(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 (p

13、os = 1; pos = n; pos+) / 存储叶结点信息 nodespos、weight = wpos - 1; / 权值 LeafCharspos = chpos - 1; / 字符 for (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双亲为pos nodespos、leftChild

14、 = r1; / r1为pos的左孩子 nodespos、rightChild = r2; / r2为pos的右孩子 nodespos、weight = nodesr1、weight + nodesr2、weight;/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 =

15、nodeschild、parent) / 从叶结点到根结点逆向求编码 if (nodesparent、leftChild = child) charCode、Insert(1, 0);/ 左分支编码为0 else charCode、Insert(1, 1); / 右分支编码为1 LeafCharCodespos = charCode; / charCode中存储字符编码 curPos = m; / 译码时从根结点开始,m为根template HuffmanTree:HuffmanTree(CharType ch, WeightType w, int n)/ 操作结果:由字符,权值与字符个数构造

16、哈夫曼树 CreatHuffmanTree(ch, w, n); / 由字符,权值与字符个数构造哈夫曼树template HuffmanTree:HuffmanTree()/ 操作结果:销毁哈夫曼树 if (nodes != NULL) delete nodes; / 释放结点信息 if (LeafChars != NULL) delete LeafChars; / 释放叶结点字符信息 if (LeafCharCodes != NULL) delete LeafCharCodes; / 释放叶结点字符编码信息template String HuffmanTree:Encode(CharType

17、 ch)/ 操作结果:返回字符编码 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; pos strCode、L

18、ength(); 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 * num - 1; / cu

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

20、 / LeafChars0未用 LeafCharCodes = 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;/ 叶结点

21、字符编码信息 template HuffmanTree &HuffmanTree:operator=(const HuffmanTree& copy) / 操作结果:将哈夫曼树copy赋值给当前哈夫曼树重载赋值运算符 if (© != this) if (nodes != NULL) delete nodes; / 释放结点信息 if (LeafChars != NULL) delete LeafChars; / 释放叶结点字符信息 if (LeafCharCodes != NULL) delete LeafCharCodes; / 释放叶结点字符编码信息 num = copy、num

22、; / 叶结点个数 curPos = 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、no

23、despos; / 结点信息 for (pos = 1; pos = num; pos+) / 复制叶结点字符信息与叶结点字符编码信息 LeafCharspos = copy、LeafCharspos; / 叶结点字符信息 LeafCharCodespos = copy、LeafCharCodespos;/ 叶结点字符编码信息 return *this;#endif#ifndef _HUFFMAN_COMPRESS_H_#define _HUFFMAN_COMPRESS_H_#include huffman_tree、h / 哈夫曼树类struct BufferType/ 字符缓存器 char

24、 ch; / 字符 unsigned int bits; / 实际比特数 ;class HuffmanCompress/ 哈夫曼压缩类protected: HuffmanTree *pHuffmanTree; FILE *infp,*outfp; / 输入/出文件 BufferType buf; / 字符缓存 void Write(unsigned int bit); / 向目标文件中写入一个比特 void WriteToOutfp(); / 强行将字符缓存写入目标文件public: HuffmanCompress(); / 无参数的构造函数 HuffmanCompress(); / 析构函数

25、 void Compress(); / 压缩算法 void Decompress(); / 解压缩算法 HuffmanCompress(const HuffmanCompress ©); / 复制构造函数 HuffmanCompress &operator=(const HuffmanCompress& copy);/ 赋值运算符;HuffmanCompress:HuffmanCompress() pHuffmanTree = NULL; / 空哈夫曼树HuffmanCompress: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); / 写入目标文件