《哈夫曼树解压与压缩.pptx》由会员分享，可在线阅读，更多相关《哈夫曼树解压与压缩.pptx（13页珍藏版）》请在金锄头文库上搜索。
1、哈夫曼树的压缩与解压 1. 算法简要描述 哈夫曼算法 哈弗曼算法是根据给定的n 个权值w1，w2，w3.wn，构造由 n 棵二 叉树构成的深林 F=T1,T2,。Tn，其中每个二叉树 Ti 分别都是只含 有一个权值 wi 的根结点，其左右子树为空（i=1，,2）。 在深林 F 中选取其根结点的权值最小的两棵二叉树，分别作其左右子树 构造一颗新的二叉树，并置这棵新的二叉树根结点的权值为其左右子树 的根结点之和。 从F 中删去这两棵二叉树，同时刚新生成的二叉树加入到深林 F 中。 重复 2,3,步骤，直至深林F 中只含有一颗二叉树为止。 哈夫曼树的实现 函数String EnCode(Char T
2、ype 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(CharTypech,WeightType w,int n)来构造由字符，权值，和字符个数构造哈夫曼树，在
4、根据哈夫曼算法很容易实 现哈夫曼类的函数以及构造函数。在在算法中，求叶结点字符的编码时，需要从 叶结点出发走一条从高叶结点到根结点的路径，而编码却是从根结点出发到叶结 点的路径，由左分支为编码 0，右分支为编码 1，得到的编码，因此从叶结点出 发到根结点的路径得到的编码是实际编码的逆序，并且编码长度不确定，又由于 可以再线性链表中构造串，因此将编码的信息储存在一个线性立案标准，每得到 一位编码都将其插入在线性链表的最前面。 在求某个字符的编码是由函数EnCode(CharType ch)来求，返回字符编码。在进行 译码时，用一个线性链表存储字符序列，由函数Decode(String strCo
5、de)来求，对 编码串strCode进行译码，返回编码前的字符序列。函数Compress()用哈夫曼编 码压缩文件。函数Decompress()解压缩用哈夫曼编码压缩的文件。 在主函数中有两个选项，一个是选择编码压缩，一个是解压。在函数中使用 了文件输入输出流，我们可以选择要压缩的文件名输入，在选出压缩文件保存的,1,地方和文件类型，将压缩所得到的文件存储在另一个文件中，解压也是如此。 2. 源代码 #ifndef HUFFMAN_TREE_NODE_H #define HUFFMAN_TREE_NODE_H / 哈夫曼树结点类模板 template struct HuffmanTreeNod
6、e ,2,WeightType weight; unsigned int parent, leftChild, rightChild; HuffmanTreeNode();,/ 权数据域 / 双亲,左右孩子域 / 无参数的构造函数模板,HuffmanTreeNode(WeightType w, int p = 0, int lChild = 0, int rChild = 0); / 已知权,双亲及左右孩子构造结构,;,/ 哈夫曼树结点类模板的实现部分 template HuffmanTreeNode:HuffmanTreeNode()/ 操作结果：构造空结点 parent = leftChi
7、ld = rightChild = 0; template HuffmanTreeNode:HuffmanTreeNode(WeightType w, int p, int lChild, int rChild) / 操作结果：构造一个权为w,双亲为p,左孩子为lChild,右孩子为rChild的结点 ,#endif #ifndef HUFFMAN_TREE_H #define HUFFMAN_TREE_H #include string.h,/ 串类 / 哈夫曼树结点类模板,#include huffman_tree_node.h / 哈夫曼树类模板,template class Huffm
8、anTree protected:,String *LeafCharCodes; int curPos;,/ 叶结点字符编码信息,LeafCharCodes0未用,/ 译码时从根结点到叶结点路径的当前结点,3,int num;,/ 叶结点个数,/ 辅助函数模板: void Select(int cur, int ,/ nodes1 cur中选择双亲为,权值最小的,两个结点r1,r2,void CreatHuffmanTree(CharType ch, WeightType w, int n);,/ 由字符,权值和字符个数构造哈夫曼树 public: / 哈夫曼树方法声明及重载编译系统默认方法声
9、明:,HuffmanTree(CharType ch, WeightType w, int n); / 由字符,权值和字符个数构造哈夫曼树,LinkList Decode(String strCode);/ 译码 HuffmanTree(const HuffmanTree / 重载赋值运算符,;,/ 孩子兄弟表示哈夫曼树类模板的实现部分 template void HuffmanTree:Select(int cur, int / 0表示空结点,for (int pos = 1; pos = cur; pos+),/ 查找树值最小的两个结点 if (nodespos.parent != 0)
10、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 ,4,void HuffmanTre
11、e:CreatHuffmanTree(CharType ch, WeightType w, int n) / 操作结果：由字符,权值和字符个数构造哈夫曼树 ,num = n; int m = 2 * n - 1;,/ 叶结点个数 / 结点个数,nodes = new HuffmanTreeNodem + 1;/ nodes0未用,/ LeafChars0未用,LeafChars = new CharTypen + 1; LeafCharCodes = new Stringn + 1; int pos;,/ LeafCharCodes0未用 / 临时变量,/ 权值 / 字符,for (pos =
12、 n + 1; pos = m; pos+),/ nodes1 pos - 1中选择双亲为,权值最小的两个结点r1,r2,for (pos = 1; pos = n; pos+) / 存储叶结点信息 nodespos.weight = wpos - 1; LeafCharspos = chpos - 1; ,/ 建立哈夫曼树 int r1, r2; Select(pos - 1, r1, r2); / 合并以r1,r2为根的树,nodesr1.parent = nodesr2.parent = pos;,/ r1,r2双亲为pos,nodespos.weight = nodesr1.weigh
13、t + nodesr2.weight;/pos的权为r1,r2的权值之和 ,for (pos = 1; pos = n; pos+),for (unsigned int child = pos, parent = nodeschild.parent; parent != 0;,else charCode.Insert(1, 1);/ 右分支编码为1,child = parent, parent = nodeschild.parent) / 从叶结点到根结点逆向求编码 if (nodesparent.leftChild = child) charCode.Insert(1, 0);/ 左分支编码
14、为0 ,LeafCharCodespos = charCode;,/ charCode中存储字符编码,/ 求n个叶结点字符的编码 LinkList charCode;/ 暂存叶结点字符编码信息 ,curPos = m;/ 译码时从根结点开始,m为根,template HuffmanTree:HuffmanTree(CharType ch, WeightType w, int n) / 操作结果：由字符,权值和字符个数构造哈夫曼树 CreatHuffmanTree(ch, w, n);/ 由字符,权值和字符个数构造哈夫曼树 template ,5,HuffmanTree:HuffmanTree(
15、) / 操作结果：销毁哈夫曼树,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;/ 找到字符,得到编码 ,t
16、hrow Error(非法字符,无法编码!);/ 抛出异常,template LinkList HuffmanTree:Decode(String strCode) / 操作结果：对编码串strCode进行译码,返回编码前的字符序列 ,for (int pos = 0; pos strCode.Length(); pos+),if (nodescurPos.leftChild = 0 / curPos回归根结点,/ 译码时从根结点到叶结点路径的当前结点为叶结点 charList.Insert(charList.Length() + 1, LeafCharscurPos); ,/ 处理每位编码 if (strCodepos = 0) curPos = nodescurPos.left
