这个题目我在ZOJ上通过，在这里提交就超时。
程序中没有多大的循环呀，真是bt。
还是看看程序吧！
/* OnlinePID ZJU_1117 ( Entropy) */
/* Huffman 算法 */
#include <stdio.h>
#include <string.h>
#define INFINITY 99999999
typedef struct{
   int plink;
   int weight;
}Node;

Node node[60]; 
int  cc; /* character count */
int  orlen; /* ASCII bit len */ 

int input()
{
    char tmp[10000];  
    int  i, j;
    
    scanf("%s", tmp);
    if( strcmp(tmp, "END") == 0 ) return 0;
    
    for(i=0; i<=26; i++)
    { node[i].weight = 0; node[i].plink = -1; }
    
    for(i=0; tmp[i]; i++)
    {
       if( tmp[i] != '_' ) j = tmp[i]-'A';
       else                j = 26;
       node[j].weight++;   node[j].plink = 0;
    }
    
    for(orlen=cc=i=0; i<=26; i++) 
      if( node[i].weight != 0 )
      { orlen += node[i].weight * 8; cc++; }
    return 1;
}
int huffman()
{
    int i, j, rets, t;
    int w1, w2, x1, x2;
    
    for(i=1; i<=cc-1; i++)
    {
       /* select two small weight */
       w1 = w2 = INFINITY; x2 = x1 = 0;
       for(j=0; j<=26+i-1; j++)
        if(node[j].plink == 0)
        {
           if(node[j].weight < w1 )
           {  w2 = w1; x2 = x1;  w1 = node[j].weight; x1 = j; }
           else if(node[j].weight < w2)
           {  w2 = node[j].weight; x2 = j; }
        }
        
       /* Add a new node, which weight is w1+w2 */
       /* and set node x1, x2 's parent to new node */
       node[26+i].weight = w1 + w2; 
       node[26+i].plink = 0;      
       node[x1].plink = node[x2].plink = 26+i;
    }
    /* Calc every character node 's depth in huffman tree */
    /* and return sum of them */
    for(rets=i=0; i<=26; i++)
    {
       j = i; t = 0;
       while(node[j].plink != 0)
       {  t++; j=node[j].plink; }
       rets += node[i].weight * t;
    }
    return rets;
}
    
int main()
{
    int oplen;
    while( input() )
    {
       if(cc==1) oplen = orlen/8;
       else oplen = huffman();
       printf("%d %d %.1lf\n", orlen, oplen, (double)orlen/oplen);
    }
    return 0;
}
     

• 你程序有问题的 (2318) hawk 2004-07-18 18:49:27
  • 这个re很奇怪，vc也不能调试，debug模式就不报错，害的我看了好久才看出来 (73) hawk 2004-07-18 18:51:02
    • 一般都不报错的.它只是一个指针指向前面的一个数据而已.还是让别人来找莫名其妙的错误更容易.有时真希有个人来给我的RE程序找一下. (0) shushu 2006-03-18 12:29:16
• Re:好假 (4) Washington 2005-08-20 16:12:59
  • Re:好假 (27) swordspirit 2009-07-25 14:47:01