文章

20

粉丝

224

获赞

56

访问

137.4k

头像
P1562 哈夫曼编码
P1562
发布于2022年2月5日 00:47
阅读数 5.2k

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

struct node {
	int x;
	// 定义优先队列的比较关系,这里我们定义的是小根堆
	bool operator < (const node& a) const {
        return x > a.x;
    }
};

int main() {
	char text[100];
	while (scanf("%s", text) != EOF) {
		if (strcmp(text, "END") != 0) {
			int len = strlen(text);
			map<char, int> m;
			// 使用 map 来存储每个字符及对应出现的次数
			for (int i = 0; i < len; ++i) {
				char key = text[i];
				++m[key];
			}
			map<char, int>::iterator iter;  
			priority_queue<node> q;
			// 将每个字符出现的次数存储进优先队列中
			for (iter = m.begin(); iter != m.end(); ++iter) q.push(node{iter->second});
			int huffman = 0;
			// 如果优先队列一开始就只有一个元素,则说明此字符串只有一种字符,对应的哈夫曼编码长度则是字符串的长度
			if (q.size() == 1) huffman = len;
			// 否则计算此哈夫曼树的带权路径长度,即 WPL
			else {
				while (q.size() > 1) {
					node num1 = q.top();
					q.pop();
					node num2 = q.top();
					q.pop();
...
登录查看完整内容


登录后发布评论

1 条评论
沉默的大多数
2022年2月5日 16:17

<script>

    alert("测试");

</script>

赞(0)