huffmancoding.java

实现哈夫曼树

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

package datacompress;

/**
 *
 * @author Han
 */
import java.io.*;
import java.util.*;
class HuffmanCoding{
  int num=0;
  int value[][]=new int[num][2];
  int numNode;
  int huffVal[][]=new int[numNode][5];
  public void stat()throws Exception{
  	 String s; 
     int A[]=new int[127];      
     FileInputStream fis=new FileInputStream("a.txt");
     InputStreamReader isr=new InputStreamReader(fis);
     BufferedReader br=new BufferedReader(isr);
     while((s=br.readLine())!=null)
        for(int i=0;i<s.length();i++){
         char a=s.charAt(i);
         int j=(int)a;
          A[j]++;
        }
     br.close();
     isr.close();
     fis.close();
   
    for(int i=0;i<127;i++){
       	if(A[i]!=0) num++;
       }  
    
    int value[][]=new int[num][2];
    int p=0;
    for(int n=0;n<127;n++){      
     if(A[n]!=0){
       value[p][0]=A[n];
       value[p][1]=n; 
       p++;
     }
    }
    for(int i=0;i<=num-2;i++){
     int k=i;
     for(int j=i+1;j<=num-1;j++){
       if(value[j][0]<value[k][0]){
       	k=j;
       }	
     }
     int m;
     m=value[i][0];value[i][0]=value[k][0];value[k][0]=m;
     m=value[i][1];value[i][1]=value[k][1];value[k][1]=m;
    } 
     for(int i=0;i<num;i++){
       for(int j=0;j<2;j++){
       System.out.print(value[i][j]);
       System.out.print("    ");
       }
       System.out.println();
       }  
  }	 	 //
   void creatree()throws Exception{             //
	int i,j,k;
	numNode=num*2-1;
	int huffVal[][]=new int[numNode][5];
	for(i=0;i<numNode;i++){
	 if(i<num){
	 huffVal[i][0]=value[i][0];
	 huffVal[i][1]=value[i][1];	
     }	 
     else{
     	huffVal[i][0]=0;   //huffVal[i][0]is the weight
        huffVal[i][1]=0;   //huffVal[i][1]is the ASCII
        huffVal[i][2]=0;   //huffVal[i][2]is the lchild index
        huffVal[i][3]=0;   //huffVal[i][3]is the rchild index
        huffVal[i][4]=0;   //huffVal[i][4]is the parent index
     }
    }   
 	for(i=num;i<numNode;i++){
 		int small1=10000;int small2=10000;
        int num1=0;int num2=0;
 		for(j=0;j<i;j++){
 			if(huffVal[j][4]==0)
 			 if(huffVal[j][0]<small1){
 				 small2=small1;
 				 num2=num1;
 				 small1=huffVal[j][0];
 				 num1=j;
 				}
 				else
 				if(huffVal[j][0]<small2){
 					small2=huffVal[j][0];
 					num2=j;
 					}
 			}
 		huffVal[i][0]=small1+small2;
 		huffVal[i][2]=num1;
 		huffVal[i][3]=num2;
 		huffVal[num1][4]=i;
 		huffVal[num2][4]=i;
    }
     for(i=0;i<numNode;i++){
       System.out.print(huffVal[i][0]+"   ");
       System.out.print(huffVal[i][1]+"   ");
       System.out.print(huffVal[i][2]+"   ");
       System.out.print(huffVal[i][3]+"   ");
       System.out.print(huffVal[i][4]+"   ");
       System.out.print("    ");
       System.out.println();
       }  			
    }
}
class Test{
   public static void main(String args[]) throws Exception{
   	HuffmanCoding h=new HuffmanCoding();
   	h.stat();
   	h.creatree();           //
   	}
}