(C++算法核心实现,MFC制作界面)哈夫曼编码算法制作压缩软件_哈夫曼树源加mfc代码

前言

一个简单的压缩软件，利用哈夫曼思想，构造哈夫曼编码，实现对文件的二进制压缩，以及解压，再利用MFC制作可视化操作界面，美化软件又简化文件操作。（各个步骤有解释可看）

软件主页面先看看

哈夫曼树结构

构造哈夫曼树存储结构：w权重即每个字节出现频度，byte结点数据即每个字节的ASCII码，fa双亲结点下标，le左孩子下标，ri右孩子下标,从下往上开始构建哈夫曼树。
根据已构造完成的哈夫曼树，从上往下开始构造每个结点的哈夫曼编码字符串，从根节点出发，如果下一个节点是其双亲的右孩子结点则在编码后接1，如果是左孩子结点则在编码后接0.存放哈夫曼树信息用到的是Huff_arr数组。

struct HaffNode {
   
	unsigned char byte;//为节点所代表的字符（ASCII码表对应的字符）
	long long w;//此节点代表字符的出现频度
	int num, fa, le, ri, code_len;//分别为节点在Huff_arr数组下标，双亲节点在Huff_arr数组下标，
    左子树下标，右子树下标，对应哈夫曼编码长度
	char code[256];//哈夫曼编码
	bool operator < (HaffNode x) const {
   
		return w > x.w;
	}
}Huff_arr[512]
1
2
3
4
5
6
7
8
9
10
11
12

步骤

①读取文件操作（包括初始化）

1、 读原文件，统计字节频度，定义Huffman树和Huffman编码的储存结构
读取文件，新建一个二进制文件用于存放统计数据，用while语句逐个读取源文件每一个字节，在每次读取的时候分别统计出现次数（权值）w和源文件长度file_length，直至文件结束。
2、 原文件字节频度统计
对字节频度排序，利用sort函数对Huff_arr[0]~ Huff_arr[520]的元素以weight为排序关键字进行降序排序。

void initpow(char *cp_inname) {
   
	unsigned char ch;
	CString str;
	FILE *ifp = fopen(cp_inname, "rb");
	if (ifp == NULL) {
   
		MessageBox(NULL, _T("该文件已存在，请重新输入"), _T("错误"), MB_ICONEXCLAMATION);
		return;
	}
	file_len = 0, bytes_cnt = 0;
	fread(&ch, 1, 1, ifp);
	while (!feof(ifp)) {
   
		Huff_arr[ch].w++, file_len++;
		fread(&ch, 1, 1, ifp);
	}
	fclose(ifp);
	for (int i = 0; i < 256; i++)
		if (Huff_arr[i].w > 0)
			bytes_cnt++;
	sort(Huff_arr, Huff_arr + 511);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

②建树

利用优先队列（priority_queue QUEUE;），每次取队头元素（权值第一小）First节点，出队后再取队头元素S（权值第二小）econd，然后将两棵子树合并为一棵子树，权值相加，并将新子树的根节点顺序存放到数组huff_arr ,再把新子树的根节点放进队列再次循环步骤，直到队列的个数为1为止。

void createhafftree() {
   
	priority_queue<HaffNode> QUEUE;
	HaffNode First, Second, Sum;
	int tot = bytes_cnt;
	while (QUEUE.size())QUEUE.pop();
	for (int i = 0; i < bytes_cnt; i++)
		Huff_arr[i].num = i, QUEUE.push(Huff_arr[i]);
	while (QUEUE.size() > 1) {
   
		First = QUEUE.top(), QUEUE.pop();
		Second = QUEUE.top(), QUEUE.pop();
		Sum.num = tot, Sum.w = First.w + Second.w;
		Sum.fa = -1, Sum.le = First.num, Sum.ri = Second.num;
		strcpy(Sum.code, "");
		Huff_arr[First.num].fa = Sum.num, Huff_arr[Second.num].fa = Sum.num;
		Huff_arr[tot++] = Sum;
		QUEUE.push(Sum);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

③构造哈夫曼编码

根据已构造完成的哈夫曼树，从上往下开始构造每个结点的哈夫曼编码字符串，从根节点出发，如果下一个节点是其双亲的右孩子结点则在编码后接1，如果是左孩子结点则在编码后接0.哈夫曼编码树的左分支代表 0，右分支代表 1，则从根结点到每个叶子结点所经过的路径组成的 0 和 1 的序列便成为该叶子结点对应字符的编码。

void createhaffcode() {
   
	int tot = bytes_cnt * 2 - 1;
	Huff_arr[tot - 1].code[0] = '\0';
	for (int i = tot - 2; i >= 0; i--) {
   
		strcpy(Huff_arr[i].code, Huff_arr[Huff_arr[i].fa].code);
		if (Huff_arr[Huff_arr[i].fa].ri == i)
			strcat(Huff_arr[i].code, "1");
		else
			strcat(Huff_arr[i].code, "0");
		Huff_arr[i].code_len = strlen(Huff_arr[i].code);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

④生成压缩文件

生成压缩码：先找出根节点的位置，然后从根节点一直往下进行编码，根据左孩子置为0，右孩子置为1这个规则一直往下编码，根据编码继承，可以直接在父节点的编码后面置0或1即可。
根据编码写入文件：得到哈夫曼编码后先将缓冲区置为空，然后按照每8位为一个字节，将二进制转为十进制进行写入文件，如果最后缓冲区还有元素，则在后面补8个0，然后再整除8，变为8位元素。

ofp = fopen(cp_outname, "wb");
	if (ofp == NULL)
1