- 浏览: 3437007 次
- 性别:
- 来自: China
文章分类
- 全部博客 (536)
- ajax (1)
- Algorithm (14)
- Android (40)
- CSS/HTML... (2)
- defy (3)
- DesignPattern (2)
- dorado (0)
- Drools (6)
- English/日本語 (7)
- Flex (2)
- Framework (0)
- Google (3)
- hibernate (13)
- homework (3)
- HTML5 (0)
- IDE (29)
- java (45)
- javaee (7)
- Javascript (14)
- java组件 (5)
- jQuery (4)
- jsp (8)
- jsf (2)
- Linux (2)
- lucene (0)
- mysql (6)
- news (3)
- Oracle (8)
- other (4)
- PHP (5)
- Python (0)
- Software Engineering (3)
- spring (7)
- struts1.x (14)
- struts2.x (14)
- strolling in cloud (1)
- subject:javaEnhance (20)
- Tomcat (7)
- validator (3)
- 学习·方法·心得 (8)
- .NET (2)
- vba (6)
- groovy (5)
- grails (2)
- SWT (0)
- big data (1)
- perl (1)
- objective-c (50)
- product (1)
- mac (7)
- ios (188)
- ios-phone (2)
- ios-system (15)
- ios-network (5)
- ios-file (4)
- ios-db (1)
- ios-media (3)
- ios-ui (27)
- ios-openSource (6)
- ios-animation (5)
- ios-drawing (7)
- c (2)
- ios-app (2)
- ios-course (15)
- ios-runtime (14)
- ios-code (8)
- ios-thread (8)
- ios-LBS (2)
- ios-issue (1)
- ios-design (2)
- Jailbreak (2)
- cocos2d (0)
- swift (16)
- ios-framework (4)
- apple watch (4)
- ios-web (1)
- react native (3)
- TVOS (1)
- OpenGL (1)
最新评论
-
xiaobinggg:
...
Session机制详解 -
菜鸟学生会:
Drools规则工作流引擎开发教程网盘地址:http://pa ...
Drools入门-----------环境搭建,分析Helloworld -
wangyudong:
不是很好用,不支持自动化测试RESTful API,也不支持自 ...
Simple REST Client POST使用方法 -
Paul0523:
很棒的一篇文章,感谢楼主分享
Session机制详解 -
啸笑天:
获取原型对象的三种方法<script>functi ...
复习JavaScript面向对象技术
创建哈夫曼树
主要思想:
(1)对List集合中所有节点进行排序。
(2)找出List集合中权值最小的两个节点。
(3)以权值最小的两个节点作为子节点创建新节点。
(4)从List集合中删除权值最小的两个节点,将新节点添加到List集合中。
import java.util.*; public class HuffmanTree { public static class Node<E> { E data; double weight; Node leftChild; Node rightChild; public Node(E data , double weight) { this.data = data; this.weight = weight; } public String toString() { return "Node[data=" + data + ", weight=" + weight + "]"; } } public static void main(String[] args) { List<Node> nodes = new ArrayList<Node>(); nodes.add(new Node("A" , 40.0)); nodes.add(new Node("B" , 8.0)); nodes.add(new Node("C" , 10.0)); nodes.add(new Node("D" , 30.0)); nodes.add(new Node("E" , 10.0)); nodes.add(new Node("F" , 2.0)); Node root = HuffmanTree.createTree(nodes); System.out.println(breadthFirst(root)); } /** * 构造哈夫曼树 * @param nodes 节点集合 * @return 构造出来的哈夫曼树的根节点 */ private static Node createTree(List<Node> nodes) { //只要nodes数组中还有2个以上的节点 while (nodes.size() > 1) { quickSort(nodes); //获取权值最小的两个节点 Node left = nodes.get(nodes.size() - 1); Node right = nodes.get(nodes.size() - 2); //生成新节点,新节点的权值为两个子节点的权值之和 Node parent = new Node(null , left.weight + right.weight); //让新节点作为权值最小的两个节点的父节点 parent.leftChild = left; parent.rightChild = right; //删除权值最小的两个节点 nodes.remove(nodes.size() - 1); nodes.remove(nodes.size() - 1); //将新生成的父节点添加到集合中 nodes.add(parent); } //返回nodes集合中唯一的节点,也就是根节点 return nodes.get(0); } //将指定数组的i和j索引处的元素交换 private static void swap(List<Node> nodes, int i, int j) { Node tmp; tmp = nodes.get(i); nodes.set(i , nodes.get(j)); nodes.set(j , tmp); } //实现快速排序算法,用于对节点进行排序。从大到小的排序 private static void subSort(List<Node> nodes , int start , int end) { //需要排序 if (start < end) { //以第一个元素作为分界值 Node base = nodes.get(start); //i从左边搜索,搜索大于分界值的元素的索引 int i = start; //j从右边开始搜索,搜索小于分界值的元素的索引 int j = end + 1; while(true) { //找到大于分界值的元素的索引,或i已经到了end处 while(i < end && nodes.get(++i).weight >= base.weight); //找到小于分界值的元素的索引,或j已经到了start处 while(j > start && nodes.get(--j).weight <= base.weight); if (i < j) { swap(nodes , i , j); } else { break; } } swap(nodes , start , j); //递归左子序列 subSort(nodes , start , j - 1); //递归右边子序列 subSort(nodes , j + 1, end); } } public static void quickSort(List<Node> nodes) { subSort(nodes , 0 , nodes.size() - 1); } //广度优先遍历 public static List<Node> breadthFirst(Node root) { Queue<Node> queue = new ArrayDeque<Node>(); List<Node> list = new ArrayList<Node>(); if( root != null) { //将根元素入“队列” queue.offer(root); } while(!queue.isEmpty()) { //将该队列的“队尾”的元素添加到List中 list.add(queue.peek()); Node p = queue.poll(); //如果左子节点不为null,将它加入“队列” if(p.leftChild != null) { queue.offer(p.leftChild); } //如果右子节点不为null,将它加入“队列” if(p.rightChild != null) { queue.offer(p.rightChild); } } return list; } }
哈夫曼编码
规律:假如有N个叶子节点需要编码,最终得到的哈夫曼树一定有N层,哈夫曼编码得到的二进制码的最大长度为N-1。
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Queue; import java.util.Scanner; public class HuffmanCoding { public static String writeString; public static class HNode { String data = ""; String coding = ""; @Override public String toString() { return "HNode [coding=" + coding + ", data=" + data + "]"; } public HNode(String data) { super(); this.data = data; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((data == null) ? 0 : data.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; HNode other = (HNode) obj; if (data == null) { if (other.data != null) return false; } else if (!data.equals(other.data)) return false; return true; } } public static class Node { HNode data; int weight; Node leftChild; Node rightChild; public Node(HNode data, int weight) { this.data = data; this.weight = weight; } public String toString() { return "Node[data=" + data + ", weight=" + weight + "]"; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((data == null) ? 0 : data.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Node other = (Node) obj; if (data == null) { if (other.data != null) return false; } else if (!data.equals(other.data)) return false; return true; } } public static void main(String[] args) { System.out.println("请输入字符串:"); Scanner scanner = new Scanner(System.in); HuffmanCoding.writeString = scanner.nextLine(); char[] chars = writeString.toCharArray(); List<Node> nodes = new ArrayList<Node>(); for (int i = 0; i < chars.length; i++) { Node t = new Node(new HNode(String.valueOf(chars[i])), 1); if (nodes.contains(t)) { nodes.get(nodes.indexOf(t)).weight++; } else { nodes.add(t); } } // System.out.println(nodes); Node root = HuffmanCoding.createTree(nodes); breadthFirst(root, nodes); for (int i = 0; i < chars.length; i++) { Node t = new Node(new HNode(String.valueOf(chars[i])), 1); System.out.print(nodes.get(nodes.indexOf(t)).data.coding); } } private static Node createTree(List<Node> nodess) { List<Node> nodes = new ArrayList<Node>(nodess); // 只要nodes数组中还有2个以上的节点 while (nodes.size() > 1) { quickSort(nodes); // 获取权值最小的两个节点 Node left = nodes.get(nodes.size() - 1); Node right = nodes.get(nodes.size() - 2); // 生成新节点,新节点的权值为两个子节点的权值之和 Node parent = new Node(new HNode(null), left.weight + right.weight); // 让新节点作为权值最小的两个节点的父节点 parent.leftChild = left; parent.rightChild = right; // 删除权值最小的两个节点 nodes.remove(nodes.size() - 1); nodes.remove(nodes.size() - 1); // 将新生成的父节点添加到集合中 nodes.add(parent); } // 返回nodes集合中唯一的节点,也就是根节点 return nodes.get(0); } public static void quickSort(List<Node> nodes) { subSort(nodes, 0, nodes.size() - 1); } private static void subSort(List<Node> nodes, int start, int end) { if (start < end) { Node base = nodes.get(start); int i = start; int j = end + 1; while (true) { while (i < end && nodes.get(++i).weight >= base.weight) ; while (j > start && nodes.get(--j).weight <= base.weight) ; if (i < j) { swap(nodes, i, j); } else { break; } } swap(nodes, start, j); // 递归左子序列 subSort(nodes, start, j - 1); // 递归右边子序列 subSort(nodes, j + 1, end); } } private static void swap(List<Node> nodes, int i, int j) { Node tmp; tmp = nodes.get(i); nodes.set(i, nodes.get(j)); nodes.set(j, tmp); } // 广度优先遍历 public static void breadthFirst(Node root, List<Node> nodes) { // System.out.println("我 "+nodes); Queue<Node> queue = new ArrayDeque<Node>(); List<Node> list = new ArrayList<Node>(); if (root != null) { // 将根元素入“队列” queue.offer(root); } while (!queue.isEmpty()) { // 将该队列的“队尾”的元素添加到List中 list.add(queue.peek()); Node p = queue.poll(); // 如果左子节点不为null,将它加入“队列” if (p.leftChild != null) { queue.offer(p.leftChild); p.leftChild.data.coding = p.data.coding + "0"; } else { // System.out.println(p+" "+p.data+" "+p.data.data+ // " "+p.data.coding); // System.out.println("nodes.indexOf(p)"+nodes.contains(p)); ((Node) nodes.get(nodes.indexOf(p))).data.coding = p.data.coding; } // 如果右子节点不为null,将它加入“队列” if (p.rightChild != null) { queue.offer(p.rightChild); p.rightChild.data.coding = p.data.coding + "1"; } // else { // nodes.get(nodes.indexOf(p)).data.coding=p.data.coding; // System.out.println("you "+p.data.coding); // } } } }
发表评论
-
qweqwe
2012-07-11 16:06 1江蛤蟆 一统江湖 -
123123123
2012-07-11 16:04 0<p>法轮</p> -
母牛繁殖问题
2011-12-30 13:08 3835question:农场的母牛寿命是5年,母牛第二年和第四年会繁 ... -
树形显示
2011-07-17 11:26 1640/** 树形结构应用十分广泛。 下面这段代码根据 ... -
求能除尽1至n的最小整数
2011-07-16 02:43 3959为什么1小时有60分钟,而不是100分钟呢?这是历史上的 ... -
java 四则运算 栈的实现
2011-07-15 13:42 13842import java.util.Stack; /* ... -
用1、2、3、3、4、5这六个数字,用java写一个程序,打印出所有不同的排列 要求:"4"不能在第三位,"3"与"5"不能相连。
2011-07-15 12:45 3377用1、2、3、3、4、5这六 ... -
【code】java红黑树
2011-06-28 10:07 3441import java.util.*; publi ... -
【code】java实现排序二叉树
2011-06-27 21:45 2861import java.util.*; publi ... -
【code】java实现十种常见内部排序
2011-06-20 19:22 3077常见的内部排序: 下面介绍这十种常见内部排序(都是从 ... -
【code】java二叉树深(先中后)、广遍历
2011-06-19 16:55 1956import java.util.*; publi ... -
【code】java二叉树的实现
2011-06-17 22:50 5850二叉树的顺序存储 public class Array ... -
【code】java树的实现
2011-06-17 22:20 11953树的父节点存储实现 import java.util. ... -
【code】java栈和队列实现
2011-06-16 22:11 4947顺序栈的实现 import java.util.Arrays ... -
【code】java线性表实现
2011-06-16 21:24 3660顺序线性表的实现 import java.util.A ...
相关推荐
哈夫曼树和哈夫曼编码的Java实现,供新手学习使用。希望能给需要的人以帮助。
c++ 源代码 哈夫曼树 哈夫曼编码 部分代码如下: #include"Huffman.h" #include"hfmTree.h" #include using namespace std; int main() { cout~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~...
哈夫曼树与哈夫曼编码 建立哈夫曼树并计算哈夫曼编码
编写一个程序,根据输入节点的权值,建立哈夫曼树并实现哈夫曼编码,同时输出哈夫曼编码
文章使用C#编程语言实现了哈夫曼编码树和哈夫曼编码,并在VS2010下调试成功
哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx
哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2
用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“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 ...
一、问题描述 运用哈夫曼算法构造哈夫曼树,并得到哈夫曼编码。 输入格式:10,5,21,18,8,13 ...1、构造哈夫曼树和哈夫曼编码的存储结构。 2、实现哈夫曼算法,实现哈夫曼树的存储并求出哈夫曼编码。
用二维数组模拟创建哈夫曼树
构建哈夫曼树及哈夫曼编码,输出哈夫曼树及哈夫曼编码,完成编码与译码的算法。 (1)掌握树的有关操作算法 (2)熟悉树的基本存储方法 (3)学习利用树求解实际问题
从终端输入若干个字符,统计(或指定)字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int num)//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈弗曼编码HC { int i,m,c,s1,s2,start,f; HuffmanTree p; char* cd; if...
小小的实验,用哈夫曼树实现哈夫曼编码,属于cpp文件,
从终端读入字符集大小 n,及 n 个字符和 m 个权值,建立哈夫曼树,并将它存于文件 hfmtree 中。 (2)C:编码 (Coding)。利用已建好的哈夫曼树(如不在内存,则从文件 hfmtree 中读入),对文件 tobetrans 中的正文进行...
详细描述了哈夫曼树的构造方法,同时推广到三元哈夫曼编码,并用C语言于VC++上实现
构建哈夫曼树,对其进行编码,实现译码功能,数据结构的实验报告。。
C++实现哈夫曼树及哈夫曼编码,代码简介https://blog.csdn.net/qq_41664447/article/details/90736442,C++源程序可直接运行
2.对文件中的内容进行哈夫曼编码并存储入文件(涉及到创建哈夫曼树,进行哈夫曼编码和写文件); 3.对编码文件进行译码(涉及到哈夫曼译码和写文件)。 4.输出要求:输出原文、译文、打印编码规则、打印哈夫曼树...