C++数据结构之文件压缩（哈夫曼树）实例详解

2023-09-27 11:42:16 128

C++数据结构之文件压缩（哈夫曼树）实例详解

概要：

项目简介：利用哈夫曼编码的方式对文件进行压缩，并且对压缩文件可以解压

开发环境：windowsvs2013

项目概述：

1.压缩

a.读取文件，将每个字符，该字符出现的次数和权值构成哈夫曼树

b.哈夫曼树是利用小堆构成，字符出现次数少的节点指针存在堆顶，出现次数多的在堆底

c.每次取堆顶的两个数，再将两个数相加进堆，直到堆被取完，这时哈夫曼树也建成

d.从哈夫曼树中获取哈夫曼编码，然后再根据整个字符数组来获取出现了得字符的编码

e.获取编码后每次凑满8位就将编码串写入到压缩文件（value处理编码1与它即可，0只移动位）

f.写好配置文件，统计每个字符及其出现次数，并以“字符+','+次数”的形式保存到配置文件中

2.解压

a.读取配置文件，统计所有字符的个数

b.构建哈夫曼树，读解压缩文件，将所读到的编码字符的这个节点所所含的字符写入到解压缩文件中，知道将压缩文件读完

c.压缩解压缩完全完成，进行小文件大文件的测试

实例代码：

#pragmaonce
#include

