链表与哈夫曼树

<!--[if !supportLists]-->一、<!--[endif]-->什么是链表？

链表是使用指针进行连接的一种数据结构，他可以提供比数组更加灵活的数据存储。

认识一下链表之前，先知道节点。

Class Node {
	Object data;/用于存储数据；
	Node next;//指向下一个的指针
}

一、哈夫曼编码

以哈夫曼树─即最优二叉树，路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

 

二、首先，需要一个Class LinkNode；结点类，用于保存节点的数据以及前一个与后一个节点的指针，这在C++中称之为指针，但是Java中是没有指针这个概念的。不过不妨碍理解。建立了一个结点类后，作为他的基础。代码如下：

public class HMF {
	private LinkNode [] nodes;
	
	public HMF(int[] data){
		nodes = new LinkNode[data.length];
		for(int i=0;i<data.length;i++){
			nodes[i]=new LinkNode();
			nodes[i].data=data[i];
		}
	}
	//对节点排序
	private void sort(LinkNode [] nodes){
		int a= nodes.length;
		for(int i=0;i<a;i++){
			for(int j=0;j<a-i-1;j++){
				if(nodes[j].data > nodes[j+1].data){
					//交换的不是数据，而是对象本身的位置
					LinkNode x =nodes[j];
					nodes[j]=nodes[j+1];
					nodes[j+1]=x;
				}
			}
		}
	}
	
	//创建哈夫曼树
	private LinkNode creatTree(){
		LinkNode [] nodes=this.nodes;//临时变量
		while(nodes.length>1){
			sort(nodes);
			LinkNode lk0=nodes[0];
			LinkNode lk1=nodes[1];
			
			//去最小的两个
			LinkNode lkn =new LinkNode();
			lkn.data=lk0.data+lk1.data;
			lkn.left=lk0;
			lkn.right=lk1;
			//新建一个小一个单位的数组
			LinkNode [] nodes2= new LinkNode[nodes.length-1];
			for(int i=2;i<nodes.length;i++){
				nodes2[i-2] =nodes[i];
			}
			
			nodes2[nodes.length-2]=lkn;
			
			nodes=nodes2;
		}
		return nodes[0];
	}
	//
	
	public void Code(){
		LinkNode root = this.creatTree();
		printTree(root," ");
	}
	public void printTree(LinkNode lk,String code){
		if(lk!=null){
			if(lk.left == null && lk.right == null)
				System.out.println(lk.data+"的编码是"+code);
				
			printTree(lk.left,code+"0");
			printTree(lk.right,code+"1");
			
		}
	}
	public static void main(String [] args){
		int [] test = { 3,5,1,6,2,7} ;
		HMF hum = new HMF(test);
		hum.Code();
	}
}