huff.java

实现哈夫曼树

/*
 * Huff.java
 *
 * Created on 2007年7月2日, 下午1:10
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package datacompress;
import java.io.*;
import java.util.*;
/**
 *
 * @author Han
 */
public class Huff {
    
    /** Creates a new instance of Huff */
    private int num;
    private int numNode;
    public    int value[][]=new int[2][num];
    public    int valueNode[][]=new int[2][num];
    
    

    
    
        public void Huff()throws IOException {
        System.out.print("程序正huff运行！");
        String s;
        int n,i;
        InputStreamReader ir;
        BufferedReader in;
        ir=new InputStreamReader(System.in);
        in=new BufferedReader(ir);
        System.out.print("input the numbers of data:");
        s=in.readLine();
        n=Integer.parseInt(s);
        System.out.print("input"+s+"numbers");

        for(i=0;i<n-1;i++){
            s=in.readLine();
            value[0][i]=i;
            value[1][i]=Integer.parseInt(s);
            valueNode[0][i]=i;
            valueNode[1][i]=Integer.parseInt(s);
            }
         }
    void class1(){
    int i,j,k,m,n;
    n=num;
    for(i=0;i<n-2;i++){
        k=i;
        for(j=i+1;j<n-1;j++)
            if(valueNode[1][k]>valueNode[1][j])
                k=j;
                if(i!=k){
                  m=valueNode[1][i];
                    valueNode[1][j]=valueNode[1][k];
                    valueNode[1][k]=m;
                    m=valueNode[0][i];
                    valueNode[0][i]=valueNode[0][k];
                    valueNode[0][k]=m;
             
                }
        
        }
    }
    void class2(int m,int n){
    int i,j,sum;
    int arr[][]=new int[2][num];            //?
    sum=arr[1][0]+arr[1][1];
    int number=n-1;
    boolean ff=true;
    for(i=2;i<number;i++){
        if(valueNode[1][i]<sum){
            valueNode[1][i-2]=valueNode[1][i];
            valueNode[0][i-2]=valueNode[0][i];
            }
        else{
                if(ff){
                    valueNode[1][i-2]=sum;
                    valueNode[0][i-2]=number-1;
                    valueNode[1][i-1]=valueNode[1][i];
                    valueNode[0][i-1]=valueNode[0][i];
                    ff=false;
                    }
                else{
                    valueNode[1][i-1]=valueNode[1][i];
                    valueNode[0][i-1]=valueNode[0][1];
                    }
            }
        if(ff){
            valueNode[1][num-1]=sum;
            valueNode[0][num-1]=number-1;
            }
        }
    }
    void huffbm(){
    int huffVal[][]=new int[numNode][4];
    int i,j,k,m,num1,num2,val,par;
    int mm=num;
    Huff huff=new Huff();
        for(i=0;i<numNode;i++){
        if(i<num)
        {huffVal[i][0]=value[1][i];}
        else
        huffVal[i][0]=0;
        huffVal[i][1]=0;
        huffVal[i][2]=0;
        huffVal[i][3]=0;
        }
        for(i=mm+1;i<=num;i++){         //?
        num1=valueNode[0][0];
        num2=valueNode[0][1];
        val=valueNode[1][0]+valueNode[1][1];
        huff.class2(i,mm--);
        par=i;
        huffVal[num1][3]=par;
        huffVal[num2][3]=par;
        huffVal[par][0]=val;
        huffVal[par][3]=0;
        huffVal[par][1]=num1;
        huffVal[par][2]=num2;
        }
    StringBuffer bm;
        for(i=0;i<num;i++){
        j=1;
        bm=new StringBuffer(" ");
            par=huffVal[j][4];
            while(par!=0){
            if(huffVal[par][2]==j)
            bm.insert(0,'0');
            else
            bm.insert(0,'1');
            j=par;
            par=huffVal[par][4];
            }
        System.out.println(bm.toString());
        }
    }
    public static void main(String args[])throws IOException{
    Huff huff=new Huff();
    System.out.print("程序正运行！");
    huff.class1();
    System.out.print("程序正运行！");
    huff.huffbm();
    System.out.print("程序正运行！");
    } 
}