Code666 (代码贴、代码片段)

[Java] 赫夫曼编码 →→→→→进入此内容的聊天室

来自 , 2020-01-02, 写在 Java, 查看 123 次.
URL http://www.code666.cn/view/2dffbc47
  1.  
  2. class HTNode{
  3.         public int weight;
  4.         public int parent,lchild,rchild;
  5.        
  6.         public HTNode(int weight) {
  7.                 this.weight=weight;
  8.                 this.parent=0;
  9.                 this.lchild=0;
  10.                 this.rchild=0;
  11.         }
  12.        
  13.         @Override
  14.         public String toString() {
  15.                 return "(w:"+this.weight+",l:"+this.lchild+",r:"+this.rchild+",p:"+this.parent+")";
  16.         }
  17. }
  18.  
  19. public class 例6_6_2 {
  20.        
  21.         public static HTNode[] huffmanTreeBuild(int[] w){
  22.                 if(w.length<=1)return null;
  23.                 int m=2*w.length-1;
  24.                 HTNode[] ht=new HTNode[m];
  25.                 for (int i = 0; i < w.length; ++i) {
  26.                         ht[i]=new HTNode(w[i]);
  27.                 }
  28.                
  29.                 for (int i = w.length; i < m; ++i) {
  30.                         ht[i]=new HTNode(0);
  31.                 }
  32.                
  33.                 for (int i = w.length; i < m; ++i) {
  34.                         int[] spc=select(ht,i);
  35.                         ht[spc[0]].parent=i;
  36.                         ht[spc[1]].parent=i;
  37.                        
  38.                         if(ht[spc[1]].lchild==0 && ht[spc[1]].rchild==0){
  39.                                 ht[i].lchild=spc[1];
  40.                                 ht[i].rchild=spc[0];
  41.                         }else{
  42.                                 ht[i].lchild=spc[0];
  43.                                 ht[i].rchild=spc[1];
  44.                         }
  45.                        
  46.                         ht[i].weight=ht[spc[0]].weight+ht[spc[1]].weight;
  47.                 }
  48.                 return ht;
  49.         }
  50.        
  51.         public static String[] huffmanTree(HTNode[] ht,int n){
  52.                 String[] hc=new String[n];
  53.                 for (int i = 0; i < n; i++) {
  54.                         String cd="";
  55.                         for (int c = i,f=ht[i].parent; f != 0; c=f,f=ht[f].parent) {
  56.                                 if(ht[f].lchild==c){
  57.                                         cd=0+cd;
  58.                                 }else{
  59.                                         cd=1+cd;
  60.                                 }
  61.                         }
  62.                         hc[i]=ht[i].weight+":"+cd;
  63.                 }
  64.                 return hc;
  65.         }
  66.        
  67.         public static String[] huffmanTree2(HTNode[] ht,int n){
  68.                 String[] hc=new String[n];
  69.                 int p,m;
  70.                 m=2*n-1;
  71.                 p=m-1;
  72.                 for (int i = 0; i < n; i++) {
  73.                         hc[i]=ht[i].weight+":";
  74.                 }
  75.                 for (int i = 0; i < m; i++) {
  76.                         ht[i].weight=0;
  77.                         if(ht[i].lchild==0 && ht[i].rchild==0){
  78.                                 ht[i].lchild=-1;
  79.                                 ht[i].rchild=-1;
  80.                         }
  81.                 }
  82.                
  83.                 String cd="";
  84.                 while(p>=0){
  85.                         if(ht[p].weight==0){
  86.                                 ht[p].weight=1;
  87.                                 if(ht[p].lchild >= 0){
  88.                                         p=ht[p].lchild;
  89.                                         cd+="0";
  90.                                 }else if(ht[p].rchild<0){
  91.                                         hc[p]+=cd;
  92.                                 }
  93.                         }else if(ht[p].weight==1){
  94.                                 ht[p].weight=2;
  95.                                 if(ht[p].rchild>=0){
  96.                                         p=ht[p].rchild;
  97.                                         cd+="1";
  98.                                 }
  99.                         }else{
  100.                                 ht[p].weight=0;
  101.                                 p=ht[p].parent;
  102.                                
  103.                                
  104.                                
  105.                                 if(cd.length()==0){
  106.                                         break;
  107.                                 }
  108.                                 cd=cd.substring(0,cd.length()-1);
  109.                         }              
  110.                 }
  111.                 return hc;
  112.         }
  113.        
  114.         public static String[] huffmanTree(int[] w){
  115.                 return huffmanTree(huffmanTreeBuild(w), w.length);
  116.         }
  117.  
  118.         private static int[] select(HTNode[] ht, int i) {
  119.                 int min1=Integer.MAX_VALUE;
  120.                 int min2=Integer.MAX_VALUE;
  121.                 int[] scp={0,0};
  122.                
  123.                 for (int j = 0; j < i; j++) {
  124.                         if(ht[j].parent>0)continue;
  125.                         if((min1>ht[j].weight) || (min1==ht[j].weight && ht[j].rchild==0 && ht[j].lchild==0)){
  126.                                 if((min1<min2) || (min1==min2 && ht[scp[0]].rchild==0 && ht[scp[0]].lchild==0) ){
  127.                                         scp[1]=scp[0];
  128.                                         min2=min1;
  129.                                 }
  130.                                 scp[0]=j;
  131.                                 min1=ht[j].weight;
  132.                         }else if((min2>ht[j].weight) || (min2==ht[j].weight && ht[j].lchild==0 && ht[j].rchild==0)){
  133.                                 scp[1]=j;
  134.                                 min2=ht[j].weight;
  135.                         }
  136.                 }
  137.                
  138.                 return scp;
  139.         }
  140.        
  141.         public static void main(String[] args) {
  142.                 int[] w=new int[]{5,29,7,8,14,23,3,11};
  143.                 String[] str=huffmanTree(w);
  144.                 String[] str2=huffmanTree2(huffmanTreeBuild(w),w.length);
  145.                
  146.                 for (String string : str) {
  147.                         System.out.println(string);
  148.                 }
  149.                
  150.                 for (String string : str2) {
  151.                         System.out.println(string);
  152.                 }
  153.         }
  154. }
  155.  

回复 "赫夫曼编码"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666