huffman.java

用java实现几个算法和应用程序,有一定的参考价值

public class HuffMan{

	private String[] huffmanStr; //数符串
	private int[] huffmanWeight;//对应的权值
	private Elem[] huffmanTree;
	// 哈夫曼编码表
	private String[] huffmanCode;
	// 字符个数
	protected int Num;
	protected int lenCode=0; //编码长度
	
	//Elem[] InnerNode; //保存内结点
	
	class Elem {
		int ID;//编号,便于后面的操作
		String str;
		int weight;
		int parent;
		int lchild;
		int rchild;

	public Elem(int id,String s, int w, int p, int l, int r) {
		ID = id;
		str = s;
		weight = w;
		parent = p;
		lchild = l;
		rchild = r;
	}//public Elem

}//class Elem
	
	public  HuffMan(int num, String[] huffmanStr, int[] huffmanWeight){
		Num = num;
		this.huffmanStr = huffmanStr;
		this.huffmanWeight = huffmanWeight;
		
		huffmanCode = new String[Num];
		//InnerNode = new Elem[num-1];
		
		//初始化huffmanTree
		huffmanTree  = new Elem[2*Num-1];
		huffmanTree();
		
		huffmanQueue hq = new huffmanQueue();

		int IdMin1;
		int IdMin2;
		int IdMerge;
		int WeightMin1;
		int WeightMin2;
		int WeightMerge;
		int currId=Num-1; //目前最大的ID
		//进行Num-1次合并操作,假设左边的元素不大于右边的元素
		
		for(int i=0;i<Num-1;i++){
			currId++;
			//strMin1 = hq.DeleteMin().
			IdMin1=hq.DeleteMin();
			WeightMin1 = huffmanTree[IdMin1].weight;
			
			IdMin2=hq.DeleteMin();
			WeightMin2 = huffmanTree[IdMin2].weight;
			
			IdMerge = currId;
			WeightMerge = WeightMin1 +WeightMin2;
			
			huffmanTree[IdMerge]= new Elem(IdMerge,"Merge"+i,WeightMerge,0,0,0);
			
			
			if(WeightMin1 > WeightMin2 ){
				huffmanTree[IdMerge].lchild = IdMin2;
				huffmanTree[IdMerge].rchild = IdMin1;
			}
			else{
				huffmanTree[IdMerge].lchild = IdMin1;
				huffmanTree[IdMerge].rchild = IdMin2;
			}
			
			huffmanTree[IdMin1].parent = IdMerge;
			huffmanTree[IdMin2].parent = IdMerge;
			
			//把新节点插入队列
			String text = "合并节点1,节点ID为: "+huffmanTree[IdMin1].ID+"节点字母为: "+huffmanTree[IdMin1].str+",频率为: "+huffmanTree[IdMin1].weight;
			text +=",节点2,节点ID为: "+huffmanTree[IdMin2].ID+"节点字母为: "+huffmanTree[IdMin2].str+",频率为: "+huffmanTree[IdMin2].weight;
			System.out.println(text);
			text="";
			text = "\n插入节点编号为:"+huffmanTree[IdMerge].ID+" "+huffmanTree[IdMerge].str+",频率为: "+huffmanTree[IdMerge].weight;
			System.out.println(text);
			
			text = "";
			text = "\n\n左结点为: "+huffmanTree[IdMerge].lchild+" 右结点为: "+huffmanTree[IdMerge].rchild+"\n";
			System.out.println(text);
			hq.queueInsert(IdMerge, WeightMerge);
			
			
		}
		//huffmanQueue();

	}
	
	//初始化huffmanTree
	public void huffmanTree(){
		for(int i=0;i<Num;i++){
			huffmanTree[i]= new Elem(i,huffmanStr[i],huffmanWeight[i],0,0,0);
		}
		
	}
	
	
	class huffmanQueue{
		int queueLen; //字符个数,也是队列的长度
		//String[] queueStr;
		int[] queueWeight;
		//String[] queueStr2;
		int[][] queueIDWeight; //二维数组,第一列存ID,第二列存weight,根据Weight递增排序
		
		
		
