我们都用过压缩软件,今天我们要讲的就是压缩软件的一种方法——哈夫曼树!
哈夫曼树其实是二叉树的一种。
我们给定一些权值作为二叉树的叶子节点,来构建一个二叉树,若带权路径长度达到最小,这样的二叉树成为最优二叉树,也就是我们说的哈夫曼树。
我们今天不仅要构建一个哈夫曼树,还要实现压缩一个字符串,让字符串以更短的方式表现出来。
准备工作:进行节点和编码类的设置。
Node类:
public class Node implements Comparable { private int data;// 节点的数据 private Node left;// 左节点 private Node right;// 右节点 private String sign;// 字符标志 /** * 构造方法 * * @param data要输入的数据 */ public Node(int data) { this.data = data; } /** * 构造方法 * * @param data要输入的数据 * @param left左节点 * @param right右节点 */ public Node(int data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } /** * 重写比较方法 */ public int compareTo(Object o) { double temp = this.data - ((Node) o).data; return temp > 0 ? 1 : temp == 0 ? 0 : -1;// 若原节点比比较节点大,返回1,相等返回0,小于返回-1 } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } public String getSign() { return sign; } public void setSign(String sign) { this.sign = sign; } }
Code类:
public class Code { private String sign;// 编码长度 private String node;// 编码 private int length;// 长度 public Code() { } public String getSign() { return sign; } public void setSign(String sign) { this.sign = sign; } public String getNode() { return node; } public void setNode(String node) { this.node = node; } public int getLength() { return length; } public void setLength(int length) { this.length = length; } }
下面我们开始实现字符串压缩:
1、统计:
我们知道文件是由字符一个个组成的,那我们首要的工作就是统计各个字符的个数。
/** * 数字符串中字符个数 * * @param str字符串 */ private void CharCount(char[] ch) { int len = ch.length;// 获取字符串长度 // 对字符串进行循环 for (int i = 0; i < len; i++) { boolean bol = true;// 创建临时变量bol,讨论字符以前是否出现过 for (int j = 0; j < i; j++) { // 遍历i位置以前的字符,如果出现过,设置bol为否 if (ch[i] == ch[j]) bol = false; } int counts = 0;// 定义数字符的变量 if (bol) // 如果以前没有出现过 { counts++;// 这个字符的数量加一 for (int k = i + 1; k < len; k++) { // 对这个字符的后面进行循环,如果出现了,count就加一 if (ch[k] == ch[i]) counts++; } } // 如果数出来的数量不为0,记录字符和它的数量 if (counts != 0) { count[num] = new Code(); count[num].setLength(counts); count[num].setNode(ch[i] + ""); num++; } } }
2、排序:
统计完各个字符的个数,我们要对字符进行排序:
ArrayList<Node> nodelist = new ArrayList<Node>();// 建立队列 // 循环将字符串中的个数输入队列 for (int i = 0; i < num; i++) { Node temp = new Node(count[i].getLength()); temp.setSign(count[i].getNode()); nodelist.add(temp);// 将节点加入队列中 } Collections.sort(node);// 对队列排序
3、构建哈夫曼树
下面我们开始构建哈夫曼树。
构建的流程是这样的:我们首先进行排序,寻找权值最小的两个叶子节点,将他们的值相加,然后将相加的值构成新的叶子节点放在最后,然后将原来两个节点移除,就这样一直进行,直至最后只剩一个节点,这个节点就为根节点。
知道原理,我们就可以利用队列来构建哈夫曼树啦~
/** * 构建哈夫曼树 * * @param node要输入的节点队列 * @return 根节点 */ public Node bulid(List<Node> node) { Collections.sort(node);// 对队列排序 // 进行循环,如果队列的长度大于1 while (node.size() > 1) { CreatAndReplace(node);// 调用替代方法 } return node.get(0);// 返回根节点 } /** * 替代方法 * * @param node节点队列 */ public void CreatAndReplace(List<Node> node) { Node left = node.get(0);// 获取第一个节点给左节点 Node right = node.get(1);// 获取第二个节点给右节点 Node root = new Node(left.getData() + right.getData());// 新建一个节点,数据是左右节点之和 root.setLeft(left);// 设置新节点的左节点 root.setRight(right);// 设置新节点的右节点 node.remove(0);// 移除第一个节点 node.remove(0);// 移除第二个节点 node.add(root);// 将根节点加入到队列中去 Collections.sort(node);// 对节点进行排序 }
4、遍历,输出码表
得到二叉树后,我们以向左用0表示,向右用1表示,依次类推,可以得到码表。
/** * 得到编码的方法 * * @param root根节点 * @param s字符串 */ public void getCode(Node root, String s) { if (root.getLeft() == null && root.getRight() == null) { code[codenum] = new Code();// 新建一个编码对象 code[codenum].setSign(root.getSign());// 将标志设置为节点的标志 code[codenum].setNode(s);// 将s设置为编码 codenum++; System.out.print("节点" + root.getSign() + "编码" + s + " "); } if (root.getLeft() != null) { // 如果在左边,编码加上0 getCode(root.getLeft(), s + "0"); } if (root.getRight() != null) { // 如果在右边,编码加上1 getCode(root.getRight(), s + "1"); } }
5、根据码表生成01串编码
根据码表和对应的字符,我们可以用码表上的01串来表示字符啦!
/** * 输出树 * * @param root根节点 */ private static void printTree(Node node) { Node left = null;// 创建左节点 Node right = null;// 创建右节点 if (node != null) // 如果跟不为空 { left = node.getLeft();// 设置left为根的左节点 right = node.getRight();// 设置右节点为node的右节点 System.out.print(node.getData());// 打印node的数据 System.out.print("(" + (left != null ? left.getData() : " ") + "," + (right != null ? right.getData() : " ") + ") "); } if (left != null)// 如果左节点不为空,打印左子树的 printTree(left); if (right != null)// 如果右节点不为空,打印右子树的 printTree(right); } //我们在主函数中调用 getCode(root, "");// 得到每个节点的编码 String strcode = ""; for (int i = 0; i < ch.length; i++) { for (int j = 0; j < num; j++) { if (code[j].getSign().equals(ch[i] + "")) { strcode += code[j].getNode(); } } } System.out.println("\n" + strcode);
6、根据01串编码还原字符串
根据01串和码表,我们可以将字符还原回来:
char[] chtemp = strcode.toCharArray(); String temp = ""; // 反压缩 for (int i = 0; i < strcode.length(); i++) { temp = temp + chtemp[i]; for (int j = 0; j < num; j++) { if (temp.equals(code[j].getNode())) { System.out.print(code[j].getSign()); temp = ""; } } }
相关推荐
数据结构课程的课程设计,实现哈夫曼树,压缩文件
树的应用——哈夫曼编码 二、 实验内容: 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。 从...
哈夫曼树 基本功能: (1) 从文件中读出一篇英文文章,包含字母和空格等字符。 (2) 统计各个字符出现的频度。 (3) 根据出现的频度,为每个出现的字符建立一个哈夫曼编码,并输出。 (4) 输入一个字符串,为其...
这是哈夫曼树源代码的源代码。可以编码,解码。是用VS2005编写的。
这是我做的一个基于哈夫曼树思想的压缩算法程序源码,希望大家指正
设计内容: 欲发一封内容为AABBCAB ……(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码。
这是大二时的数据结构的课设,今天与大家分享。可以读写文件,编码译码,以及对输入的异常处理。
用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAME IS MY FAVORITE”。 字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N ...
重庆大学数据结构项目2——哈夫曼编码树.用MFC实现界面。界面良好,程序结构清晰
树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。
一个简单的基于哈夫曼树的压缩解压文件程序
利用哈夫曼算法实现压缩解压缩,Linux c
用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树
包含实验报告,题目等等,十分详细,物超所值
数据结构课程设计 ——哈夫曼编/译码器,里面什么都有 啊
哈夫曼树实现的压缩工具源代码,用netbeans导入可以看见源代码,仅供学习参考
数据结构课程设计模——哈夫曼编码译码器.doc
哈夫曼树的应用——数据结构课程设计
数据结构课程设计模——哈夫曼编码译码器.c语言程序