2. 哈夫曼编码的实现。对教材P167中习题5.18,编码实现哈夫曼编码树,并对“Chapter Graphs surveys the most important graph processing problems including depth-first search breadth first search minimum spanning trees and shortest paths ”语句使用构造的哈夫曼编码进行压缩(不区分大小写),对压缩后的数据进行解压缩。
(由于运行结果图片无法上传,故请见谅,请读者自行复制代码调试)
package main;
public class note {
private note left;
private note right;
private int weight;
private String letter;
private String code;
public note(){
this.left=null;
this.right=null;
this.weight=0;
this.letter="";
this.code="";
}
/*
* 用于获取相应的属性
*/
public note getleft(){
return this.left;
}
public note getright(){
return this.right;
}
public int getweight(){
return this.weight;
}
public String getletter(){
return this.letter;
}
public String getcode(){
return this.code;
}
/*
* 用于设置相应的属性
*/
public void setleft(note left){
this.left=left;
}
public void setright(note right){
this.right=right;
}
public void setweight(int weight){
this.weight=weight;
}
public void setletter(String letter){
this.letter=letter;
}
public void setcode(String code){
this.code=code;
}
}
package main;
import java.util.*;
public class huffman {
public static void main(String[] args){
note[] Notes=new note[27];
ArrayList list=new ArrayList();
list=newlist(Notes);
note n=new note();
n=gettree(list);
list=getcode(n);
//输出每个字符对应的编码。
for(int j=0;j<list.size();j++){
n=(note)list.get(j);
System.out.print(n.getletter()+": ");
System.out.println(n.getcode());
}
String str="Chapter Graphs surveys the most important graph processing problems including depth first search breadth first search minimum spanning trees and shortest paths ";
str=str.toLowerCase();
System.out.println(str);//输出原始字符串。
str=compress(str,list);
System.out.println(str);//输出压缩后的字符编码。
str=unzip(str,list);
System.out.println(str);//输出解压缩后的字符串。
}
//初始化list和所有的节点
public static ArrayList newlist(note[] Notes){
for(int i=0;i<Notes.length;i++){
Notes[i]=new note();
}
Notes[0].setletter(" ");
Notes[0].setweight(173);
Notes[1].setletter("a");
Notes[1].setweight(68);
Notes[2].setletter("b");
Notes[2].setweight(13);
Notes[3].setletter("c");
Notes[3].setweight(26);
Notes[4].setletter("d");
Notes[4].setweight(35);
Notes[5].setletter("e");
Notes[5].setweight(102);
Notes[6].setletter("f");
Notes[6].setweight(18);
Notes[7].setletter("g");
Notes[7].setweight(17);
Notes[8].setletter("h");
Notes[8].setweight(49);
Notes[9].setletter("i");
Notes[9].setweight(58);
Notes[10].setletter("j");
Notes[10].setweight(2);
Notes[11].setletter("k");
Notes[11].setweight(6);
Notes[12].setletter("l");
Notes[12].setweight(34);
Notes[13].setletter("m");
Notes[13].setweight(21);
Notes[14].setletter("n");
Notes[14].setweight(55);
Notes[15].setletter("o");
Notes[15].setweight(59);
Notes[16].setletter("p");
Notes[16].setweight(16);
Notes[17].setletter("q");
Notes[17].setweight(1);
Notes[18].setletter("r");
Notes[18].setweight(48);
Notes[19].setletter("s");
Notes[19].setweight(51);
Notes[20].setletter("t");
Notes[20].setweight(77);
Notes[21].setletter("u");
Notes[21].setweight(24);
Notes[22].setletter("v");
Notes[22].setweight(9);
Notes[23].setletter("x");
Notes[23].setweight(2);
Notes[24].setletter("w");
Notes[24].setweight(19);
Notes[25].setletter("y");
Notes[25].setweight(16);
Notes[26].setletter("z");
Notes[26].setweight(1);
ArrayList list=new ArrayList(27);
for(int i=0;i<27;i++){
list.add(Notes[i]);
}
return list;
}
//获取list集中的一个权重最小节点
public static note getmin(ArrayList list){
note min=new note();
note compare=new note();
min=(note) list.get(0);
for(int i=1;i<list.size();i++){
compare=(note)list.get(i);
if(min.getweight()>compare.getweight()){
min=compare;
}
}
return min;
}
//将list集中的两个权重最小节点合并成一个新节点并返回一个新的list。
public static ArrayList getnewlist(ArrayList list){
note l=new note();
note r=new note();
note n=new note();
//获取字母表的最小两个节点并合并成一个新节点
l=getmin(list);
n.setleft(l);
list.remove(l);
r=getmin(list);
n.setright(r);
list.remove(r);
//设置新节点的权重和包含的字母
n.setweight(l.getweight()+r.getweight());
n.setletter(l.getletter()+r.getletter());
list.add(n);
return list;
}
//获得最终的哈弗曼树
public static note gettree(ArrayList list){
note tree=new note();
while(list.size()!=1){
list=getnewlist(list);
}
tree=(note)list.get(0);
return tree;
}
//根据哈弗曼树形成相应的哈弗曼编码
public static ArrayList getcode(note tree){
ArrayList list=new ArrayList();
String code="";
String ch="";
note middle=new note();//中间辅助用的
note letters=new note();//字符
note[] Notes=new note[27];
list=newlist(Notes);
for(int i=0;i<list.size();i++){
letters=(note)list.get(i);
ch=letters.getletter();
if(tree.getletter().contains(ch)){
code="";
middle=tree;
while(middle.getleft()!=null||middle.getleft()!=null){
if(middle.getleft()!=null&&middle.getleft().getletter().contains(ch)){
code=code+"1";
middle=middle.getleft();
}
if(middle.getright()!=null&&middle.getright().getletter().contains(ch)){
code=code+"0";
middle=middle.getright();
}
}
letters.setcode(code);
list.remove(i);
list.add(i,letters);
}
}
return list;
}
//对字符串进行压缩。
public static String compress(String str,ArrayList list){
String codes="";
codes=str;
for(int j=0;j<list.size();j++){
codes=codes.replace(((note) list.get(j)).getletter(),((note) list.get(j)).getcode());
}
return codes;
}
//对已经压缩了的字符串进行解压缩。
public static String unzip(String code,ArrayList list){
String dates="";
//dates=code;
for(int i=0;i<code.length();){
for(int j=0;j<list.size();j++){
int index=code.indexOf(((note)list.get(j)).getcode(),i);
if(i==index){
i=i+((note)list.get(j)).getcode().length();
dates=dates+((note)list.get(j)).getletter();
break;
}
}
}
return dates;
}
}