huffman.java

java版本的哈夫曼编码 可以编码也可以解码

import java.util.Stack;//引Stack类
import java.io.*;
public class Huffman 
{

  static int n,n1,n2,m; 
  static  Huffman c=new   Huffman(); 
 
  String HT[][]=new String[100][5];
   
public static void main (String []args)throws IOException
  {   
  
       c.InitTreeNode();
       c.HuffmanTreeCreat();
       c.HuffmanTreeCode();
       
       //c.GetCodingSen(str);
       c.HuffmanTreeEncoding();
      // c.HuffmanTreeDecoding(coding);  
         
          
         
   }
   
            
public  void InitTreeNode()throws IOException
  { 
     int i=0;
    
     InputStreamReader ir = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(ir);
     
    System.out.println("请输入字符集大小n");
     
     n=Integer.valueOf(in.readLine()).intValue();
     m=2*n-1;
    
    System.out.println("请输入n个字符和n个权值");
   
    for (i=0;i<n;i++)
     { 
   
       HT[i][0]=""; 
       HT[i][1]=in.readLine();
       HT[i][2]="0"; 
       HT[i][3]="";
       HT[i][4]=in.readLine();
      
      }
    
    for (;i<m;i++)
      {  
       HT[i][0]=""; 
       HT[i][1]="";
       HT[i][2]="0"; 
       HT[i][3]="";
       HT[i][4]="0"; 
     
      }
   }
public  void Select(int end)//找出最小和次小的两个结点序号,返回S1,S2
 {    int i;
      int min1=1000;
      int min2;
   for (i=end-1;i>=0;i--)
    { //找最小的结点序号用n1标记
     if (HT[i][2].equals("0")&&Integer.valueOf(HT[i][4]).intValue()<min1)
      { 
         n1=i;
         min1=Integer.valueOf(HT[i][4]).intValue();
       }
     }
       min2=1000;
    for(i=end-1;i>=0;i--)
     { //找次小结点的序号用n2标记
       
       if(HT[i][2].equals("0")&&n1!=i&&Integer.valueOf(HT[i][4]).intValue()<min2)
        {
           n2=i;
           min2=Integer.valueOf(HT[i][4]).intValue();
         }
      }
   }
public void HuffmanTreeCreat()
   {//建立HUFFMAN树
     int i=0;
    
    for(i=n;i<m;i++)
     {
        Select(i);
        HT[n1][2]=i+"";
        HT[n2][2]=i+"";
        HT[n1][3]="left_child";
        HT[n2][3]="right_child";
        HT[i][4]=(Integer.valueOf(HT[n1][4]).intValue()+Integer.valueOf(HT[n2][4]).intValue())+"";
    
       // System.out.println(HT[n1][1]);
       // System.out.println(HT[n2][1]);
      }
   } 
public  void HuffmanTreeCode()
   {//HUFFMAN编码
       int i,p,t,j;
   					
       Stack stack=new Stack();
       
       System.out.println("哈夫曼编码为:");
     for (i=0;i<n;i++)
      {  
          j=0;
          p=i;
    
        while (Integer.valueOf(HT[p][2]).intValue()!=0)
         {//从结点回溯,左孩子为0,右孩子为1
           
            if (HT[p][3].equals("left_child")) 
                { 
                  stack.push("0");
                  j++;
                 }
         
         
             else if (HT[p][3].equals("right_child"))
                 { 
                   stack.push("1");
                   j++;
                  }
          
             p=Integer.valueOf(HT[p][2]).intValue();
           }
  
   
         for(t=0;t<j;t++)
           HT[i][0]=HT[i][0].concat(stack.pop().toString());
           System.out.print(HT[i][1]+"：");
           System.out.print(HT[i][0]);
           System.out.println();
    
       }
    }
public  void HuffmanTreeEncoding()throws IOException
 {//将句子进行编码
     int i,j,position;
     String s1;
    //Huffman c=new   Huffman();  
      InputStreamReader ir = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(ir);
    do                      
    {     
          i=0;position=0;
        
          System.out.println("输入要编码的句子:");
          s1=in.readLine();
        
        if(s1.equals("exit"))
          System.exit(0);  //退出循环  
           
          String coding[]=new String[s1.length()];
        
           
   
    
       while (position<s1.length()) 
         {  
            for(j=0;j<n;j++)
             {
               if (HT[j][1].equals(s1.charAt(position)+"")) //字母吻合则用代码取代
                { 
                    coding[position]=HT[j][0];
                    break;
                 }
        
              }
     
              position++;  
           } 
        
         System.out.println("编码结果:");
         
      for(i=0;i<coding.length;i++)
         System.out.print(coding[i]);
         System.out.println();
         
         System.out.println("你要译码吗y/n:");
          s1=in.readLine();
        if(s1.equals("y"))
        c.HuffmanTreeDecoding(coding );
         else continue;
    }while(true);
 }
 
public void HuffmanTreeDecoding(String coding[])
   { //HUFFMAN译码过程,将代码翻译为句子
    
       int i,position=0,j;
       //System.out.println( coding.length);
      
       String   s2[]=new String[coding.length];
 
     while (position<coding.length) 
     {   
       for(j=0;j<n;j++)
         {
           if (HT[j][0].equals(coding[position])) //代码吻合则用字母取代
              {
             	s2[position]=HT[j][1];
             	break;
               }
        
          }
     
        position++;  
      }
        
        System.out.println("译码结果:");
        
        for(i=0;i<s2.length;i++)
         System.out.print(s2[i]);
         System.out.println(); 
         
          
    }
  		
}