C++數(shù)據(jù)結(jié)構(gòu)之文件壓縮（哈夫曼樹(shù)）實(shí)例詳解
成都創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的黎平網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
概要：
項(xiàng)目簡(jiǎn)介：利用哈夫曼編碼的方式對(duì)文件進(jìn)行壓縮，并且對(duì)壓縮文件可以解壓
開(kāi)發(fā)環(huán)境：windows vs2013
項(xiàng)目概述：
1.壓縮
a.讀取文件，將每個(gè)字符，該字符出現(xiàn)的次數(shù)和權(quán)值構(gòu)成哈夫曼樹(shù)
b.哈夫曼樹(shù)是利用小堆構(gòu)成，字符出現(xiàn)次數(shù)少的節(jié)點(diǎn)指針存在堆頂，出現(xiàn)次數(shù)多的在堆底
c.每次取堆頂?shù)膬蓚€(gè)數(shù)，再將兩個(gè)數(shù)相加進(jìn)堆，直到堆被取完，這時(shí)哈夫曼樹(shù)也建成
d.從哈夫曼樹(shù)中獲取哈夫曼編碼，然后再根據(jù)整個(gè)字符數(shù)組來(lái)獲取出現(xiàn)了得字符的編碼
e.獲取編碼后每次湊滿8位就將編碼串寫入到壓縮文件（value處理編碼1與它即可，0只移動(dòng)位）
f.寫好配置文件，統(tǒng)計(jì)每個(gè)字符及其出現(xiàn)次數(shù)，并以“字符+','+次數(shù)”的形式保存到配置文件中
2.解壓
a.讀取配置文件，統(tǒng)計(jì)所有字符的個(gè)數(shù)
b.構(gòu)建哈夫曼樹(shù)，讀解壓縮文件，將所讀到的編碼字符的這個(gè)節(jié)點(diǎn)所所含的字符寫入到解壓縮文件中，知道將壓縮文件讀完
c.壓縮解壓縮完全完成，進(jìn)行小文件大文件的測(cè)試
實(shí)例代碼：
#pragma once
#include
template
struct Less
{
bool operator()(const T& l, const T& r) const
{
return l < r;
}
};
template
struct Greater
{
bool operator()(const T& l, const T& r) const
{
return l > r;
}
};
template
class Heap
{
public:
Heap()
{}
Heap(T* array, size_t n) //建堆
{
_array.reserve(n);
for (size_t i = 0; i < n; i++)
{
_array.push_back(array[i]);
}
for (int i = (_array.size() - 2) >> 1; i >= 0; --i)
{
_AdjustDown(i);
}
}
const T& Top()const
{
return _array[0];
}
void Push(const T& x)
{
_array.push_back(x);
_AdjustUp(_array.size() - 1);
}
size_t Size()
{
return _array.size();
}
void Pop()
{
assert(_array.size() > 0);
swap(_array[0], _array[_array.size() - 1]);
_array.pop_back();
_AdjustDown(0);
}
bool Empty()
{
return _array.size() == 0;
}
void Print()
{
for (size_t i = 0; i < _array.size(); ++i)
{
cout << _array[i] << " ";
}
cout << endl;
}
protected:
void _AdjustUp(int child) //上調(diào)
{
Compare ComFunc;
int parent = (child - 1) >> 1;
while (child)
{
if (ComFunc(_array[child], _array[parent]))
{
swap(_array[child], _array[parent]);
child = parent;
parent = (child - 1) >> 1;
}
else
{
break;
}
}
}
void _AdjustDown(int root) //下調(diào)
{
Compare ComFunc;
int parent = root;
int child = 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;
};
void TestHeap()
{
int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
//Heap heap(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();
}
#pragma once
#include"Heap.h"
template
struct HuffmanTreeNode
{
HuffmanTreeNode* _left;
HuffmanTreeNode* _right;
HuffmanTreeNode* _parent;
T _w; //權(quán)值
HuffmanTreeNode(const T& x)
:_w(x)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
{}
};
template
class HuffmanTree
{
typedef HuffmanTreeNode Node;
public:
HuffmanTree()
:_root(NULL)
{}
HuffmanTree(T* a, size_t n, const T& invalid = T()) //構(gòu)建哈夫曼樹(shù)
{
struct Compare
{
bool operator()(Node* l, Node* r) const
{
return l->_w < r->_w;
}
};
Heap minHeap;
for (size_t i = 0; i < n; ++i)
{
if (a[i] != invalid)
{
minHeap.Push(new Node(a[i]));
}
}
while (minHeap.Size() > 1)
{
Node* left = minHeap.Top();
minHeap.Pop();
Node* right = minHeap.Top();
minHeap.Pop();
Node* parent = new Node(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);
delete root;
}
HuffmanTree(const HuffmanTree& tree);
HuffmanTree& operator=(const HuffmanTree& tree);
protected:
Node* _root;
};
void TestHuffmanTree()
{#pragma once
#include
using namespace std;
#include
#include"HuffmanTree.h"
typedef long long LongType;
struct CharInfo
{
unsigned char _ch; //字符
LongType _count; //字符出現(xiàn)的次數(shù)
string _code; //huffman編碼
CharInfo(LongType count = 0)
:_count(count)
, _ch(0)
, _code("")
{}
bool operator<(const CharInfo& info) const
{
return _count < info._count;
}
CharInfo operator+(const CharInfo& info)
{
return CharInfo(_count + info._count);
}
bool operator!=(const CharInfo& info)const
{
return _count != info._count;
}
};
struct CountInfo
{
unsigned char _ch; //字符
LongType _count; //字符出現(xiàn)的次數(shù)
};
class FileCompress
{
public:
FileCompress()
{
for (size_t i = 0; i < 256; ++i)
{
_info[i]._ch = i;
}
}
void Compress(const char* filename)
{
assert(filename);
//統(tǒng)計(jì)字符出現(xiàn)的次數(shù)，均已二進(jìn)制方式讀寫
FILE* fout = fopen(filename, "rb");
assert(fout);
int ch = fgetc(fout);
string CompressFile = filename;
CompressFile += ".huffman";
FILE* fin = fopen(CompressFile.c_str(), "wb");
assert(fin);
CountInfo info;
while (ch != EOF)
{
_info[(unsigned char)ch]._count++;
ch = fgetc(fout);
}
//構(gòu)建huffman tree
CharInfo invalid;
invalid._count = 0;
HuffmanTree tree(_info, 256, invalid);
//生成huffman code
GetHuffmanCode(tree.GetRoot());
//壓縮
//寫配置文件
for (size_t i = 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); //返回到文件開(kāi)始
ch = fgetc(fout);
char value = 0; //二進(jìn)制
int pos = 0; //左移位數(shù)
while (ch != EOF)
{
string& code = _info[(unsigned char)ch]._code;
size_t i = 0;
for (i = 0; i < code.size(); ++i)
{
value <<= 1;
++pos;
if (code[i] == '1')
{
value |= 1;
}
if (pos == 8) //滿8位寫進(jìn)文件中
{
fputc(value, fin);
value = 0;
pos = 0;
}
}
ch = fgetc(fout);
}
if (pos)
{
value <<= (8 - pos);
fputc(value, fin);
}
fclose(fin);
fclose(fout);
}
void GetHuffmanCode(HuffmanTreeNode* root) //huffman編碼
{
if (root == NULL)
{
return;
}
if (root->_left == NULL && root->_right == NULL)
{
HuffmanTreeNode *parent, *cur;
cur = root;
parent = cur->_parent;
string& code = _info[(unsigned char)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);
}
//解壓
void UnCompress(const char* filename)
{
assert(filename);
string UnCompressFile = filename;
size_t index = 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);
CountInfo info;
fread(&info, sizeof(CountInfo), 1, fout);
//讀配置信息
while (1)
{
fread(&info, sizeof(CountInfo), 1, fout);
if (info._count == -1)
{
break;
}
_info[(unsigned char)info._ch]._ch = info._ch;
_info[(unsigned char)info._ch]._count = info._count;
}
//重建huffman樹(shù)
CharInfo invalid;
invalid._count = 0;
HuffmanTree tree(_info, 256, invalid);
HuffmanTreeNode* root = tree.GetRoot();
HuffmanTreeNode* cur = root;
LongType count = root->_w._count;
int value = fgetc(fout);
if (value == EOF) //只有一種字符
{
if (info._ch != 0)
{
while (cur->_w._count--)
{
fputc(cur->_w._ch, fin);
}
}
}
else
{
while (value != EOF)
{
int pos = 7;
char test = 1;
while (pos >= 0)
{
if (value & (test << pos))
{
cur = cur->_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]; //所有字符信息
};
void TestFileCompress()
{
FileCompress fc;
//fc.Compress("實(shí)驗(yàn).doc");
//fc.UnCompress("實(shí)驗(yàn).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");
}
int array[10] = { 2, 4, 6, 9, 7, 8, 5, 0, 1, 3 };HuffmanTree t(array, 10);}
#include
#include
#include
using namespace std;
#include"Heap.h"
#include"HuffmanTree.h"
#include"FileCompress.h"
int main()
{
//TestHeap();
TestHuffmanTree();
TestFileCompress();
system("pause");
return 0;
}
以上就是哈夫曼樹(shù)的實(shí)例詳解，如有疑問(wèn)請(qǐng)留言或者到本站社區(qū)交流，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
網(wǎng)站欄目：C++數(shù)據(jù)結(jié)構(gòu)之文件壓縮（哈夫曼樹(shù)）實(shí)例詳解
地址分享：
http://weahome.cn/article/jdgesh.html
重慶分公司
重慶分公司
