当前位置： 首页 > article >正文

哈夫曼树（构建、编码、译码）（详细分析+C++代码实现）

article 2025/1/23 4:20:52

 D 哈夫曼树

题目要求

编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。
为确保构建的哈夫曼树唯一，本题做如下限定：

  1. 选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
  2. 若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
  3. 生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。

输入格式:

输入为3行。第1行为一个字符串，包含不超过5000个字符，至少包含两个不同的字符，每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串，表示待译码的哈夫曼编码。

输出格式:

输出第一行为用空格间隔的2个整数，分别为压缩前后文本大小，以字节为单位，一个字符占1字节，8个二进制位占1字节，若压缩后文本不足8位，则按1字节算。输出从第二行开始，每行为1个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出INVALID。

输入样例:

cbaxyyzz
0100
011

输出样例:

8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID

题目分析

要点1：原文本字符数据整理

根据输入的字符串，整理字符的种类数，以及各字符的个数，并将其按照出现次数从小到大进行排列，若次数相同，则先出现的仍在前。

//数据预处理
//计算输入的文本出现的所有不同的字符和对应数量
const int N = 5010;
int h[N], idx,w[N];  //w数组存储字符在文本中出现的个数，idx最终保存不同的字符种类数，h数组存储对应字符的下标
char da[N];  //da数组存储字符
int PreLengh;  //初始文本的长度
string line;  //初始文本
void input() {
	cin >> line;
	PreLengh = line.size();
	for (char ch : line) {  //遍历文本中的每一个字符
		if (w[h[ch]] == 0) {  //字符的权重为0，该字符第一次出现
			da[++idx] = ch;
			h[ch] = idx;
			w[idx] = 1;
		}
		else {
			w[h[ch]]++;  //否则，不是第一次出现，权重+1
		}
	}
	//数据录入结束，进行排序
	//冒泡排序，从小到大排列，权重相同的原来在前仍在前
	for (int i = 1; i <= idx; i++) {
		for (int j = 1; j <= idx - 1; j++) {
			if (w[j] > w[j + 1]) {
				swap(w[j], w[j + 1]);
				swap(da[j], da[j + 1]);  //权重和数据都要交换
			}
		}
	}
}

要点2：构建huffman树

1.在森林中取权值最小的两个根结点s和nl，合并成一棵二叉树，并生成一个新结点T作为这两个结点的父亲，T的权值是它的两个子结点的权值之和。

2.对新森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。 

//创建哈夫曼树
HuffmanTree* createHuffmanTree(char data[],int weight[],int n) {
	HuffmanTree* tree=new HuffmanTree;
	tree->m = n;  //结点总数
	tree->H = new HuffmanNode * [tree->m + 1];
	HuffmanNode* p1, * p2, * p, * t;
	//初始化结点
	for (int i = 1; i <= tree->m; i++) {
		tree->H[i] = new HuffmanNode;
		tree->H[i]->INFO = data[i];
		tree->H[i]->Weight = weight[i];
		tree->H[i]->LLINK = NULL;
		tree->H[i]->RLINK = NULL;
	}
	//组合结点
	int i, j;
	for (int i = 1; i < tree->m; i++) {  //遍历所有结点
		t = new HuffmanNode;
		p1 = tree->H[i];  //选取最小的两个结点作为左右子树
		p2 = tree->H[i + 1];
		t->LLINK = p1;
		t->RLINK = p2;
		t->Weight = p1->Weight + p2->Weight;
		p = t;
		j = i + 2;
		//比较排列，仍要保证从小到大排列
		while (j <= tree->m && (p->Weight) >= tree->H[j]->Weight) {
			tree->H[j - 1] = tree->H[j];
			j++;
		}
		//将新生成的树放入森林中
		tree->H[j - 1] = p;
	}
	return tree;
}

要点3：Huffman编码

要输出所有字符的编码，遍历思想，走左子树则+0，走右子树则+1，直至走到叶结点，为字符，存储为对应字符的Huffman编码。

//Huffman编码
//char标志字符，与其对应的Huffman编码
typedef unordered_map<char, string> UMCS;
UMCS HuffmanCode;
void CreateHuffmanCode(HuffmanNode* root, string code) {
	if (root == NULL) return;
	if (!root->LLINK && !root->RLINK) {  //如果是叶结点，遍历到字符
		HuffmanCode[root->INFO] = code; 
	}
	CreateHuffmanCode(root->LLINK, code + "0");  //左子树+0
	CreateHuffmanCode(root->RLINK, code + "1");  //右子树+1
}

 要点4：对二进制进行译码

