//这段C基本通过,帮改成java;实现哈夫曼树的程序

Question

//这段C基本通过,帮改成java; 
#include <stdio.h> 
#include <stdlib.h> 
#define MaxValue 10000 
#define MaxBit 10 
#define MaxN 100 
typedef struct 
{  
int weight; 
int flag; 
int parent; 
int leftChild; 
int rightChild; 
}HaffNode; 
typedef struct 
{ 
int  bit[MaxN]; 
int start; 
int weight; 
}Code; void Haffman(int weight[], int n ,HaffNode haffTree[]) 
{ 
int i,j,m1,m2,x1,x2; 
for(i=0;i <2*n-1;i++) 
{ 
if(i <n)haffTree[i].weight=weight[i]; 
else haffTree[i].weight=0; 
haffTree[i].parent=-1; 
haffTree[i].flag=0;haffTree[i].leftChild=-1; 
haffTree[i].rightChild=-1; 
} for(i=0;i <n-1;i++) 
{ 
m1=m2=MaxValue; 
x1=x2=0; 
for(j=0;j <n+i;j++) 
{ 
if(haffTree[j].weight <m1&&haffTree[j].flag==0) 
{ 
m2=m1; 
x2=x1; 
m1=haffTree[j].weight; 
x1=j; 
} 
else if(haffTree[j].weight <m2&&haffTree[j].flag==0) 
{ 
m2=haffTree[j].weight; 
x2=j; 
} 
} 
haffTree[x1].parent=n+i; 
        haffTree[x2].parent=n+i; 
        haffTree[x1].flag=1; 
haffTree[x2].flag=1; 
haffTree[n+1].weight=haffTree[x1].weight+haffTree[x2].weight; 
haffTree[n+i].leftChild=x1; 
haffTree[n+i].leftChild=x2; 
} 
} void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 
{ 
Code *cd=(Code *)malloc(sizeof(Code)); 
int i,j,child,parent; 
for(i=0;i <n-i;i++) 
{ 
cd->start=n-1; 
cd->weight=haffTree[i].weight; 
child=i; 
parent=haffTree[child].parent; while(parent !=-1) 
{ 
if(haffTree[parent].leftChild==child) 
  cd->bit[cd->start]=0; 
else
  cd->bit[cd->start]=1;
cd->start--; 
child=parent; 
parent=haffTree[child].parent; 
} for(j=cd->start+1;j <n;j++) 
  haffCode[i].bit[j]=cd->bit[j]; 
haffCode[i].start=cd->start+1; 
        haffCode[i].weight=cd->weight; 
} 
} 
void main(void) 
{ 
int i,j,n=4; 
int weight[]={1,3,5,7}; 
HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n+1)); 
Code *myHaffCode=(Code *)malloc(sizeof(Code)*n); 
if(n>MaxN) 
{ 
printf("out\n"); 
exit(0); 
} 
Haffman(weight,n,myHaffTree); 
HaffmanCode(myHaffTree,n,myHaffCode); 
for(i=0;i <n;i++) 
{ 
printf("Weight=%d  Code=",myHaffCode[i].weight); 
for(j=myHaffCode[i].start;j <n;j++) 
printf("%d",myHaffCode[i].bit[j]); 
printf("\n"); 
} } 

Answer 1