		public huffmanQueue(){
			queueIDWeight = new int[Num][Num];
			queueLen = Num;
			for(int i=0;i<Num;i++){
				queueIDWeight[i][0] = huffmanTree[i].ID;
				queueIDWeight[i][1] = huffmanTree[i].weight;
				System.out.println("节点编号为: "+queueIDWeight[i][0]+",频率为: "+queueIDWeight[i][1]);
			}
				                 
			//因为元素比较少,所以用冒泡法进行排序
			for(int i=Num-1;i>=0;i--){
				for(int j=0;j<i;j++){
					if(queueIDWeight[j][1]>queueIDWeight[j+1][1]){
						int tempID=queueIDWeight[j][0];
						int tempWeight = queueIDWeight[j][1];
						
						queueIDWeight[j][0] = queueIDWeight[j+1][0];
						queueIDWeight[j][1] = queueIDWeight[j+1][1];
	
						queueIDWeight[j+1][0] = tempID;
						queueIDWeight[j+1][1] =  tempWeight;
					}//if
				}//for
			}//for

			System.out.println("队列排序后:");
			for(int i=0;i<Num;i++){
				System.out.println("节点编号为: "+queueIDWeight[i][0]+",频率为: "+queueIDWeight[i][1]);
			}//for

		}//huffmanQueue()
		
		//返回ID
		public int DeleteMin(){
			
			/*
			System.out.println("DeleteMin前的情况:");
			for(int i=0;i<queueLen;i++){
				System.out.println("节点编号为: "+queueIDWeight[i][0]+",频率为: "+queueIDWeight[i][1]);
			}//for
			*/
			
			
			int idDelete;
			idDelete = queueIDWeight[0][0];
			System.out.println("DeleteMin后的情况: ");
			
			for(int i=0;i<queueLen-1;i++){
				queueIDWeight[i][0] = queueIDWeight[i+1][0];
				queueIDWeight[i][1] = queueIDWeight[i+1][1];
				
				System.out.println("编号为: "+queueIDWeight[i][0]+",频率为: "+queueIDWeight[i][1]);
			}
			
			//System.out.println("DeleteMin后的情况2222222 ");
			
			queueLen--;
			
			return idDelete;
		}
		
		public void queueInsert(int insertId,int insertWeight){
			System.out.println("调用函数时得到的值插入的节点的编号为:"+insertId+",频率为: "+insertWeight);
			int i=0;
			if(queueLen==0){
				queueIDWeight[i][0] = insertId;
				queueIDWeight[i][1] = insertWeight;
			}
			else{
				while(queueIDWeight[i][1]<=insertWeight && i<queueLen){
					i++;
				}
				
					//保存后面的值
					for(int j=queueLen;j>i;j--){
						queueIDWeight[j][0]=queueIDWeight[j-1][0];
						queueIDWeight[j][1]=queueIDWeight[j-1][1];
					}
					queueIDWeight[i][0] = insertId;
					queueIDWeight[i][1] = insertWeight;
				
			}
			queueLen++;
			
		}
		
		public int getQueueLen(){
			return queueLen;
		}
		
		
	}
	
	public String huffmanCode(int id){
		String strCode="";
		int pa=0;
		
		System.out.println();
		/*pa = huffmanTree[id].parent;
		System.out.println("节点"+id+"即: "+huffmanTree[id].str+", 的父节点为: "+pa+huffmanTree[pa].str);
		if(id == huffmanTree[pa].lchild){
			strCode ="0"+strCode;
		}
		else if(id == huffmanTree[pa].rchild){
			strCode ="1"+strCode;
		}
			id = pa;*/
		
		
		while(id!=2*Num-2){
			pa = huffmanTree[id].parent;
			System.out.println("节点"+id+"即: "+huffmanTree[id].str+", 的父节点为: "+pa+huffmanTree[pa].str);
			if(id == huffmanTree[pa].lchild){
				System.out.println("是它的左孩子");
				strCode ="0"+strCode;
			}
			else if(id == huffmanTree[pa].rchild){
				System.out.println("是它的左孩子");
				strCode ="1"+strCode;
			}
			id = pa;
		}	
		
		return strCode;
	}
	
	
	public String[] huffmanCodeArray(){
		for(int i=0;i<Num;i++){
			huffmanCode[i]=huffmanCode(i);
		}
		return huffmanCode;
	}
	
	public int getLenCode(){
		for(int i=0;i<Num;i++){
			lenCode +=huffmanTree[i].weight*huffmanCode[i].length();
		}
		return lenCode;
	}
	
	
	public static void main(String[] args){
		int Count = 4;
		String[] strhuff0 = {"A","B","C","D"};
		int[] weight0 ={50,10,25,15};
		
		HuffMan hf = new HuffMan(Count,strhuff0,weight0);
		String[] strCode = hf.huffmanCodeArray();
		System.out.println("\n\n******************");
		for(int i=0;i<strCode.length;i++)
			System.out.println(strhuff0[i]+" 的编码为: "+strCode[i]);
		System.out.println("编码的总长度为: "+hf.getLenCode());
	}//main

	
	
	
}