赫夫曼编码

[java]代码库
class HTNode{
    public int weight;
    public int parent,lchild,rchild;
     
    public HTNode(int weight) {
        this.weight=weight;
        this.parent=0;
        this.lchild=0;
        this.rchild=0;
    }
     
    @Override
    public String toString() {
        return "(w:"+this.weight+",l:"+this.lchild+",r:"+this.rchild+",p:"+this.parent+")";
    }
}
 
public class 例6_6_2 {
     
    public static HTNode[] huffmanTreeBuild(int[] w){
        if(w.length<=1)return null;
        int m=2*w.length-1;
        HTNode[] ht=new HTNode[m];
        for (int i = 0; i < w.length; ++i) {
            ht[i]=new HTNode(w[i]);
        }
         
        for (int i = w.length; i < m; ++i) {
            ht[i]=new HTNode(0);
        }
         
        for (int i = w.length; i < m; ++i) {
            int[] spc=select(ht,i);
            ht[spc[0]].parent=i;
            ht[spc[1]].parent=i;
             
            if(ht[spc[1]].lchild==0 && ht[spc[1]].rchild==0){
                ht[i].lchild=spc[1];
                ht[i].rchild=spc[0];
            }else{
                ht[i].lchild=spc[0];
                ht[i].rchild=spc[1];
            }
             
            ht[i].weight=ht[spc[0]].weight+ht[spc[1]].weight;
        }
        return ht;
    }
     
    public static String[] huffmanTree(HTNode[] ht,int n){
        String[] hc=new String[n];
        for (int i = 0; i < n; i++) {
            String cd="";
            for (int c = i,f=ht[i].parent; f != 0; c=f,f=ht[f].parent) {
                if(ht[f].lchild==c){
                    cd=0+cd;
                }else{
                    cd=1+cd;
                }
            }
            hc[i]=ht[i].weight+":"+cd;
        }
        return hc;
    }
     
    public static String[] huffmanTree2(HTNode[] ht,int n){
        String[] hc=new String[n];
        int p,m;
        m=2*n-1;
        p=m-1;
        for (int i = 0; i < n; i++) {
            hc[i]=ht[i].weight+":";
        }
        for (int i = 0; i < m; i++) {
            ht[i].weight=0;
            if(ht[i].lchild==0 && ht[i].rchild==0){
                ht[i].lchild=-1;
                ht[i].rchild=-1;
            }
        }
         
        String cd="";
        while(p>=0){
            if(ht[p].weight==0){
                ht[p].weight=1;
                if(ht[p].lchild >= 0){
                    p=ht[p].lchild;
                    cd+="0";
                }else if(ht[p].rchild<0){
                    hc[p]+=cd;
                }
            }else if(ht[p].weight==1){
                ht[p].weight=2;
                if(ht[p].rchild>=0){
                    p=ht[p].rchild;
                    cd+="1";
                }
            }else{
                ht[p].weight=0;
                p=ht[p].parent;
                 
                 
                 
                if(cd.length()==0){
                    break;
                }
                cd=cd.substring(0,cd.length()-1);
            }       
        }
        return hc;
    }
     
    public static String[] huffmanTree(int[] w){
        return huffmanTree(huffmanTreeBuild(w), w.length);
    }
 
    private static int[] select(HTNode[] ht, int i) {
        int min1=Integer.MAX_VALUE;
        int min2=Integer.MAX_VALUE;
        int[] scp={0,0};
         
        for (int j = 0; j < i; j++) {
            if(ht[j].parent>0)continue;
            if((min1>ht[j].weight) || (min1==ht[j].weight && ht[j].rchild==0 && ht[j].lchild==0)){
                if((min1<min2) || (min1==min2 && ht[scp[0]].rchild==0 && ht[scp[0]].lchild==0) ){
                    scp[1]=scp[0];
                    min2=min1;
                }
                scp[0]=j;
                min1=ht[j].weight;
            }else if((min2>ht[j].weight) || (min2==ht[j].weight && ht[j].lchild==0 && ht[j].rchild==0)){
                scp[1]=j;
                min2=ht[j].weight;
            }
        }
         
        return scp;
    }
     
    public static void main(String[] args) {
        int[] w=new int[]{5,29,7,8,14,23,3,11};
        String[] str=huffmanTree(w);
        String[] str2=huffmanTree2(huffmanTreeBuild(w),w.length);
         
        for (String string : str) {
            System.out.println(string);
        }
         
        for (String string : str2) {
            System.out.println(string);
        }
    }
}
[代码运行效果截图]
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[java]代码库

[代码运行效果截图]

网友评论 (发表评论)

回复评论

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