package untitled1;/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2008</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 *///这段C基本通过,帮改成java; 
//#define MaxValue 10000 
//#define MaxBit 10 
//#
class  HaffNode
{  
int weight; 
int flag; 
int parent; 
int leftChild; 
int rightChild; 
} 
class Code 
{ 
  int MaxN =100 ;
int  bit[]=new int[MaxN]; 
int start; 
int weight; 
} 
public class H{
    int MaxValue =10000 ;  
  public void Haffman(int weight[], int n ,HaffNode haffTree[]) 
        { 
           
                int i,j,m1,m2,x1,x2; 
                for(i=0;i <2*n-1;i++) 
                { 
                  haffTree[i]=new HaffNode();
                if(i<n)haffTree[i].weight=weight[i]; 
                        else haffTree[i].weight=0; 
                        haffTree[i].parent=-1; 
                        haffTree[i].flag=0;haffTree[i].leftChild=-1; 
                        haffTree[i].rightChild=-1; 
                }                 for(i=0;i <n-1;i++) 
                { 
                        m1=m2=MaxValue; 
                        x1=x2=0; 
                for(j=0;j <n+i;j++) 
                { 
                if(haffTree[j].weight <m1&&haffTree[j].flag==0) 
                { 
                        m2=m1; 
                        x2=x1; 
                        m1=haffTree[j].weight; 
                        x1=j; 
                } 
                else if(haffTree[j].weight <m2&&haffTree[j].flag==0) 
                { 
                        m2=haffTree[j].weight; 
                x2=j; 
                } 
                } 
                haffTree[x1].parent=n+i; 
                haffTree[x2].parent=n+i; 
                 haffTree[x1].flag=1; 
                haffTree[x2].flag=1; 
                haffTree[n+1].weight=haffTree[x1].weight+haffTree[x2].weight; 
                haffTree[n+i].leftChild=x1; 
                haffTree[n+i].leftChild=x2; 
                } 
                } public void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 
{ 
        Code cd=new Code(); 
         int i,j,child,parent;
         for(i=0;i<n;i++) 
          {
             cd.start=n-1; 
             cd.weight=haffTree[i].weight; 
             child=i; 
             parent=haffTree[child].parent; 
             while(parent !=-1) 
             { 
             if(haffTree[parent].leftChild==child) 
             cd.bit[cd.start]=0; 
            else 
                cd.bit[cd.start]=1; 
                cd.start--; 
                child=parent; 
                parent=haffTree[child].parent; 
                }
                 haffCode[i]=new Code();
                 
        for(j=cd.start+1;j <n;j++) 
               
                haffCode[i].bit[j]=cd.bit[j]; 
                haffCode[i].start=cd.start+1; 
                haffCode[i].weight=cd.weight; 
          
}
} 
public static void main(String args[]) 
{ 
        int i,j,n=4;
        int MaxN =100 ;
        H h=new H(); 
        int weight[]={1,3,5,7};
        HaffNode myHaffTree[]=new HaffNode[2*n+1]; 
        Code myHaffCode[]=new Code[n]; 
        if(n>MaxN) 
        { 
        System.out.print("out\n"); 
        System.exit(0); 
        } 
        h.Haffman(weight,n,myHaffTree); 
        h.HaffmanCode(myHaffTree,n,myHaffCode); 
      for(i=0;i <n;i++) 
     { 
       System.out.print("Weight="+myHaffCode[i].weight+"Code="); 
                for(j=myHaffCode[i].start;j <n;j++) 
                System.out.print(myHaffCode[i].bit[j]); 
                System.out.print("\n"); 
              } 
            } 
}结果:
Weight=1Code=111
Weight=3Code=110
Weight=5Code=10
Weight=7Code=0
lz的c代码有点问题!!!

Answer 2

Weight=1Code=111 
Weight=3Code=110 
Weight=5Code=10 
Weight=7Code=0 是正确//c代码错在哪,我两遍都找不到

Answer 3

如多些数,和手算答案不一样
public static void main(String args[]) 
{ 
        int i,j,n=14;
        int MaxN =100 ;
        H h=new H(); 
       //int weight[]={40,18,10,10,7,6,5,4};
       int weight[]={1,1,3,3,4,2,2,4,11,13,12,15,14,15};
        HaffNode myHaffTree[]=new HaffNode[2*n+1]; 
        Code myHaffCode[]=new Code[n]; 
        if(n>MaxN) 
        { 
        System.out.print("out\n"); 
        System.exit(0); 
        } 
        h.Haffman(weight,n,myHaffTree); 
        h.HaffmanCode(myHaffTree,n,myHaffCode); 
      for(i=0;i <n;i++) 
     { 
       System.out.print("Weight="+myHaffCode[i].weight+"  Code="); 
                for(j=myHaffCode[i].start;j <n;j++) 
                System.out.print(myHaffCode[i].bit[j]); 
                System.out.print("\n"); 
              } 
            }

Answer 4

