[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);
}
}
}
[代码运行效果截图]
初级程序员
by: andyhu2017 发表于:2017-09-01 14:43:09 顶(0) | 踩(0) 回复
好吊,好代码。
回复评论