成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

C++實(shí)現(xiàn)文件壓縮及解壓縮

    原理：Huffman樹的應(yīng)用：Huffman編碼，為出現(xiàn)頻率較高的字符指定較短的碼字，而為出現(xiàn)頻率較低的字符指定較短的碼字，可以實(shí)現(xiàn)二進(jìn)制文件的壓縮。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：主機(jī)域名、雅安服務(wù)器托管、營銷軟件、網(wǎng)站建設(shè)、三河網(wǎng)站維護(hù)、網(wǎng)站推廣。

Heap.h

#pragma once

#include <vector>

//仿函數(shù)
template<class T>
struct Lesser
{
	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 = Lesser<T>>
class Heap
{
public:
	Heap()
	{}

	Heap(const T* a, size_t 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);
		}
	}

	void Push(const T& x)
	{
		_a.push_back(x);
		_AdjustUp(_a.size()-1);
	}

	void Pop()
	{
		assert(!_a.empty());

		swap(_a[0], _a[_a.size()-1]);
		_a.pop_back();
		_AdjustDown(0);
	}

	T& Top()
	{
		assert(!_a.empty());

		return _a[0];
	}

	bool Empty()
	{
		return _a.empty();
	}

	size_t Size()
	{
		return _a.size();
	}

protected:
	void _AdjustUp(int child)
	{
		Compare cmp;
		int parent = (child-1)/2;

		while (child > 0)//parent>=0 ?
		{
			if (cmp(_a[child], _a[parent]))
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child-1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void _AdjustDown(int parent)
	{
		Compare cmp;
		int child = parent*2 + 1;

		while (child < _a.size())
		{
			if (child+1 < _a.size() && cmp(_a[child+1], _a[child]))
			{
				++child;
			}

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

protected:
	vector<T> _a;
};

HuffmanTree.h

#pragma once

#include "Heap.h"

template<class T>
struct HuffmanTreeNode
{
	HuffmanTreeNode<T>* _left;
	HuffmanTreeNode<T>* _right;
	HuffmanTreeNode<T>* _parent;
	T _weight;

	HuffmanTreeNode(const T& weight)
		:_left(NULL)
		,_right(NULL)
		,_parent(NULL)
		,_weight(weight)
	{}
};

template<class T>
class HuffmanTree
{
	typedef HuffmanTreeNode<T> Node;

public:
	HuffmanTree()
		:_root(NULL)
	{}

	~HuffmanTree()
	{
		_Destory(_root);
	}

	HuffmanTree(const T* a, size_t size, const T& invalid)
	{
		_root = _CreateTree(a, size, invalid);
	}

	Node* GetRoot()
	{
		return _root;
	}

protected:
	Node* _CreateTree(const T* a,size_t size, const T& invalid)
	{
		assert(a);

		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]));
			}
		}

		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; 
			left->_parent = parent;
			right->_parent = parent;

			minHeap.Push(parent);
		}

		return minHeap.Top();
	}

	void _Destory(Node* root)
	{
		if (root == NULL)
			return;

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

protected:
	Node* _root;
};

void HuffmanTreeTest()
{
	int a[] = {0,1,2,3,4,5,6,7,8,9};
	HuffmanTree<int> ht(a, 10, -1);

}

FileCompress.h

#pragma once
#include "HuffmanTree.h"
#include <Windows.h>

struct CharInfo
{
	char _ch;
	int _count;
	string _code;

	CharInfo(unsigned char ch = 0)
		:_ch(ch)
		,_count(0)
	{}

	CharInfo operator+(const CharInfo& x)
	{
		CharInfo tmp;
		tmp._count = _count + x._count;
		return tmp;
	}

	bool operator!=(const CharInfo& x) const
	{
		return _count != x._count;
	}

	bool operator<(const CharInfo& x) const
	{
		return _count < x._count;
	}

};

template<class T>
class FileCompress
{
public:
	FileCompress()
	{
		for (size_t i = 0; i < 256; ++i)
		{
			_infos[i] = i;
		}
	}

