前言

本文由一個資料結構大作業改造而來，記錄制作程序和部分制作心得，

一、初步確定壓縮和解壓程序

壓縮程序

1.讀取檔案

需要前置知識包括：

檔案操作問題：C++檔案操作大全（程序需要使用最基本的檔案操作）

二進制讀取寫入問題：二進制檔案操作，位運算（需要靈活操作二進制每一位數字，如批量獲取指定范圍二進制位，與批量修改二進制位）

了解資料儲存的本質計算機中所有型別檔案都以二進制形式儲存于計算機或者說硬碟中，理論上只要還原所有二進制位即可還原該檔案，

舉例來說：當我們使用文本檔案打開任何不是文本型別的檔案時都會出現亂碼，其實這就是二進制位以字符形式表現出來的樣子，C++中每個字符占8個二進制位，比如我們用文本打開一個MP3格式檔案時文本中出現的每一個字符亂碼就是每8個二進制位在文本形式下以字符格式表現，所有理論上我們之需要還原這些字符亂碼那么我們便可還原該MP3檔案，而這些亂碼本身又是二進制，最終我們只要還原每個二進制位是0或1，即可還原該檔案，

這也就是可以壓縮任何格式檔案的原理，

檔案讀取速度：檔案讀取速度使用不同函式會又不同的速度，個人使用時感覺上C語言檔案操作會稍微快于C++檔案操作函式，這個涉及最后壓縮時間優化問題，后文會提，

檔案操作函式測驗：部分函式需要根據需求自行測驗后在使用，否則容易導致Bug，比如feof()函式

while (!feof(ifs))
{
   fread((char*)data,1,sizeof(data),ifs);
}

在這樣使用時，while陳述句會在到達檔案末尾時再進入一次回圈，具體照成的原因如下：

注意：feof判斷檔案結束是通過讀取函式fread/fscanf等回傳錯誤來識別的，故而判斷檔案是否結束應該是在讀取函式之后進行判斷，比如，在while回圈讀取一個檔案時，如果是在讀取函式之前進行判斷，則如果檔案最后一行是空白行，可能會造成記憶體錯誤，

2.一個字符一個字符讀取，根據讀取到的字符建立字符出現頻率表

3.建立哈夫曼樹

需要前置知識：哈夫曼樹建立程序

4.這里使用優先佇列，每次選擇兩個權值最小字符作為結點建立樹，并再次將得到的樹的根結點放入優先佇列中，最終創建哈夫曼樹

struct cmp
{
	bool operator()(pair<unsigned long long, TreeNode*>& r, pair<unsigned long long, TreeNode*>& s) {
		if (r.first == s.first)
		{
			return r.second->val > s.second->val;
		}
		return r.first > s.first;
	}
};

priority_queue<pair<unsigned long long, TreeNode*>, vector<pair<unsigned long long, TreeNode*>>, cmp> qNode

需要前置知識：STL優先佇列使用，及其自定義排序方法

5.遍歷哈夫曼樹，根據葉子結點路徑，建立關于每個字符對應到哈夫曼編碼的映射，并儲存于哈希表中

需要前置知識：樹的遍歷，STL哈希表的使用

涉及問題：

哈夫曼編碼儲存問題（應該使用何種資料型別儲存哈夫曼編碼）（該問題涉及到檔案壓縮時寫入新壓縮檔案時的速度問題）

6、創建壓縮檔案，并寫入前置資訊

真正寫入原檔案哈夫曼編碼之前，我們需要寫入該檔案部分資訊，方便解壓時使用，

涉及問題：

哈夫曼樹寫入形式：我們解壓時需要對照哈夫曼編碼，還原原檔案對應字符，也就是原檔案二進制，我們壓縮時寫入的只是這些字符對應的哈夫曼編碼，所以我們需要根據原哈夫曼樹來確定這些哈夫曼編碼表示的字符是誰，所以我們在解壓時需要壓縮時建立的哈夫曼樹來進行解壓或者說解密，

在C++中所以資料型別都有自己所占空間位元組數，使用sizeof()即可得到，我們自定義類也同樣有大小，也就意味這這些資料型別其實也是以二進制形式存在的，只有我們得到這些資料的二進制資訊，要這些資訊賦值給一個新的該種型別，我們即可得到原本該型別的資料，

例如：int型別大小4個位元組，賦值為3，將其以二進制形式寫入檔案中，以二進制形式讀取該檔案，并讀取4個位元組大小的二進制位，賦值給一個新的int型別，這個int的數值就變成了3.

		int sufSize=0;
		fread(&sufSize, sizeof(sufSize), 1, fp);

注意：我們不可以使用該方法儲存或讀取帶有指標的型別，這樣只會將該型別的指標寫入或者讀取出來，而指標所指向的內容并不會寫入檔案中，所以在讀取時可能導致型別中的指標指向一個沒有被分配空間的地方，形成危險的野指標，

