[c] HDOJ1053 哈夫曼树的应用

150 阅读 0 评论 99 点赞

我是靠谱客的博主热心仙人掌，这篇文章主要介绍[c] HDOJ1053 哈夫曼树的应用，现在分享给大家，希望可以做个参考。

http://acm.hdu.edu.cn/showproblem.php?pid=1053

题目标题：entropy

题目大意：将一串字符串用哈夫曼树的方法压缩，求压缩前与压缩后所占空间与压缩比例

这个题是数据结构中哈夫曼树的应用，把每个字符出现的次数记录下来，每次把最少的两个合成一个结点，并由此得到哈夫曼树，然后对每个节点编码，向左标0，向右标1，得到每个字母的编码后计算空间即可。需要注意只有一个字符的情况。

复制代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;

int sum1=0,sum2=0;

struct Node{
	char value;
	int num;
	Node* left=NULL;
	Node* right=NULL;
};

Node* make(Node *a,Node *b){
	Node *p;
	p=(Node*)malloc(sizeof(Node));
	p->left=a;
	p->right=b;
	p->value=1;
	p->num=a->num+b->num;
	return p;
}

bool Judge(Node *a,Node *b){
	if(a->num > b->num) return true;
	else return false;
}

void DFS(Node *a,int cur){
	if(a->left==NULL && a->right==NULL){
		sum2+=cur*a->num;
		return;
	}
	else {
		if(a->left!=NULL) 
			DFS(a->left,cur+1);
		if(a->right!=NULL) 
			DFS(a->right,cur+1);
	}
	free(a);
}

int main()
{
	vector <Node*> Vec;
	string x;
	while(cin>>x){
		sum1=0;
		sum2=0;
		if(x=="END") break;
		sum1=x.size()*8;
		for(int i=0;i<x.size();i++){
			int sign=0;
			for(int j=0;j<Vec.size();j++){
				if(x[i]==Vec[j]->value){
					sign=1;
					Vec[j]->num++;
					break;
				}
			}
			if(sign==0){
				Node* p;
				p=(Node*)malloc(sizeof(Node));
				p->value=x[i];
				p->num=1;
				p->left=NULL;
				p->right=NULL;
				Vec.push_back(p);
			}
		}
		int n=Vec.size()-1;
		int ssign=1;
		if(n==0) ssign=0;
		for(int i=0;i<n;i++){
			sort(Vec.begin(),Vec.end(),Judge);
			Node* p;
			p=make(Vec[Vec.size()-1],Vec[Vec.size()-2]);
			Vec[Vec.size()-2]=p;
			Vec.pop_back();
		}
		Node *q=Vec[0];
		if(ssign==1)
			DFS(q,0);
		else sum2=sum1/8;
		printf("%d %d %.1fn",sum1,sum2,(double)sum1/(double)sum2);
		Vec.clear();
	}
	return 0;
}

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;

int sum1=0,sum2=0;

struct Node{
	char value;
	int num;
	Node* left=NULL;
	Node* right=NULL;
};

Node* make(Node *a,Node *b){
	Node *p;
	p=(Node*)malloc(sizeof(Node));
	p->left=a;
	p->right=b;
	p->value=1;
	p->num=a->num+b->num;
	return p;
}

bool Judge(Node *a,Node *b){
	if(a->num > b->num) return true;
	else return false;
}

void DFS(Node *a,int cur){
	if(a->left==NULL && a->right==NULL){
		sum2+=cur*a->num;
		return;
	}
	else {
		if(a->left!=NULL) 
			DFS(a->left,cur+1);
		if(a->right!=NULL) 
			DFS(a->right,cur+1);
	}
	free(a);
}

int main()
{
	vector <Node*> Vec;
	string x;
	while(cin>>x){
		sum1=0;
		sum2=0;
		if(x=="END") break;
		sum1=x.size()*8;
		for(int i=0;i<x.size();i++){
			int sign=0;
			for(int j=0;j<Vec.size();j++){
				if(x[i]==Vec[j]->value){
					sign=1;
					Vec[j]->num++;
					break;
				}
			}
			if(sign==0){
				Node* p;
				p=(Node*)malloc(sizeof(Node));
				p->value=x[i];
				p->num=1;
				p->left=NULL;
				p->right=NULL;
				Vec.push_back(p);
			}
		}
		int n=Vec.size()-1;
		int ssign=1;
		if(n==0) ssign=0;
		for(int i=0;i<n;i++){
			sort(Vec.begin(),Vec.end(),Judge);
			Node* p;
			p=make(Vec[Vec.size()-1],Vec[Vec.size()-2]);
			Vec[Vec.size()-2]=p;
			Vec.pop_back();
		}
		Node *q=Vec[0];
		if(ssign==1)
			DFS(q,0);
		else sum2=sum1/8;
		printf("%d %d %.1fn",sum1,sum2,(double)sum1/(double)sum2);
		Vec.clear();
	}
	return 0;
}