这是哈夫曼树啊！不对吗？
你的编码函数错了个地方
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 
{ 
Code *cd=(Code *)malloc(sizeof(Code)); 
int i,j,child,parent; 
for(i=0;i <n-i;i++)        //这个不对，应该是for(i=0;i<n;i++)
{ 
cd->start=n-1; 
cd->weight=haffTree[i].weight; 
child=i; 
parent=haffTree[child].parent; while(parent !=-1) 
{ 
if(haffTree[parent].leftChild==child) 
  cd->bit[cd->start]=0; 
else 
  cd->bit[cd->start]=1; 
cd->start--; 
child=parent; 
parent=haffTree[child].parent; 
} for(j=cd->start+1;j <n;j++) 
  haffCode[i].bit[j]=cd->bit[j]; 
haffCode[i].start=cd->start+1; 
        haffCode[i].weight=cd->weight; 
} 
} 

Answer 5

不好意思，我看错了，确实不是颗哈夫曼树
package beans;
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2008</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 *///这段C基本通过,帮改成java; 
//#define MaxValue 10000 
//#define MaxBit 10 
//#
class  HaffNode
{  
int weight; 
int flag; 
int parent; 
int leftChild; 
int rightChild; 
} 
class Code 
{ 
  int MaxN =100 ;
int  bit[]=new int[MaxN]; 
int start; 
int weight; 
} 
public class H{
    int MaxValue =10000 ;  
  public void Haffman(int weight[], int n ,HaffNode haffTree[]) 
        { 
           
                int i,j,m1,m2,x1,x2; 
                for(i=0;i <2*n-1;i++) 
                { 
                haffTree[i]=new HaffNode();
                 if(i<n)haffTree[i].weight=weight[i];
                        else haffTree[i].weight=0; 
                        haffTree[i].parent=-1; 
                        haffTree[i].flag=0;
                        haffTree[i].leftChild=-1; 
                        haffTree[i].rightChild=-1; 
                } 
                for(i=0;i <n-1;i++) 
                { 
                        m1=m2=MaxValue;//非叶子节点
                        x1=x2=0;
                        for(j=0;j <n+i;j++)//在 
                        { 
                         if(haffTree[j].weight <m1&&haffTree[j].flag==0) 
                         { 
                         m2=m1; 
                         x2=x1; 
                         m1=haffTree[j].weight; 
                         x1=j; 
                         } 
                else if(haffTree[j].weight<m2 && haffTree[j].flag==0) 
                { 
                        m2=haffTree[j].weight; 
                        x2=j;
                } 
                } 
                haffTree[x1].parent=n+i; 
                haffTree[x2].parent=n+i; 
                 haffTree[x1].flag=1; 
                haffTree[x2].flag=1; 
                haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; 
                haffTree[n+i].leftChild=x1; 
                haffTree[n+i].rightChild=x2; 
                } 
                } public void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 
{ 
       
  Code cd=new Code(); 
      int i,j,child,parent;
      for(i=0;i<n;i++) 
       {
          cd.start=n-1; 
          cd.weight=haffTree[i].weight; 
          child=i; 
          parent=haffTree[child].parent; 
          while(parent !=-1) 
          { 
          if(haffTree[parent].leftChild==child) 
          cd.bit[cd.start]=0; 
         else 
             cd.bit[cd.start]=1; 
             cd.start--; 
             child=parent; 
             parent=haffTree[child].parent; 
             }
              haffCode[i]=new Code();
              
     for(j=cd.start+1;j <n;j++) 
            
             haffCode[i].bit[j]=cd.bit[j]; 
             haffCode[i].start=cd.start+1; 
             haffCode[i].weight=cd.weight; 
       
}          }
public static void main(String args[]) 
{ 
 int i,j,n=4; 
     int MaxN =100 ; 
     H h=new H(); 
   //int weight[]={40,18,10,10,7,6,5,4}; 
   int weight[]={2,4,3,3}; 
     HaffNode myHaffTree[]=new HaffNode[2*n+1]; 
     Code myHaffCode[]=new Code[n]; 
     if(n>MaxN) 
     { 
     System.out.print("out\n"); 
     System.exit(0); 
     } 
     h.Haffman(weight,n,myHaffTree);
  /*   for(i=0;i<n*2-1;i++)
     {
      System.out.println(myHaffTree[i].leftChild+" "+myHaffTree[i].rightChild+" "+myHaffTree[i].weight+" "+myHaffTree[i].parent);
      
     }*/
     h.HaffmanCode(myHaffTree,n,myHaffCode); 
   for(i=0;i<n;i++) 
 { 
   System.out.print("Weight="+myHaffCode[i].weight+"  Code="); 
             for(j=myHaffCode[i].start;j<n;j++) 
             System.out.print(myHaffCode[i].bit[j]); 
             System.out.print("\n"); 
           } }}
