Huffman树

Huffman树

时间: 1ms        内存:128M

描述:

我们大家都学习了Huffman算法,给出每一个点的权值,它可以求出一个具有最小加权外部路径的二叉树,也就是使造价 W(k1)*Lk1 + ... + W(kn)*Lkn (树枝长度为根结点到叶结点边数)最小的二叉树。现在由你来完成这项工作。

输入:

输入一共有2行。
第一行为一个整数n,它表示点的个数。
第二行有n(1 < n <= 1000)个数,第i(1 <= i <= n)个数表示第i个点的权值

输出:

输出为一个数,为最小造价值。

示例输入:

5
10 5 20 10 18 

示例输出:

141 

提示:

参考答案(内存最优[752]):

#include<stdio.h>    

typedef struct node {    
    int weight;    
    int ok;    
}NODE;    

int main()
{    
    int n,n1,n2,i,j,min1,min2,sum=0;    
    NODE t[2002];    
    scanf("%d",&n);    
    for(i = 0;i < n;i++) 
	{    
        scanf("%d",&t[i].weight);    
        t[i].ok = 1;    
    }    
    for(i = n;i < 2*n-1;i++) 
	{    
        n1 = n2 = -1;    
        min1 = min2 = 999999;    
        for(j = 0;j < i;j++) 
		{    
            if (t[j].ok) 
			{    
               if (t[j].weight < min1) 
			   {    
                   min2 = min1;    
                   n2 = n1;    
                   min1 = t[j].weight;    
                   n1 = j;    
               } 
			   else if (t[j].weight < min2) 
			   {    
                   min2 = t[j].weight;    
                   n2 = j;    
               }    
            }    
        }    
        t[i].weight = t[n1].weight + t[n2].weight;    
        sum += t[i].weight;    
        t[i].ok = 1;    
        t[n1].ok = t[n2].ok = 0;    
    }    
    printf("%d",sum);
    return 0;
}   


参考答案(时间最优[0]):

#include<stdio.h>    

typedef struct node {    
    int weight;    
    int ok;    
}NODE;    

int main()
{    
    int n,n1,n2,i,j,min1,min2,sum=0;    
    NODE t[2002];    
    scanf("%d",&n);    
    for(i = 0;i < n;i++) 
	{    
        scanf("%d",&t[i].weight);    
        t[i].ok = 1;    
    }    
    for(i = n;i < 2*n-1;i++) 
	{    
        n1 = n2 = -1;    
        min1 = min2 = 999999;    
        for(j = 0;j < i;j++) 
		{    
            if (t[j].ok) 
			{    
               if (t[j].weight < min1) 
			   {    
                   min2 = min1;    
                   n2 = n1;    
                   min1 = t[j].weight;    
                   n1 = j;    
               } 
			   else if (t[j].weight < min2) 
			   {    
                   min2 = t[j].weight;    
                   n2 = j;    
               }    
            }    
        }    
        t[i].weight = t[n1].weight + t[n2].weight;    
        sum += t[i].weight;    
        t[i].ok = 1;    
        t[n1].ok = t[n2].ok = 0;    
    }    
    printf("%d",sum);
    return 0;
}   


题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注