데이터 구조 - 파일 압축 (하프 만 인 코딩 으로 구현)
9435 단어 데이터 구조
#pragma once
#include
#include
#include
#include
using namespace std;
template
struct Less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template
struct Great
{
bool operator()(const T& l, const T& r)
{
return l>r;
}
};
template>
class Heap
{
public:
Heap()
{}
Heap(T* a, size_t size)
{
_array.reserve(size);
for (size_t i = 0; i < size; i++)
{
_array.push_back(a[i]);
}
// ， ，
for (int i = (size - 2) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
void Push(const T&data)
{
_array.push_back(data);
AdjustUp(_array.size() - 1);
}
void Pop()
{
if (!_array.empty())
{
swap(_array[0], _array[_array.size() - 1]);
_array.pop_back();
AdjustDown(0);
}
}
const T& Top()
{
assert(!_array.empty());
return _array[0];
}
bool Empty()
{
return _array.empty();
}
size_t Size()
{
return _array.size();
}
private:
void AdjustUp(int root)
{
int child = root;
int parent = (child - 1) / 2;
compare com;
while (parent >= 0)
{
if (com(_array[child], _array[parent]))
{
swap(_array[child], _array[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
void AdjustDown(int root)
{
size_t parent = root;
size_t child = root * 2 + 1;
compare com;
while (child < _array.size())
{
if (child + 1 < _array.size() && com(_array[child + 1], _array[child]))
child++;
if (com(_array[child], _array[parent]))
{
swap(_array[child], _array[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
vector _array;
};
HuffmanTree.h:
#pragma once
#include"Heap.h"
template
struct HuffmanNode
{
HuffmanNode* _left;
HuffmanNode* _right;
HuffmanNode* _parent;
W _w;//
HuffmanNode(const W& w)
:_left(NULL)
, _right(NULL)
, _parent(NULL)
, _w(w)
{}
};
template
class HuffmanTree
{
public:
typedef HuffmanNode Node;//HuffmanNode Node
HuffmanTree()
{
root = NULL;
}
HuffmanTree(W* w, size_t size, const W& invalid)// huffmantree w， size，
{
//1. ， 、 Huffmantree
//
struct NodeCompare
{
bool operator()(Node* l, Node* r)
{
return l->_w < r->_w;
}
};
//2.
Heap minheap;
for (size_t i = 0; i < size; i++)
{
if (w[i] != invalid)
{
minheap.Push(new Node(w[i]));
}
}
//3. Huffmantree
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;
}
private:
//
HuffmanTree(const HuffmanTree& tree);
HuffmanTree& operator=(const HuffmanTree& tree);
Node* root;
};
FileCompress.h
#pragma once
#include
using namespace std;
#include
#include
#include"Huffman.h"
// ， HuffmanTree
struct CharInfo
{
char _ch;
string _code;// Huffman
long long _count;//ch
bool operator !=(const CharInfo& info)
{
return _count!= info._count;
}
bool operator Node;
//
struct ConfInfo
{
char _ch;
long long _count;
};
public:
// _info[]
FileCompress()
{
for (int i = 0; i < 256; i++)
{
_info[i]._ch = i;
_info[i]._count = 0;
}
}
//
void Compress(char* file)
{
//1. ，
FILE* fout = fopen(file, "rb");
assert(fout);
char ch = getc(fout);
while (!feof(fout))
{
_info[(unsigned char)ch]._count++;
ch = getc(fout);
}
//2. HuffmanTree
CharInfo invalid;
invalid._count = 0;
HuffmanTree tree(_info, 256, invalid);
//3. Huffman
string code;
Node* root = tree.GetRoot();
GetHuffmanCode(root, code);
//4. ， ; HuffmanTree
string Comfile = file;
Comfile += ".Compress";
FILE* fin = fopen(Comfile.c_str(), "wb");
ConfInfo info;
for (int i = 0; i < 256; i++)
{
if (_info[i]._count != 0)
{
info._ch = _info[i]._ch;
info._count = _info[i]._count;
fwrite(&info, sizeof(ConfInfo), 1, fin);
}
}
//
info._count = 0;
fwrite(&info, sizeof(ConfInfo), 1, fin);
//5.
fseek(fout, 0, SEEK_SET);
char value = 0;
int pos = 0;
Node* cur = root;
ch = fgetc(fout);
while (!feof(fout))
{
string code = _info[(unsigned char)ch]._code;
for (int i = 0; i < code.size(); i++)
{
if (code[i] == '1')
value |= (1 << pos);
else if (code[i] == '0')
value &= ~(1 << pos);
else
assert(false);
pos++;
if (pos == 8)
{
putc(value, fin);
pos = 0;
value = 0;
}
}
ch = getc(fout);
}
if (pos != 0)
putc(value, fin);
//
fclose(fout);
fclose(fin);
}
void UnCompress(char* file)
{
//1.
assert(file);
FILE* fout = fopen(file, "rb");
assert(fout);
while (1)
{
ConfInfo info;
fread(&info, sizeof(ConfInfo), 1, fout);
if (info._count == 0)
break;
_info[(unsigned char)info._ch]._count = info._count;
}
//2. huffmanTree
CharInfo invalid;
invalid._count = 0;
HuffmanTree tree(_info,256,invalid);
//3.
string UnCompress = file;
size_t find = UnCompress.rfind('.');
UnCompress.erase(find, UnCompress.size() - find);
UnCompress += ".UnCompress";
FILE* fin = fopen(UnCompress.c_str(), "wb");
Node* root = tree.GetRoot();
Node* cur = root;
long long count = root->_w._count;
char value = fgetc(fout);
while (!feof(fout))
{
for (size_t pos = 0; pos < 8; pos++)
{
if (value & (1 << pos))
cur = cur->_left;
else
cur = cur->_right;
if (cur->_left == NULL && cur->_right == NULL)
{
putc(cur->_w._ch, fin);
cur = root;
count--;
if (count == 0)
break;
}
}
value = getc(fout);
}
fclose(fout);
fclose(fin);
}
private:
void GetHuffmanCode(Node* root, string code)// HuffmanCode
{
if (root == NULL)
return;
if (root->_left == NULL && root->_right == NULL)
{
_info[(unsigned char)root->_w._ch]._code = code;
return;
}
GetHuffmanCode(root->_left, code + '1');
GetHuffmanCode(root->_right, code + '0');
}
CharInfo _info[256];
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
