优先队列求哈夫曼编码长度

发表于 | 分类于
字数统计: 271 word | 阅读时长 ≈ 1 min
problem：

数据结构实验之二叉树六：哈夫曼编码

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 #include< iostream>
 #include< queue>
 #include< functional>
using namespace std;
int main(){
	char s[1000];
	int t[500];
	priority_queue<int, vector<int>, greater<int> >q;
	while (cin >> s){
		int sum1, sum2 = 0;
		memset(t, 0, sizeof(t));
		int len = strlen(s);
		sum1 = len * 8;
		for (int i = 0; i < len; i++){
			t[s[i]]++;	//将字符串中的字符转化为ASCII码中的编号存入数组中，并且记录个数
		}
		for (int i = 0; i < 500; i++){
			if (t[i] != 0){
				q.push(t[i]);
			}
		}
		while (!q.empty()){   //每次取出最小的两个也就是队列最开始两个，相加产生的新数据存入队列中
			int x1 = q.top();
			q.pop();
			if (!q.empty()){   //这里要判断一下，上一步取出x1后队列是不是空了,避免在空的队列中操作
				int x2 = q.top();
				q.pop();
				int x3 = x1 + x2;
				sum2 += x3;
				q.push(x3);
			}			
		}
		printf("%d %d %.1lf\n", sum1, sum2, 1.0 * sum1 / sum2);
	}
	return 0;
}
还有一道类似的搬东西的题

合并果子之哈夫曼树

0%