算法:求 Huffuman树 构造费用

问题背景:
            Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。
            给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下:
              1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}
                中。这个过程的费用记为pa + pb。
              2. 重复步骤1,直到{pi}中只剩下一个数。
              在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。


本题任务:
            对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用,构造示例参考下图。

算法:求 Huffuman树 构造费用

解题思路:
            对于这一题,我们可以采用qsort函数进行排序,并设计精简操作代码即可。


参考代码:

 #include<stdio.h>
#include<stdlib.h> int compare (const void * a, const void * b) //small-> big
{
return *((int*)a)-*((int*)b);
}
int main(){
int num,i;
scanf("%d",&num);
int* numlist=(int*)malloc(sizeof(int)*num);
for(i=;i<num;i++)
scanf("%d",&numlist[i]);
int sum=,temp;
while(num>)
{
qsort(numlist,num,sizeof(int),compare); //SORT
temp=numlist[]+numlist[];
sum+=temp;//Two Small Number Add
numlist=numlist+;
*numlist=temp;
num--;
}
printf("%d",sum);
return ;
}
上一篇:1064 - You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'groups)VALUES('1','hh','hh@163.com','Boss')' at line 1


下一篇:linux页缓存