HuffmanTree

发表于 分类于

XDOJ-哈夫曼树、Huffman编码

一、问题描述

问题描述
假设用于通信的电文由ｎ个字符组成，字符在电文中出现的频度（权值）为w1,w2,…,wn，试根据该权值序列构造哈夫曼树，并计算该树的带权路径长度。

输入说明
第１行为ｎ的值，第２行为ｎ个整数，表示字符的出现频度。

输出说明
输出所构造哈夫曼树的带权路径长度。

输入样例
8
7 19 2 6 32 3 21 10

输出样例
261

二、C代码

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
#include<stdio.h>
#include<stdlib.h>
typedef struct{
	int weight;
	int parent,lchild,rchild;
}HTNOTE,*HuffmanTree;
//typedef char** HuffmanCode;
void Select(HuffmanTree HT, int n, int* s1, int* s2);
void CreatHuffmanTree(HuffmanTree* HT,int *w,int n){
	int i=0,s1=0,s2=0;
	if(n<=1) return;
	int m=2*n-1;
	*HT=(HuffmanTree)malloc(sizeof(HTNOTE)*(m+1));
	if(!*HT) exit(-1);
	HuffmanTree adjust = NULL;
	for(adjust=*HT+1,i=1;i<=n;i++,adjust++,w++){
		adjust->weight=*w;
		adjust->parent=0;
		adjust->rchild=0;
		adjust->lchild=0;
	}
	for(;i<=m;i++,adjust++){
		adjust->weight=0;
		adjust->parent=0;
		adjust->rchild=0;
		adjust->lchild=0;
	}
	for(i=n+1;i<=m;i++){
	   Select(*HT, i-1, &s1, &s2);
	   (*HT + s1)->parent = (*HT + s2)->parent = i;
		(*HT + i)->lchild = s1;
		(*HT + i)->rchild = s2;
		(*HT + i)->weight = (*HT + s1)->weight + (*HT + s2)->weight;	
	}
}
int Min(HuffmanTree HT,int n){
	int min=1000;
	int flag;
	for(int i=1;i<=n;i++){
		if((HT+i)->weight<min&&(HT+i)->parent==0){
			flag=i;
			min=(HT+i)->weight;
		}	
	}
		(HT+flag)->parent=1;
		return flag;
}
void Select(HuffmanTree HT, int n, int* s1, int* s2) {
	*s1 = Min(HT, n);
	*s2 = Min(HT, n);
}
int FindWay(HuffmanTree HT,int n,int *w){
	int sum=0;
     for(int i=1;i<=n;i++){
     	HuffmanTree q=HT+i;
     	int m=0;
     	while(q->parent!=0){
     		q=HT+q->parent;
     		m++;
		 }
		 sum+=m*w[i-1];
	 }
	 return sum;
	}

int main(){
	int n;
	scanf("%d",&n);
	int w[n];
	for(int i=0;i<n;i++){
		scanf("%d",&w[i]);
	}
	HuffmanTree HT;
	CreatHuffmanTree(&HT,w,n);
	int sum=FindWay(HT,n,w);
	printf("%d",sum);
	/*for(int i=1;i<=2*n-1;i++){
		printf("%d ",(HT+i)->weight);
	}*/
}