因此我們不能直接將鏈式建立的哈夫曼樹寫入檔案中，但是我們可以寫入建立哈夫曼樹所需資訊，不帶指標即可，建立哈夫曼樹需要的是字符出現頻率表，因此我們只需要將每個字符與其對應出現頻率做成一個鍵值對，也就是pair型別，再一個一個寫入即可，在解壓時一個一個讀取，重新建立還原壓縮時的哈夫曼樹即可，

因此我們需要寫入頻率表資料個數，方便解壓時使用，才能在解壓時知道要讀取多少個

解壓檔案型別寫入：我們解壓檔案時需要確定檔案是什么型別，所以我們需要將原檔案型別，如MP3后綴資訊寫入，注意不能直接將string型別的二進制資訊寫入，因為string型別帶有指標，我們需要將后綴名一個字符一個字符的寫入，同時也需要寫入字符個數，解壓時才知道需要讀取多少個字符作為檔案后綴

		//字符出現頻率哈希表
        unordered_map<unsigned char, unsigned long long>& weight
       	//寫入預置資訊
		//寫入解壓檔案所需檔案名后綴
		int sufSize = suffixName.size();                 //寫入后綴字符個數
		fwrite((char*)&sufSize, sizeof(sufSize), 1, ofs);//寫入后綴字符個數
		for (auto& c : suffixName)
		{
			fwrite(&c, sizeof(c), 1, ofs);
		
        //儲存構建哈夫曼樹所需內容大小
		int weightSize = weight.size();
		fwrite((char*)&weightSize, sizeof(weightSize),1,ofs);
		//儲存構建哈夫曼樹所需，字符出現權值的哈希表
		for (auto &c:weight)
		{
			fwrite((char*)&c, sizeof(c),1,ofs);
		}
        //預置資訊寫入完成

7.再次讀取原檔案，根據每個字符轉換到對應哈夫曼編碼輸出到新壓縮檔案中，

需要前置知識：

檔案寫入操作：

位運算：

涉及問題：

哈夫曼編碼儲存問題：由于檔案操作最小單位長度是一個位元組，也就是8個二進制位，然而哈夫曼編碼長度不確定最短：1位二進制，最長位：128位二進制，我們不能8個二進制只儲存一個字符對應的哈夫曼編碼，這樣等于沒有壓縮，所以我們需要將不同長度哈夫曼編碼合并，

比如：a,b,c所對應哈夫曼編碼分別為：010，011，01，由于最檔案操作以8個二進制位為單位，所以我們需要將a,b,c對應哈夫曼編碼寫入一個字符中，合并成01001101，并將其賦值給一個字符，在將該字符以二進制形式寫入檔案中，

寫入速度問題：使用如何寫入檔案檔案會更快，

完成壓縮程序

解壓程序

1.讀取檔案后綴并創建新檔案，新檔案名稱可根據用戶輸入創建，

2.讀取還原哈夫曼樹所需資訊，既字符出現頻率表，

首先讀取頻率表中資料個數，使用int型別儲存該數值，根據該數值確定回圈次數逐個讀取出字符及其對應頻率的資料，并將資料放入哈希表中，

3.根據字符出現頻率表重新還原哈夫曼樹

4.開始讀取壓縮檔案中哈夫曼編碼資料，將哈夫曼編碼對應字符以二進制形式寫入解壓檔案中，

使用位運算讀取二進制位，并且按0，1走哈夫曼樹，0表示哈夫曼樹左兒子，1表示哈夫曼樹右兒子，

到達樹的葉子結點時，輸出該字符到新檔案中，

5.讀完壓縮檔案，解壓完成，

二、確定大類和內部函式設計，及具體函式內部實作及步驟解釋

1.大類設計：

這里設計四個類，分別在四個頭檔案中，

第一個大類：HuaffmanTree 在 “HuaffmanTree.h” 頭檔案中定義

#pragma once
#include<fstream>
#include<unordered_map>
#include<queue>
#include<map>
#include<vector>
using namespace std;

哈夫曼樹結點定義
struct TreeNode{};

優先佇列自定義排序比較仿函式
struct cmp{};

哈夫曼樹類
class HuaffmanTree
{
public:
    哈夫曼樹根結點
	TreeNode* root;

    哈夫曼樹建構式傳入，字符對應出現頻率哈希表，呼叫創建哈夫曼函式核心函式，由此建立哈夫曼樹，
    HuaffmanTree(unordered_map<unsigned char, unsigned long long> weight){}
    
    哈夫曼樹解構式呼叫ClearTree函式遞回回收釋放記憶體
	~HuaffmanTree() { ClearTree(root);}

private:
    創建哈夫曼樹核心函式，建構式會呼叫該函式傳入需要引數，回傳創建好的哈夫曼樹根結點
	TreeNode* CreateTree(unordered_map<unsigned char, unsigned long long>& weight){}
    
    回收并釋放哈夫曼樹分配的記憶體空間，解構式會呼叫此函式
    void ClearTree(TreeNode* root){}

由該函式將字符出現頻率哈希表，轉換為優先佇列，用于創建哈夫曼樹
void WeightSort(priority_queue<pair<unsigned long long, TreeNode*>, vector<pair<unsigned long long, TreeNode*>>, cmp> &qNode, unordered_map<unsigned char, unsigned long long>& weight){}

樹結點的定義：

struct TreeNode {
    當該結點作為葉子結點時，此處儲存對應源檔案中8個二進制位所表示的字符
	unsigned char val = 0;

    表示該結點以及其子結點權值總和
	unsigned long long weight = 0;

    左兒子
	TreeNode* left;

    右兒子
	TreeNode* right;

    樹結點多個建構式多載，方便以各種方式創建結點
    默認建構式
	TreeNode() : val(0), left(nullptr), right(nullptr) {}

    傳入字符建構式
	TreeNode(unsigned char x) : val(x), left(nullptr), right(nullptr) {}

    傳入權值建構式
	TreeNode(unsigned long long y) :  weight(y),left(nullptr), right(nullptr) {}

    傳入權值和字符建構式
	TreeNode(unsigned long long y, unsigned char x) : val(x), weight(y), left(nullptr), right(nullptr) {}

    傳入字符，左右兒子建構式
	TreeNode(unsigned char x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}

    傳入權值，左右兒子建構式
	TreeNode(unsigned long long y, TreeNode* left, TreeNode* right) : weight(y), left(left), right(right) {}

    傳入權值，字符，左右兒子建構式
	TreeNode(unsigned long long y, unsigned char x, TreeNode* left, TreeNode* right) : val(x), weight(y), left(left), right(right) {}

};

優先佇列自定義排序方法函式：

struct cmp
{
    多載（）運算子，將該類作為仿函式使用
	bool operator()(pair<unsigned long long, TreeNode*>& r, pair<unsigned long long, TreeNode*>& s) {
        建立哈夫曼樹時有可能多個結點權值相等，此時回傳字符比較結果
		if (r.first == s.first)
		{
			return r.second->val > s.second->val;
		}
        當權值不同時回傳權值比較結果
		return r.first > s.first;
	}
};

哈夫曼樹建構式：

    需要傳入以字符為鍵，字符出現頻率為值的哈希表
    HuaffmanTree(unordered_map<unsigned char, unsigned long long> weight)
	{
        呼叫創建樹的核心函式，并將回傳的結點作為樹的根結點
		root = CreateTree(weight);
	}

創建哈夫曼樹核心函式：

	TreeNode* CreateTree(unordered_map<unsigned char, unsigned long long>& weight)
	{
        創建空優先佇列
		priority_queue<pair<unsigned long long, TreeNode*>,vector<pair<unsigned long long, TreeNode*>>,cmp> qNode;

        呼叫權值讀取函式，將字符與頻率哈希表中資料一個個讀入，空優先佇列中（字符出現頻率既為結點權值）
		WeightSort(qNode, weight);//創建初始優先佇列

        哈夫曼樹順序構造法，不斷從優先佇列中取出最小權值的兩個結點，構造一棵新的樹，該樹根結點
權值為其左右兒子結點權值之和，而其根結點字符資料等于左兒子字符資料（方便優先佇列排序）

		while (qNode.size()>1)//當優先佇列中資料個數大于一時進行
		{
            取出最小權值結點鍵值對，賦值給p
			pair<unsigned long long, TreeNode*> p = qNode.top();

            洗掉最小權值結點
			qNode.pop();

            取出第二小權值結點鍵值對，賦值給q
			pair<unsigned long long, TreeNode*> q = qNode.top();

            洗掉第二小權值結點
			qNode.pop();

            創建新結點，并將p,q作為其左右兒子，其權值大小等于p,q權值之和，其字符等于p字符
			TreeNode* node = new TreeNode((p.first + q.first), p.second->val, p.second,q.second);

            將新樹根結點與其權值對應，創建鍵值對pair
			pair<unsigned long long, TreeNode*> s(p.first + q.first, node);

            將創建好的新樹根結點放入優先佇列中備選
			qNode.push(s);
		}

        最終哈夫曼樹創建完成回傳哈夫曼樹根結點
		return qNode.top().second;
	}

注意：當優先佇列中資料權值相等時出隊順序會變成隨機，也就是說一棵哈夫曼樹中，有兩個結點若不是葉子結點，那么其字符資料為空，當其權值相等時，優先佇列無法比較兩個結點先后順序，就照成其出隊順序隨機，那么壓縮時創建的哈夫曼樹，和解壓時的哈夫曼樹構造可能就會不同，就照成解壓時哈夫曼編碼對應字符與壓縮時不一致，最終解壓錯誤變成一堆亂碼，所以為了解決該問題，我們需要將不是葉子結點的樹結點的字符值設定為其左兒子的字符值，這樣優先佇列才能比較出確定的順序，（也是我寫該程式中遇到的bug之一）

字符頻率哈希表向優先佇列轉換函式：

	傳入權值表，填入優先佇列
void WeightSort(priority_queue<pair<unsigned long long, TreeNode*>, 
    vector<pair<unsigned long long, TreeNode*>>, cmp> &qNode, unordered_map<unsigned 
    char, unsigned long long>& weight) 
	{
       回圈遍歷哈希表，逐個將字符頻率鍵值對創建成一個樹結點，并將該結點與字符出現頻率對應成新的鍵值對，放入優先佇列中
		for (auto&c:weight)
		{
			TreeNode* p = new TreeNode(c.second,c.first);
			qNode.push(make_pair(c.second, p));
		}
	};

哈夫曼樹清空函式：用于回收哈夫曼樹空間，哈夫曼樹解構式呼叫

遞回后序遍歷樹，從葉子結點開始回收空間
    void ClearTree(TreeNode* root)
	{
		if (!root)
		{
			return;
		}
		ClearTree(root->left);
		ClearTree(root->right);
		delete(root);
	}

第二大類：PackPress定義在PackPress.h頭檔案中，用于壓縮檔案

#pragma once
#include"HuaffmanTree.h"
using namespace::std;

用于記錄字符對應哈夫曼編碼路徑，如a的哈夫曼編碼為0101
struct path{};

class PackPress
{
public:
    建構式，會呼叫StartPress函式完成壓縮
	PackPress(string &p,string &e, string &s)//傳入需要壓縮的檔案名及路徑{};
    
    解構式，會回收指向哈夫曼樹的指標所指向的空間，
這時會呼叫哈夫曼樹類的解構式，該解構式會呼叫清空哈夫曼樹的函式，最終完成回收空間，
	~PackPress() { if(huaffTree)delete (huaffTree); };

   介面函式，壓縮綜合區，呼叫各個函陣列合完成壓縮
	int StartPress(){}
private:
    用于記錄需要壓縮檔案的名稱以及路徑
	string pressFileName;

    用于記錄壓縮后檔案名稱
	string emitFileName;

    用于記錄原檔案后綴名，寫入壓縮檔案，方便解壓時讀取
	string suffixName;

    一個指向哈夫曼樹類的指標
	HuaffmanTree* huaffTree;//哈夫曼樹

用于讀取原檔案，創建字符對頻率哈希表，并呼叫創建哈夫曼樹函式，創建哈夫曼樹
bool ReadFiles(unordered_map<unsigned char, unsigned long long> &weight){}

用于創建壓縮檔案，并根據原檔案將原檔案中字符所對應哈夫曼編碼寫入壓縮檔案中，并寫入前置資訊
bool WriteFiles(unordered_map<unsigned char, unsigned long long>& weight){}

用于呼叫哈夫曼樹建構式，傳入字符頻率表，創建哈夫曼樹，并將哈夫曼樹指標指向創建的哈夫曼樹
TreeNode* CreateTree(unordered_map<unsigned char, unsigned long long>& weight){}

遞回遍歷哈夫曼樹，記錄每個葉子結點字符所對應哈夫曼路徑，也就是哈夫曼編碼，創建哈希表，寫入壓縮時使用
void TransLookTree(unordered_map<unsigned char, pair<int, path>> &map,TreeNode* root,int n,path x){}

哈夫曼路徑儲存結構：

struct path
{
	unsigned long long x = 0;
	unsigned long long y = 0;
};

注意：這里選擇，自定義一個結構體，結構體內部使用兩個8位元組大小的資料型別來儲存哈夫曼編碼，

原因一：一個字符的哈夫曼編碼最長為二進制255位，既32個位元組大小，但是這種可能性較小，小于1G的檔案基本上不會到這樣長的編碼，而大于1G的檔案使用該程式壓縮將會非常慢，考慮到寫入壓縮檔案演算法不能太復雜（太復雜寫不出來），所以最多記錄16個位元組大小的哈夫曼編碼，需要使用兩個8位元組大小資料儲存哈夫曼編碼

原因二：若動態陣列儲存，在寫入壓縮檔案時，我們只能對哈夫曼編碼一位一位的讀取和操作，這樣會大大增加時間復雜度，所以我們使用兩個8位元組大小資料型別，使用位運算操作，批量處理二進制位，既批量處理哈夫曼編碼，加快寫入速度

壓縮建構式：

	PackPress(string &p,string &e, string &s)傳入需要壓縮的檔案名及路徑
	{
		huaffTree = __nullptr;
		pressFileName = p;
		emitFileName = e;
		suffixName = s;
		StartPress();呼叫綜合服務區
	};

壓縮解構式：

~PackPress() { if(huaffTree)delete (huaffTree); };

壓縮綜合函式：

用戶介面函式，壓縮綜合區
int StartPress()
	{
        儲存所有字符出現頻率
		unordered_map<unsigned char,unsigned long long> weight;
		
        讀取資料，哈夫曼樹創建成功
        if(ReadFiles(weight)==0)return 0;
 		
        寫資料，完成壓縮
        if(WriteFiles(weight)==0)return -1;
        return 1;
	}

原檔案讀取函式：

bool ReadFiles(unordered_map<unsigned char, unsigned long long> &weight)//讀取檔案，以二進制讀取，并創建權值表,創建哈夫曼樹，
	{
        打開需要壓縮的檔案
		FILE* ifs;
		fopen_s(&ifs,pressFileName.c_str(),"rb");
		if (ifs == nullptr) return 0;
        
        開一個10240位元組大小的陣列用于當讀取快取區，避免一個字符一個字符讀取，加快讀取速度
		unsigned char it[10240] = { 0 };
		while (!feof(ifs))
		{
            用k記錄到底讀取到了幾個位元組的資料
			int k=fread(it,1,sizeof(it),ifs);
			int i = 0;
            僅遍歷實際讀取到的資料
			while (i<k)
			{
                讀取到字符后使其出現頻率加一
				weight[it[i++]]++;
			}
		}
        關閉檔案
		fclose(ifs);
 
        檔案讀取完成后呼叫創建哈夫曼樹函式，創建哈夫曼樹
		CreateTree(weight);//創建哈夫曼樹
		return 1;
	}

創建哈夫曼樹函式：

     傳入字符頻率哈希表
    TreeNode* CreateTree(unordered_map<unsigned char, unsigned long long>& weight)
	{
       呼叫哈夫曼樹類建構式，傳入字符頻率哈希表，創建哈夫曼樹，并將指標指向該樹
		huaffTree = new HuaffmanTree(weight);
        
        回傳創建好的哈夫曼樹的根結點
		return huaffTree->root;
	}

遍歷哈夫曼樹函式：

//傳入空哈希表，遍歷哈夫曼樹，填哈希表
void TransLookTree(unordered_map<unsigned char, pair<int, path>> &map,TreeNode* root,int n,path x)
	{
        遞回遍歷哈夫曼樹，到葉子結點后，將字符對應哈夫曼編碼放到哈希表中
		if (!root->right&&!root->left)
		{
			map.insert(make_pair(root->val,make_pair(n,x)));
			return;
		}
		TransLookTree(map, root->left,n+1,x);
		if (n < 64)  x.x |= ((unsigned long long)1 << (63 - n));
		else  x.y |= ((unsigned long long)1 << (127 - n));
		TransLookTree(map, root->right,n+1,x);
		return;
	}

注意：

一、此處哈希表的鍵是字符，而值是我們自定義的結構體path與哈夫曼編碼長度n形成的pair型別，用n作為pair的鍵，記錄哈夫曼實際編碼長，這樣我們在寫入時，才能知道自定義結構體中16個位元組，128個二進制位中到底有多少位是哈夫曼編碼有實際意義，方便寫入哈夫曼編碼時使用，

這里不選擇陣列記錄哈夫曼編碼的原因，在哈夫曼編碼路徑儲存自定義結構體struct path,那里有說明，此處不再贅述，

二、關鍵陳述句

if (n < 64) x.x |= ((unsigned long long)1 << (63 - n));
else x.y |= ((unsigned long long)1 << (127 - n));

用于結構體中x，y用于實際記錄哈夫曼編碼，當哈夫曼編碼大于64位，時使用y記錄，所以一段較長哈夫曼編碼可能儲存在結構體x和y中，所以在寫入哈夫曼編碼時要考慮到這一點，

壓縮檔案寫入函式（核心）：

bool WriteFiles(unordered_map<unsigned char, unsigned long long>& weight)
	{
		創建哈夫曼編碼的哈希表，哈夫曼編碼表（空）
		unordered_map<unsigned char,pair<int,path>> map;  
       
        哈夫曼路徑儲存處
		path x;
        
        遍歷哈夫曼樹并創建哈夫曼編碼表
		TransLookTree(map, huaffTree->root,0,x);     
		
        打開原檔案，創建新壓縮檔案并打開
		FILE* ifs;
		FILE* ofs;
		fopen_s(&ifs, pressFileName.c_str(), "rb");
		fopen_s(&ofs, emitFileName.c_str(), "wb+");
		if (ifs == nullptr)return 0;
		if (ofs == nullptr)return 0;
		
        寫入預置資訊
		寫入解壓檔案所需檔案名后綴
		int sufSize = suffixName.size();
		fwrite((char*)&sufSize, sizeof(sufSize), 1, ofs);
		for (auto& c : suffixName)
		{
			fwrite(&c, sizeof(c), 1, ofs);
		}
		
        儲存構建哈夫曼樹所需內容大小
		int weightSize = weight.size();
		fwrite((char*)&weightSize, sizeof(weightSize),1,ofs);
		
        儲存構建哈夫曼樹所需，字符出現權值的哈希表
		預置資訊寫入完成
		for (auto &c:weight)
		{
			fwrite((char*)&c, sizeof(c),1,ofs);
		}
		

        轉換所有原檔案位元組資訊為哈夫曼編碼，并儲存入壓縮檔案中
		以64二進制位位單位寫入
        以下為合并每個位元組的哈夫曼編碼到64位二進制資料型別n中，并寫入，
		int eight = 64;
		unsigned long long n=0;
		unsigned char s[10240] = { 0 };
		while (!feof(ifs))
		{
			int k=fread(s, 1,sizeof(s),ifs);
			int i = 0;
			while (i < k)
			{
				path x = map[s[i]].second;
				int k = map[s[i]].first;
				if (k <= 64)
				{
					if (eight > k) {
						n |= (x.x >> (64 - eight)); eight -= k;
					}
					else if (eight == k) {
						n |= (x.x >> (64 - eight));
						fwrite((char*)&n, sizeof(n), 1, ofs);
						n = 0;
						eight = 64;
					}
					else
					{
						n |= (x.x >> (64 - eight));
						fwrite((char*)&n, sizeof(n), 1, ofs);
						n = 0;
						n |= (x.x << eight);
						eight = 64 - (k - eight);
					}
				}
				else
				{
					int t = eight;
					n |= (x.x >> (64 - eight));
					fwrite((char*)&n, sizeof(n), 1, ofs);
					n = 0;
					eight = 64;
					n |= (x.x << t);
					eight -= t;
					if (eight > k - 64)
					{
						n |= (x.y >> (64 - eight));
						eight -= k;
					}
					else if (eight == k - 64) { n |= (x.y >> (64 - eight)); 
                    fwrite((char*)&n, sizeof(n), 1, ofs); n = 0; eight = 64; }
					else
					{
						n |= (x.y >> (64 - eight));
						fwrite((char*)&n, sizeof(n), 1, ofs);
						n = 0;
						n |= (x.y << eight);
						eight = 64 - ((k - 64) - eight);
					}
				}
				i++;
			}	
		}
        該句用來處理到，最后哈夫曼編碼長度不夠64位時，直接寫入，可能會導致一些多余資訊
        不過不影響原檔案
		if(eight!=0) fwrite((char*)&n, sizeof(n), 1, ofs);

        哈夫曼編碼寫入完畢

		關閉檔案
		fclose(ifs);
		fclose(ofs);
		return 1;
	}

注意：此處合并，并且寫入哈夫曼編碼演算法比較復雜，篇幅有限不方便敘述，

第三大類：PackRelease定義在PackRelease.h頭檔案中用于解壓縮，

#pragma once
#include "HuaffmanTree.h"
using namespace::std;

解壓縮類
class PackRelease
{
public:
    解壓縮建構式，會呼叫StartRelease函式進行解壓操作
	PackRelease(string p, string r) {}；
	~PackRelease() { delete(huaffTree); };
    
    解壓縮綜合函式會組合呼叫私有函式成員，完成解壓操作，
	int StartRelease(){}

private:
    指標指向還原后的哈夫曼樹
	HuaffmanTree* huaffTree;
    壓縮文名，包括檔案路徑
	string pressFileName;
    解壓縮后的檔案名，包括檔案保存路徑
	string releaseFileName;

    開始解壓縮，創建解壓檔案，根據壓縮檔案資訊，與還原的哈夫曼樹，完成解壓
	bool ReleaseFiles(FILE* frp){}

    用于還原哈夫曼樹，會一個個讀取壓縮檔案中儲存的字符頻率鍵值對，并放入哈希表中，
    呼叫哈夫曼樹類的建構式還原壓縮時的哈夫曼樹
	HuaffmanTree* ReCreateTree(FILE* fp){}

    用于獲取前置資訊，既解壓后檔案型別，既檔案名稱后，如.mp3格式
	void GetSuffixName(FILE* fp){}
}

建構式：

	PackRelease(string p, string r) 
	{
        記錄壓縮檔案路徑及名稱方便其他函式使用
		pressFileName = p;

        記錄解壓文保存路徑及名稱方便其他函式使用
		releaseFileName = r;

        呼叫解壓綜合函式，完成解壓
		StartRelease();
	};

解構式：

	~PackRelease() { delete(huaffTree); };

解壓綜合函式：

	int StartRelease()
	{
        打開壓縮檔案
		FILE* fp;
		fopen_s(&fp, pressFileName.c_str(), "rb");
		if (fp == nullptr)return 0;

		獲取解壓檔案型別，及檔案后綴讀入，如.mp3,并將其寫入成員資料releaseFileName中
		GetSuffixName(fp);
		后綴寫入完成
      
        呼叫哈夫曼樹還原函式，重新還原壓縮時建立的哈夫曼樹，
        并使成員資料huaffTree指向還原的哈夫曼樹
		huaffTree = ReCreateTree(fp);

        呼叫解壓函式，最終完成解壓
		ReleaseFiles(fp);

        關閉壓縮檔案
		if(fp)fclose(fp);
		return 1;
	}

解壓檔案寫入函式：

	bool ReleaseFiles(FILE* frp)
	{
        創建解壓檔案
		FILE* fwp;
        以二進制，寫入，若沒有該檔案追加創建的形式打開
		fopen_s(&fwp, releaseFileName.c_str(), "wb");
		if (fwp == nullptr)return 0;

        用于儲存讀取壓縮檔案得到的二進制資料
		unsigned long long s;
		TreeNode* it = huaffTree->root;
		while (!feof(frp))
		{	
            對壓縮檔案按每8個位元組既64個二進制位進行讀取，存入s中
			fread((char*)&s, sizeof(s),1, frp);
            
            用于判斷s中儲存的資訊是否使用完畢
			int eight = 64;

            回圈走哈夫曼樹到達葉子結點時，將得到的字符寫入解壓檔案中
			while (eight > 0)
			{
				int x = (s >> (eight - 1)) & 1;
				if (x == 0)it = it->left;
				if (x == 1)it = it->right;
				if (!it->left && !it->right)
				{
					fwrite(&it->val, sizeof(it->val), 1, fwp);
					it = huaffTree->root;
				}
				eight--;
			}
		}
        完成解壓縮操作
   
        關閉解壓檔案
		if (fwp)fclose(fwp);
		return 1;
	}

還原哈夫曼樹函式：


	HuaffmanTree* ReCreateTree(FILE* fp)
	{
		讀一個int型別，表示字符頻率鍵值對資料的數目
		unordered_map<unsigned char, unsigned long long> weight;
		int mapSize = 0;
		if (fp == nullptr) return nullptr;
		fread(&mapSize, sizeof(mapSize), 1, fp);

        創建臨時儲存空間，讀取到的鍵值對都會賦值給data
		pair<unsigned char, unsigned long long> data;

        回圈讀入鍵值對并將其放入哈希表中，直到讀取全部鍵值對完畢
		while (mapSize>0)
		{
			fread(&data, sizeof(data), 1, fp);
			weight.insert(data);
			mapSize--;
		}
       
        根據創建的哈希表，呼叫哈夫曼樹類的建構式，還原哈夫曼樹
		HuaffmanTree* huaffTree = new HuaffmanTree(weight);
		return huaffTree;
	}

獲得解壓檔案名稱后綴函式：

	void GetSuffixName(FILE* fp)
	{
        讀取后綴字符個數
		int sufSize=0;
		fread(&sufSize, sizeof(sufSize), 1, fp);

        字符儲存臨時空間
		char s;
     
        回圈讀取后綴字符
		while (sufSize>0)
		{
			fread(&s, 1, 1, fp);
            將讀到的字符加入releaseFileName中用于創建解壓檔案
			releaseFileName += s;
			sufSize--;
		}
	}

第四大類：Press定義在Press.h頭檔案中，用于和用戶互動，同時處理檔案名稱，檔案保存路徑等問題的預處理類，

#pragma once
#include<iostream>
#include"PackPress.h"
#include"PackRelease.h"
using namespace::std;

class Press
{
public:
	Press() {};
	~Press() {};
	void Start(){}
private:
    處理需要壓縮檔案的名稱，分離檔案名，與檔案型別名（既檔案后綴）
	string GetSuffix(string &FileName){}
};

用戶介面函式：

void Start()
	{
        檔案保存路徑名
		string path = "C:\\Users\\hwx\\Desktop\\TheInvisibleGuardian\\";
        
        壓縮檔案后綴
		string tempSuffixName = ".hwx";
       
        需要壓縮檔案完全名稱包括檔案型別
		string FileName;
        
        需要壓縮檔案型別名稱既檔案后綴
		string suffixName;

         需要壓縮檔案名稱不包括檔案型別名
		string PressName;
      
        壓縮檔案名稱
		string tempName;
      
        解壓檔案名稱
		string ReleaseName;
		int p = 0;
		cout << "檔案默認路徑為：" << path << endl;
		cout << "壓縮檔案請按：1   解壓檔案請按：2 修改檔案默認路徑請按：3" << endl;
		cout << "請選擇需要進行的操作：";
		cin >> p;
		if (p == 1)
		{
			cout << "請輸入需要壓縮的檔案名，包含檔案后綴：";
			cin >> FileName;
			suffixName = GetSuffix(FileName);
			PressName = path + FileName + suffixName;
			tempName = path + FileName + tempSuffixName;
			PackPress H(PressName, tempName, suffixName);
		}
		else if (p == 2)
		{
			cout << "請輸入需要解壓的檔案名";
			cin >> FileName;
			tempName = path + FileName + tempSuffixName;
			ReleaseName = path + FileName + "(解壓版）";
			PackRelease D(tempName, ReleaseName);
		}
		else if (p == 3)
		{
			cout << "請輸入新的檔案默認路徑";
			cin >> path;
			cout << "檔案默認路徑為：" << path << endl;
		}
		else
		{
			cout << "無效輸入";
		}
	}

獲得需要壓縮檔案的檔案型別，也就是名稱后綴函式：

string GetSuffix(string &FileName)
	{
		int i = FileName.size() - 1;
		for (; i >= 0; i--)
		{
			if (FileName[i] == '.')
			{
				break;
			}
		}
		string s;
		int j = i;
		for (; i < FileName.size(); i++)
		{
			s.push_back(FileName[i]);
		}
		for (int f=FileName.size()-1; f>=j; f--)
		{
			FileName.pop_back();
		}
		return s;
	}

三、檔案壓縮和解壓程序函式流程及函式呼叫順序

壓縮程序：

——Press建構式

——Start函式

——GetSuffix(FileName)函式

——PackPress建構式

——StartPress()函式

——（ReadFiles(weight)函式-CreateTree(weight)函式）

——（WriteFiles(weight)函式-TransLookTree()函式）

——完成壓縮

解壓縮程序：

——Press建構式

——Start函式

——PackRelease 建構式

——StartRelease()函式

——GetSuffixName(fp)函式

——ReCreateTree(fp)函式

——ReleaseFiles(fp)函式

——完成解壓程序

程式測驗

壓縮檔案格式	mp3	txt	jpg	mp4	使用360壓縮（mp4)
壓縮前檔案大小	57mb	12.1mb	129kb	1.35gb	1.35gb
壓縮后檔案大小	50.9mb	9.3mb	129kb	1.35gb	1.34gb
壓縮時間	1分10秒	16秒	無	28分鐘	1分鐘
解壓時間	9秒	1.989秒	無	4分鐘	5秒

該程式壓縮和解壓縮時間與現有壓縮軟體相比較慢，最主要占用時間部分是讀檔案操作，占用壓縮和解壓縮檔案90%以上的時間.

總結

本文章僅記錄或者分享該程式制作程序，由于個人能力有限，其中若有誤，敬請指正，還望諒解

未經允許請勿轉載，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286389.html

標籤：其他

上一篇：山東專升本計算機網路（二）

下一篇：計算機網路實驗4 - TCP套接字編程 - 點對點聊天 - 代碼實作

基于哈夫曼編碼的C++壓縮程式

前言

一、初步確定壓縮和解壓程序

壓縮程序

1.讀取檔案

2.一個字符一個字符讀取，根據讀取到的字符建立字符出現頻率表

3.建立哈夫曼樹

4.這里使用優先佇列，每次選擇兩個權值最小字符作為結點建立樹，并再次將得到的樹的根結點放入優先佇列中， 最終創建哈夫曼樹

需要前置知識：STL優先佇列使用，及其自定義排序方法

5.遍歷哈夫曼樹，根據葉子結點路徑，建立關于每個字符對應到哈夫曼編碼的映射，并儲存于哈希表中

6、創建壓縮檔案，并寫入前置資訊

7.再次讀取原檔案，根據每個字符轉換到對應哈夫曼編碼輸出到新壓縮檔案中，

完成壓縮程序

解壓程序

1.讀取檔案后綴并創建新檔案，新檔案名稱可根據用戶輸入創建，

2.讀取還原哈夫曼樹所需資訊，既字符出現頻率表，

3.根據字符出現頻率表重新還原哈夫曼樹

4.開始讀取壓縮檔案中哈夫曼編碼資料，將哈夫曼編碼對應字符以二進制形式寫入解壓檔案中，

5.讀完壓縮檔案，解壓完成，

二、確定大類和內部函式設計，及具體函式內部實作及步驟解釋

1.大類設計：

第一個大類：HuaffmanTree 在 “HuaffmanTree.h” 頭檔案中定義

第二大類：PackPress定義在PackPress.h頭檔案中，用于壓縮檔案

壓縮建構式：

壓縮解構式：

壓縮綜合函式：

原檔案讀取函式：

創建哈夫曼樹函式：

遍歷哈夫曼樹函式：

壓縮檔案寫入函式（核心）：

第三大類：PackRelease定義在PackRelease.h頭檔案中用于解壓縮，

第四大類：Press定義在Press.h頭檔案中，用于和用戶互動，同時處理檔案名稱，檔案保存路徑等問題的預處理類，

三、檔案壓縮和解壓程序函式流程及函式呼叫順序

壓縮程序：

——Press建構式

——Start函式

——GetSuffix(FileName)函式

——PackPress建構式

——StartPress()函式

——（ReadFiles(weight)函式-CreateTree(weight)函式）

——（WriteFiles(weight)函式-TransLookTree()函式）

——完成壓縮

解壓縮程序：

——Press建構式

——Start函式

——PackRelease 建構式

——StartRelease()函式

——GetSuffixName(fp)函式

——ReCreateTree(fp)函式

——ReleaseFiles(fp)函式

——完成解壓程序

程式測驗

該程式壓縮和解壓縮時間與現有壓縮軟體相比較慢，最主要占用時間部分是讀檔案操作，占用壓縮和解壓縮檔案90%以上的時間.

總結

4.這里使用優先佇列，每次選擇兩個權值最小字符作為結點建立樹，并再次將得到的樹的根結點放入優先佇列中，最終創建哈夫曼樹