哈夫曼树解压与压缩.docx
《哈夫曼树解压与压缩.docx》由会员分享，可在线阅读，更多相关《哈夫曼树解压与压缩.docx（23页珍藏版）》请在冰点文库上搜索。
哈夫曼树解压与压缩
哈夫曼树的压缩与解压
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.哈夫曼树的实现
函数StringEnCode（CharTypech）：
表示哈夫曼树已存在，返回字符ch的编码。
函数LinkListUnCode（StringstrCode）：
表示对哈夫曼树进行译码，返回编码前的字符序列。
根据算法可以看出，在具有n个结点权值的哈夫曼树的构造过程中，每次都是从F中删去两棵树，增加一棵树，即每次结束后减少一棵树，经过n-1次处理后，F中就只剩下一棵树了。
另外，每次合并都要产生一个新的结点，合并n-1次后共产生了n-1个新结点，并且这n-1个新节点都是具有左右子树的分支结点。
则最终得到的哈夫曼树中共有2n-1个结点，并且其中没有度为1的分支结点，最后一次产生的新结点就是哈夫曼树的根结点。
源代码中创建了一个哈夫曼树结点类，其中有数据成员weight，parent，leftChild，rightChild分别代表了权值，双亲，左孩子，右孩子。
在哈夫曼树类中有数据成员*nodes，*LeafChars，*LeafCharCodes，curPos，num，分别用来存储结点信息，叶结点字符信息，叶结点字符编码信息，译码时从根结点到叶结点路径的当前结点，叶结点个数。
哈夫曼树类中含有多个函数，有构造函数，析构函数等。
由函数HuffmanTree（CharTypech[],WeightTypew[],intn）来构造由字符，权值，和字符个数构造哈夫曼树，在根据哈夫曼算法很容易实现哈夫曼类的函数以及构造函数。
在在算法中，求叶结点字符的编码时，需要从叶结点出发走一条从高叶结点到根结点的路径，而编码却是从根结点出发到叶结点的路径，由左分支为编码0，右分支为编码1，得到的编码，因此从叶结点出发到根结点的路径得到的编码是实际编码的逆序，并且编码长度不确定，又由于可以再线性链表中构造串，因此将编码的信息储存在一个线性立案标准，每得到一位编码都将其插入在线性链表的最前面。
在求某个字符的编码是由函数EnCode（CharTypech）来求，返回字符编码。
在进行译码时，用一个线性链表存储字符序列，由函数Decode（StringstrCode）来求，对编码串strCode进行译码，返回编码前的字符序列。
函数Compress（）用哈夫曼编码压缩文件。
函数Decompress（）解压缩用哈夫曼编码压缩的文件。
在主函数中有两个选项，一个是选择编码压缩，一个是解压。
在函数中使用了文件输入输出流，我们可以选择要压缩的文件名输入，在选出压缩文件保存的地方和文件类型，将压缩所得到的文件存储在另一个文件中，解压也是如此。
2.源代码
#ifndef__HUFFMAN_TREE_NODE_H__
#define__HUFFMAN_TREE_NODE_H__
//哈夫曼树结点类模板
template
structHuffmanTreeNode
{
WeightTypeweight;//权数据域
unsignedintparent,leftChild,rightChild;//双亲,左右孩子域
HuffmanTreeNode（）;//无参数的构造函数模板
HuffmanTreeNode（WeightTypew,intp=0,intlChild=0,intrChild=0）;
//已知权,双亲及左右孩子构造结构
};
//哈夫曼树结点类模板的实现部分
template
HuffmanTreeNode:
:
HuffmanTreeNode（）//操作结果：
构造空结点
{
parent=leftChild=rightChild=0;
}
template
HuffmanTreeNode:
:
HuffmanTreeNode（WeightTypew,intp,intlChild,intrChild）//操作结果：
构造一个权为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
classHuffmanTree
{
protected:
HuffmanTreeNode*nodes;//存储结点信息,nodes[0]未用
CharType*LeafChars;//叶结点字符信息,LeafChars[0]未用
String*LeafCharCodes;//叶结点字符编码信息,LeafCharCodes[0]未用
intcurPos;//译码时从根结点到叶结点路径的当前结点
intnum;//叶结点个数
//辅助函数模板:
voidSelect（intcur,int&r1,int&r2）;//nodes[1~cur]中选择双亲为,权值最小的两个结点r1,r2
voidCreatHuffmanTree（CharTypech[],WeightTypew[],intn）;
//由字符,权值和字符个数构造哈夫曼树
public:
//哈夫曼树方法声明及重载编译系统默认方法声明:
HuffmanTree（CharTypech[],WeightTypew[],intn）;//由字符,权值和字符个数构造哈夫曼树
virtual~HuffmanTree（）;//析构函数模板
StringEncode（CharTypech）;//编码
LinkListDecode（StringstrCode）;//译码
HuffmanTree（constHuffmanTree©）;//复制构造函数模板
HuffmanTree&operator=（constHuffmanTreeWeightType>©）;//重载赋值运算符
};
//孩子兄弟表示哈夫曼树类模板的实现部分
template
voidHuffmanTree:
:
Select（intcur,int&r1,int&r2）
//操作结果：
nodes[1~cur]中选择双亲为,权值最小的两个结点r1,r2
{
r1=r2=0;//0表示空结点
for（intpos=1;pos<=cur;pos++）
{//查找树值最小的两个结点
if（nodes[pos].parent!
=0）continue;//只处理双亲不为的结点
if（r1==0）
{
r1=pos;//r1为空,将pos赋值给r1
}
elseif（r2==0）
{
r2=pos;//r2为空,将pos赋值给r2
}
elseif（nodes[pos].weight{
r1=pos;//nodes[pos]权值比nodes[r1]更小,将pos赋为r1
}
elseif（nodes[pos].weight{
r2=pos;//nodes[pos]权值比nodes[r2]更小,将pos赋为r2
}
}
}
template
voidHuffmanTree:
:
CreatHuffmanTree（CharTypech[],WeightTypew[],intn）
//操作结果：
由字符,权值和字符个数构造哈夫曼树
{
num=n;//叶结点个数
intm=2*n-1;//结点个数
nodes=newHuffmanTreeNode[m+1];//nodes[0]未用
LeafChars=newCharType[n+1];//LeafChars[0]未用
LeafCharCodes=newString[n+1];//LeafCharCodes[0]未用
intpos;//临时变量
for（pos=1;pos<=n;pos++）
{//存储叶结点信息
nodes[pos].weight=w[pos-1];//权值
LeafChars[pos]=ch[pos-1];//字符
}
for（pos=n+1;pos<=m;pos++）
{//建立哈夫曼树
intr1,r2;
Select（pos-1,r1,r2）;//nodes[1~pos-1]中选择双亲为,权值最小的两个结点r1,r2
//合并以r1,r2为根的树
nodes[r1].parent=nodes[r2].parent=pos;//r1,r2双亲为pos
nodes[pos].leftChild=r1;//r1为pos的左孩子
nodes[pos].rightChild=r2;//r2为pos的右孩子
nodes[pos].weight=nodes[r1].weight+nodes[r2].weight;//pos的权为r1,r2的权值之和
}
for（pos=1;pos<=n;pos++）
{//求n个叶结点字符的编码
LinkListcharCode;//暂存叶结点字符编码信息
for（unsignedintchild=pos,parent=nodes[child].parent;parent!
=0;
child=parent,parent=nodes[child].parent）
{//从叶结点到根结点逆向求编码
if（nodes[parent].leftChild==child）charCode.Insert（1,'0'）;//左分支编码为'0'
elsecharCode.Insert（1,'1'）;//右分支编码为'1'
}
LeafCharCodes[pos]=charCode;//charCode中存储字符编码
}
curPos=m;//译码时从根结点开始,m为根
}
template
HuffmanTree:
:
HuffmanTree（CharTypech[],WeightTypew[],intn）
//操作结果：
由字符,权值和字符个数构造哈夫曼树
{
CreatHuffmanTree（ch,w,n）;//由字符,权值和字符个数构造哈夫曼树
}
template
HuffmanTree:
:
~HuffmanTree（）
//操作结果：
销毁哈夫曼树
{
if（nodes!
=NULL）delete[]nodes;//释放结点信息
if（LeafChars!
=NULL）delete[]LeafChars;//释放叶结点字符信息
if（LeafCharCodes!
=NULL）delete[]LeafCharCodes;//释放叶结点字符编码信息
}
template
StringHuffmanTree:
:
Encode（CharTypech）
//操作结果：
返回字符编码
{
for（intpos=1;pos<=num;pos++）
{//查找字符的位置
if（LeafChars[pos]==ch）returnLeafCharCodes[pos];//找到字符,得到编码
}
throwError（"非法字符,无法编码!
"）;//抛出异常
}
template
LinkListHuffmanTree:
:
Decode（StringstrCode）
//操作结果：
对编码串strCode进行译码,返回编码前的字符序列
{
LinkListcharList;//编码前的字符序列
for（intpos=0;pos{//处理每位编码
if（strCode[pos]=='0'）curPos=nodes[curPos].leftChild;//'0'表示左分支
elsecurPos=nodes[curPos].rightChild;//'1'表示左分支
if（nodes[curPos].leftChild==0&&nodes[curPos].rightChild==0）
{//译码时从根结点到叶结点路径的当前结点为叶结点
charList.Insert（charList.Length（）+1,LeafChars[curPos]）;
curPos=2*num-1;//curPos回归根结点
}
}
returncharList;//返回编码前的字符序列
}
template
HuffmanTree:
:
HuffmanTree（constHuffmanTree©）
//操作结果：
由哈夫曼树copy构造新哈夫曼树——复制构造函数模板
{
num=copy.num;//叶结点个数
curPos=copy.curPos;//译码时从根结点到叶结点路径的当前结点
intm=2*num-1;//结点总数
nodes=newHuffmanTreeNode[m+1];//nodes[0]未用
LeafChars=newCharType[num+1];//LeafChars[0]未用
LeafCharCodes=newString[num+1];//LeafCharCodes[0]未用
intpos;//临时变量
for（pos=1;pos<=m;pos++）
{//复制结点信息
nodes[pos]=copy.nodes[pos];//结点信息
}
for（pos=1;pos<=num;pos++）
{//复制叶结点字符信息与叶结点字符编码信息
LeafChars[pos]=copy.LeafChars[pos];//叶结点字符信息
LeafCharCodes[pos]=copy.LeafCharCodes[pos];//叶结点字符编码信息
}
}
template
HuffmanTree&HuffmanTree:
:
operator=（constHuffmanTree©）
//操作结果：
将哈夫曼树copy赋值给当前哈夫曼树——重载赋值运算符
{
if（©!
=this）
{
if（nodes!
=NULL）delete[]nodes;//释放结点信息
if（LeafChars!
=NULL）delete[]LeafChars;//释放叶结点字符信息
if（LeafCharCodes!
=NULL）delete[]LeafCharCodes;//释放叶结点字符编码信息
num=copy.num;//叶结点个数
curPos=copy.curPos;//译码时从根结点到叶结点路径的当前结点
intm=2*num-1;//结点总数
nodes=newHuffmanTreeNode[m+1];//nodes[0]未用
LeafChars=newCharType[num+1];//LeafChars[0]未用
LeafCharCodes=newString[num+1];//LeafCharCodes[0]未用
intpos;//临时变量
for（pos=1;pos<=m;pos++）
{//复制结点信息
nodes[pos]=copy.nodes[pos];//结点信息
}
for（pos=1;pos<=num;pos++）
{//复制叶结点字符信息与叶结点字符编码信息
LeafChars[pos]=copy.LeafChars[pos];//叶结点字符信息
LeafCharCodes[pos]=copy.LeafCharCodes[pos];//叶结点字符编码信息
}
}
return*this;
}
#endif
#ifndef__HUFFMAN_COMPRESS_H__
#define__HUFFMAN_COMPRESS_H__
#include"huffman_tree.h"//哈夫曼树类
structBufferType//字符缓存器
{
charch;//字符
unsignedintbits;//实际比特数
};
classHuffmanCompress//哈夫曼压缩类
{
protected:
HuffmanTree*pHuffmanTree;
FILE*infp,*outfp;//输入/出文件
BufferTypebuf;//字符缓存
voidWrite（unsignedintbit）;//向目标文件中写入一个比特
voidWriteToOutfp（）;//强行将字符缓存写入目标文件
public:
HuffmanCompress（）;//无参数的构造函数
~HuffmanCompress（）;//析构函数
voidCompress（）;//压缩算法
voidDecompress（）;//解压缩算法
HuffmanCompress（constHuffmanCompress©）;//复制构造函数
HuffmanCompress&operator=（constHuffmanCompress©）;//赋值运算符
};
HuffmanCompress:
:
HuffmanCompress（）
{
pHuffmanTree=NULL;//空哈夫曼树
}
HuffmanCompress:
:
~HuffmanCompress（）
{
if（pHuffmanTree!
=NULL）
delete[]pHuffmanTree;//释放空间
}
voidHuffmanCompress:
:
Write（unsignedintbit）//操作结果：
向目标文件中写入一个比特
{
buf.bits++;//缓存比特数自增
buf.ch=（buf.ch<<1）|bit;//将bit加入到缓存字符中
if（buf.bits==8）
{//缓存区已满,写入目标文件
fputc（buf.ch,outfp）;//写入目标文件
buf.bit
升级会员 