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

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

《哈夫曼树解压与压缩Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《哈夫曼树解压与压缩Word格式文档下载.docx（23页珍藏版）》请在冰点文库上搜索。

//哈夫曼树结点类模板

template<

classWeightType>

structHuffmanTreeNode

{

WeightTypeweight;

//权数据域

unsignedintparent,leftChild,rightChild;

//双亲,左右孩子域

HuffmanTreeNode（）;

//无参数的构造函数模板

HuffmanTreeNode（WeightTypew,intp=0,intlChild=0,intrChild=0）;

//已知权,双亲及左右孩子构造结构

};

//哈夫曼树结点类模板的实现部分

HuffmanTreeNode<

WeightType>

:

HuffmanTreeNode（）//操作结果：

构造空结点

parent=leftChild=rightChild=0;

}

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"

//串类

huffman_tree_node.h"

//哈夫曼树结点类模板

//哈夫曼树类模板

classCharType,classWeightType>

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）;

//编码

LinkList<

Decode（StringstrCode）;

//译码

HuffmanTree（constHuffmanTree<

CharType,WeightType>

&

copy）;

//复制构造函数模板

HuffmanTree<

operator=（constHuffmanTree<

CharType,

WeightType>

&

copy）;

//重载赋值运算符

//孩子兄弟表示哈夫曼树类模板的实现部分

voidHuffmanTree<

Select（intcur,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<

nodes[r1].weight）

//nodes[pos]权值比nodes[r1]更小,将pos赋为r1

nodes[r2].weight）

//nodes[pos]权值比nodes[r2]更小,将pos赋为r2

}

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;

=n;

{//存储叶结点信息

nodes[pos].weight=w[pos-1];

//权值

LeafChars[pos]=ch[pos-1];

//字符

for（pos=n+1;

=m;

{//建立哈夫曼树

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的权值之和

{//求n个叶结点字符的编码

LinkList<

char>

charCode;

//暂存叶结点字符编码信息

for（unsignedintchild=pos,parent=nodes[child].parent;

parent!

=0;

child=parent,parent=nodes[child].parent）

{//从叶结点到根结点逆向求编码

if（nodes[parent].leftChild==child）charCode.Insert（1,'

0'

）;

//左分支编码为'

elsecharCode.Insert（1,'

1'

//右分支编码为'

LeafCharCodes[pos]=charCode;

//charCode中存储字符编码

curPos=m;

//译码时从根结点开始,m为根

HuffmanTree<

HuffmanTree（CharTypech[],WeightTypew[],intn）

CreatHuffmanTree（ch,w,n）;

//由字符,权值和字符个数构造哈夫曼树

~HuffmanTree（）

销毁哈夫曼树

{

if（nodes!

=NULL）delete[]nodes;

//释放结点信息

if（LeafChars!

=NULL）delete[]LeafChars;

//释放叶结点字符信息

if（LeafCharCodes!

=NULL）delete[]LeafCharCodes;

//释放叶结点字符编码信息

StringHuffmanTree<

Encode（CharTypech）

返回字符编码

=num;

{//查找字符的位置

if（LeafChars[pos]==ch）returnLeafCharCodes[pos];

//找到字符,得到编码

throwError（"

非法字符,无法编码!

"

//抛出异常

LinkList<

Decode（StringstrCode）

对编码串strCode进行译码,返回编码前的字符序列

charList;

//编码前的字符序列

for（intpos=0;

strCode.Length（）;

{//处理每位编码

if（strCode[pos]=='

）curPos=nodes[curPos].leftChild;

//'

表示左分支

elsecurPos=nodes[curPos].rightChild;

//'

if（nodes[curPos].leftChild==0&

nodes[curPos].rightChild==0）

{//译码时从根结点到叶结点路径的当前结点为叶结点

charList.Insert（charList.Length（）+1,LeafChars[curPos]）;

curPos=2*num-1;

//curPos回归根结点

returncharList;

//返回编码前的字符序列

HuffmanTree（constHuffmanTree<

copy）

由哈夫曼树copy构造新哈夫曼树——复制构造函数模板

num=copy.num;

curPos=copy.curPos;

//译码时从根结点到叶结点路径的当前结点

intm=2*num-1;

//结点总数

LeafChars=newCharType[num+1];

LeafCharCodes=newString[num+1];

//LeafCharCodes[0]未用

{//复制结点信息

nodes[pos]=copy.nodes[pos];

//结点信息

{//复制叶结点字符信息与叶结点字符编码信息

LeafChars[pos]=copy.LeafChars[pos];

//叶结点字符信息

LeafCharCodes[pos]=copy.LeafCharCodes[pos];

//叶结点字符编码信息

copy）

将哈夫曼树copy赋值给当前哈夫曼树——重载赋值运算符

if（&

copy!

=this）

{

if（nodes!

if（LeafChars!

if（LeafCharCodes!

num=copy.num;

curPos=copy.curPos;

//译码时从根结点到叶结点路径的当前结点

intm=2*num-1;

//结点总数

nodes=newHuffmanTreeNode<

LeafChars=newCharType[num+1];

LeafCharCodes=newString[num+1];

intpos;

for（pos=1;

{//复制结点信息

nodes[pos]=copy.nodes[pos];

{//复制叶结点字符信息与叶结点字符编码信息

LeafChars[pos]=copy.LeafChars[pos];

LeafCharCodes[pos]=copy.LeafCharCodes[pos];

}

return*this;

#ifndef__HUFFMAN_COMPRESS_H__

#define__HUFFMAN_COMPRESS_H__

huffman_tree.h"

//哈夫曼树类

structBufferType//字符缓存器

charch;

//字符

unsignedintbits;

//实际比特数

classHuffmanCompress//哈夫曼压缩类

char,unsignedlong>

*pHuffmanTree;

FILE*infp,*outfp;

//输入/出文件

BufferTypebuf;

//字符缓存

voidWrite（unsignedintbit）;

//向目标文件中写入一个比特

voidWriteToOutfp（）;

//强行将字符缓存写入目标文件

HuffmanCompress（）;

//无参数的构造函数

~HuffmanCompress（）;

//析构函数

voidCompress（）;

//压缩算法

voidDecompress（）;

//解压缩算法

HuffmanCompress（constHuffmanCompress&

//复制构造函数

HuffmanCompress&

operator=（constHuffmanCompress&

//赋值运算符

HuffmanCompress:

HuffmanCompress（）

pHuffmanTree=NULL;

//空哈夫曼树

~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