逻辑结构设计
分析可知哈夫曼树是二叉树,所以逻辑结构应该选择树形结构
存储结构设计
由于要存储二叉树的结点,所以二叉树的链式存储方式。链式存储可以更好的表现出二叉树中各个结点之间的关系,有左孩子,右孩子,和父节点三个指针,这样更加方便查找和遍历。
哈夫曼树由HuffmanTreeNode构成,每个结点包括结点的权值,父节点指针域,左右孩子指针域,和存编码的code属性。然后把这些结点通过链表按二叉树关系一个个存储到链表中。
主要操作设计
DataNode类:用来存储字符及其字符在输入的字符串中出现的次数,方便后期拿到字符的权值。
HuffmanTreeNode类,实现了Comparable接口,重写compareTo方法,方便实现两个结点的权值的比较,为后期创建哈夫曼树找最小权值结点提供方便。里面有data,保存字符数据,weight’用来存权值,lchild表示左孩子指针,rchild表示右孩子指针,parents表示父节点,code用来存编码好的哈夫曼编码。
LinkedNode类:是链表的结点类,有链表的结点的数据以及其指向下一结点的指针域。链表结点数据即存储HuffmanTreeNode类型的数据
LinkedNode类:是链表的结点类,有链表的结点的数据以及其指向下一结点的指针域。链表结点数据即存储HuffmanTreeNode类型的数据。
MyList类。是链表类,有头指针,尾指针,链表长度等属性。主要是写里面的构造方法,用传进的哈夫曼树结点数组,对其进行权值升序排列,将数组转成按权值升序的链表。还有add方法,也是向链表中添加结点,并保证其顺序必须升序
HuffmanTree类,有根节点,构造方法是通过传进来的Mylist类型的链表,进行创建哈夫曼树。
Huffman类。继承自Application类。写了以下几个静态方法:
(1) startFile() 方法主要初始化文件,要求从控制台输入字符串,并将字符串写入tobetrans.txt文件中。以用来后面对这些字符串做处理。
(2) getStringB()方法,是从tobetrans.txt文件中获取输入的字符串,并返回Stringbuffer字符串。
(3) getLinkedList(String sb) 根据字符串,将判断每个字符出现的次数,把次数作为权值,并根据此创建每一个字符的结点,并用这些结点创建Mylist类型的链表返回。
(4) getCodeing(HuffmanTreeNode leaf,String str)方法,对所有的叶子节点进行编码,运用递归方法,如果向左递归,则编码+‘0,向右递归则 +‘1’,当没有左右孩子时,就把编码加入此叶子结点的code属性中。
(5) CompressionBytes(StringBuffer sb)是 接收二进制字符串,转化byte数组的方法。
(6) Codeing() 方法是将调用getCodeing()方法将每个叶子节点编码,通过循环,把每个字符的编码拼接起来,然后调用CompreessionBytes(sb) 方法将此二进制字符串压缩成byte数组,并保存写入到codefile.txt文件中。
(7) getBytes() 方法 通过获取codefile.txt文件中的二进制数组,并将其转化成字节数组。
(8) decoding() 方法是解码方法,通过getBytes() 方法获取编码字节数组,并通过遍历字节数组,找到哈夫曼树的根节点,根根节点根据字节数组的01值遍历找到叶子节点输出其data值,并加入stringBuffer里面,并将此字符串写入textfile.txt文件中。
(9) Print()方法是调用getBytes()方法获取字节数组之后,将二进制字符串按一行50个字符写入codeprint.txt中。
(10) JavaFx的start方法 ,布局好面板,并给每个按钮添加点击事件,画出哈夫曼树。
技术难点与解决方法
哈夫曼树的构建算法:
解决方法和思路:
找到最小权值的两个结点,并把他们一个作为左结点右节点,把他们权值相加,并用此全值创建新的结点作为两个结点的父节点,并让此节点左右孩子指针分别指向两个子结点,两子结点也设置此节点为父节点,并把根节点改为父节点。
//根据传来数据的集合创建哈弗吗树
public HuffmanTree(MyList list) {
int size = list.getSize();
if (size > 1){
for (int i = 0; i < size - 1; i++) {
LinkedNode p = list.getHead().getNext();
//找到第一个叶子节点
while(p.getData().getParents() != null){
p = p.getNext();
}
HuffmanTreeNode min = p.getData();
p = p.getNext();
//找到第二个叶子节点
while(p.getData().getParents() != null){
p = p.getNext();
}
HuffmanTreeNode seMin = p.getData();
HuffmanTreeNode lchild = min;
HuffmanTreeNode rchild = seMin;
HuffmanTreeNode parents = new HuffmanTreeNode(lchild.getWeight()+rchild.getWeight());
parents.setLchild(lchild);
parents.setRchild(rchild);
lchild.setParents(parents);
rchild.setParents(parents);
list.Add(parents);
root=parents;
}
}else{
root = list.getHead().getNext().getData();
}
}
对哈夫曼树编码
解决方法和思路:
对所有的叶子节点进行编码,运用递归方法,如果向左递归,则编码+‘0‘,向右递归则 +‘1’,当没有左右孩子时,就把编码加入此叶子结点的code
//对每个叶子节点进行编码,并将编码存入code属性里面
public static void getCoding(HuffmanTreeNode leaf,String str){
String str1 = str;
String str2 = str;
if (leaf != null){
if (leaf.lchild == null && leaf.rchild==null){
leaf.setCode(str.toString());
}else {
str1 += "0";
getCoding(leaf.lchild,str1);
str2 += "1";
getCoding(leaf.rchild,str2);
}
}
}
/**
权值升序链表的获得
解决方法及思路:
根据字符串,用双层循环判断每个字符出现的次数,把次数作为权值,并根据此创建每一个字符的结点,并用这些结点创建Mylist类型的链表返回。
/** 根据sb遍历,建立字符出现的次数为权值,字符为data的节点DataNode
并根据这些节点建立DataNode数组
根据该节点数组建立一个权值升序的链表
返回该链表
**/
public static MyList getLinkedList(String sb){
ArrayList<DataNode> list = new ArrayList<>();
list.add(new DataNode(sb.charAt(0)));
for (int i = 1,j; i < sb.length(); i++) {
//判断出现次数
for (j = 0;j < list.size();j++){
if (sb.charAt(i) == list.get(j).getCh()){
list.get(j).setConstant(list.get(j).getConstant()+1);
break;
}
}
//如果最后一个
if (j == list.size()){
list.add(new DataNode(sb.charAt(i)));
}
}
HuffmanTreeNode[] tree = new HuffmanTreeNode[list.size()];
for (int k = 0; k < list.size(); k++) {
tree[k] = new HuffmanTreeNode(list.get(k).getCh(),list.get(k).getConstant());
}
MyList myList = new MyList(tree);
return myList;
}
哈夫曼树的画法
解决思路及方法:
找到构建好的树的根节点。如果有左孩子或右孩子并根据结点左右画线和⚪,如果没有则直接画圈,并用label标签把权值装进去,然后递归画出哈夫曼树。
public void drawTree(Pane pane,HuffmanTreeNode root,double X,double Y,int i){
// pane.getChildren().clear();
if (root != null){
Circle circle = new Circle(X,Y,20);
circle.setFill(null);
circle.setStroke(Color.BLACK);
String weight = "" + root.getWeight();
Label text1 = new Label(weight);
text1.setLayoutX(X-5);
text1.setLayoutY(Y-5);
if(root.lchild != null && root.rchild != null) {
Line l1 = new Line(X, Y+20, X-i+20, Y+100);
Label t0 = new Label("0");
t0.setLayoutX((X+X-i)/2 - 10);
t0.setLayoutY((Y+20+Y+100)/2);
Line l2 = new Line(X, Y+20, X+i-20, Y+100);
Label t1 = new Label("1");
t1.setLayoutX((X+X+i)/2 + 10);
t1.setLayoutY((Y+20+Y+100)/2);
pane.getChildren().addAll(circle, text1, l1, l2, t0, t1);
} else {
String str = "" + root.getData();
Label data = new Label(str);
data.setLayoutX(X-5);
data.setLayoutY(Y+25);
pane.getChildren().addAll(circle, text1, data);
}
drawTree(pane, root.lchild, X-i, Y+100, i-40);
drawTree(pane, root.rchild, X+i, Y+100, i-40);
}
}