Huffman算法实现文件加密

使用Huffman算法来加密文件

这次的blog只是为了记录一下本人第一次自己编写的算法（源于博主的课设作业）

参考的博客和文章忘了出处，如有相似的，请联系博主

此次程序主要使用C++来编写，其中由于特殊原因混有一些C语言，博主会逐渐逐渐完善代码

程序的功能是在rawletter.txt中读取出现的字符以及其权重（权重可以理解成出现的概率），然后通过使用Huffman算法来形成每个字符对应的Huffman编码，按照原来rawletter.txt文件中的字符一一对应生成由Huffman码构成的新文件codefile.txt，达到加密的效果。

此外程序还将生成key to letter.txt文件来记录每一个字符以及其对应的Huffman码

博主对文件的解密功能还没完全实现，目前只能生成一个translate.txt文件，但无法识别换行符`

#include<iostream>
#include<ostream>
#include<string>
#include<fstream>
using namespace std;

class huffmannode   //节点类
{
	friend void getmin(huffmannode n1[], int *p1, int*p2, int k);
	friend void display(int num, huffmannode n[], string code[]);
	friend void receive(int *num, huffmannode p1[]);
	friend void translate(string code[], int num, huffmannode n[]);

	char str;    //每个节点对应的字符
	int weight, parent, lchild, rchild;   
public:
	huffmannode()
	{
		this->parent = 0;
		this->weight = 0;
		this->rchild = 0;
		this->lchild = 0;
	}

	huffmannode& combine(huffmannode& n1, huffmannode& n2,int index1,int index2,int index)  //把两个节点合成新节点的函数
	{
		this->weight = n1.weight + n2.weight;
		n1.parent = index;
		n2.parent = index;
		this->lchild = index1;
		this->rchild = index2;
		return *this;
	}
};

void getmin(huffmannode n[],int *p1,int*p2,int k)              //得到权值最小的两个节点
{
	int i;
	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0)
		{
			*p1 = i;
		}
	}

	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0 && n[i].weight < n[*p1].weight)
		{
			*p1 = i;
		}
	}

	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0 && i != *p1)
		{
			*p2 = i;
		}
	}

	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0 && n[i].weight < n[*p2].weight&& i !=*p1)
		{
			*p2 = i;
		}
	}
}

void display(int num,huffmannode n[],string code[])    //形成每个字符对应的Huffman码    运用了文件操作
{
	ofstream fout1("key to letter.txt");

	for (int i = 0; i < num; i++)
	{

		for (int j=i, f = n[j].parent; f; j = f, f = n[j].parent)
		{
			if (n[f].lchild == j)
			{
				code[i]+='0';
			}
			else
			{
				code[i]+='1';
			}
		}
		reverse(code[i].begin(), code[i].end());        //把字符串反向
		fout1 << n[i].str << " -> " << code[i] << endl;
		
	}
	fout1.close();
	
	ofstream fout("codefile.txt");
	ifstream fin("rawletter.txt");
	if (!fin.is_open())
	{
		cout << "the rawletter.txt isn't existed" << endl;
		return ;
	}

	char buffer;
	fin >> noskipws;          //使流的输入不会忽略空格和换行符

	while (fin.peek()!=EOF)      //peek返回下一个值的值，若使用ofe的话，会读取多一个字符
	{
		fin >> buffer;
		
		for (int i = 0; i < num; i++)
		{
			if (n[i].str == buffer)
			{
				fout << code[i] << endl;
			}
		}
	}

	fin.close();
	fout.close();
	
	//编码完成 ——》写入文件中
}

//下面两个函数的作用是读取rawletter.txt文件，计算出出现的字符以及对应的权重（因为特殊原因，是博主同学编写的。。。）

void search(char a[], int b[52], char file[1000]);

void receive(int *num, huffmannode p1[]);

void translate(string code[],int num,huffmannode n[])     //解密文件  由Huffman码组成的文件 --》字符文件（翻译文件）
{
	string buffer;
	ofstream fout("translate.txt");
	ifstream fin("codefile.txt");
	if (!fin.is_open())
	{
		cout << "codefile.txt is not found" << endl;
		return;
	}

	while (getline(fin,buffer))
	{
		for (int i = 0; i < num; i++)
		{
			if (code[i] == buffer)
			{
				fout << n[i].str;
			}
		}
	}

	fout.close();
	fin.close();
}

int main()
{
	int i = 0,j;//j:用来迭代
	int num;//num是字符种类的数量
	string code[65];//用来存放每个字符对应的Huffman码
	huffmannode pl[65];

	receive(&num, pl);   

	for (j = 0; j <num-1; j++)
	{
		int p1, p2, k = j + num;
		getmin(pl, &p1, &p2, k);        //得到最小的两个节点
		pl[k].combine(pl[p1], pl[p2], p1, p2, k);     //合成新的节点
	}

	
	display(num, pl,code);
	translate(code, num, pl);
	return 0;
}

void receive(int *num,huffmannode p1[])
{
	char a[67] = { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890.," };
	a[66] = '\n';
	int b[67] = { 0 }, i, L = 0,sum=0;
	int k = 0;//用于迭代
	
	char file[9999];
	
	ifstream fp("rawletter.txt");
	if (!fp.is_open())
	{
		cout << "rawletter.txt isn't existed" << endl;
		return;
	}

	while (!fp.eof())
	{
		fp.getline(file, 9999);
		search(a, b, file);
	}
	fp.close();
	
	for (i = 0; i < 66; i++)
	{
		if (b[i] != 0)
		{
			L++;
		}
		sum += b[i];//得出字符总数量  
	}
	*num = L;//字符种类的数量

	for ( i = 0; i < 66; i++)
	{
		if (b[i] != 0)
		{
			//计算权重 -> 赋予HuffmanTree的节点
			float temp = b[i] / sum;
			p1[k].weight = int(temp);
			p1[k].str = a[i];
			k++;
		}
	}
}

//计算某种字符出现的频率
void search(char a[], int b[], char file[1000])
{
	int i, j;
	for (i = 0; i<66; i++)
	{
		for (j = 0; file[j] != '\0'; j++)
		{
			if (file[j] == a[i])
			{
				b[i] += 1;
			}
		}
	}
}