溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
<html>
<HEAD></HEAD>
<BODY>
<textarea rows="10" cols="50"> </textarea>
<FONT >û</FONT>
<textarea rows="20" cols="150">
【文件壓縮解壓項目】
【項目技術：】
模版堆，哈夫曼樹，哈夫曼編碼，函數對象，feof函數，文件讀寫
【項目準備：】
文件運行于Visual Studio 平臺(VS)，
數據準備一份待壓縮文件，本程序運行可以不做準備。
【項目過程：】
壓縮過程
1.從待壓縮原文件中統計字符個數，利用堆建立哈夫曼樹。
2.依據哈弗曼樹寫入每個字符相應的哈夫曼編碼。將這里的字符 和統計出現的次數寫入配置文件。
3.打開一個新文件，按照哈夫曼編碼用較短編碼代替原文件較長的編碼，實現壓縮。
//配置文件丟失后 壓縮的文件也就失去了意義這兩個文件是相互對應互相起作用的。
解壓過程：
1.根據配置文件中的次數再次建立哈夫曼樹，哈夫曼字符編碼集。
2.根據哈夫曼字符編碼集，翻譯程序生成的短的編碼文件。翻譯得到的內容寫入新文件
//可以對比原文件與翻譯后的文件
//時間上的考慮，在調試版本與發行版本中壓縮世界總是大于解壓時間。
【項目思考：】對于少量信息的文本，壓縮所能遇見的問題 對于中文字符 二次壓縮
為什么配置文件里不直接寫構造好的編碼 ，雖然這樣可以做到
因為人的思想總是快一點 以為對照字符與哈夫曼編碼進行翻譯能夠快 而實際計算機在運行中 總是對 待翻譯的編碼
在配置文件中比對編碼和尋找對應的字符。
對于項目運行后的警告 文件讀寫復習。
</textarea>
<p><FONT >324</FONT></p>
<textarea rows="20" cols="150">
#include <iostream>
using namespace std;
#include <cassert>
#include <string>
#include <vector>
#include <cassert>
#include <time.h>
template<class T>
struct Less
{
bool operator() (const T& l, const T& r)
{
return l < r;
}
};
template<class T>
struct Greater
{
bool operator() (const T& l, const T& r)
{
return l > r;
}
};
template<class T, class Compare = Less>
class Heap
{
public:
Heap()
{}
Heap(const T* a, size_t size)
{
_a.reserve(size);
for (size_t i = 0; i < size; ++i)
{
_a.push_back(a[i]);
}
for (int i = (_a.size() - 2) / 2; i >= 0; --i)
{
_AdjustDown(i);
}
}
Heap(vector<T>& a)
{
_a.swap(a);
for (int i = (_a.size() - 2) / 2; i >= 0; --i)
{
_AdjustDown(i);
}
}
void Push(const T& x)
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);
}
void Pop()
{
size_t size = _a.size();
assert(size > 0);
swap(_a[0], _a[size - 1]);
_a.pop_back();
_AdjustDown(0);
}
T& Top()
{
assert(!_a.empty());
return _a[0];
}
size_t size()
{
assert(!_a.empty());
return (_a.size());
}
protected:
void _AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
Compare com;
if (com(_a[child], _a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void _AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _a.size())
{
Compare com;
if (child + 1 < _a.size()
&& com(_a[child + 1], _a[child]))
{
++child;
}
if (com(_a[child], _a[parent]))
{
swap(_a[parent], _a[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
protected:
vector<T> _a;
};
/*/
------文件可拆分線--------#include "Heap.h" -------
構建哈夫曼樹 (利用小堆構建哈夫曼樹)
/*/
template <class T>
struct HuffmanNode
{
HuffmanNode<T>*_left;
HuffmanNode<T>*_right;
T _weight;
HuffmanNode(const T&weight)
:_left(NULL)
, _right(NULL)
, _weight(weight)
{}
};
template <class T>
class HuffmanTree
{
typedef HuffmanNode<T> Node;
public:
HuffmanTree(const T*a, size_t size, const T& invalid)
/*/invalid代表非法值，若為非法值，則不構建哈夫曼樹/*/
{
_root = CreateTree(a, size, invalid);
}
Node* GetRootNode()
{
return _root;
}
protected:
Node* CreateTree(const T*a, size_t size, const T& invalid)
{
struct Compare
{
bool operator()(const Node*l, const Node*r)
{
return (l->_weight < r->_weight);
}
};
Heap <Node*, Compare> minHeap;
for (size_t i = 0; i < size; ++i)
{
if (a[i] != invalid)
{
minHeap.Push(new Node(a[i]));
}
}
/*/小堆的top結點的權值必是最小的，每次選出小堆的top構造哈夫曼樹的結點/*/
while (minHeap.size()>1)
{
Node* left = minHeap.Top();
minHeap.Pop();
Node* right = minHeap.Top();
minHeap.Pop();
Node* parent = new Node(left->_weight + right->_weight);
/*/哈夫曼樹特點，父結點是兩個子結點和/*/
parent->_left = left;
parent->_right = right;
minHeap.Push(parent);
}
return minHeap.Top();
}
protected:
HuffmanNode<T>* _root;
};
/*/
----文件可分割線--#include "HuffmanTree.h"------
統計字符次數 構建哈夫曼樹（堆） 生成哈夫曼編碼 讀取源文件字符壓縮
哈夫曼樹根結點的權值就是源文件讀入的個數
統計字符次數
/*/
typedef unsigned long long LongType;
struct CharInfo
{
unsigned char _ch; /*/字符/*/
LongType _count; /*/出現次數/*/
string _code; /*/Huffman code/*/
CharInfo()
:_ch(0)
, _count(0)
{}
CharInfo(LongType count)
:_ch(0)
, _count(count)
{}
bool operator!=(const CharInfo&info) const
{
return _count != info._count;
}
CharInfo operator+(const CharInfo&info) const
{
return CharInfo(_count + info._count);
}
bool operator<(const CharInfo&info) const
{
return _count < info._count;
}
};
template <class T>
class FileCompress
{
typedef HuffmanNode<T> Node;
public:
FileCompress()
{
for (size_t i = 0; i < 256; ++i)
{
_infos[i]._ch = i;
_infos[i]._count = 0;
}
}
public:
void Compress(const char* filename)
{
assert(filename);
/*/統計文件中字符出現的次數/*/
FILE* fout = fopen(filename, "rb");
assert(fout);
char ch = fgetc(fout);
while (!feof(fout))
{
_infos[(unsigned char)ch]._count++;
ch = fgetc(fout);
}
/*/構建哈夫曼樹/*/
CharInfo invalid(0);
HuffmanTree<CharInfo>tree(_infos, 256, invalid);
/*/生成哈夫曼編碼/*/
string code;
GenerateHuffmanCode(tree.GetRootNode(), code);
/*/讀取源文件字符壓縮，將哈夫曼編碼寫進對應的位/*/
string Compressfilename = filename;
Compressfilename += ".compress";
FILE* fin = fopen(Compressfilename.c_str(), "wb"); /*/用二進制讀寫文件/*/
fseek(fout, 0, SEEK_SET); /*/定位到文件起始位置/*/
ch = fgetc(fout);
char value = 0;
int pos = 0;
while (!feof(fout))
{
string &code = _infos[(unsigned char)ch]._code;
/*/注意code要為引用/*/
for (size_t i = 0; i < code.size(); ++i)
/*/利用位存儲哈夫曼編碼，減少內存/*/
{
value <<= 1;
if (code[i] == '1')
{
value |= 1;
}
if (++pos == 8)
/*/
滿8位（1字節），將哈夫曼編碼寫進對應的文件，
然后繼續讀取這個字符的后續編碼
/*/
{
fputc(value, fin);
value = 0;
pos = 0;
}
}
ch = fgetc(fout); /*/繼續讀取下一個字符的哈夫曼編碼/*/
}
if (pos != 0)
/*/如果最后幾位哈夫曼編碼不滿8位，
則需要補充記錄， 后續補充(配置文件)/*/
{
value <<= (8 - pos);
fputc(value, fin);
}
/*/寫配置文件，方便解壓縮的時候重建哈夫曼樹/*/
string configfilename = filename;
configfilename += ".config";
FILE* finconfig = fopen(configfilename.c_str(), "wb");
assert(finconfig);
char buffer[128]; /*/設置寫入緩沖區/*/
string str;
for (size_t i = 0; i < 256; ++i)
{
if (_infos[i]._count>0)
{
str += _infos[i]._ch;
str += ",";
str += _itoa(_infos[i]._count, buffer, 10);
/*/itoa將整數_count轉換成字符存入buffer中，10為進制/*/
str += '\n';
}
fputs(str.c_str(), finconfig);
str.clear();
}
fclose(fout);
fclose(fin);
fclose(finconfig);
}
/*/解壓縮/*/
void UnCompress(const char* filename)
{
string configfilename = filename;
configfilename += ".config";
FILE* foutconfig = fopen(configfilename.c_str(), "rb");
assert(foutconfig);
string str;
LongType charCount = 0;
while (Readline(foutconfig, str))
{
if (str.empty())
{
str += '\n';
}
else
{
_infos[(unsigned char)str[0]]._count = atoi(str.substr(2).c_str());
/*/將配置文件中保存的字符格式轉換為次數，
（如a,4所以從第2個字符開始）/*/
str.clear();
}
}
/*/重建哈夫曼樹/*/
CharInfo invalid(0);
HuffmanTree<CharInfo>tree(_infos, 256, invalid);
charCount = tree.GetRootNode()->_weight._count;
string Compressfilename = filename;
Compressfilename += ".compress";
FILE* fout = fopen(Compressfilename.c_str(), "rb");
assert(fout);
string UnCompressfilename = filename;
UnCompressfilename += ".uncompress";
FILE* fin = fopen(UnCompressfilename.c_str(), "wb");
assert(fin);
char ch = fgetc(fout);
HuffmanNode<CharInfo>* root = tree.GetRootNode();
HuffmanNode<CharInfo>* cur = root;
int pos = 7;
while (1)
{
if (ch & (1 << pos))
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
if (pos-- == 0)
{
pos = 7;
ch = fgetc(fout); /*/繼續讀取字符/*/
}
if (cur->_left == NULL&&cur->_right == NULL)
{
fputc(cur->_weight._ch, fin);
if (--charCount == 0)
{
break;
}
cur = root;
}
}
fclose(fin);
}
protected:
void GenerateHuffmanCode(HuffmanNode<CharInfo>* root, string code)
{
if (root == NULL)
{
return;
}
if (root->_left)
{
GenerateHuffmanCode(root->_left, code + '0');
}
if (root->_right)
{
GenerateHuffmanCode(root->_right, code + '1');
}
if ((root->_left == NULL) && (root->_right == NULL))
{
_infos[root->_weight._ch]._code = code;
}
}
bool Readline(FILE* fout, string& str)
{
char ch = fgetc(fout);
if (feof(fout))
{
return false;
}
while (!feof(fout) && ch != '\n')
{
str += ch;
ch = fgetc(fout);
}
return true;
}
protected:
CharInfo _infos[256];
};
void TestCompress()
{
FileCompress<int> fc;
double start_compress = clock();
fc.Compress("Input.txt");
double finish_compress = clock();
fc.UnCompress("Input.txt");
double finish_uncompress = clock();
cout << "壓縮時間是：" << finish_compress - start_compress << "ms" << endl;
cout << "解壓縮時間是：" << finish_uncompress - finish_compress << "ms" << endl;
}
void wztest(char* s)
{
FileCompress<int> fc;
double start_compress = clock();
fc.Compress(s);
double finish_compress = clock();
fc.UnCompress(s);
double finish_uncompress = clock();
cout << "壓縮時間是：" << finish_compress - start_compress << "ms" << endl;
cout << "解壓縮時間是：" << finish_uncompress - finish_compress << "ms" << endl;
}
#include <iostream>
#include <fstream>
using namespace std;
void testfile()
{
char *s="WZXXXXXXXXXXXX.TXT";
ofstream fout(s);
int ss=100;
while(ss--){
fout <<"123abcdefghijklmnopqrstuvwxyz";
}
wztest(s);
}
int main0()
{
TestCompress();
system("pause");
return 0;
}
int main()
{ FILE *pFile = fopen("xxx.txt", "w");
char x[]="wzzx sts bit ";
fwrite(x, 6,12,pFile);
fclose(pFile); fflush(pFile);
wztest("xxx.txt");
system("pause");
return 0;
}
</textarea>
<p><FONT >ogr</FONT></p>
<p><FONT >pgspt</FONT></p>
<p><FONT >%^&*(</FONT></p>
<textarea rows="20" cols="150">
程序運行可以進行微設計
可以用用戶輸入絕對路徑
然后將對應的文件壓縮 同文件目錄中產生新文件
注意轉義操作
</textarea>
<FONT >ABCDEFGH</FONT>
<p><FONT >LMOIJK</FONT></p>
<p><FONT >PQRSD</FONT></p>
<textarea rows="20" cols="150">
</textarea>
</div>
</body>
</html>免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