	void Compress(const char* filename)
	{
		assert(filename);

		FILE* fOutFile = fopen(filename, "rb");
		assert(fOutFile);

		char ch = fgetc(fOutFile);

		int charCount = 0;//統(tǒng)計(jì)字符總數(shù)
		
		while (!feof(fOutFile))
		{
			++charCount;
			_infos[(unsigned char)ch]._count++;

			ch = fgetc(fOutFile);
		}

		//創(chuàng)建Huffman樹
		CharInfo invalid(0);
		HuffmanTree<CharInfo> t(_infos, 256, invalid);
		//由Huffman樹生成Huffman編碼
		_GenerateHuffmanCode(t.GetRoot());

		//壓縮
		string compressFilename = filename;
		compressFilename += ".compress";
		FILE* fInCompress = fopen(compressFilename.c_str(), "wb");
		assert(fInCompress);

		fseek(fOutFile, 0, SEEK_SET);
		ch = fgetc(fOutFile);
		char value = 0;
		int size = 0;
		while (!feof(fOutFile))
		{
			string& code = _infos[(unsigned char)ch]._code;

			for (size_t i = 0; i < code.size(); ++i)
			{
				value <<= 1;
				
				if (code[i] == '1')
				{
					value |= 1;
				}

				++size;

				if (size == 8)
				{
					fputc(value, fInCompress);
					size = 0;
					value = 0;
				}
			}

			ch = fgetc(fOutFile);
		}

		if (size > 0)//補(bǔ)位
		{
			value <<= (8-size);
			fputc(value, fInCompress);
		}

		//寫配置文件，方便解壓縮時(shí)讀取
		string configFilename = filename;
		configFilename += ".config";
		FILE* fInConfig = fopen(configFilename.c_str(), "wb");
		assert(fInConfig);

		string line;
		char buffer[128];
		
		//將字符總數(shù)寫入配置文件第一行
		line += itoa(charCount, buffer, 10);
		line += "\n";
		fputs(line.c_str(), fInConfig);
		line.clear();

		for (size_t i = 0; i < 256; ++i)
		{
			if (_infos[i]._count)
			{
				line += _infos[i]._ch;
				line += ',';
				line += itoa(_infos[i]._count, buffer, 10);
				line += '\n';

				fputs(line.c_str(), fInConfig);
			}

			line.clear();
		}

		fclose(fOutFile);
		fclose(fInCompress);
		fclose(fInConfig);
	}

	void UnCompress(const char* filename)
	{
		//讀取配置文件
		string configFilename = filename;
		configFilename += ".config";
		FILE* fOutConfig = fopen(configFilename.c_str(), "rb");
		assert(fOutConfig);

		string line;
		
		//讀取字符總數(shù)
		_ReadLine(fOutConfig, line);
		int charCount = atoi(line.c_str());
		line.clear();

		while (_ReadLine(fOutConfig, line))
		{
			if (!line.empty())
			{
				unsigned char ch = line[0];
				_infos[ch]._count = atoi(line.substr(2).c_str());
				
				line.clear();
			}
			else
			{
				line.clear();
				_ReadLine(fOutConfig, line);

				unsigned char ch = '\n';
				_infos[ch]._count = atoi(line.substr(1).c_str());

				line.clear();
			}
		}

		//重建Huffman樹
		CharInfo invalid(0);
		HuffmanTree<CharInfo> t(_infos, 256, invalid);
		
		//讀.compress文件，寫.uncompress文件
		string compressFilename = filename;
		compressFilename += ".compress";
		FILE* fOutCompress = fopen(compressFilename.c_str(), "rb");
		assert(fOutCompress);

		string uncompressFilename = filename;
		uncompressFilename += ".uncompress";
		FILE* fInUncompress = fopen(uncompressFilename.c_str(), "wb");
		assert(fInUncompress);

		HuffmanTreeNode<CharInfo>* root = t.GetRoot();
		HuffmanTreeNode<CharInfo>* cur = root;

		int pos = 7;
		char ch = fgetc(fOutCompress);
		while (1)
		{
			if (ch & (1<<pos))
				cur = cur->_right;
			else
				cur = cur->_left;

			if (cur->_left == NULL && cur->_right == NULL)
			{
				fputc(cur->_weight._ch, fInUncompress);

				cur = root;

				if (--charCount == 0)//字符已讀取完，遇到補(bǔ)位的0不再讀取
				{
					break;
				}
			}

			--pos;
			if (pos == -1)
			{
				ch = fgetc(fOutCompress);
				pos = 7;
			}
		}

		fclose(fOutCompress);
		fclose(fInUncompress);

	}


protected:
	void _GenerateHuffmanCode(HuffmanTreeNode<CharInfo>* root)
	{
		if (root == NULL)
			return;
		
		_GenerateHuffmanCode(root->_left);
		_GenerateHuffmanCode(root->_right);

		if (root->_left == NULL && root->_right == NULL)
		{
			HuffmanTreeNode<CharInfo>* cur = root;
			HuffmanTreeNode<CharInfo>* parent = root->_parent;
			string& code = _infos[(unsigned char)cur->_weight._ch]._code;

			while (parent)
			{
				if (parent->_left == cur)
					code += '0';
				if (parent->_right == cur)
					code += '1';

				cur = parent;
				parent = cur->_parent;
			}

			reverse(code.begin(), code.end());
		}

	}

