hmtree.java

java编写的哈夫蔓编码译码器（绝对原创）

package huff;

import java.util.*;
public class HmTree {
	private final int OK=1;
	private final int INIT_NODE_NUMBER=82;
    private TreeNode[] node=new TreeNode[INIT_NODE_NUMBER/2];//node为普通节点
    private TreeNode[] leavs=new TreeNode[INIT_NODE_NUMBER/2];//leavs为叶子节点
    private ArrayList<TreeNode> nodeList=new ArrayList<TreeNode>();
    private char[] charecters=new char[INIT_NODE_NUMBER/2];
    private TreeNode root;
    private ArrayList<TreeNode> treeContainer=new ArrayList<TreeNode>();    
    public HmTree(){
                           	
    }    
    public HmTree(String txt){
    	for(int i=0;i<INIT_NODE_NUMBER/2;i++){
    		node[i]=new TreeNode();
    		leavs[i]=new TreeNode();
    	}
    	getCharecters();
    	for(int i=0;i<leavs.length;i++){
    		leavs[i].setKey(charecters[i]);
    	}
    	for(int i=0;i<node.length;i++){
    		node[i].setKey('~');
    	}
    	getKeyPower(txt);
    	
    	
    	this.addToList();
    	
    	for(int i=0;;i++){
    		
    		node[i].setLchild(nodeList.get(0));
    		node[i].setRchild(nodeList.get(1));
    		node[i].setPower(nodeList.get(0).getPower()+nodeList.get(1).getPower());
    		treeContainer.add(nodeList.remove(0));
    		treeContainer.add(nodeList.remove(0));
    		int t=0;
    		//System.out.println("nodeList size()"+nodeList.size()); 
    		if(nodeList.size()==0){
    			treeContainer.add(node[i]);
    			break;
    		}
    		while(true){
    			if(t>=nodeList.size()){nodeList.add(node[i]);break;}
    			if(nodeList.get(t).getPower()>node[i].getPower()){
    				nodeList.add(t,node[i]);
    				//System.out.println("add"+node[i].getPower()+"to nodelist"+t);
    				break;
    			}
    			t++;
    		}
    		this.root=node[i+1];
    	}
    	this.root.setCode(Character.toString('0'));
    	initCode(root);
    	for(int i=0;i<treeContainer.size();i++){
    		String code=treeContainer.get(i).getCode();
    		StringBuilder sb=new StringBuilder(code);
    		sb.deleteCharAt(0);
    		code=sb.toString();
    		treeContainer.get(i).setCode(code);
    	}
    	
    }
   /* private int setHMtree(ArrayList<TreeNode> container){
    	this.treeContainer.clear();
    	this.treeContainer.addAll(container);
    	return OK;
    }*/
    private int initCode(TreeNode root){    	
    	TreeNode p=root;  
    		if(p.getLchild()!=null){
    		     p.getLchild().setCode(p.getCode()+'0');
    		     initCode(p.getLchild());
    		}
    		if(p.getRchild()!=null){
    			 p.getRchild().setCode(p.getCode()+'1');
    			 initCode(p.getRchild());
    		}                 	    	   	
    	return OK;
    }
    public ArrayList<TreeNode> getTree(){
    	return treeContainer;
    }
    public static String deCode(ArrayList<TreeNode>tree,String code){
    	String txt="";
    	TreeNode root=tree.get(tree.size()-1);
    	/*for(int i=0;i<tree.size();i++)
    	{
    		System.out.println(tree.get(i).getPower());
    	}*/
    	TreeNode p=root;
    	System.out.println(p.getPower());
    	System.out.println(p.getKey());
    	System.out.println(code);
    	for(int i=0;i<code.length();i++){
    		if(p.getLchild()==null&&p.getRchild()==null){
    			i--;
    			//System.out.println("code["+i+"]:"+p.getPower()+" leavs "+p.getKey());
    			txt=txt+p.getKey();p=root;continue;
    		}
    		else if(code.charAt(i)=='0'){
    			p=p.getLchild();
    			//System.out.println("code["+i+"]=="+code.charAt(i)+"  "+p.getPower()+"to L");
    			continue;
    		}
    		else if(code.charAt(i)=='1'){
    			p=p.getRchild();
    			//System.out.println("code["+i+"]=="+code.charAt(i)+"  "+p.getPower()+"to R");
    			continue;
    		}
    	  }
    	txt=txt+p.getKey();
    	return txt;
    	
    }
    public static String code(ArrayList<TreeNode> c,String txt){
    	String code="";
    	char[] chars=new char[81];
    	String[] strings=new String[81];
    	for(int i=0;i<c.size();i++){
    		chars[i]=c.get(i).getKey();
    		strings[i]=c.get(i).getCode();
    	}
    	txt=txt.toLowerCase();
    	for(int i=0;i<txt.length();i++){
    		int j=80;
    		for( ;j>=0;j--)
    		if(txt.charAt(i)==chars[j]){
    			System.out.println(chars[j]+" code is"+strings[j]);
    			code=code+strings[j];
    			break;
    		}
    		if(j==-1){for(int t=80;t>=0;t--){
                if(chars[t]=='*'){code=code+strings[t];}     			
    		}
    			
    		}
    	}
    	StringBuffer sb=new StringBuffer(code);
    	for(int i=50,offset=0;i<sb.length()-offset;i=i+50,offset++){
    		sb=sb.insert(i+offset,'\n');
    	}
                code=sb.toString();    	
    	    	return code;
    }
    private void addToList(){    	
	     for(int i=0;i<leavs.length;i++){
	           this.nodeList.add(leavs[i]);    	   
	       }
	     for(int i=1;i<nodeList.size();i++)
	    	 for(int j=0;j<i;j++){
	    		 if(nodeList.get(i).getPower()<nodeList.get(j).getPower()){
	    			 nodeList.add(j,nodeList.remove(i));
	    		 }
	    	 }
	     for(int i=0;i<nodeList.size();i++){ 	 
	      //System.out.println("nodeList "+i+" "+nodeList.get(i).getPower());
	     }
	     
    }
    private void getCharecters(){  
		charecters[0]='a';
		charecters[1]='b'; charecters[2]='c'; charecters[3]='d'; 
		charecters[4]='e'; charecters[5]='f'; charecters[6]='g';    	
		charecters[7]='h'; charecters[8]='i'; charecters[9]='j';   	
		charecters[10]='k'; charecters[11]='l';  charecters[12]='m';    	
		charecters[13]='n'; charecters[14]='o';  charecters[15]='p';    	
		charecters[16]='q'; charecters[17]='r';  charecters[18]='s';    	
		charecters[19]='t';    	charecters[20]='u';    	charecters[21]='v';   
		charecters[22]='w';   	charecters[23]='x';   	charecters[24]='y';  
		charecters[25]='z';    	charecters[26]='0';   	charecters[27]='1';   
		charecters[28]='2';   	charecters[29]='3';   	charecters[30]='4';   
		charecters[31]='5';   	charecters[32]='6';    	charecters[33]='7';  
		charecters[34]='8';    	charecters[35]='9';    	charecters[36]=',';    
		charecters[37]='.';    	charecters[38]='?';    	charecters[39]=' ';  	
		charecters[40]='*';
    }
    private void getKeyPower(String txt){
    	//初始化各个节点的权值，没有键值的节点初始化为-1
    	int[] counter=new int[INIT_NODE_NUMBER/2];
    	for(int i=0;i<counter.length;i++){counter[i]=0;}
    	for(int i=0;i<=txt.length()-1;i++){
    		switch (txt.charAt(i)){
    		case 'a':counter[0]++;break;
    		case 'b':counter[1]++;break;
    		case 'c':counter[2]++;break;
    		case 'd':counter[3]++;break;
    		case 'e':counter[4]++;break;
    		case 'f':counter[5]++;break;
    		case 'g':counter[6]++;break;
    		case 'h':counter[7]++;break;
    		case 'i':counter[8]++;break; 		
    		case 'j':counter[9]++;break;
    		case 'k':counter[10]++;break;
    		case 'l':counter[11]++;break;
    		case 'm':counter[12]++;break;
    		case 'n':counter[13]++;break;
    		case 'o':counter[14]++;break;
    		case 'p':counter[15]++;break;
    		case 'q':counter[16]++;break;
    		case 'r':counter[17]++;break;
    		case 's':counter[18]++;break;
    		case 't':counter[19]++;break;
    		case 'u':counter[20]++;break;
    		case 'v':counter[21]++;break;
    		case 'w':counter[22]++;break;
    		case 'x':counter[23]++;break;
    		case 'y':counter[24]++;break;
    		case 'z':counter[25]++;break;
    		case '0':counter[26]++;break;
    		case '1':counter[27]++;break;
    		case '2':counter[28]++;break;
    		case '3':counter[29]++;break;
    		case '4':counter[30]++;break;
    		case '5':counter[31]++;break;
    		case '6':counter[32]++;break;
    		case '7':counter[33]++;break;
    		case '8':counter[34]++;break;
    		case '9':counter[35]++;break;
    		case ',':counter[36]++;break;
    		case '.':counter[37]++;break;
    		case '?':counter[38]++;break;
    		case ' ':counter[39]++;break;
    		default: counter[40]++;
    		}
    	}
    	for(int i=0;i<INIT_NODE_NUMBER/2;i++){
    	leavs[i].setPower(counter[i]);
    	//System.out.println("set "+leavs[i].getKey()+" power"+counter[i]);
    	}
    	for(int i=0;i<INIT_NODE_NUMBER/2;i++){
    	node[i].setPower(-1);
    	}
    	
    }
}