读入一整串的二进制数，遇到0就走左子树，遇到1就走右子树，直至走到叶结点，为字符，一个字符到此译码成功，将该字符串到总答案中。若此时还有编码剩余，则重新从树根开始，继续译码，直至读入全部二进制编码。

若全部二进制读入完毕，但此时指针不位于叶结点，证明译码失败，没有正确结束。输出"INVALID"。

//对二进制进行译码
void TransHuffmanCode(HuffmanNode* root) {
	HuffmanNode* t = root;
	for (int num = 2; num > 0; num--) {
		string op,ans="";
		cin >> op;  //读入整串的二进制编码
		for (int i = 0; i < op.size(); i++) {
			char k = op[i];
			if (k == '0') t = t->LLINK;  //如果是0，就走左指针
			if (k == '1') t = t->RLINK;  //如果是1，就走右指针
			if (!t->LLINK && !t->RLINK) {  //走到叶结点，译码成功，串入答案ans
				ans = ans + t->INFO;
				if (i != op.size() - 1) t = root;  //若还有编码未译完，重新返回树根，继续译码
			}
		}
		if (!(!t->LLINK && !t->RLINK)) cout<<"INVALID";  //如果译码到最后，没有走到叶结点，证明译码失败
		else cout << ans;
		cout << endl;
		t = root;
	}
}

完整代码

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;

//Huffman结点
typedef struct HuffmanNode {
	char INFO;  //信息域
	int Weight;  //权值
	HuffmanNode* LLINK;  //左链接
	HuffmanNode* RLINK;  //右链接
}HuffmanNode;

//Huffman树的构建
typedef struct HuffmanTree {
	HuffmanNode** H;  //存储哈夫曼树结点的数组H
	int m;  //哈夫曼树结点总数
}HuffmanTree;

//数据预处理
//计算输入的文本出现的所有不同的字符和对应数量
const int N = 5010;
int h[N], idx,w[N];  //w数组存储字符在文本中出现的个数，idx最终保存不同的字符种类数，h数组存储对应字符的下标
char da[N];  //da数组存储字符
int PreLengh;  //初始文本的长度
string line;  //初始文本
void input() {
	cin >> line;
	PreLengh = line.size();
	for (char ch : line) {  //遍历文本中的每一个字符
		if (w[h[ch]] == 0) {  //字符的权重为0，该字符第一次出现
			da[++idx] = ch;
			h[ch] = idx;
			w[idx] = 1;
		}
		else {
			w[h[ch]]++;  //否则，不是第一次出现，权重+1
		}
	}
	//数据录入结束，进行排序
	//冒泡排序，从小到大排列，权重相同的原来在前仍在前
	for (int i = 1; i <= idx; i++) {
		for (int j = 1; j <= idx - 1; j++) {
			if (w[j] > w[j + 1]) {
				swap(w[j], w[j + 1]);
				swap(da[j], da[j + 1]);  //权重和数据都要交换
			}
		}
	}
}

//创建哈夫曼树
HuffmanTree* createHuffmanTree(char data[],int weight[],int n) {
	HuffmanTree* tree=new HuffmanTree;
	tree->m = n;  //结点总数
	tree->H = new HuffmanNode * [tree->m + 1];
	HuffmanNode* p1, * p2, * p, * t;
	//初始化结点
	for (int i = 1; i <= tree->m; i++) {
		tree->H[i] = new HuffmanNode;
		tree->H[i]->INFO = data[i];
		tree->H[i]->Weight = weight[i];
		tree->H[i]->LLINK = NULL;
		tree->H[i]->RLINK = NULL;
	}
	//组合结点
	int i, j;
	for (int i = 1; i < tree->m; i++) {  //遍历所有结点
		t = new HuffmanNode;
		p1 = tree->H[i];  //选取最小的两个结点作为左右子树
		p2 = tree->H[i + 1];
		t->LLINK = p1;
		t->RLINK = p2;
		t->Weight = p1->Weight + p2->Weight;
		p = t;
		j = i + 2;
		//比较排列，仍要保证从小到大排列
		while (j <= tree->m && (p->Weight) >= tree->H[j]->Weight) {
			tree->H[j - 1] = tree->H[j];
			j++;
		}
		//将新生成的树放入森林中
		tree->H[j - 1] = p;
	}
	return tree;
}