	bool _ReadLine(FILE* filename, string& line)
	{
		char ch = fgetc(filename);
		
		if (ch == EOF)
			return false;

		while (ch != EOF && ch != '\n')
		{
			line += ch;
			ch = fgetc(filename);
		}

		return true;
	}

protected:
	CharInfo _infos[256];
};

void CompressTest()
{
	//壓縮
	FileCompress<CharInfo> compress;

	int CompressBegin = GetTickCount();

	compress.Compress("Input.BIG");

	int CompressEnd = GetTickCount();

	cout<<"壓縮用時(shí)："<<CompressEnd-CompressBegin<<" ms"<<endl;
}

void UncompressTest()
{
	//解壓縮
	FileCompress<CharInfo> uncompress;

	int UncompressBegin = GetTickCount();

	uncompress.UnCompress("Input.BIG");

	int UncompressEnd = GetTickCount();

	cout<<"解壓縮用時(shí)："<<UncompressEnd-UncompressBegin<<" ms"<<endl;
}

Test.cpp

#include <iostream>
using namespace std;
#include <assert.h>

#include "FileCompress.h"

int main()
{
	CompressTest();

	UncompressTest();
	return 0;
}



下面是對一個(gè)大小為8.04MB文件的測試：


C++實(shí)現(xiàn)文件壓縮及解壓縮

結(jié)果成功壓縮、解壓縮：


C++實(shí)現(xiàn)文件壓縮及解壓縮

壓縮后的文件大小：


C++實(shí)現(xiàn)文件壓縮及解壓縮


壓縮后的文件：


C++實(shí)現(xiàn)文件壓縮及解壓縮


配置文件：


C++實(shí)現(xiàn)文件壓縮及解壓縮


用Beyond Compare文本比較工具檢查原文件與解壓后的文件：


C++實(shí)現(xiàn)文件壓縮及解壓縮

無差異


C++實(shí)現(xiàn)文件壓縮及解壓縮

網(wǎng)站欄目：C++實(shí)現(xiàn)文件壓縮及解壓縮
文章分享：http://jinyejixie.com/article0/pgiooo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、軟件開發(fā)、企業(yè)網(wǎng)站制作、企業(yè)建站、商城網(wǎng)站、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

外貿(mào)網(wǎng)站制作
玉田县| 乡城县| 新巴尔虎右旗| 军事| 仪陇县| 论坛| 图木舒克市| 巴楚县| 寿宁县| 资兴市| 武山县| 墨玉县| 宣恩县| 六安市| 大埔区| 县级市| 南昌市| 论坛| 德格县| 十堰市| 海原县| 宜宾市| 梨树县| 阆中市| 故城县| 凤庆县| 镇宁| 大洼县| 江阴市| 桓仁| 武乡县| 洪江市| 甘泉县| 阿拉善左旗| 凤翔县| 晋宁县| 留坝县| 轮台县| 林芝县| 阿图什市| 鹤岗市|