课程设计---哈夫曼树的编码与解码（Java详解）
目录
一.设计任务&&要求：
二.方案设计报告：
2.1 哈夫曼树编码&译码的设计原理：
2.3设计目的：
2.3设计的主要过程：
2.4程序方法清单：
三.整体实现源码：
四.运行结果展示：
五.总结与反思：
一.设计任务&&要求：
题目要求：测试数据是一段任意的英文，也可以是一段完整的中文，采用哈夫曼算法进行编码，可输出对应的字符编码的解码
哈夫曼编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景，是数据压缩中的一个重要理论依据。对输入的一串文字符号实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出字符串。要求完成以下功能：
1.针对给定的字符串，建立哈夫曼树。
2.生成哈夫曼编码。
3.对编码字符串译码。
二.方案设计报告：
2.1 哈夫曼树编码&译码的设计原理：
- 哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在数据通信中，通常需要将传送文字转换成由二进制字符0，1组成的二进制串，称之为编码。构建一个哈夫曼树，设定哈夫曼树中的左分支为0，右分支代表1，则从根结点到每个叶子节点所经过的路径组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可以有效缩短传送文字的总长度。哈夫曼树则是用于构造使编码总长最短，最节省空间成本的编码方案。
-
2.3设计目的：
-
(1) 巩固和加深对数据结构课程所学知识的理解，了解并掌握数据结构与算法的设计方法；
(2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
(3) 提高综合运用所学的理论知识和方法，独立分析和解决问题的能力；
(4) 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；
(5) 培养查阅资料，独立思考问题的能力。
2.3设计的主要过程：
1.哈夫曼树叶子节点的创建
叶子节点需要存储字符，及其出现的频率，指向左右子树的指针和将来字符所编码成的二进制数字。这里用一个静态内部来来初始化树的叶子节点：
//用一个静态内部类来初始化树的节点 static class Node{ char ch; //记录字符 int freq; //统计每个字符出现的频次 Node left; Node right; String code; //编码 public Node(char ch) { this.ch = ch; } public Node(int freq, Node left, Node right) { this.freq = freq; this.left = left; this.right = right; } //判断是否是叶子节点->哈夫曼树是满二叉树 boolean isLeaf(){ return left == null; } public char getCh() { return ch; } public void setCh(char ch) { this.ch = ch; } public int getFreq() { return freq; } public void setFreq(int freq) { this.freq = freq; } //重写的toString 方法只需要打印字符和其对应的频次即可 @Override public String toString() { return "Node{" + "ch=" + ch + ", freq=" + freq + '}'; } }2.构建哈夫曼树
构建过程：首先要统计每个字符出现的频率①.将统计了出现频率的字符，放入优先级队列中，利用优先级队列的特点，将字符按照出现的频率从小到大排序②.每次出队两个频次最低的元素，给它们找一个父亲节点③.将父亲节点放入队列中，重复②~③两个步骤④.当队列中只剩一个元素时，哈夫曼树就构建完了
//构造哈夫曼树 //->由于这里是一个自定义的类，我们需要传入比较器，按照节点的频次进行比较 PriorityQueue q = new PriorityQueue( //通过Comparator 的方法来获得Node节点的其中一个属性 Comparator.comparingInt(Node::getFreq) ); for(Node node : hash.values()){ q.offer(node); } while(q.size() >= 2){ Node x = q.poll(); Node y = q.poll(); int freq = x.freq + y.freq; q.offer(new Node(freq,x,y)); }3.哈夫曼编码
通过将每个叶子节点保存好的字符编码利用StringBuilder中的append（）方法拼接起来后返回即可
//编码操作： public String encode(){ char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); for(char c : chars){ sb.append(hash.get(c).code); } return sb.toString(); }4.哈夫曼译码
从根节点开始，寻找数字对应的字符编码,如果是0向右走，如果是数字1向左走，如果没有走到头(一个字符的编码结尾)，每一步数字的索引cur++，每找到一个编码字符，在将node重置为根节点,接着重个节点开始继续往下寻找,一直找到字符串末尾即可
/** * 从根节点开始，寻找数字对应的字符 * 数字是0 向右走，数字是1 向左走 * 如果没有走到头，每一步数字的索引 cur++ * 走到头就可以 找到编码字符，再将node 重置为根节点 * @param str * @return */ //解码操作： public String decode(String str){ char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); int cur = 0; Node node = root; while(cur- 大致模块图：
设计流程图：
2.4程序方法清单：
①.构造哈夫曼树：public HuffmanTree(){
}//这里我选择在函数的构造方法中将哈夫曼树给先构造完
②.编码：public String encode(){};
③.解码:pulbic String decode(){};
④.找到编码，并计算其对应的bit位：private int findCode(Node node,StringBuilder code){};
⑤.打印菜单:menu(){};
⑥.测试函数：main(){};
模块展示：
三.整体实现源码：
import java.util.*; public class HuffmanTree { //用一个静态内部类来初始化树的节点 static class Node{ char ch; //记录字符 int freq; //统计每个字符出现的频次 Node left; Node right; String code; //编码 public Node(char ch) { this.ch = ch; } public Node(int freq, Node left, Node right) { this.freq = freq; this.left = left; this.right = right; } //判断是否是叶子节点->哈夫曼树是满二叉树 boolean isLeaf(){ return left == null; } public char getCh() { return ch; } public void setCh(char ch) { this.ch = ch; } public int getFreq() { return freq; } public void setFreq(int freq) { this.freq = freq; } //重写的toString 方法只需要打印字符和其对应的频次即可 @Override public String toString() { return "Node{" + "ch=" + ch + ", freq=" + freq + '}'; } } String str; Node root; Map hash = new HashMap(); public HuffmanTree(){ } public HuffmanTree(String str){ this.str = str; //统计字符出现的频次 char[] chars = str.toCharArray(); for(char ch : chars){ if(!hash.containsKey(ch)){ hash.put(ch,new Node(ch)); } Node node = hash.get(ch); node.freq++; } for(Node node : hash.values()){ System.out.println(node); } //构造哈夫曼树 //->由于这里是一个自定义的类，我们需要传入比较器，按照节点的频次进行比较 PriorityQueue q = new PriorityQueue( //通过Comparator 的方法来获得Node节点的其中一个属性 Comparator.comparingInt(Node::getFreq) ); for(Node node : hash.values()){ q.offer(node); } while(q.size() >= 2){ Node x = q.poll(); Node y = q.poll(); int freq = x.freq + y.freq; q.offer(new Node(freq,x,y)); } root = q.poll(); //System.out.println(root); //计算每个字符的编码 以及其一共包含的bit位 System.out.println("输出编码信息:"); int sum = findCode(root,new StringBuilder()); for(Node node : hash.values()){ //打印节点及其编码信息 System.out.println(node + " " + node.code); } System.out.println("总共占有的bit位是：" + sum); } //找到编码，并计算其对应的bit位 private int findCode(Node node,StringBuilder code){ int sum = 0; if(node.isLeaf()){ //找到编码 并计算字符串编码后所占的bits node.code = code.toString(); sum = node.freq * code.length(); }else{ sum += findCode(node.left,code.append("0")); code.deleteCharAt(code.length() - 1); sum += findCode(node.right,code.append("1")); code.deleteCharAt(code.length() - 1); } return sum; } //编码操作： public String encode(){ char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); for(char c : chars){ sb.append(hash.get(c).code); } return sb.toString(); } /** * 从根节点开始，寻找数字对应的字符 * 数字是0 向右走，数字是1 向左走 * 如果没有走到头，每一步数字的索引 cur++ * 走到头就可以 找到编码字符，再将node 重置为根节点 * @param str * @return */ //解码操作： public String decode(String str){ char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); int cur = 0; Node node = root; while(cur ",i*100/(all_block_nums-1)); for(int j = 1;j
- 大致模块图：
