溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
C++數據結構之文件壓縮（哈夫曼樹）實例詳解
概要：
項目簡介：利用哈夫曼編碼的方式對文件進行壓縮，并且對壓縮文件可以解壓
開發環境：windows vs2013
項目概述：
1.壓縮
a.讀取文件，將每個字符，該字符出現的次數和權值構成哈夫曼樹
b.哈夫曼樹是利用小堆構成，字符出現次數少的節點指針存在堆頂，出現次數多的在堆底
c.每次取堆頂的兩個數，再將兩個數相加進堆，直到堆被取完，這時哈夫曼樹也建成
d.從哈夫曼樹中獲取哈夫曼編碼，然后再根據整個字符數組來獲取出現了得字符的編碼
e.獲取編碼后每次湊滿8位就將編碼串寫入到壓縮文件（value處理編碼1與它即可，0只移動位）
f.寫好配置文件，統計每個字符及其出現次數，并以“字符+','+次數”的形式保存到配置文件中
2.解壓
a.讀取配置文件，統計所有字符的個數
b.構建哈夫曼樹，讀解壓縮文件，將所讀到的編碼字符的這個節點所所含的字符寫入到解壓縮文件中，知道將壓縮文件讀完
c.壓縮解壓縮完全完成，進行小文件大文件的測試
實例代碼：
#pragma once
#include<vector>
template<class T>
struct Less
{
bool operator()(const T& l, const T& r) const
{
return l < r;
}
};
template<class T>
struct Greater
{
bool operator()(const T& l, const T& r) const
{
return l > r;
}
};
template<class T, class Compare>
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) //上調
{
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) //下調
{
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<T> _array;
};
void TestHeap()
{
int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
//Heap<int> heap(a, sizeof(a) / sizeof(a[0]));
//Heap<int, Less<int>> heap(a, sizeof(a) / sizeof(a[0]));
Heap<int, Greater<int>> heap(a, sizeof(a) / sizeof(a[0]));
heap.Print();
heap.Push(25);
heap.Print();
heap.Pop();
heap.Print();
}
#pragma once
#include"Heap.h"
template<class T>
struct HuffmanTreeNode
{
HuffmanTreeNode<T>* _left;
HuffmanTreeNode<T>* _right;
HuffmanTreeNode<T>* _parent;
T _w; //權值
HuffmanTreeNode(const T& x)
:_w(x)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
{}
};
template<class T>
class HuffmanTree
{
typedef HuffmanTreeNode<T> Node;
public:
HuffmanTree()
:_root(NULL)
{}
HuffmanTree(T* a, size_t n, const T& invalid = T()) //構建哈夫曼樹
{
struct Compare
{
bool operator()(Node* l, Node* r) const
{
return l->_w < r->_w;
}
};
Heap<Node*, Compare> 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<T>& tree);
HuffmanTree& operator=(const HuffmanTree<T>& tree);
protected:
Node* _root;
};
void TestHuffmanTree()
{<pre code_snippet_id="2340790" snippet_file_name="blog_20170418_2_3778260" name="code" class="cpp">#pragma once
#include<iostream>
using namespace std;
#include<assert.h>
#include"HuffmanTree.h"
typedef long long LongType;
struct CharInfo
{
unsigned char _ch; //字符
LongType _count; //字符出現的次數
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; //字符出現的次數
};
class FileCompress
{
public:
FileCompress()
{
for (size_t i = 0; i < 256; ++i)
{
_info[i]._ch = i;
}
}
void Compress(const char* filename)
{
assert(filename);
//統計字符出現的次數，均已二進制方式讀寫
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);
}
//構建huffman tree
CharInfo invalid;
invalid._count = 0;
HuffmanTree<CharInfo> 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); //返回到文件開始
ch = fgetc(fout);
char value = 0; //二進制
int pos = 0; //左移位數
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位寫進文件中
{
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<CharInfo>* root) //huffman編碼
{
if (root == NULL)
{
return;
}
if (root->_left == NULL && root->_right == NULL)
{
HuffmanTreeNode<CharInfo> *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樹
CharInfo invalid;
invalid._count = 0;
HuffmanTree<CharInfo> tree(_info, 256, invalid);
HuffmanTreeNode<CharInfo>* root = tree.GetRoot();
HuffmanTreeNode<CharInfo>* 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("實驗.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");
}</pre><br>
int array[10] = { 2, 4, 6, 9, 7, 8, 5, 0, 1, 3 };HuffmanTree<int> t(array, 10);}
<pre></pre>
<p></p>
<pre></pre>
<p></p>
<p></p>
<p></p>
<pre code_snippet_id="2340790" snippet_file_name="blog_20170418_3_1128302" name="code" class="cpp">#include <iostream>
#include <assert.h>
#include <windows.h>
using namespace std;
#include"Heap.h"
#include"HuffmanTree.h"
#include"FileCompress.h"
int main()
{
//TestHeap();
TestHuffmanTree();
TestFileCompress();
system("pause");
return 0;
}</pre><br>
<br>
<p></p>
<p><br>
</p>
<p><br>
</p>
<link rel="stylesheet" rel="external nofollow" >
以上就是哈夫曼樹的實例詳解，如有疑問請留言或者到本站社區交流，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