这下好了，结果：
Weight=2  Code=00
Weight=4  Code=11
Weight=3  Code=01
Weight=3  Code=10
仔细看了下，错误还真不少，连建树的函数也错了，建议lz不要到网上去找代码了！我就吃过苦头，有找错的时间还不如
自己写个好了

Answer 6

太感谢 J_Factory
书上题目是和程序结果有点不一样.第一次发图,不行过会发 

Answer 7

引用 5 楼 cm 的回复:
  
      12 
      ¦ 
      / \ 
      8 4 
      ¦ 
    / \ 
    5  3 
    ¦ 
  / \ 
  2 3 
这是以上程序的结果 
 
这是哈夫曼树啊！不对吗？         12 
        ¦ 
      /    \ 
     5     7
      ¦    ¦ 
    / \   / \ 
    2 3   3 4
我想要的是这样,书上手动答案是这样
Csdn上,如何贴图

Answer 8

http://c1m2.bb.iyaya.com/xiangce-3241566.html
书上题目,小数改int,与程序结果不一样

Answer 9

图能看到吗
public static void main(String args[]) 
{ 
     int i,j,n=4; 
     int MaxN =100 ; 
     H h=new H(); 
   //int weight[]={40,18,10,10,7,6,5,4}; 
   int weight[]={2,4,3,3}; //图上的数是int(1,3,5,11,20,6,8,13,17,6,8);图上得出1的编码是00000，3的编码是00001；
与程序不一样，
再一次感谢了

Answer 10

int(1,3,5,11,20,6,8,13,17,6,8); 
这个数组得到的权值和的到是349
哈夫曼数权值总和会是最小的，
 你看书上的到的树权值和是这个就对了，编码可能会不同的。。

Answer 11

//我改成double型
结果:
Weight=0.01  Code=11000
Weight=0.03  Code=11001
Weight=0.05  Code=1101
Weight=0.11  Code=111
Weight=0.2  Code=10
Weight=0.06  Code=010
Weight=0.08  Code=011
Weight=0.13  Code=00
与书上不一样
package beans;
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2008</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 *///这段C基本通过,帮改成java; 
//#define MaxValue 10000 
//#define MaxBit 10 
//#
class  HaffNode
{  
double weight; 
int flag; 
int parent; 
int leftChild; 
int rightChild; 
} 
class Code 
{ 
  int MaxN =100 ;
int  bit[]=new int[MaxN]; 
int start; 
double weight; 
} 
 class H{
    int MaxValue =10000 ;  
  public void Haffman(double weight[], int n ,HaffNode haffTree[]) 
        { 
           
                int i,j,x1,x2; 
               double m1,m2;
                for(i=0;i <2*n-1;i++) 
                { 
                haffTree[i]=new HaffNode();
                    if(i<n) haffTree[i].weight=weight[i];
                        else haffTree[i].weight=0; 
                        haffTree[i].parent=-1; 
                        haffTree[i].flag=0;
                        haffTree[i].leftChild=-1; 
                        haffTree[i].rightChild=-1; 
                } 
                for(i=0;i <n-1;i++) 
                { 
                        m1=m2=MaxValue;//非叶子节点
                        x1=x2=0;
                        for(j=0;j <n+i;j++)//在 
                        { 
                            if(haffTree[j].weight <m1&&haffTree[j].flag==0) 
                            { 
                                m2=m1; 
                                x2=x1; 
                                m1=haffTree[j].weight; 
                                x1=j; 
                            } 
                else if(haffTree[j].weight<m2 && haffTree[j].flag==0) 
                { 
                        m2=haffTree[j].weight; 
                        x2=j;
                } 
                } 
                haffTree[x1].parent=n+i; 
                haffTree[x2].parent=n+i; 
                 haffTree[x1].flag=1; 
                haffTree[x2].flag=1; 
                haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; 
                haffTree[n+i].leftChild=x1; 
                haffTree[n+i].rightChild=x2; 
                } 
                } public void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 
{ 
       
      Code cd=new Code(); 
      int i,j,child,parent;
      for(i=0;i<n;i++) 
       {
          cd.start=n-1; 
          cd.weight=haffTree[i].weight; 
          child=i; 
          parent=haffTree[child].parent; 
          while(parent !=-1) 
          { 
          if(haffTree[parent].leftChild==child) 
          cd.bit[cd.start]=0; 
         else 
             cd.bit[cd.start]=1; 
             cd.start--; 
             child=parent; 
             parent=haffTree[child].parent; 
             }
            haffCode[i]=new Code();
              
     for(j=cd.start+1;j <n;j++) 
            
             haffCode[i].bit[j]=cd.bit[j]; 
             haffCode[i].start=cd.start+1; 
             haffCode[i].weight=cd.weight; 
       
}          }
public static void main(String args[]) 
{ 
     int i,j,n=8; 
     int MaxN =100 ; 
     H h=new H(); 
 //  int weight[]={40,18,10,10,7,6,5,4}; 
    double weight[]={0.01,0.03,0.05,0.11,0.20,0.06,0.08,0.13,0.17,0.06,0.08};
     HaffNode myHaffTree[]=new HaffNode[2*n+1]; 
     Code myHaffCode[]=new Code[n]; 
     if(n>MaxN) 
     { 
     System.out.print("out\n"); 
     System.exit(0); 
     } 
     h.Haffman(weight,n,myHaffTree);
  /*   for(i=0;i<n*2-1;i++)
     {
         System.out.println(myHaffTree[i].leftChild+" "+myHaffTree[i].rightChild+" "+myHaffTree[i].weight+" "+myHaffTree[i].parent);
         
     }*/
     h.HaffmanCode(myHaffTree,n,myHaffCode); 
   for(i=0;i<n;i++) 
 { 
   System.out.print("Weight="+myHaffCode[i].weight+"  Code="); 
             for(j=myHaffCode[i].start;j<n;j++) 
             System.out.print(myHaffCode[i].bit[j]); 
             System.out.print("\n"); 
           } }}

Answer 12

我也手工建了个树,结果和程序输出的结果一样,是书上左右画的没规则,我太信书了,
没有 J_Factory 的指点,我都想放弃了.thanks
最后俩小问题:
 double weight[]={0.01,0.03,0.05,0.11,0.20,0.06,0.08,0.13,0.17,0.06,0.08}; 
//double 改成float为何精度不够2楼与7楼修改的除了以下,还有哪?
                haffTree[n+1].weight=haffTree[x1].weight+haffTree[x2].weight; //----haffTree[n+1]是n+i;
                haffTree[n+i].leftChild=x1; 
                haffTree[n+i].leftChild=x2; 
                } 
                } public void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 