//Huffman编码
//char标志字符，与其对应的Huffman编码
typedef unordered_map<char, string> UMCS;
UMCS HuffmanCode;
void CreateHuffmanCode(HuffmanNode* root, string code) {
	if (root == NULL) return;
	if (!root->LLINK && !root->RLINK) {  //如果是叶结点，遍历到字符
		HuffmanCode[root->INFO] = code; 
	}
	CreateHuffmanCode(root->LLINK, code + "0");  //左子树+0
	CreateHuffmanCode(root->RLINK, code + "1");  //右子树+1
}

//计算压缩后文本的大小
int PostLength = 0;
void PostNum(UMCS HuffmanCode) {
	for (char k : line) {  //从头到位按照原文本的逐一计算
		PostLength += HuffmanCode[k].size();
	}
	PostLength = (PostLength + 7) / 8;  //以字节为单位计算，不足8位，按一字节算
}

//打印输出huffman编码
void printHuffmanCode() {
	for (int i = 1; i <= idx; i++) {  //da数组内存储的即为数据字符
		cout << da[i] << ":" << HuffmanCode[da[i]] << endl;
	}
}

//对二进制进行译码
void TransHuffmanCode(HuffmanNode* root) {
	HuffmanNode* t = root;
	for (int num = 2; num > 0; num--) {
		string op,ans="";
		cin >> op;  //读入整串的二进制编码
		for (int i = 0; i < op.size(); i++) {
			char k = op[i];
			if (k == '0') t = t->LLINK;  //如果是0，就走左指针
			if (k == '1') t = t->RLINK;  //如果是1，就走右指针
			if (!t->LLINK && !t->RLINK) {  //走到叶结点，译码成功，串入答案ans
				ans = ans + t->INFO;
				if (i != op.size() - 1) t = root;  //若还有编码未译完，重新返回树根，继续译码
			}
		}
		if (!(!t->LLINK && !t->RLINK)) cout<<"INVALID";  //如果译码到最后，没有走到叶结点，证明译码失败
		else cout << ans;
		cout << endl;
		t = root;
	}
}
int main() {
	//数据预处理
	input();
	//创建Huffman树
	HuffmanTree* tree = createHuffmanTree(da, w, idx);
	//构造Huffman编码
	CreateHuffmanCode(tree->H[idx], "");
	//计算编码后文本大小
	PostNum(HuffmanCode);
	//输出压缩前后文本大小
	cout << PreLengh << ' ' << PostLength << endl;
	//输出各字符的Huffman编码
	printHuffmanCode();
	//对输入的Huffman二进制编码进行译码
	TransHuffmanCode(tree->H[idx]);
	return 0;
}

 提交结果


http://www.kler.cn/a/514408.html

相关文章：

  • 本地 AI 模型“不实用”？
  • 什么是HTTP3？
  • Linux shell 批量验证端口连通性
  • Chrome远程桌面无法连接怎么解决？
  • 《Effective Java》学习笔记——第1部分 创建对象和销毁对象的最佳实践
  • 【Java面试】RabbitMQ
  • 纯前端实现表格中的数据导出功能-使用xlsx和file-saver
  • 【大数据】机器学习----------计算机学习理论
  • OpenHarmony OTA升级参考资料记录
  • 路由重分布
  • Hack The Box-Starting Point系列Vaccine
  • 【机器学习实战中阶】使用SARIMAX，ARIMA预测比特币价格，时间序列预测
  • LINUX下设置分离状态（Detached State）和未设置分离状态的主要区别在于线程资源的管理方式和线程的生命周期。以下是两种状态的对比：
  • 1.21学习
  • Ceisum无人机巡检直播视频投射
  • SpringCloud学习笔记【尚硅谷2024版】
  • 2025年1月19日（舵机VCC）
  • vue3切换路由后页面不报错显示空白，刷新后显示正常
  • 鸿蒙产业学院正式揭牌！软通动力与深信息签署校企合作框架协议
  • Postgresql源码（141）JIT系列分析汇总
  • HDFS的Shell操作
  • 【愚公系列】《微信小程序与云开发从入门到实践》059-迷你商城小程序的开发（加入购物车与创建订单功能开发）
  • c++ 与 Matlab 程序的数据比对
  • 【Docker】 privileged: true:允许容器获得比默认更高的权限
  • JavaScript正则表达式解析：模式、方法与实战案例
  • 基于微信小程序高校订餐系统的设计与开发ssm+论文源码调试讲解