template
structLess
{
booloperator()(constT&l,constT&r)const
{
returnl
structGreater
{
booloperator()(constT&l,constT&r)const
{
returnl>r;
}
};

template
classHeap
{
public:
Heap()
{}

Heap(T*array,size_tn)//建堆
{
_array.reserve(n);

for(size_ti=0;i>1;i>=0;--i)
{
_AdjustDown(i);
}
}

constT&Top()const
{
return_array[0];
}

voidPush(constT&x)
{
_array.push_back(x);
_AdjustUp(_array.size()-1);
}

size_tSize()
{
return_array.size();
}

voidPop()
{
assert(_array.size()>0);
swap(_array[0],_array[_array.size()-1]);
_array.pop_back();
_AdjustDown(0);
}

boolEmpty()
{
return_array.size()==0;
}

voidPrint()
{
for(size_ti=0;i<_array.size();++i)
{
cout<<_array[i]<<"";
}
cout<>1;
while(child)
{
if(ComFunc(_array[child],_array[parent]))
{
swap(_array[child],_array[parent]);
child=parent;
parent=(child-1)>>1;
}
else
{
break;
}
}
}




void_AdjustDown(introot)//下调
{
CompareComFunc;
intparent=root;
intchild=root*2+1;
while(child<_array.size())
{
if(child+1<_array.size()&&ComFunc(_array[child+1],_array[child]))
{
++child;
}

if(ComFunc(_array[child],_array[parent]))
{
swap(_array[child],_array[parent]);
parent=child;
child=parent*2+1;
}
else
{
break;
}
}
}



protected:
vector_array;


};




voidTestHeap()
{
inta[]={10,11,13,12,16,18,15,17,14,19};
//Heapheap(a,sizeof(a)/sizeof(a[0]));
//Heap>heap(a,sizeof(a)/sizeof(a[0]));
Heap>heap(a,sizeof(a)/sizeof(a[0]));
heap.Print();
heap.Push(25);
heap.Print();
heap.Pop();
heap.Print();
}





#pragmaonce
#include"Heap.h"

template
structHuffmanTreeNode
{
HuffmanTreeNode*_left;
HuffmanTreeNode*_right;
HuffmanTreeNode*_parent;
T_w;//权值


HuffmanTreeNode(constT&x)
:_w(x)
,_left(NULL)
,_right(NULL)
,_parent(NULL)
{}

};

template
classHuffmanTree
{
typedefHuffmanTreeNodeNode;
public:
HuffmanTree()
:_root(NULL)
{}

HuffmanTree(T*a,size_tn,constT&invalid=T())//构建哈夫曼树
{
structCompare
{
booloperator()(Node*l,Node*r)const
{
returnl->_w_w;
}
};

HeapminHeap;
for(size_ti=0;i1)
{
Node*left=minHeap.Top();
minHeap.Pop();
Node*right=minHeap.Top();
minHeap.Pop();
Node*parent=newNode(left->_w+right->_w);
parent->_left=left;
parent->_right=right;
left->_parent=parent;
right->_parent=parent;
minHeap.Push(parent);
}
_root=minHeap.Top();
}


Node*GetRoot()
{
return_root;
}

~HuffmanTree()
{
_Destory(_root);
}





protected:
void_Destory(Node*root)
{
if(root==NULL)
{
return;
}

_Destory(root->_left);
_Destory(root->_right);
deleteroot;
}

HuffmanTree(constHuffmanTree&tree);
HuffmanTree&operator=(constHuffmanTree&tree);

protected:
Node*_root;

};


voidTestHuffmanTree()
{#pragmaonce

#include
usingnamespacestd;
#include
#include"HuffmanTree.h"


typedeflonglongLongType;
structCharInfo
{
unsignedchar_ch;//字符
LongType_count;//字符出现的次数
string_code;//huffman编码

CharInfo(LongTypecount=0)
:_count(count)
,_ch(0)
,_code("")
{}


booloperator<(constCharInfo&info)const
{
return_counttree(_info,256,invalid);

//生成huffmancode
GetHuffmanCode(tree.GetRoot());

//压缩
//写配置文件
for(size_ti=0;i<256;++i)
{
if(_info[i]._count)
{
info._ch=_info[i]._ch;
info._count=_info[i]._count;
fwrite(&info,sizeof(info),1,fin);
}
}

info._count=-1;
fwrite(&info,sizeof(info),1,fin);

fseek(fout,0,SEEK_SET);//返回到文件开始
ch=fgetc(fout);
charvalue=0;//二进制
intpos=0;//左移位数
while(ch!=EOF)
{
string&code=_info[(unsignedchar)ch]._code;
size_ti=0;
for(i=0;i*root)//huffman编码
{
if(root==NULL)
{
return;
}

if(root->_left==NULL&&root->_right==NULL)
{
HuffmanTreeNode*parent,*cur;
cur=root;
parent=cur->_parent;
string&code=_info[(unsignedchar)root->_w._ch]._code;
while(parent)
{
if(cur==parent->_left)
{
code+='0';
}
else
{
code+='1';
}
cur=parent;
parent=cur->_parent;
}
reverse(code.begin(),code.end());
}
GetHuffmanCode(root->_left);
GetHuffmanCode(root->_right);
}

//解压
voidUnCompress(constchar*filename)
{
assert(filename);
stringUnCompressFile=filename;
size_tindex=UnCompressFile.rfind('.');
assert(index!=string::npos);
UnCompressFile=UnCompressFile.substr(0,index);
UnCompressFile+=".unhuffman";
FILE*fout=fopen(filename,"rb");
assert(fout);
FILE*fin=fopen(UnCompressFile.c_str(),"wb");
assert(fin);
CountInfoinfo;
fread(&info,sizeof(CountInfo),1,fout);

//读配置信息
while(1)
{
fread(&info,sizeof(CountInfo),1,fout);
if(info._count==-1)
{
break;
}
_info[(unsignedchar)info._ch]._ch=info._ch;
_info[(unsignedchar)info._ch]._count=info._count;
}

//重建huffman树
CharInfoinvalid;
invalid._count=0;
HuffmanTreetree(_info,256,invalid);
HuffmanTreeNode*root=tree.GetRoot();
HuffmanTreeNode*cur=root;
LongTypecount=root->_w._count;
intvalue=fgetc(fout);

if(value==EOF)//只有一种字符
{
if(info._ch!=0)
{
while(cur->_w._count--)
{
fputc(cur->_w._ch,fin);
}
}
}
else
{
while(value!=EOF)
{
intpos=7;
chartest=1;
while(pos>=0)
{
if(value&(test<_right;
}
else
{
cur=cur->_left;
}
if(cur->_left==NULL&&cur->_right==NULL)
{
fputc(cur->_w._ch,fin);
cur=root;
if(--count==0)
{
break;
}
}
--pos;
}
value=fgetc(fout);
}
}

fclose(fout);
fclose(fin);
}

protected:
CharInfo_info[256];//所有字符信息
};

voidTestFileCompress()
{
FileCompressfc;
//fc.Compress("实验.doc");
//fc.UnCompress("实验.doc.huffman");
//fc.Compress("qq.JPG");
//fc.UnCompress("qq.JPG.huffman");
//fc.Compress("www.MP3");
//fc.UnCompress("www.MP3.huffman");

fc.Compress("yppppp.txt");
fc.UnCompress("yppppp.txt.huffman");
}

intarray[10]={2,4,6,9,7,8,5,0,1,3};HuffmanTreet(array,10);}

#include #include #include usingnamespacestd; #include"Heap.h" #include"HuffmanTree.h" #include"FileCompress.h" intmain() { //TestHeap(); TestHuffmanTree(); TestFileCompress(); system("pause"); return0; }

以上就是哈夫曼树的实例详解，如有疑问请留言或者到本站社区交流，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

C++数据结构之文件压缩（哈夫曼树）实例详解

热门推荐

随机推荐