Answer 13

就这两处
不知道你对精度的要求，float是32位的，double是64位的，一个是单精度，另一个是双精度。
这个程序用float没有问题吧，看下有没有都改成float。。

Answer 14

//多谢了，
记段代码
for(j=myHaffCode[i].start;j<n;j++) 
             System.out.print(myHaffCode[i].bit[j]); 
           System.out.print("  码长="+(n-myHaffCode[i].start)+"位"); 
            System.out.print("\n"); 
         codelong=codelong+(n-myHaffCode[i].start)*myHaffCode[i].weight;
           } 
     System.out.print(codelong+"\n"); 
}
 }

Answer 15

package beans;
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2008</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 *///这段C基本通过,帮改成java; 
//#define MaxValue 10000 
//#define MaxBit 10 
//#
class  HaffNode
{  
double weight; 
int flag; 
int parent; 
int leftChild; 
int rightChild; 
} 
class Code 
{ 
  int MaxN =100 ;
int  bit[]=new int[MaxN]; 
int start; 
double weight; 
} 
 class H{
    int MaxValue =10000 ;  
  public void Haffman(double weight[], int n ,HaffNode haffTree[]) 
        { 
           
                int i,j,x1,x2; 
               double m1,m2;
                for(i=0;i <2*n-1;i++) 
                { 
                haffTree[i]=new HaffNode();
                        if(i<n) haffTree[i].weight=weight[i];
                        else haffTree[i].weight=0; 
                        haffTree[i].parent=-1; 
                        haffTree[i].flag=0;
                        haffTree[i].leftChild=-1; 
                        haffTree[i].rightChild=-1; 
                } 
                for(i=0;i <n-1;i++) 
                { 
                        m1=m2=MaxValue;//非叶子节点
                        x1=x2=0;
                        for(j=0;j <n+i;j++)//在 
                        { 
                            if(haffTree[j].weight <m1&&haffTree[j].flag==0) 
                            { 
                                m2=m1; 
                                x2=x1; 
                                m1=haffTree[j].weight; 
                                x1=j; 
                            } 
                             else if(haffTree[j].weight<m2 && haffTree[j].flag==0) 
                             { 
                        m2=haffTree[j].weight; 
                        x2=j;
                              } 
                          } 
                haffTree[x1].parent=n+i; 
                haffTree[x2].parent=n+i; 
                 haffTree[x1].flag=1; 
                haffTree[x2].flag=1; 
                haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; 
               //if(i==0)  
                System.out.println( haffTree[n+i].weight+" ");                haffTree[n+i].leftChild=x1; 
                haffTree[n+i].rightChild=x2; 
                } 
                } public void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) 
{ 
       
      Code cd=new Code(); 
      int i,j,child,parent;
      for(i=0;i<n;i++) 
       {
          cd.start=n-1; 
          cd.weight=haffTree[i].weight; 
          child=i; 
          parent=haffTree[child].parent; 
          // System.out.println(parent+" ");
          while(parent !=-1) 
          {  if(haffTree[parent].leftChild==child) 
          cd.bit[cd.start]=0; 
         else 
             cd.bit[cd.start]=1; 
             cd.start--; 
             child=parent; 
             parent=haffTree[child].parent; 
             }
            haffCode[i]=new Code();
              
     for(j=cd.start+1;j <n;j++) 
            
             haffCode[i].bit[j]=cd.bit[j]; 
             haffCode[i].start=cd.start+1; 
             haffCode[i].weight=cd.weight; 
       
}          }
   public  static  String[]  Split(String  Source,  String  Delimiter)  {  
       int  iCount,  iPos,  iLength;      
       boolean  bEnd;  //判断结束的符号是不是分割符号  
       String  sTemp;  //  
       String[]  aSplit  =  null,  t  =  null;  //aSplit结果返回    t临时的  
 
       sTemp  =  Source;  
       iCount  =  0;  
       iLength  =  Delimiter.length();  
       bEnd=sTemp.endsWith(Delimiter);  
 
       for  (;  ;  )  {  
           iPos  =  sTemp.indexOf(Delimiter);  
           if  (iPos  <  0)  //直到没有分割的字符串，就退出  
               break;  
           else  {  
 
               if  (iCount  >  0)  t  =  aSplit;    //第一次，不用拷贝数组  
 
               iCount++;  
               aSplit  =  new  String[iCount];  //新的数组，  
 
               if  (iCount  >  1)  {                      //不是第一次，拷贝数组  
                   for  (int  i  =  0;  i  <  t.length;  i++)  aSplit[i]  =  t[i];  
               }  
 
               aSplit[iCount  -  1]  =  sTemp.substring(0,  iPos);    
               sTemp  =  sTemp.substring(iPos  +  iLength);            //  取余下的字符串  
           }  
       }  
 
       if(  (sTemp.length()  >=  0) ||  bEnd)  {    //  判断最后剩余的  String，如果最后的字符是分割符号  
           if  (iCount  >  0)  t  =  aSplit;  
           iCount++;  
           aSplit  =  new  String[iCount];  
           if  (iCount  >  1)  {  
               for  (int  i  =  0;  i  <  t.length;  i++)  aSplit[i]  =  t[i];  
           }  
 
           aSplit[iCount  -  1]  =  sTemp;  
       }  
 
       return  aSplit;  
   }  public static void main(String args[]) 
{ 
     int i,j,n=8;
         double codelong=0; 
     int MaxN =100 ; 
     H h=new H(); 
 //  int weight[]={40,18,10,10,7,6,5,4}; 
    //double weight[]={0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04};
   String str="0.01,0.03,0.05,0.11,0.2,0.06,0.08,0.13,0.17,0.08,0.08";
    // //String str="1,3,5,7";
    // String [] temp=str.split(",");
   String [] temp=Split(str,",");
        double []weight=new double[temp.length];
        for ( i = 0; i < temp.length; i++) {
            weight[i]=Double.valueOf(temp[i]);
        }
     n= temp.length;
     HaffNode myHaffTree[]=new HaffNode[2*n+1]; 
     Code myHaffCode[]=new Code[n]; 
     if(n>MaxN) 
     { 
     System.out.print("out\n"); 
     System.exit(0); 
     } 
     h.Haffman(weight,n,myHaffTree);
  /*   for(i=0;i<n*2-1;i++)
     {
         System.out.println(myHaffTree[i].leftChild+" "+myHaffTree[i].rightChild+" "+myHaffTree[i].weight+" "+myHaffTree[i].parent);
         
     }*/
     h.HaffmanCode(myHaffTree,n,myHaffCode); 
   for(i=0;i<n;i++) 
 { 
   System.out.print("Weight="+myHaffCode[i].weight+"  Code="); 
             for(j=myHaffCode[i].start;j<n;j++) 
             { System.out.print(myHaffCode[i].bit[j]); 
             
             }
           System.out.print("  码长="+(n-myHaffCode[i].start)+"位"); 
            System.out.print("\n"); 
         codelong=codelong+(n-myHaffCode[i].start)*myHaffCode[i].weight;
           } 
     System.out.print(codelong+"\n"); 
}
 }

