哈夫曼编码（测试）

题目描述

给定一个数字N，代表有N种不同的字符，已知每种字符的出现次数，现在要求你设计一种编码，使得任意一个编码都不是另外一个编码的前缀，并且使得这些字符经过编码压缩之后的总长度最小；

Input

一个数字N 代表有多少种不同的字符(0<=N<=1000)

N个数字 每个数字代表一种字符的出现次数

Output

一个数字，代表总的编码长度

Sample Input

5

1

2

3

4

5

3

3

8

8

Sample Output

33

30

用结构体数组存储树的节点，不断地寻找两个最小节点构成一个新节点，直到编成一颗完整的二叉树。然后用递归求出每个节点的深度，也就是码长，分别乘上对应叶子节点的权重即是总编码长度。

`#include

include

define MAX 1005

define INF 99999

struct TNode{

int left;

int right;

int weight;

int deep;

}t[MAX*2];

struct T12{

int t1;

int t2;

};

int visited[MAX*2];

T12 FindSmall(int n);

void CntDeep(int deep,int index);

int main()

{

int n,x;

while(~scanf("%d",&n))

{

//输入、初始化

memset(visited,0,sizeof(visited));

memset(t,0,sizeof(t));

for(int i=1;i<=n;i++)

{

scanf("%d",&x);

t[i].weight=x;

}

//建树

int cnt=n;

while(cnt<=2*n-1)

{

struct T12 t12=FindSmall(cnt);

visited[t12.t1]=1;

visited[t12.t2]=1;

cnt++;

visited[cnt]=0;

t[cnt].left=t12.t1;

t[cnt].right=t12.t2;

t[cnt].weight=t[t[cnt].left].weight + t[t[cnt].right].weight;

}

//统计深度

CntDeep(0,2*n-1);

int ans=0;

for(int i=1;i<=n;i++)

{

ans+=t[i].weight * t[i].deep;

}

printf("%d\n",ans);

}

return 0;

}

//查找还没进树的两个最小结点

T12 FindSmall(int n)

{

struct T12 t12;

int w1,w2;

w1=w2=INF;

for(int i=1;i<=n;i++)

{

if(visited[i]==0){

if(t[i].weight

w2=w1;

t12.t2=t12.t1;

w1=t[i].weight;

t12.t1=i;

}else{

if(t[i].weight

w2=t[i].weight;

t12.t2=i;

}

}

}

}

return t12;

}

//统计深度

void CntDeep(int deep,int index)

{

if(index==0) return;

t[index].deep=deep;

CntDeep(deep+1,t[index].left);

CntDeep(deep+1,t[index].right);

}`

emmmm感觉代码的颜色可能会有点奇怪。

后面会加上一些应用题。