Answer 16

using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication1
{
    public class HaffNode
    {
        public float weight;
        public int flag;
        public int parent;
        public int leftChild;
        public int rightChild;
    }    public class Code
    {
        int MaxN = 100;
        public int[] bit = new int[100];
        public int start;
        public float weight;
    }    public class H
    {
        int MaxValue = 10000;
        public void Haffman(float[] weight, int n, HaffNode[] haffTree)
        {            int i, j, x1, x2;
            float m1, m2;
            for (i = 0; i < 2 * n - 1; i++)
            {
                haffTree[i] = new HaffNode();
                if (i < n) haffTree[i].weight = weight[i];
                else haffTree[i].weight = 0;
                haffTree[i].parent = -1;
                haffTree[i].flag = 0;
                haffTree[i].leftChild = -1;
                haffTree[i].rightChild = -1;
            }
            for (i = 0; i < n - 1; i++)
            {
                m1 = m2 = MaxValue;//非叶子节点
                x1 = x2 = 0;
                for (j = 0; j < n + i; j++)//在 
                {
                    if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
                    {
                        m2 = m1;
                        x2 = x1;
                        m1 = haffTree[j].weight;
                        x1 = j;
                    }
                    else if (haffTree[j].weight < m2 && haffTree[j].flag == 0)
                    {
                        m2 = haffTree[j].weight;
                        x2 = j;
                    }
                }
                haffTree[x1].parent = n + i;
                haffTree[x2].parent = n + i;
                haffTree[x1].flag = 1;
                haffTree[x2].flag = 1;
                haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
                haffTree[n + i].leftChild = x1;
                haffTree[n + i].rightChild = x2;
            }
        }        public void HaffmanCode(HaffNode[] haffTree, int n, Code[] haffCode)
        {            Code cd = new Code();
            int i, j, child, parent;
            for (i = 0; i < n; i++)
            {
                cd.start = n - 1;
                cd.weight = haffTree[i].weight;
                child = i;
                parent = haffTree[child].parent;
                while (parent != -1)
                {
                    if (haffTree[parent].leftChild == child)
                        cd.bit[cd.start] = 0;
                    else
                        cd.bit[cd.start] = 1;
                    cd.start--;
                    child = parent;
                    parent = haffTree[child].parent;
                }
                haffCode[i] = new Code();                for (j = cd.start + 1; j < n; j++)                    haffCode[i].bit[j] = cd.bit[j];
                haffCode[i].start = cd.start + 1;
                haffCode[i].weight = cd.weight;            }        }        class Program
        {            int[] Space = new int[100];
            char[,] board = new char[80, 80];
            int MaxDepth = -1;
            void OutputBoard()
            {
                int i, j;
                for (i = 0; i <= MaxDepth && i < 80; i++)
                {
                    for (j = 0; j < 79; j++)
                    {
                        System.Console.WriteLine("%c", board[i, j]);
                    }
                    System.Console.WriteLine();
                }
                System.Console.WriteLine();
            }            public int NumLen(float a)
            {
                return (int)(System.Math.Log10((double)a) + 1);
            }            public int Pretreat(HaffNode[] haffTree, int k, int n, int depth, int space, bool isLeft)
            {
                int ret = space;
                int tmp = 0;
                int numLen = 0;
                if (k >= 0 && k < 2 * n - 1)
                {
                    if (Space[depth] < ret)
                    {
                        Space[depth] = ret;
                    }
                    else
                    {
                        ret = Space[depth] + 1;
                    }
                    tmp = ret;
                    /*要把左子树遍历完，才能知道自己所在的位置*/
                    if (haffTree[k].rightChild != -1)/*leftChild*/
                    {
                        tmp = Pretreat(haffTree, haffTree[k].rightChild, n, depth + 1, ret - 2, true);
                    }
                    if (tmp > ret)
                    {
                        ret = tmp;
                    }
                    numLen = NumLen(haffTree[k].weight);
                    if (Space[depth] < ret + numLen)
                    {
                        Space[depth] = ret + numLen;
                    }
                    haffTree[k].flag = ret;
                    System.Console.WriteLine(board[depth * 2] + ret, numLen, "%d", haffTree[k].weight);                    if (MaxDepth < depth * 2)
                    {
                        MaxDepth = depth * 2;
                    }
                    if (haffTree[k].leftChild != -1)
                    {
                        board[depth * 2 + 1][ret - 1] = '/';
                    }
                    if (!isLeft && depth * 2 > 0)
                    {
                        board[depth * 2 - 1][ret] = '\\';
                    }
                    if (haffTree[k].leftChild != -1)/*rightChild*/
                    {
                        Pretreat(haffTree, haffTree[k].leftChild, n, depth + 1, ret + 1, false);
                    }
                    return ret + 2;
                }
                return 0;
            }            static void Main(string[] args)
            {
                int i, j, n = 11;
                int MaxN = 100;
                H h = new H();
                //int weight[]={40,18,10,10,7,6,5,4}; 
                float[] weight = { 0.01F, 0.03F, 0.05F, 0.11F, 0.20F, 0.06F, 0.08F, 0.13F, 0.17F, 0.06F, 0.08F };                HaffNode[] myHaffTree = new HaffNode[2 * n + 1];
                Code[] myHaffCode = new Code[n];
                float codelong = 0;
                if (n > MaxN)
                {
                    System.Console.WriteLine("out");
                    return;
                }
                h.Haffman(weight, n, myHaffTree);
                /*   for(i=0;i<n*2-1;i++)
                   {
                       System.out.println(myHaffTree[i].leftChild+" "+myHaffTree[i].rightChild+" "+myHaffTree[i].weight+" "+myHaffTree[i].parent);
         
                   }*/
                h.HaffmanCode(myHaffTree, n, myHaffCode);
                for (i = 0; i < n; i++)
                {
                    System.Console.WriteLine("Weight=" + myHaffCode[i].weight + "  Code=");
                    //for (j = myHaffCode[i].start; j < n; j++)
                    //    System.Console.WriteLine(myHaffCode[i].bit[j]);
                    //System.Console.WriteLine("\n");
                    for (j = myHaffCode[i].start; j < n; j++)
                        System.Console.WriteLine(myHaffCode[i].bit[j]);
                    System.Console.WriteLine("  码长=" + (n - myHaffCode[i].start) + "位");
                    System.Console.WriteLine("\n");
                    codelong = codelong + (n - myHaffCode[i].start) * myHaffCode[i].weight;
                }
                System.Console.WriteLine("cm=" + codelong);
            }        }
    }
}